Variable-Speed Traveling Salesman Problem for Vehicles with Curvature Constrained Trajectories

Abstract

This paper presents a novel approach to the multigoal trajectory planning for vehicles with curvature-constrained trajectories such as fixed-wing aircraft. In the existing formulation called the Dubins Traveling Salesman Problem (DTSP), the vehicle speed is assumed to be constant over the whole trajectory, and that does not allow adaptation of the turning radius of the trajectory between the target locations. It does not support optimization of the overall flight time of the multi-goal trajectory by exploiting higher speeds for longer turning radii. Therefore, we propose a novel problem formulation called the Variable-Speed Traveling Salesman Problem (VS-TSP) that employs time-efficient trajectories with variable speed based on a generalization of the Dubins vehicle model, allowing multiple turning radii and change of the forward speed of the vehicle. The VS-TSP allows the vehicle to slow down if high maneuverability is necessary and speed up if high-speed turns with a large radius are beneficial to the overall tour cost. Based on the evaluation results for Cessna 172 aircraft model, the proposed VNS-based algorithm with variable speed provides up to about 20 % faster trajectories than a solution of the DTSP with a single turning radius.