A Hierarchical Divide‐and‐Conquer Neural Approach for Multiple Traveling Salesman Problems
Networks · 2026-09 · 88 (2) · 163-177
DOI: 10.1002/net.70049 ↗At a glance
Journal article in Networks, published online on 2026-05-07. Written by Bei Ou and 4 co-authors. Cited 1 times so far (Crossref); 45 references. Funded by: Natural Science Basic Research Program of Shaanxi Province.
Abstract (original language)
The multiple traveling salesman problem (mTSP) has attracted considerable attention due to its importance in logistics, robotics, and transportation systems. However, existing deep reinforcement learning (DRL) methods often rely on monolithic solution paradigms, which limit scalability, underutilize local graph structures, and hinder adaptability in dynamic decision‐making. To address these challenges, we propose a hierarchical divide‐and‐conquer neural approach (HDCN) for solving mTSPs in a scalable and principled manner. HDCN adopts a hierarchical architecture that decomposes the global problem into task allocation and route planning, which are jointly optimized within a unified framework. At the upper level, an affinity‐guided self‐organizing map is employed to generate structured task assignments by capturing latent spatial patterns. At the lower level, a neighborhood‐aware deep reinforcement learning model with a transformer‐inspired policy network constructs routing trajectories conditioned on the allocation results. To improve adaptability during sequential decision‐making, an integrator is introduced to fuse dynamic environmental states with static graph representations. Extensive experiments conducted on mTSP benchmarks with varying scales and spatial distributions demonstrate that HDCN consistently outperforms mainstream heuristic methods and DRL‐based baselines in terms of solution quality, scalability, and generalization performance, highlighting its effectiveness and robustness for large‐scale and complex mTSP scenarios.
Funding
- Natural Science Basic Research Program of Shaanxi Province
Cite
APA
Ou, B., Guan, Q., Zhu, Z., Cao, H., & Yan, D. (2026). A Hierarchical Divide‐and‐Conquer Neural Approach for Multiple Traveling Salesman Problems. Networks, 88(2), 163-177. https://doi.org/10.1002/net.70049
Vancouver
Ou B, Guan Q, Zhu Z, Cao H, Yan D. A Hierarchical Divide‐and‐Conquer Neural Approach for Multiple Traveling Salesman Problems. Networks. 2026;88(2):163-177. doi:10.1002/net.70049
BibTeX
@article{Ou2026,
author = {Ou, Bei and Guan, Qingshu and Zhu, Zheng and Cao, Hui and Yan, Dapeng},
title = {A Hierarchical Divide‐and‐Conquer Neural Approach for Multiple Traveling Salesman Problems},
journal = {Networks},
year = {2026},
volume = {88},
number = {2},
pages = {163--177},
doi = {10.1002/net.70049}
}
EUVIMED