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

1 Introduction

The Capacitated Vehicle Routing Problem (CVRP) is a fundamental research topic in combinatorial optimization and serves as a canonical model for numerous real-world applications, including urban logistics [Jeong and Song, 2025], last-mile delivery [Tiwari and Sharma, 2023], postal distribution [Sbai et al., 2022], and transportation planning [Leng and Li, 2021], where goods must be delivered from a central depot to a set of geographically distributed customers. In practical applications, CVRP instances often incorporate additional constraints to reflect real-world operational requirements. For example, time window constraints [Vidal et al.,

∗Corresponding author: wl@nju.edu.cn

2014] enforce that customers must be served within specified intervals, while open route constraints [Li et al., 2007] allow vehicles to finish their service without returning to the depot. Given the NP-hard nature [Lenstra and Kan, 1981] and the increased complexity introduced by these variants, developing a unified and efficient approximate solver has become an important and long-standing research objective.

With the development of learning-based methods in the field of combinatorial optimization, a number of foundation models for VRPs have recently been proposed [Berto et al., 2024; Drakulic et al., 2025; Zhou et al., 2024]. These methods introduce advanced architectural designs inspired by Large Language Models (LLMs), incorporating components such as multi-head mixed-attention blocks, transformerbased encoders, and mixture-of-experts (MoE) structures to construct a unified network architecture capable of addressing diverse VRP variants. From a learning perspective, these models typically adopt POMO-style [Kwon et al., 2020] reinforcement learning or imitation learning paradigms to train neural networks that directly generate high-quality routing solutions in an end-to-end manner. In this solving framework, the incorporation of domain knowledge is manifested in two ways: (1) the design of network architectures guided by problem-specific insights; and (2) solution samples generated by classical solvers. Although promising results have been achieved, relying solely on model- or data-driven domain knowledge overlooks the importance of algorithmic design in solving classical problems, thereby limiting further improvements in solution quality.

To directly leverage domain knowledge in solving CVRPs, we exploit the decomposable nature of the problem. Problem decomposition has a long-standing history in the study of CVRPs, particularly within the field of evolutionary computation [Zhang et al., 2022]. Among these approaches, the Route-first Cluster-second (RFCS) heuristic [Prins et al., 2014] represents one of the most influential strategies, and numerous variants have been developed following this principle. Specifically, the RFCS heuristic first constructs a global route covering all customer nodes (excluding the depot) using heuristic methods such as TSP solvers. It then applies a polynomial-time optimal algorithm to divide the global route into feasible vehicle tours, thereby producing a valid solution to original CVRP variants. Manually designed algorithms can naturally incorporate various operational constraints. More importantly, once the global route is generated, the subsequent process typically runs in polynomial time, ensuring high computational efficiency. For example, [Vidal, 2015] give a O(n) algorithm given a global route for minsum CVRP, and [Wang et al., 2025] gives a binary searchbased splitting algorithm for minmax VRPs. Nevertheless, such methods generally rely on TSP-based heuristics to construct the global route, and the optimal TSP tour does not necessarily yield an optimal solution to the original CVRP variants after a cluster-second operation. In this paper, we introduce reinforcement learning to automatically learn the route first part, avoiding the limitations of handcrafted TSPbased heuristics.

However, the problem decomposition mechanism introduces a partial observability challenge: the context of a partial route cannot be fully assessed until the entire route is generated and the subsequent splitting stage is completed. To address this issue, we introduce a history-enhanced module as the core of our context processor. This module use the LSTM [Hochreiter and Schmidhuber, 1997] architecture to maintain a temporal hidden state that continuously aggregates historical information throughout the route construction process, allowing the model to infer the latent information of the problem even when the final evaluation signal is postponed. Beyond mitigating partial observability, the history-enhanced context representation also provides a unified neural architecture across different VRP variants. By encoding the evolving decision context into a learned hidden state, the framework eliminates the need for manually designed problem-specific contexts. As a result, the same network architecture can generalize seamlessly across multiple problem types-such as open-route, backhaul-request, and time-window CVRPs-without additional adaptation.

The main contributions can be summarized as follows.

