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.


    Access

    Access via TIB

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

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


    Contributors:


    Publication date :

    2011


    Size :

    6 Seiten, 23 Quellen



    Type of media :

    Conference paper


    Type of material :

    Print


    Language :

    English




    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