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.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    On the Travelling Salesman Problem with Neighborhoods in a Polygonal World


    Weitere Titelangaben:

    Lect. Notes in Networks, Syst.


    Beteiligte:
    Cascalho, José M. (Herausgeber:in) / Tokhi, Mohammad Osman (Herausgeber:in) / Silva, Manuel F. (Herausgeber:in) / Mendes, Armando (Herausgeber:in) / Goher, Khaled (Herausgeber:in) / Funk, Matthias (Herausgeber:in) / Kulich, Miroslav (Autor:in) / Vidašič, Jan (Autor:in) / Mikula, Jan (Autor:in)

    Kongress:

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



    Erscheinungsdatum :

    2022-08-25


    Format / Umfang :

    12 pages





    Medientyp :

    Aufsatz/Kapitel (Buch)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    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

    Freier Zugriff


    Hybrid ABC/PSO to solve travelling salesman problem

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