An exact algorithm for a heterogeneous, multiple depot, multiple traveling salesman problem

Unmanned aerial vehicles are being used in several monitoring applications to collect data from a set of targets. These vehicles are heterogeneous in the sense that they can differ either in their motion constraints or sensing capabilities. Furthermore, not all vehicles may be able to visit a given target because vehicles may occasionally be equipped with disparate sensors due to the respective payload restrictions. This article addresses a problem where a group of heterogeneous vehicles located at distinct depots visit a set of targets. The targets are partitioned into disjoint subsets: targets to be visited by specific vehicles and targets that any of the vehicles can visit. The objective is to find an optimal tour for each vehicle starting at its respective depot such that each target is visited at least once by some vehicle, the vehicle-target constraints are satisfied and the sum of the costs of the tours for all the vehicles is minimized. We formulate the problem as a mixed-integer linear program and develop a branch-and-cut algorithm to compute an optimal solution to the problem. Computational results show that optimal solutions for problems involving 100 targets and 5 vehicles can be obtained within 300 seconds on average, further corroborating the effectiveness of the proposed approach.