Fast Heuristics for the 3D Multi-Goal Path Planning based on the Generalized Traveling Salesman Problem with Neighborhoods
Authors: Jan Faigl, Petr Váňa, and Jindřiška Deckerová
A fast heuristics based on the Growing Self-Organizing Array (GSOA) and sampled-based approches to tackle the complex Generalized Traveling Salesman Problem with Neighborhoods (GTSPN).
Abstract
In this paper, we address the multi-goal path planning problem to determine a cost-efficient path to visit a set of 3D regions. The problem is a variant of the Traveling Salesman Problem with Neighborhoods (TSPN) where an individual neighborhood consists of multiple regions, and the problem is to determine a shortest multi-goal path to visit at least one region of each neighborhood. Because each neighborhood may consist of several regions, it forms a neighborhood set, and the problem is called the Generalized TSPN (GTSPN) in the literature. We propose two heuristic algorithms to provide a feasible solution of the GTSPN quickly. The first algorithm is based on a decoupled approach using a solution of the Generalized TSP that is further improved by a quick post-processing procedure. Besides, we propose to employ the existing unsupervised learning technique called the Growing Self-Organizing Array (GSOA) to quickly find a feasible solution of the GTSPN that can be further improved by more demanding optimization. The reported results on existing benchmarks for the GTSPN indicate that both proposed heuristics provide better or competitive solutions than the state-of-the-art reference algorithm, but they are up to two orders of magnitude faster.
Citation:
@article{faigl19ral,
author = {Faigl, Jan and Deckerová, Jindřiška and Váňa, Petr},
title = {Fast Heuristics for the {3D} Multi-Goal Path Planning based on the
Generalized Traveling Salesman Problem with Neighborhoods},
journal = {IEEE Robotics and Automation Letters},
year = {2019},
pages = {2439--2446},
volume = {4},
issue = {3},
doi = {10.1109/LRA.2019.2900507}
}