Scholarlink

<p>Traditional methods for solving the multiple traveling salesman problem (MTSP), such as metaheuristics, face a well-known trade-off between computational speed and solution quality. Neural combinatorial networks (NCNs) offer an efficient alternative for addressing traveling salesman problems (TSPs) but lack a native decomposition mechanism for MTSP and suffer from performance decay at scale. To mitigate these limitations, this study proposes a two-phase optimization algorithm, k-means++ hierarchical clustering with neural combinatorial networks (KHC-NCN), tailored for the symmetric Euclidean 2D multi-depot closed-path MTSP (MDCP-MTSP). The k-means++ clustering fulfills the inherent requirement of MTSP to group cities, while the end-to-end NCN enables rapid and high-quality optimization of the segmented subproblems, thus accelerating the overall solution process. The proposed coarse-to-fine hierarchical clustering and solution merging of subproblem tours alleviate the performance degradation typically observed when NCNs are generalized to large clusters. Comprehensive experimental evaluations on typical symmetric Euclidean 2D TSPLIB instances illustrated KHC-NCN’s superior optimization quality and reliability compared to numerous traditional metaheuristics. Furthermore, across 44 test cases derived from 11 TSPLIB instances with varying numbers of salesmen and scaling to 1060 nodes, KHC-NCN produced shorter tours in nearly 73% of cases, achieved orders-of-magnitude mean end-to-end wall-clock speedups, and simultaneously improved solution quality by an average of at least 3% over traditional clustering-based algorithms. In the same benchmark, KHC-NCN demonstrated competitive solution quality against LKH-3 and outperformed the neural solver POMO, both applied to the MDCP-MTSP setting through problem reformulation, while achieving substantial computational speedups. Finally, an MDCP-MTSP benchmark on all available symmetric Euclidean 2D TSP instances from the TSPLIB has been established, offering a reference for future research within this domain.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年4月2日

查看全文
  • Chun-Sheng Zhao,
  • Li-Pei Wong,
  • Chey Fung

摘要

Traditional methods for solving the multiple traveling salesman problem (MTSP), such as metaheuristics, face a well-known trade-off between computational speed and solution quality. Neural combinatorial networks (NCNs) offer an efficient alternative for addressing traveling salesman problems (TSPs) but lack a native decomposition mechanism for MTSP and suffer from performance decay at scale. To mitigate these limitations, this study proposes a two-phase optimization algorithm, k-means++ hierarchical clustering with neural combinatorial networks (KHC-NCN), tailored for the symmetric Euclidean 2D multi-depot closed-path MTSP (MDCP-MTSP). The k-means++ clustering fulfills the inherent requirement of MTSP to group cities, while the end-to-end NCN enables rapid and high-quality optimization of the segmented subproblems, thus accelerating the overall solution process. The proposed coarse-to-fine hierarchical clustering and solution merging of subproblem tours alleviate the performance degradation typically observed when NCNs are generalized to large clusters. Comprehensive experimental evaluations on typical symmetric Euclidean 2D TSPLIB instances illustrated KHC-NCN’s superior optimization quality and reliability compared to numerous traditional metaheuristics. Furthermore, across 44 test cases derived from 11 TSPLIB instances with varying numbers of salesmen and scaling to 1060 nodes, KHC-NCN produced shorter tours in nearly 73% of cases, achieved orders-of-magnitude mean end-to-end wall-clock speedups, and simultaneously improved solution quality by an average of at least 3% over traditional clustering-based algorithms. In the same benchmark, KHC-NCN demonstrated competitive solution quality against LKH-3 and outperformed the neural solver POMO, both applied to the MDCP-MTSP setting through problem reformulation, while achieving substantial computational speedups. Finally, an MDCP-MTSP benchmark on all available symmetric Euclidean 2D TSP instances from the TSPLIB has been established, offering a reference for future research within this domain.