Time-Optimized Routing Problem for Vehicles with Bounded Curvature

Abstract

In this paper we introduce the k-Dubins TSP (k-DTSP), the problem of planning efficient paths among a set of points of interest in the environment for multiple robots with bounded curvature (Dubins vehicle). We propose a non-linear mathematical formulation for the problem which is undertaken by a combinatorial approach based on the discretization of the robot's heading. The main objective of the methodology is to minimize the length of longest tour, thus reducing the total time to visit all points. Numerous trials that were carried out in a simulated environment provide statistical insight on the performance of the proposed technique which surpasses a heuristic approach built upon classical methods found in the literature for diverse scenarios.