2020/02/03 by Jan Drchal, Drchal, Jan, Jan Faigl +3 · 1 citation
Engineering · Social Sciences · Computer Science · #Vehicle Routing Optimization Methods #Transportation Planning and Optimization #Robotic Path Planning Algorithms
paper · pdf · doi:10.48550/arxiv.2002.00811
Dubins tours represent a solution of the Dubins Traveling Salesman Problem\n(DTSP) that is a variant of the optimization routing problem to determine a\ncurvature-constrained shortest path to visit a set of locations such that the\npath is feasible for Dubins vehicle, which moves only forward and has a limited\nturning radius. The DTSP combines the NP-hard combinatorial optimization to\ndetermine the optimal sequence of visits to the locations, as in the regular\nTSP, with the continuous optimization of the heading angles at the locations,\nwhere the optimal heading values depend on the sequence of visits and vice\nversa. We address the computationally challenging DTSP by fast evaluation of\nthe sequence of visits by the proposed Windowing Surrogate Model (WiSM) which\nestimates the length of the optimal Dubins path connecting a sequence of\nlocations in a Dubins tour. The estimation is sped up by a regression model\ntrained using close to optimum solutions of small Dubins tours that are\ngeneralized for large-scale instances of the addressed DTSP utilizing the\nsliding window technique and a cache for already computed results. The reported\nresults support that the proposed WiSM enables a fast convergence of a\nrelatively simple evolutionary algorithm to high-quality solutions of the DTSP.\nWe show that with an increasing number of locations, our algorithm scales\nsignificantly better than other state-of-the-art DTSP solvers.\n