WiSM: Windowing Surrogate Model for Evaluation of Curvature-Constrained Tours with Dubins vehicle
This addresses routing optimization for curvature-constrained vehicles like drones, offering incremental improvements in computational efficiency for large-scale instances.
The paper tackles the computationally challenging Dubins Traveling Salesman Problem (DTSP) by introducing the Windowing Surrogate Model (WiSM) to estimate optimal Dubins path lengths, enabling a simple evolutionary algorithm to converge quickly to high-quality solutions, with results showing better scalability as the number of locations increases compared to other state-of-the-art solvers.
Dubins tours represent a solution of the Dubins Traveling Salesman Problem (DTSP) that is a variant of the optimization routing problem to determine a curvature-constrained shortest path to visit a set of locations such that the path is feasible for Dubins vehicle, which moves only forward and has a limited turning radius. The DTSP combines the NP-hard combinatorial optimization to determine the optimal sequence of visits to the locations, as in the regular TSP, with the continuous optimization of the heading angles at the locations, where the optimal heading values depend on the sequence of visits and vice versa. We address the computationally challenging DTSP by fast evaluation of the sequence of visits by the proposed Windowing Surrogate Model (WiSM) which estimates the length of the optimal Dubins path connecting a sequence of locations in a Dubins tour. The estimation is sped up by a regression model trained using close to optimum solutions of small Dubins tours that are generalized for large-scale instances of the addressed DTSP utilizing the sliding window technique and a cache for already computed results. The reported results support that the proposed WiSM enables a fast convergence of a relatively simple evolutionary algorithm to high-quality solutions of the DTSP. We show that with an increasing number of locations, our algorithm scales significantly better than other state-of-the-art DTSP solvers.