A Hierarchical Divide‐and‐Conquer Neural Approach for Multiple Traveling Salesman Problems

ABSTRACT 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.