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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    On the Travelling Salesman Problem with Neighborhoods in a Polygonal World


    Additional title:

    Lect. Notes in Networks, Syst.



    Conference:

    Climbing and Walking Robots Conference ; 2022 ; Ponta Delgada, Portugal September 12, 2022 - September 14, 2022



    Publication date :

    2022-08-25


    Size :

    12 pages





    Type of media :

    Article/Chapter (Book)


    Type of material :

    Electronic Resource


    Language :

    English




    THE TRAVELLING SPACE SALESMAN PROBLEM

    Gaur, Deepak | TIBKAT | 2022


    On the Discretized Dubins Travelling Salesman Problem

    Epstein, C. / Cohen, I. / Shima, T. et al. | British Library Conference Proceedings | 2014


    Intuitionistic Fuzzy Modeling to Travelling Salesman Problem

    Garai, Arindam / Roy, Tapan Kumar | BASE | 2013

    Free access


    Hybrid ABC/PSO to solve travelling salesman problem

    Yang, Weihong / Pei, Zhili | British Library Online Contents | 2013