The Travelling Salesman Problem with Neighborhoods (TSPN), as an extension of the broadly studied Travelling Salesman Problem, has many practical applications in robotics. Although several approaches to the problem have been introduced, they assume an environment without obstacles. In this paper, we introduce a method for the TSPN with polygonal neighborhoods taking polygonal obstacles into account. The method splits the problem into two subproblems: the Generalized Travelling Salesman Problem and the Touring Polygons Problem, which are solved sequentially. While the mature metaheuristic called Generalize Large Neighborhoods Search is employed to solve the first subproblem, the second one is solved by modifying the rubber-band algorithm. The experimental results show that the proposed approach outperforms a state-of-the-art algorithm modified for the environment with obstacles by 10–20% in most cases.
On the Travelling Salesman Problem with Neighborhoods in a Polygonal World
Lect. Notes in Networks, Syst.
Climbing and Walking Robots Conference ; 2022 ; Ponta Delgada, Portugal September 12, 2022 - September 14, 2022
2022-08-25
12 pages
Aufsatz/Kapitel (Buch)
Elektronische Ressource
Englisch
THE TRAVELLING SPACE SALESMAN PROBLEM
TIBKAT | 2022
|On the Discretized Dubins Travelling Salesman Problem
British Library Conference Proceedings | 2014
|Generalized travelling-salesman problem and its applications
Tema Archiv | 1976
|Hybrid ABC/PSO to solve travelling salesman problem
British Library Online Contents | 2013
|