A Hierarchical Framework for Solving the Constrained Multiple Depot Traveling Salesman Problem

The Multiple Depot Traveling salesman Problem (MDTSP) is a variant of the well known NP-hard Traveling Salesman Problem (TSP) with more than one salesmen to collaboratively visit all destinations, which widely encounters in task or mission planning in multi-agent robotic systems. Traditional MDTSP does not consider constraints such as limited battery level or inter-agent conflicts that are widely seen in practical problem, leading to the high risk of generating infeasible or unsafe solution in practice. In this work, we incorporate realistic constraints on energy and resource consumption into MDTSP to form the Constrained MDTSP (CMDTSP). We design a novel hierarchical framework to solve such CMDTSP with provide high-quality solution and low computational complexity, addressing the problem of lacking good heuristics when solving CMDTSP. The framework decomposes a given large CMDTSP problem into manageable sub-problems, each handled by a salesman individually via an existing solver for Traveling Salesman Problem (TSP) and heuristic search to generate tours. The proposed solutions are then aggregated and processed through a relatively small Mixed-Integer Linear Program (MILP) to form a feasible solution that meets the constraints. Compared with exact method, We reduce the number of real variables in MILP from forth order of cities to linear and the number of integer variables from quadratic to linear. We demonstrate the advantages of our framework on solution quality and running time over existing methods by experiments on both real road maps as well as synthetic datasets. Our framework gives a mean optimality gap 12.48% on small dataset, and a 5.22%~14.84% solution quality increase with more than 79.8x speedup over the best baseline on large dataset where exact method times out.