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

摘要

The Multiple Depot Traveling Salesman Problem (MDTSP) is a variant of the NP-hard Traveling Salesman Problem (TSP) with more than one salesman to jointly visit all destinations, commonly found in task planning in multi-agent robotic systems. Traditional MDTSP overlooks practical constraints like limited battery level and inter-agent conflicts, often leading to infeasible or unsafe solutions in reality. In this work, we incorporate energy and resource consumption constraints to form the Constrained MDTSP (CMDTSP). We design a novel hierarchical framework to obtain high-quality solutions with low computational complexity. The framework decomposes a given CMDTSP instance into manageable sub-problems, each handled individually via a TSP solver and heuristic search to generate tours. The tours are then aggregated and processed through a Mixed-Integer Linear Program (MILP), which contains significantly fewer variables and constraints than the MILP for the exact CMDTSP, to form a feasible solution efficiently. We demonstrate the performance of our framework on both real-world and synthetic datasets. It reaches a mean 12.48% optimality gap and 41.7x speedup over the exact method on common instances and a 5.22% <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\sim$</tex-math></inline-formula> 14.84% solution quality increase with more than 79.8x speedup over the best baseline on large instances where the exact method times out.