• We propose a unified knowledge-embedded RFCS framework that integrates RL with the route-first cluster-second (RFCS) heuristic to address a wide range of CVRP variants. This framework combines general learning-based methods and algorithmic design principles, enabling flexible adaptation to various types of problem-specific constraints.
• We introduce a history-enhanced context processing module that preserves a unified neural network architecture across general CVRP variants. This module simplifies the design of context features by exploiting a common representation provided by the route-first component, enabling effective handling of complex constraints.
• We perform extensive experiments to evaluate the solution quality and transfer capabilities of the framework across diverse CVRP settings. The results demonstrate that the proposed knowledge-embedded RFCS framework consistently outperforms existing learning-based methods and exhibits strong zero-shot generalization to unseen problem variants.

2 RelatedWork

Since the introduction of neural networks into combinatorial optimization by the Pointer Network [Vinyals et al., 2015], a series of learning-based combinatorial optimization solvers have subsequently emerged, collectively referred to as Neural Combinatorial Optimization (NCO). From the perspective of solution paradigms, learning-based approaches can be broadly classified into three categories [Wu et al., 2024]: (1) Learning to Construct (L2C), which focuses on directly generating solutions; (2) Learning to Improve (L2I), which aims to refine or enhance existing solutions; and (3) Learning to Predict (L2P), which leverages neural networks to support and augment traditional operations research methods. In the L2C paradigm, the Attention Model (AM) [Kool et al., 2018] proposed a Transformer-based encoder-decoder architecture to directly generate solutions. Subsequently, POMO [Kwon et al., 2020] and Sym-NCO [Kim et al., 2022a] introduced multi-start and symmetry-based [Shi et al., 2025; Yu et al., 2024] training strategies, respectively, during the solution generation process, further enhancing solution quality. More recent studies have focused on improving generalization capability [Gao et al., 2024], addressing diverse objectives and constraints [Son et al., 2024; Zheng et al., 2024; Bi et al., 2024], and scaling up to larger problem instances [Luo et al., 2023; Kim et al., 2022b]. This paradigm achieves a favorable balance between solution quality and inference efficiency, and it is also adopted in this work. The L2I paradigm originated from learning local rewriting operations [Chen and Tian, 2019], and was later extended to the learning of heuristic operators such as 2-OPT and cross-exchange [d O Costa et al., 2020; Hottung and Tierney, 2020; Sui et al., 2021; Wu et al., 2021]. In recent years, research in this direction has increasingly focused on large-scale problem solving [Cheng et al., 2023; Li et al., 2025]. Although this paradigm is more suitable for handling large-scale problems, it is relatively difficult to employ a unified framework to address diverse types of constraints. The L2P paradigm integrates traditional algorithmic approaches with learning-based methods, such as combining learning with the LKH algorithm [Xin et al., 2021; Zheng et al., 2021], integrating learning with dynamic programming [Kool et al., 2022; Xu et al., 2020], and leveraging large language models (LLMs) and meta-learning for automated algorithm design [Liu et al., 2024b; Dernedde et al., 2025]. Methods of this type, by incorporating principles of algorithm design, have the potential to improve solution quality. In this work, we adopt a similar approach within the L2C framework, introducing knowledge as a reward signal, which facilitates the handling of general forms of constraints.

3 Preliminaries

In this section, we first introduce the general form CVRPs. Then, we summarize the RL formulation for CVRPs, describing how solutions can be modeled as sequential actions and optimized under the RL paradigm.

3.1 General FormCVRPs

The CVRPs can be defined on a complete graph G = (V, E), where V = {v0, v1, · · · , vn} is the set of nodes, with v0 representing the depot and {v1, · · · , vn} representing the customer nodes. Each edge (i, j) ∈ E is associated with a non-negative cost cij. As a common practice, each node is assigned a two-dimensional coordinate, and the Euclidean distance is used as the cost. Vehicles with identical capacity Q are stationed at the depot. Each customer node i ∈ {1, · · · , n} has a nonzero demand qi ≤ Q that must be satisfied by exactly one vehicle. Each vehicle travels from the depot node, serves customers and returns to the depot. The total demand of the served nodes should not exceed the capacity.

