A Hierarchical Divide‐and‐Conquer Neural Approach for Multiple Traveling Salesman Problems
Networks · 2026-09 · 88 (2) · 163-177
DOI: 10.1002/net.70049 ↗Kurz gefasst
Fachartikel in der Zeitschrift Networks, online erschienen am 07.05.2026. Verfasst von Bei Ou und 4 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 45 Literaturangaben. Gefördert von: Natural Science Basic Research Program of Shaanxi Province.
Abstract (Originalsprache)
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.
Förderung
- Natural Science Basic Research Program of Shaanxi Province
Zitieren
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