High Accuracy Discretization-based Integer Programming for the Dubins Multiple Traveling Salesman Problem with Min-max Objective

Abstract

Many robotic exploration and surveillance applications can be modeled as a single-robot Euclidean traveling salesman problem (TSP). However, the robot in the real-world is usually limited by turning radius or curvature; Moreover, multiple robots can accelerate the completion of the applications. This paper thus studies the Dubins multiple traveling salesman problem (DMTSP) with a min-max objective where the robots are with limited turning radius. Compared to the single robot, multiple robots also need a high corporation to min-max the completion time of the application, and the cooperation makes the problem more difficult. As no mathematical programming work for DMTSP yet has been found in the literature, we propose two approximate (discretization-based) mixed integer linear program-ming (MILP) formulations for the studied problem in this paper. These formulations were compared to the existing Euclidean multiple TSP (MTSP) method and the genetic algorithms for Dubins TSP (DTSP). The results show the effectiveness of our methods on mild-large instances and high accuracy results towards genetic algorithms. The results also are with a fairly small 5% gap to the Euclidean MTSP results which ignores the curvature limits.