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

Area of Science:

• Operations Research
• Artificial Intelligence
• Combinatorial Optimization

Background:

• Traditional multiple traveling salesman problem (MTSP) methods like metaheuristics present a speed-quality trade-off.
• Neural combinatorial networks (NCNs) are efficient for TSPs but lack MTSP decomposition and scale poorly.
• Existing NCNs struggle with performance degradation on large-scale problems.

Purpose of the Study:

• To introduce a novel algorithm, k-means++ hierarchical clustering with neural combinatorial networks (KHC-NCN), for the symmetric Euclidean 2D multi-depot closed-path MTSP (MDCP-MTSP).
• To address the limitations of NCNs in MTSP decomposition and scalability.
• To improve both solution quality and computational speed for MDCP-MTSP.

Main Methods:

• A two-phase optimization approach combining k-means++ hierarchical clustering and NCNs.
• Utilizing k-means++ for city grouping inherent to MTSP.
• Employing end-to-end NCNs for rapid, high-quality optimization of subproblems.

Main Results:

• KHC-NCN demonstrated superior optimization quality and reliability over traditional metaheuristics on TSPLIB instances.
• Achieved shorter tours in nearly 73% of test cases, with orders-of-magnitude speedups and average 3% quality improvement over clustering algorithms.
• Outperformed POMO and showed competitive results against LKH-3 on MDCP-MTSP, with significant computational speedups.

Conclusions:

• KHC-NCN effectively mitigates NCN performance decay at scale for MDCP-MTSP through hierarchical clustering and subproblem merging.
• The algorithm offers a significant advancement in solving large-scale, multi-depot routing problems efficiently.
• Established a new benchmark for MDCP-MTSP on TSPLIB instances to guide future research.