A Clustering-Based Multi-Task Balancing Method for Depot Optimization in Single-Depot Multiple Traveling Salesman Problems

In the single-depot multi-traveling salesman problem, traditional depot location methods often overlook task balance among traveling salesmen, leading to excessive load on certain units and compromising overall operational efficiency. To address this issue, this paper proposes an optimized depot location method based on clustering and multi-task balancing. The core contribution lies in the design of a multi-weight adaptive depot optimization method. This approach clusters city nodes into multiple groups through cluster analysis and dynamically synthesizes direction vectors using information such as the number of samples within each cluster and the convex perimeter. It iteratively optimizes depot locations, minimizing the total path length while enhancing workload balance across all traveling salesman routes. Additionally, a “divide-and-conquer” strategy decomposes the complex MTSP into multiple parallel TSP subproblems, which are then efficiently solved using Or-Tools. A comprehensive evaluation framework is introduced, incorporating Total-Sum distance, Min-Max distance, Workload Balance, Cluster separability, Robustness, and Running time. Experimental results on the TSPLIB standard dataset demonstrate that the proposed method exhibits significant advantages over various traditional clustering algorithms in both route optimization and route balancing, validating its effectiveness and practicality. The method’s robust performance provides a reliable solution for real-world applications such as logistics distribution, further highlighting its practical value. Experimental results show that the proposed method reduces the total travel distance and improves workload balance on multiple TSPLIB instances compared with conventional depot selection baselines.