A Unified Knowledge Embedded Reinforcement Learning-based Framework for Generalized Capacitated Vehicle Routing Problems
A Unified Knowledge Embedded Reinforcement Learning-based Framework for Generalized Capacitated Vehicle Routing Problems
Wen Wang, Xiangchen Wu, Liang Wang, Hao Hu, Xianping Tao
Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence
Main Track. Pages 6208-6216.
https://doi.org/10.24963/ijcai.2026/691
The Capacitated Vehicle Routing Problem (CVRP) is a fundamental NP-hard problem with broad applications in logistics and transportation. Real-world CVRPs often involve diverse objectives and complex constraints, such as time windows or backhaul requirements, motivating the development of a unified solution framework.
Recent reinforcement learning (RL) approaches have shown promise in combinatorial optimization, yet they rely on end-to-end learning and lack explicit problem-solving knowledge, limiting solution quality.
In this paper, we propose a knowledge-embedded framework inspired by the Route-First Cluster-Second heuristics.
It incorporates knowledge at two levels: (1) decomposing CVRPs into the route-first and cluster-second subproblems, and (2) leveraging dynamic programming to solve the second subproblem, whose results guide the RL-based constructive solver to solve the first problem.
To mitigate partial observability caused by problem decomposition, we introduce a unified history-enhanced context processing module.
Extensive experiments show that this framework achieves superior solution quality compared with state-of-the-art learning-based methods, with a smaller gap to classical heuristics, demonstrating strong generalization across diverse CVRP variants.
Keywords:
Planning and Scheduling: Applications
Planning and Scheduling: Learning in planning and scheduling
