Lower and Upper Bounds for a Multiple Depot UAV Routing Problem

This paper extends the well known Held-Karp´s lower bound available for a single travelling salesman problem to the following multiple depot UAV routing problem (MDURP): Given a collection of UAVs that start at different depots, a set of terminals and destinations, the problem is to choose paths for each of the UAVs so that (1) each UAV starts at its respective depot, visits atleast one destination and reaches any one of the terminals not visited by other UAVs; (2) each destination is visited by exactly one UAV; and (3) the cost of the paths is a minimum among all possible paths for the UAVs. The criteria for the cost of paths considered is the total cost of the edges travelled by the entire collection. This MDURP is formulated as a minimum cost constrained forest problem subject to side constraints. By dualizing the side constraints, one can obtain an infinite family of lower bounds for MDURP. Each lower bound can be computed in a tractable way using a matroid intersection algorithm. Also, when the costs of traveling between any two locations satisfy triangle inequality, it is shown that there exists a 2-approximation algorithm for solving the MDURP