We study the problem of finding the minimum length curvature constrained closed path through a set of regions in the plane. This problem is referred to as the Dubins Traveling Salesperson Problem with Neighborhoods (DTSPN). Two algorithms are presented that transform this infinite dimensional combinatorial optimization problem into a finite dimensional asymmetric TSP by sampling and applying the appropriate transformations, thus allowing the use of existing approximation algorithms. We show for the case of disjoint regions, the first algorithm needs only to sample each region once to produce a tour within a factor of the length of the optimal tour that is independent of the number of regions. We present a second algorithm that performs no worse than the best existing algorithm and can perform significantly better when the regions overlap.


    Zugriff

    Zugriff über TIB

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Algorithms for the traveling salesman problem with neighborhoods involving a Dubins vehicle


    Beteiligte:

    Erschienen in:

    Erscheinungsdatum :

    2011


    Format / Umfang :

    6 Seiten, 23 Quellen



    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Print


    Sprache :

    Englisch




    Dubins orienteering problem with neighborhoods

    Penicka, Robert / Faigl, Jan / Vana, Petr et al. | IEEE | 2017


    On the Discretized Dubins Travelling Salesman Problem

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




    2012-2562 Fuzzy Clustering Based Genetic Algorithm for the Multi-Depot Polygon Visiting Dubins Multiple Traveling Salesman Problem

    Ernest, N. / Cohen, K. / American Institute of Aeronautics and Astronautics | British Library Conference Proceedings | 2012