Solving multi-depot closed-path multiple traveling salesman problem using k-means++ hierarchical clustering and neural combinatorial networks

Smarter routes for many drivers

From parcel vans to delivery drones and disaster relief convoys, planners often face a puzzle: how can several vehicles starting from different locations share the work of visiting hundreds or thousands of stops without wasting fuel or time? This paper presents a new way to divide and conquer that puzzle, combining a classic clustering trick with a modern neural network so that computers can lay out efficient routes in seconds instead of minutes or hours.

The challenge of many depots and many drivers

The study tackles a demanding version of the famous traveling salesperson puzzle, where instead of one traveler there are many, each starting and ending at its own base. Together they must visit every city exactly once while keeping the total distance as short as possible. This setup mimics tasks such as coordinating fleets of trucks, groups of robots, or aerial drones that share work over a region. Because the number of possible route combinations explodes as cities and drivers grow, exact methods become too slow, and traditional trial-and-error search methods often struggle or must trade solution quality for speed.

Limits of classic search and simple dividing

For years, engineers have leaned on “metaheuristics” such as genetic algorithms, ant colony search and particle swarms. These mimic natural processes to explore many candidate routes and gradually improve them. They can be flexible but come with two big drawbacks: they give no firm guarantees about how good a solution is, and they can be very slow for large maps, especially when each new task requires starting the search over. A popular speedup is to first cluster the cities into regions using tools like k-means and then solve a smaller puzzle within each cluster. While this split-then-solve strategy helps, the final quality is still limited by the underlying search method, and aiming for better routes usually means paying with even longer runtimes.

Teaching a network to route, then helping it scale

Recent years have brought a different idea: train a neural network to output good routes directly. After learning on many example city layouts, such a network can propose a full tour in a single forward pass, much like a language model writes a sentence. These neural solvers work impressively well on single-driver problems of modest size, but they stumble when asked to coordinate many drivers or when the city set is much larger than in training. The authors’ key move is to wrap such a neural solver inside a careful two-step process that reshapes a huge, multi-driver task into many smaller, familiar subproblems the network can handle comfortably.

How the two-phase method works

The proposed method, called KHC-NCN, starts by using an improved version of k-means clustering to assign cities to different depots and drivers. If a resulting region contains too many cities for the neural solver to handle reliably, the method automatically splits that region further into smaller pieces, each of a size close to what the network saw during training. The coordinates in each piece are rescaled into a standard square so they resemble the training data even more closely. The neural network then produces a route for each small piece. Finally, a merging step stitches these sub-routes together into a single loop for each driver, using simple geometric rules to connect pieces where doing so adds the least extra distance.

Speed and quality on real benchmark maps

The authors test their method on a broad collection of standard maps from a public benchmark set widely used in routing research. They compare against many established search techniques and against both a top hand-crafted solver and another neural approach. Across 44 test cases with different map sizes and numbers of drivers, their method finds shorter total routes in nearly three quarters of the cases while also being dramatically faster, often by orders of magnitude. It holds up especially well as the number of cities climbs into the hundreds or thousands, where many classic approaches slow down or deliver weaker routes.

What this means for real-world routing

In simple terms, the study shows that letting a fast neural network handle many small, well-shaped puzzles can beat spending lots of time on one huge puzzle. By clustering cities in a way that respects the network’s comfort zone, then cleverly combining the partial answers, the method delivers routes that are both short and quick to compute. For applications like logistics, multi-robot planning and emergency response, this points to a practical way to get near-real-time route plans that make better use of vehicles and energy than many existing tools.

Citation: Zhao, CS., Wong, LP. & Fung, C. Solving multi-depot closed-path multiple traveling salesman problem using k-means++ hierarchical clustering and neural combinatorial networks. Sci Rep 16, 15631 (2026). https://doi.org/10.1038/s41598-026-45824-3

Keywords: vehicle routing, neural networks, clustering, optimization, logistics