On solution of the Dubins touring problem
Jan Faigl, Petr Váňa, Martin Saska, Tomáš Báča, Vojtěch Spurný · 2017
The Dubins traveling salesman problem (DTSP) combines the combinatorial optimization of the optimal sequence of waypoints to visit the required target locations with the continuous optimization to determine the optimal headings at the waypoints. Existing decoupled approaches to the DTSP are based on an independent solution of the sequencing part as the Euclidean TSP and finding the optimal headings of the waypoints in the sequence. In this work, we focus on the determination of the optimal headings in a given sequence of waypoints and formulate the problem as the Dubins touring problem (DTP). The DTP can be solved by a uniform sampling of possible headings; however, we propose a new informed sampling strategy to find approximate solution of the DTP. Based on the presented results, the proposed algorithm quickly converges to a high-quality solution, which is less than 0.1% from the optimum. Besides, the proposed approach also improves the solution of the DTSP, and its feasibility has been experimentally verified in a real practical deployment.