Discretization-Based and Look-Ahead Algorithms for the Dubins Traveling Salesperson Problem
A new class of discretization-based look-ahead algorithms (DLAAs) for the Dubins traveling salesperson problem (DTSP) is presented that compares favorably with the existing algorithms from the literature. The discretization level and the length of the look-ahead horizon are the two parameters that uniquely determine a DLAA, and depending on the application in hand, their values can be easily modified to strike a balance between the execution time and the length of the resulting admissible tour. The time complexity of a DLAA is the sum of two terms, one linear in the number of targets (cities) and one that corresponds to the specification of an initial order for the targets. For instances of the DTSP with densely distributed targets, an algorithm that relies on clustering and leads to shorter tours than the DLAA is also presented.