A Unified Knowledge Embedded Reinforcement Learning-based Framework for Generalized Capacitated Vehicle Routing Problems

Technical Summary: A Unified Knowledge Embedded Reinforcement Learning-based Framework for Generalized Capacitated Vehicle Routing Problems

Problem Definition
The Capacitated Vehicle Routing Problem (CVRP) is a fundamental NP-hard combinatorial optimization problem central to logistics and transportation. Real-world applications often require solving generalized variants that incorporate complex constraints such as time windows (VRPTW), backhaul/pickup requirements (VRPB), open routes (OVRP), and distance limits (VRPL). While recent learning-based methods have shown promise, they often rely on end-to-end training that lacks explicit algorithmic knowledge, potentially limiting solution quality. Furthermore, existing approaches struggle to unify diverse constraint types within a single framework without extensive architectural modifications.

Methodology
The authors propose a Unified Knowledge-Embedded Reinforcement Learning (RL) Framework inspired by the classical Route-First Cluster-Second (RFCS) heuristic. Unlike traditional end-to-end solvers, this framework decomposes the problem into two distinct stages, integrating algorithmic design principles with neural learning:

1. Route-First (RL Component): A neural network policy (based on a Transformer encoder-decoder architecture) learns to generate a global permutation of customer nodes. This stage focuses on constructing a sequence that visits all customers exactly once.
2. Cluster-Second (Knowledge Component): A dynamic programming (DP) solver takes the customer permutation generated by the RL agent and optimally splits it into feasible vehicle routes. This module explicitly handles all constraints (capacity, time windows, backhaul, distance limits) and computes the optimal cost for the given sequence.
3. Reward Mechanism: The RL agent is trained using the negative total cost computed by the DP solver as the reward signal. This aligns the RL optimization objective directly with the original problem formulation, eliminating the need for heuristic TSP solvers to generate the initial route.
4. Unified Context Processing: To address the partial observability introduced by problem decomposition (where the full context of a partial route is unknown until splitting is complete), the framework introduces a history-enhanced context module. This module utilizes an LSTM architecture to maintain a temporal hidden state that aggregates historical decision information throughout the route construction process. This allows the model to infer latent problem states and provides a unified neural architecture capable of handling diverse CVRP variants without manual redesign.

Key Contributions

• Unified Knowledge-Embedded Framework: The paper integrates RL with the RFCS heuristic, combining general learning-based methods with algorithmic design principles. This allows for flexible adaptation to various problem-specific constraints (e.g., open routes, backhauls, time windows) within a single network architecture.
• History-Enhanced Context Module: The authors introduce a mechanism that preserves a unified neural architecture across general CVRP variants. By encoding the evolving decision context into a learned hidden state via LSTM, the framework simplifies context feature design and effectively handles complex constraints without requiring problem-specific context engineering.
• Dynamic Programming Integration: The framework leverages a DP-based solver to provide optimal splitting and reward signals, ensuring that the RL policy learns to cooperate with algorithmic constraints rather than relying solely on end-to-end approximation.

Experimental Results
Extensive experiments were conducted on 16 CVRP variants (including atomic problems and their combinations) with 50 and 100 nodes.

• Solution Quality: The proposed framework (RFCS) consistently outperformed state-of-the-art learning-based methods (MTPOMO, MvMoE, RouteFinder) across most variants. It achieved an average optimality gap reduction from 2.60% (best baseline) to 1.82% compared to the best-known solutions.
• Zero-Shot Generalization: The framework demonstrated superior zero-shot transfer capabilities. When tested on unseen vehicle capacity distributions (50–90) and mixed backhaul constraints, RFCS maintained better performance than baselines.
• Scalability: The method scaled effectively to large instances (500 and 1000 nodes) without fine-tuning, outperforming baselines in both cost and inference time.
• Ablation Studies: Removing the history-enhanced module (replacing LSTM with a fully connected layer) resulted in a significant performance drop, confirming the necessity of historical information. Additionally, applying the DP module post-hoc to solutions from other learning methods yielded only marginal improvements, highlighting that the DP-based reward signal is crucial during the training phase for the RL agent to learn effective cooperation.

Significance and Claims
The paper claims that the proposed framework offers a unified and efficient approach to solving diverse CVRP variants. By embedding domain knowledge (via the RFCS heuristic and DP solver) into the RL training loop, the method overcomes the limitations of purely data-driven approaches that lack explicit problem-solving knowledge. The authors assert that this approach achieves a favorable balance between solution quality and inference efficiency, offering a flexible architecture that generalizes seamlessly across multiple problem types (e.g., open-route, backhaul, time-window) without additional adaptation. The work suggests that integrating algorithmic design principles with neural networks is a viable path toward improving solution quality in combinatorial optimization.