Following [Berto et al., 2024], we consider a generalized formulation of the CVRP that incorporates multiple additional constraints: (1) Open routes - vehicles are not required to return to the depot; (2) Backhaul demands - customer requests may involve both delivery and pickup operations; (3) Distance limits - the travel distance of each route must not exceed a predefined threshold; and (4) Time windows - each customer must be served within a specified time interval. Each additional constraint can be independently activated or deactivated, resulting in sixteen problem variants, denoted as CVRP, OVRP, VRPB, VRPL, VRPTW, etc.

We aim to minimize the total travel cost over all vehicle routes. Let {Rk}Kk=1 denote a feasible routing plan, where Rk is the sequence of nodes served by vehicle k. The cost of route Rk is given by

with ci,j representing the travel cost between nodes i and j. The min-sum objective is then formulated as

subject to the following feasibility conditions: 1) each customer is visited exactly once; 2) the total demand on each route does not exceed vehicle capacity; and 3) all additional constraints are satisfied. Here, K denotes the number of active vehicles in the solution.

3.2 Reinforcement Learning for CVRPs

In the RL framework for CVRPs, a constructive solver sequentially builds a solution by selecting one customer node at a time. Formally, at step t, the solver selects an action at ∈ Vt based on a context ct, which corresponds to visiting a customer node next, according to a stochastic policy at ∼ πθ(at | ct), parameterized by neural network parameters θ. After visiting node at, the state is updated to ct+1, and the set of available actions is reduced: Vt+1 = Vt \ {at}.

Once all customers are visited and feasible routes are constructed, the solver receives a reward R based on the objective. The RL training objective is to maximize the expected reward over all possible construction sequences:

where τ = (a0, a1, · · · , aT ) denotes a trajectory generated by the policy. Gradient-based optimization can be performed using policy gradient methods, e.g., REINFORCE [Williams, 1992], optionally enhanced with baselines to reduce variance:

where b is a baseline value.

4 The ProposedMethod

Unlike a fully end-to-end learning paradigm, we propose a knowledge-embedded RL framework for solving generalized CVRPs. The framework integrates problem-solving principles with algorithmic design insights into the training process to improve solution quality. It also simplifies transition modeling in the training environment, reduces the complexity of incorporating new constraints, and enables a unified network architecture applicable across multiple CVRP variants.

4.1 The Overall Framework

The overall framework is illustrated in Figure 1. We adopt a route-first, cluster-second heuristic structure. The RL component focuses on the route-first stage, where the objective is to generate a sequence that visits all customer nodes exactly once, resulting in a permutation of customer indices. All complex constraints are handled by a dynamic programmingbased cluster-second module. Given any customer permutation, this module determines the optimal splitting of the sequence into feasible vehicle routes while satisfying additional constraints such as time windows and duration limits.

Although the framework consists of two components, the reward signal is computed based on the solution produced by the cluster-second module. This reward is then used to optimize the route-first policy through RL, thereby aligning the optimization objective of the RL model with that of the original problem formulation. In this way, the framework eliminates the dependence on heuristic TSP solvers and achieves a direct, learning-based formulation of the routing problem.

4.2 The Unified Environment

The framework allows problems with heterogeneous constraints or objectives to be reduced to an identical learning structure, thus we adopt a unified formulation for constructing the RL environments under different constraint settings, as described below.

States: At step t, the environment maintains a state or context st that summarizes all relevant information needed for decision-making:

where:

• X ∈ Rn×2 denotes the coordinates of depot and customer nodes. We use xi, yi for the i-th node;
• q ∈ Rn×1 represents the customer demands, including negative values for pickup nodes. We use qi for the i-th node;
• TW ∈ Rn×3 encodes time windows and service durations. We use ri, si, di to denote the start time, the service duration, and the deadline for node i.
• l ∈ R represents distance limits;
• n0, n1 ∈ R track the cumulative delivered and pickedup quantities for each route;
• vt ∈ {0, . . . , n} is the current node being visited;

Algorithm 1 Dynamic Programming-based Solver

