Approximation improves routing for multiple depot traveling salesman problem
A $(1+1/\sqrt{2})$-Approximation for the Multiple-Depot Traveling Salesman Problem
Data Structures and Algorithms
Summary
The traveling salesman problem asks how to find the shortest route that visits many points. This paper looks at a version where there are multiple starting points called depots, and routes must start and end there. The authors created a new method that gives a better approximate solution than the commonly used one, improving how close to the best route it can get. Their approach uses a special way to grow and connect parts of the route, then fixes certain connections to make a complete path.
What this means in practice
- •For logistics planners: Generate more efficient multi-route delivery plans starting and ending at several depot locations with tighter cost guarantees.
- •For robotic fleet operators: Plan coordinated routes for multiple autonomous robots that must return to assigned bases, improving energy and time efficiency.
Authors
Jingyang Zhao, Yuxi Liu, Mingyu Xiao
Abstract
The metric traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization that asks for a minimum-cost tour covering all clients in a metric graph. The metric multiple-depot TSP (MD-TSP) is a natural extension, where the graph contains depots and clients, and the objective is to compute a minimum-cost set of tours covering all clients, with each tour starting and ending at the same depot. When the number of depots is part of the input, an adaptation of the Christofides--Serdyukov heuristic yields an approximation ratio of $2$. In this paper, we introduce a $(1+1/\sqrt{2})$-approximation algorithm. Like the Christofides--Serdyukov heuristic, our algorithm first computes a rooted spanning forest (RSF), then a matching to correct its odd degrees, and finally obtains a solution by shortcutting. However, instead of using a minimum-cost RSF, we construct an RSF by a primal-dual algorithm for a natural cut relaxation. The algorithm grows rootless components and the component containing all depots at different rates, adding an edge when its dual constraint becomes tight. Vertex labels record the times at which clients first become connected to a depot. The two-speed growth provides a joint bound on the forest cost and two label-dependent terms that also arise in bounding the parity-correction cost. Balancing the coefficients of these two terms by setting both to $\sqrt{2}-1$ yields the claimed approximation ratio.