Institute of Transportation Studies at UC Berkeley

This paper extends the well known Held-Karp's lower bound available for a single Travelling Salesman Problem to the multiple depot case. The LP-relaxation of a symmetric multiple vehicle, multiple depot problem is shown to be lower bounded by an infinite family of bounds. Each lower bound can be computed in a tractable way using a matroid intersection algorithm. When the costs of travelling between any two locations satisfy triangle inequality, it is shown that there exists a 2-approximation algorithm for solving the multiple depot, multiple TSP. These results are useful in solving the following path planning problem of UAVs: Given a set of UAVs, their starting locations, a set of final UAV locations, a set of destinations to visit and the cost of travelling between any two locations, find a path for each UAV such that each destination is visited once by any one UAV and the total cost travelled by all the UAVs is minimum.