Require: Customer sequence π = (a1, a2, · · · , an), node attributes, variant flags Ensure: Minimum total route cost p[n] 1: Initialize p[0] ← 0, p[i] ←+∞ for all i = 1, . . . , n 2: for t = 0 to n-1 do 3: Initialize lo ← 0, li ← 0, tnow ← 0, cost ← 0 4: for i = t + 1 to n do 5: lo ← lo +max(qai , 0), li ← li +max(-qai , 0) 6: if lo > Q or li > Q or precedence violated then 7: break 8: end if 9: cost ← cost + cai-1,ai 10: if TW active then 11: tnow ← max(tnow, rai ) + sai 12: if tnow > dai then 13: break 14: end if 15: end if 16: if L active and cost > l then 17: break 18: end if 19: if O active then 20: p[i] ←min(p[i], p[t] + cost) 21: else 22: p[i] ←min(p[i], p[t] + cost + cai,0) 23: end if 24: end for 25: end for 26: return p[n]

fined as +∞. Algorithm 1 details the procedure. Specifically, lines 5-6 manage the backhaul-related variants, and all other constraints, including capacity, time windows, and duration limits, are handled through their respective conditional checks. It is straightforward to extend this algorithm to incorporate additional constraints. For example, adding support for the mixed-backhaul constraint [Zhou et al., 2024] can be achieved by simply adjusting the condition in line 6.

• m ∈ {0, 1}n is the action mask, indicating feasible next visited nodes;
• f ∈ {0, 1}4 encodes the variant features (O, B, L, TW) of the current instance, where each element represents a binary flag indicating whether the corresponding constraint is active.

When certain attributes are absent, default values are used as placeholders to maintain a unified data structure.

Actions: The action at step t is selecting the next node at ∈ {1, . . . , n + 1} to visit.

Transitions: Benefiting from the proposed design, state updates can be performed through a simple and efficient procedure. The variables n0, n1, vt are updated directly according to their definitions, while m is refreshed by setting the value of each visited node to zero. The responsibility for checking action feasibility is fully delegated to the clustersecond module.

Rewards: We employ a dynamic programming-based solver (Section 4.3) to optimally convert the solutions to the original problem. The reward is defined as the negative of the total cost computed by this solver.

We hypothesize that this structural consistency contributes substantially to the effectiveness and generality of the proposed framework.

4.3 Dynamic Programming-based Solver

To compute the optimal cost of the route-first sequence, we develop a dynamic programming (DP)-based approach capable of naturally handling diverse constraint types. Let a given sequence of customer nodes (excluding the depot) be denoted as π = (a1, a2, . . . , an), and let p[i] represent the minimum total cost to serve the first i nodes. The DP formulation recursively computes

where C(j + 1, i) is the cost of serving nodes (πj+1, . . . , πi) as a single vehicle route, subject to capacity, pickup-anddelivery precedence, distance, and time window constraints. To naturally handle these constraints, a simple yet effective strategy is adopted: if the sequence (πj+1, . . . , πi) cannot form a feasible single vehicle route, C(j + 1, i) is de-

4.4 Model Architecture

The route-first module is parameterized by a neural network consisting of an transformer-based encoder-decoder architecture augmented with history-enhanced context representation. The architecture is designed to handle various CVRP variants within a unified network architecture.

Encoder: The encoder maps the raw node features into a latent embedding space. Let the node attributes for the i-th customer be xi = [xi, yi, qi, ri, si, di] ∈ R6 . For the depot node, the attribute is represented as x0 = [x0, y0, O, B, L, TW, l] ∈ R7 .

The node features are projected via learnable linear layers:

The sequence of initial embeddings H(0) = [h(0) 0 , . . . , h(0) n ] ∈ R(n+1)×d is then processed by a stack of multiple Routefinder Transformer [Berto et al., 2024] blocks. Each block consists of:

1. Multi-head self-attention: H(i) = H(i-1) + MHA(RMSNorm(H(i-1) )),
2. Gated feedforward network:

A final RMS normalization is applied to produce node embeddings H(N) ∈ R(n+1)×d (Hereafter, (N) is omitted for notational simplicity), and a graph-level embedding g is computed by mean pooling of H.

