End-to-End Graph-Embedded Reinforcement Learning for Solving the Shortest Path Problem with Constraints
TL;DR
This study introduces E2E_GERL, a novel end-to-end graph-embedded reinforcement learning algorithm for the time-constrained SPP, which achieves better results with substantially lower inference time than classical and NCO baselines, which also validate the potential of integrating NCO into constrained optimization problem algorithms.
Abstract
The shortest path problem (SPP) with constraints constitutes a fundamental yet computationally prohibitive NP-hard challenge in operations research and logistics. Traditional optimization algorithms, including both exact and approximate methods, often suffer from prohibitive computational times and severe scalability bottlenecks on large-scale instances. In contrast, emerging Neural Combinatorial Optimization (NCO) approaches offer the potential for rapid inference but frequently fail to guarantee structural feasibility under strict constraints. To bridge this gap, this study introduces E2E_GERL, a novel end-to-end graph-embedded reinforcement learning algorithm for the time-constrained SPP. The problem is reformulated as a structure-aware and resource-aware sequential decision-making process, where a neural graph embedding network, structure2vec, is integrated to capture the long-term structural equivalence of critical graph nodes. In our framework, a ReLU-based Lagrangian penalty is introduced to embed time constraint violation into the learning objective, and n-step Q-learning is employed to effectively overcome delayed path-level consequences. Extensive experiments on synthetic graphs, modified benchmark instances, and a real-world logistics network demonstrate the superiority of the proposed algorithm, E2E_GERL. It achieves better results with substantially lower inference time than classical and NCO baselines, which also validate the potential of integrating NCO into constrained optimization problem algorithms.