A Reinforcement Learning Heuristic Framework with Residual Graph Convolutional Networks for Solving the CVRP

In the rapidly developing fields such as smart logistics today, reasonable route planning holds significant economic value for related enterprises in reducing operational costs. As a result, research on the Capacitated Vehicle Routing Problem (CVRP) has become a hotspot in academia. Most studies primarily focus on determining vehicle routes through the application of exact algorithms or metaheuristic algorithms. However, since the construction of such algorithms often relies on expert experience, they suffer from drawbacks such as getting trapped in local optima. This study proposes a Residual Graph Convolutional Deep Q-Network (RGCN-DQN) framework, which formulates the operator selection process of the Adaptive Large Neighborhood Search (ALNS) algorithm as a Markov decision process. By pairing destruction operators with repair operators, an action space is generated to solve CVRP instances of varying scales. The results demonstrate that, compared to traditional ALNS and benchmark algorithms, the proposed method offers advantages in solution quality and other performance metrics. Furthermore, the hybrid framework introduced in this study can be extended to other combinatorial optimization problems, offering both theoretical significance and practical value.