Decoder: At each decoding step t, the policy selects the next node at based on a context embedding ct ∈ Rd computed from:

where h0 and hcurrent are embeddings of the depot and current nodes, and dt = Linear([n0, n1]) encodes the cumulative delivery/pickup loads. This history-enhanced context enables the agent to maintain a hidden state capturing historical information, mitigating partial observability induced by the knowledge-embedded RFCS framework.

A multi-head attention mechanism is applied between ct and the node embeddings H:

where mt is the action mask. The resulting attention output is projected back into the embedding space, producing a compatibility score for each candidate node:

with infeasible actions masked by -∞. Here, α = 10 is a temperature scaling factor controlling exploration.

This architecture ensures that the same network can process all CVRP variants without variant-specific modifications. The decoder outputs a probability distribution over feasible next nodes, from which the action is sampled or greedily selected. The network is trained via REINFORCE [Williams, 1992] accroding to equation (4).

5 Experiments

We empirically validate the effectiveness of the proposed knowledge-embedded framework in this section. Our experimental design examines three key aspects: solution quality, generalization ability, and ablation analysis-corresponding to the following research questions:

• RQ1 Does the proposed knowledge-enhanced framework improve solution quality?
• RQ2 How effectively does the proposed framework generalize across different problems?
• RQ3 What is the impact of incorporating historical information into the learning process?

5.1 Experiment Settings

Following the data generation process in [Berto et al., 2024], depot and customer coordinates are uniformly sampled within the unit square. For training instances with 50 and 100 customers, the vehicle capacities Q are set to 40 and 50, respectively, while customer demands are uniformly sampled from {1, 2, · · · , 9}. In the backhaul scenario, 20% of the customers are randomly assigned negative demands to simulate pickup requests. For the time-window constraints, the service duration of each customer is uniformly sampled from [0.15, 0.18]. The length of the time window is drawn uniformly from [0.18, 0.2], and both the starting and ending times are generated by applying a random offset uniformly sampled from the feasible range. The distance limit is uniformly drawn from [2Dmax, 3], where Dmax denotes the maximum Euclidean distance between the depot and the farthest customer node.

During training, all problem attributes are randomly generated on the fly, and the constraint flags are uniformly sampled across different variants. For each training batch, we fix one particular constraint configuration so that all instances in the batch share the same problem setting. For each problem setting, the model is trained for 300 epochs, with 1,280,000 samples per epoch and a batch size of 512. To stabilize training and improve final convergence, the learning rate is progressively decreased toward the end of training. The framework demonstrates better performance without using POMO-style multi-start [Kwon et al., 2020]. During training, we simply perform eight stochastic policy rollouts per instance and take their average cost as the baseline.

We evaluate our framework using the open-source dataset from [Berto et al., 2024]. We do not use multi-start sampling; instead, for each instance, we perform 8-fold data augmentation and generate as many trajectories as there are nodes, selecting the best among them. This approach ensures consistent comparison data and produces an identical number of trajectories for all methods. The code can be found at https://github.com/wenwenla/ijcai26-cvrp-solver.

5.2 Baselines

We select the following methods as baselines for comparison, which are described in detail below. These solvers are open-source, allowing reproducible comparisons. We select two classical optimization algorithms, PyVRP [Wouda et al., 2024] and OR-Tools [Furnon and Perron, 2024], as non-learning baselines for comparison. We also compare with three recent learning-based VRP solvers: (1) MTPOMO [Liu et al., 2024a], a multi-task VRP solver based on POMO [Kwon et al., 2020]; (2) MVMoE [Zhou et al., 2024], a multi-task VRP solver leveraging mixture-of-experts networks for unified handling of different VRP variants; and (3) RouteFinder [Berto et al., 2024], a transformer-based foundation model designed for general VRPs.

5.3 Results for RQ1

