A Reinforcement Learning Framework for Scalable Partitioning and Optimization of Large-Scale Capacitated Vehicle Routing Problems

The Capacitated Vehicle Routing Problem (CVRP) is a central challenge in combinatorial optimization, with critical applications in logistics and transportation. Traditional methods struggle with large-scale instances, due to the computational demands, while learned construction models often suffer from degraded solution quality and constraint violations. This work proposes SPORL, a Scalable Partitioning and Optimization via Reinforcement Learning framework for large-scale CVRPs. SPORL decomposes the problem using a learned partitioning strategy, followed by parallel subproblem solving, and employs a greedy decoding scheme at inference to ensure scalability for instances with up to 1000 customers. A key innovation is a context-based attention mechanism that incorporates sub-route embeddings, enabling more informed and constraint-aware partitioning decisions. Extensive experiments on benchmark datasets with up to 1000 customers demonstrated that SPORL consistently outperformed state-of-the-art learning-based baselines (e.g., AM, POMO) and achieved competitive performance relative to strong heuristics such as LKH3, while reducing inference time from hours to seconds. Ablation studies confirmed the critical role of the proposed context embedding and decoding strategy in achieving high solution quality.