OT-Dispatch Net: Learning Dynamic Dispatch Policies via Optimal Transport

In this paper, we study the multiple traveling salesman problem (mTSP) in a dynamic setting, termed DmTSP, where multiple agents jointly serve a set of requests that arrive sequentially and must be assigned without knowledge of future demand. Compared with mTSP, DmTSP poses a key challenge of jointly determining request allocation across agents and individual assignments while accounting for their downstream routing effects, which remains unexplored. To tackle DmTSP, we propose OT-Dispatch Net, a reinforcement learning framework based on optimal transport (OT). Specifically, OT-Dispatch Net uses an agent marginal and transport costs to model request allocation and agent-request preferences, respectively, allowing OT to couple allocation and assignment decisions in a unified dispatch plan. A soft-quota decoder is further developed to map the resulting transport plan to feasible joint assignments. The policy is trained using a potential-based reward function designed to capture the downstream routing effects induced by dispatch decisions. We theoretically characterize the impact of approximation errors on dispatch quality and show that workload stability can be preserved under bounded decision error. Experiments across synthetic and real-world replay settings demonstrate its superior performance over existing learning-based methods.