A Learning-Based Framework for Constrained Shortest Path Problems
Xuefeng Jin, Shun‐Zheng Yu · 2023
The doubly resource constrained elementary shortest path problem (DRCESPP) has important applications in intelligent network scenarios. For solving this strong NP-hard problem, we introduce learning-based techniques and present a solution framework integrating preprocessing, graph neural networks (GNNs) and deep reinforcement learning (DRL). First, the preprocessing procedure reduces the network size and provides initial feasible paths. Then, the classifier, implemented by a graph attention network (GAT), filters out the reduced networks where better paths exist after preprocessing. Finally, a DRL-based heuristic attempts to construct the optimal path for the filtered reduced networks with an end-to-end solution paradigm. We devise a crafted reward function and a shared low-variance baseline for the reinforcement learning optimization algorithm. Our experiments suggest that the proposed framework achieves better performance compared with competitive heuristic algorithms in terms of solution quality and computational efficiency.