EUVIMEDDescobrir EUVIMED
Open access · CC BY 4.0

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

Chunlong Fu, Jiaxin Zou, Guofang Liu, Pingli Zheng, Kaiwen Xiao, Yang Deng, Hongxia He, Qi Jiang

Mathematics · 2026-08-05 · 14 (15) · 2811

DOI: 10.3390/math14152811 ↗

At a glance

Journal article in Mathematics, published online on 2026-08-05. Written by Chunlong Fu and 7 co-authors. 48 references. The full text is freely available (open access, CC BY 4.0). Funded by: Opening Foundation of the State Key Laboratory of Cognitive Intelligence, Anhui iFLYTEK Co., Ltd., 2024 Young Teacher Research Fund Project of Sichuan University Jinjiang College.

ResumoDados bibliográficosCiteRelated studies

Abstract (original language)

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.

Funding

  • Opening Foundation of the State Key Laboratory of Cognitive Intelligence, Anhui iFLYTEK Co., Ltd.
  • 2024 Young Teacher Research Fund Project of Sichuan University Jinjiang College

Cite

APA

Fu, C., Zou, J., Liu, G., Zheng, P., Xiao, K., Deng, Y., He, H., & Jiang, Q. (2026). A Clustering-Based Multi-Task Balancing Method for Depot Optimization in Single-Depot Multiple Traveling Salesman Problems. Mathematics, 14(15), 2811. https://doi.org/10.3390/math14152811

Vancouver

Fu C, Zou J, Liu G, Zheng P, Xiao K, Deng Y, et al. A Clustering-Based Multi-Task Balancing Method for Depot Optimization in Single-Depot Multiple Traveling Salesman Problems. Mathematics. 2026;14(15):2811. doi:10.3390/math14152811

BibTeX
@article{Fu2026,
  author = {Fu, Chunlong and Zou, Jiaxin and Liu, Guofang and Zheng, Pingli and Xiao, Kaiwen and Deng, Yang and He, Hongxia and Jiang, Qi},
  title = {A Clustering-Based Multi-Task Balancing Method for Depot Optimization in Single-Depot Multiple Traveling Salesman Problems},
  journal = {Mathematics},
  year = {2026},
  volume = {14},
  number = {15},
  pages = {2811},
  doi = {10.3390/math14152811}
}
Start for free →