Combinatorial Motion Planning of Multiple Vehicle Systems

In this paper, we are concerned with the development of approximation algorithms for the combinatorial motion planning of a collection of m vehicles. Specifically, we consider the following multiple depot, generalized multiple traveling salesmen problem (GMTSP). We are given m vehicles that start at possibly different locations and n targets that must be visited. The problem is to choose at most p les m vehicles so that (1) each target is visited by exactly one of the chosen vehicles and (2) the cost of the tours of the chosen vehicles is a minimum among all possible choices and their corresponding tours of vehicles. The criteria for the cost of tours considered is the total distance (total cost of edges) traveled by the entire collection. This problem is a generalization of the symmetric traveling salesman problem (TSP) and is NP-hard. We show that there is a 2-approx algorithm for this problem. We also provide a branch and bound procedure for this problem