PaE:Adeep reinforcement learning-based two-level online solution for uncertain moving-target traveling salesman problems

This paper investigates an uncertain Moving-Target Traveling Salesman Problem (MT-TSP), in which the future motion trajectories of targets are uncertain. The objective is to maximize the number of visited targets within a bounded region while minimizing the total travel distance. To address the challenges introduced by dynamic target maneuvers, we propose a two-level online solution framework, termed PaE (Plan and Execute), which leverages the current observations of targets to solve the problem in real time. The high-level module plans the next target to visit, while the low-level module executes the corresponding access process. We develop a deep reinforcement learning–based algorithm at the high level, which employs an attention-based model to effectively exploit both the current environment state and historical visiting information when selecting the next tar-get. At the low level, rapid target access is achieved through a lightweight prediction mechanism with continuous state updates. Extensive experiments in simulated environments demonstrate that PaE is capable of extracting key problem features to capture dynamic changes, leveraging rich contextual information to guide decision-making, and generating high-quality solutions within extremely short computation times.