Table 1 presents the average costs over 1,000 unseen instances [Berto et al., 2024] for sixteen CVRP variants, including the atomic problems-CVRP, OVRP, VRPB, VRPL, and VRPTW-as well as their various combinations. The knowledge-embedded framework outperforms all learningbased methods across all variants, except for the VRPL variant, where it performs slightly below RouteFinder. The average optimality gap are shown in Figure 2. RFCS achieves a marked improvement by reducing the average optimality gap from 2.60% to 1.82% on average, highlighting the stronger solution quality achieved by our framework. Since the proposed framework shares the same neural network forwardpropagation cost as other learning-based methods, and the dynamic programming-based splitting algorithm has a time complexity of O(n2 ), its computational overhead is negligible compared with neural network inference. Therefore, the overall solving time of our framework is comparable to that of the baseline learning-based methods. While classic approaches often yield better solution quality, they usually demand tens of minutes to complete a computation, in contrast to learning-based methods, which require only a few seconds. For more discussions regarding runtime and scalability, please refer to the appendix of the arXiv version.

5.4 Results for RQ2

We evaluate the zero-shot transfer capability of RFCS across different capacity distributions encountered during training. During training, for scenarios with n = 50, the vehicle capacity was set to 40. We directly evaluate the model obtained in RQ1 on instances with varying vehicle capacities to examine its performance changes. The target distribution of vehicle capacities ranges from [50, 90], and the experimental results of zero-shot transfer evaluation are presented in Table 2. The results indicate that when the capacity distributions differ between training and evaluation, the knowledge-embedded framework exhibits superior zero-shot transfer performance compared to existing learning-based methods.

A commonly studied CVRP variant introduces mixed linehaul and backhaul demands [Zhou et al., 2024], allowing vehicles to alternate between delivery and pickup operations instead of strictly finishing deliveries before pickups. In this case, the key constraint is that the vehicle load must not violate the capacity limit at any time. As described in section 4.3, we only need to modify the Algorithm 1 to adapt the solver to this scenario. The zero-shot transfer results to mixed demands are shown in Table 3. The results show that our method outperforms the baselines when transferring from VRPB and OVRPB to the mixed constraint scenario, achieves comparable performance for VRPBL, and exhibits a notable performance drop for VRPBTW. While the framework does not surpass the baselines across every test case, the findings highlight its inherent flexibility and adaptability.

5.5 Results for RQ3

We conduct an ablation study to assess the contribution of the history-enhanced context in the knowledge-embedded framework. The results are summarized in Table 4. For the variant without historical information, we adopt an identical training setup, except that the LSTMmodule in the decoder responsible for handling historical information is replaced with a fully connected layer. The results of this ablation study highlight the necessity of incorporating historical information. While the LSTM is not the most advanced architecture for modeling history, it was chosen for its ability to incrementally maintain past information. Further improvements in processing historical information by introduce more advanced network represent an interesting direction for future research.

Another interesting ablation concerns whether incorporating the dynamic programming-based reward during training is necessary. To address this question, we examine the results obtained by directly applying the dynamic programming module to optimize the solutions for CVRP generated by baselines. The corresponding results are shown in Table 5. From the table, we observe that applying the cluster-second optimization improves the solutions generated by the learning-based methods. However, the improvement is marginal, and the resulting performance remains inferior to that of RFCS trained with the dynamic programming-based reward. This not only highlights the optimality improvement provided by the DP procedure, but also demonstrates that incorporating the DP-based reward during training is necessary.

6 Conclusion

In this paper, we propose a unified framework for a broad range of CVRP variants. Inspired by the route-first clustersecond heuristic, the framework integrates RL with dynamic programming-based algorithmic design knowledge to solve CVRPs with various constraints. Specifically, the route-first component leverages RL to generate visitation sequences. The cluster-second component employs dynamic programming to optimally convert a given sequence into a feasible solution for the original problem, and provides the cost as a reward to guide RL. The proposed framework not only achieves strong performance in terms of solution quality and transferability but also offers a flexible and unified approach to handling diverse constraints. In future work, we plan to incorporate more advanced network architectures with this framework to achieve even better results. We also plan to extend this approach to other domains beyond routing problems.

Acknowledgments

This work was supported by the NSFC Major Research Plan Key Program under Grant No. 92582204, and the Collaborative Innovation Center of Novel Software Technology and Industrialization.