Lifelong Learning with Behavior Consolidation for Vehicle Routing

Jiyuan Pei, Yi Mei, Jialin Liu, Mengjie Zhang, Xin Yao

TL;DR

Neural solvers excel at vehicle routing problems but suffer from catastrophic forgetting when sequentially trained on new problem distributions or scales. This paper introduces LLR-BC (Lifelong Learning Router with Behavior Consolidation), a framework that combines fine-grained experience replay, confidence-aware weighting, and decision-seeking behavior consolidation to retain past knowledge. LLR-BC significantly outperforms existing lifelong learning baselines, maintaining high model plasticity while preventing performance degradation on previously learned routing tasks.

What Problem Does This Paper Address?

Deep reinforcement learning (DRL) has revolutionized neural construction solvers for Vehicle Routing Problems (VRPs) and Traveling Salesman Problems (TSPs). However, these models are typically trained under a "one-off" paradigm on a fixed problem distribution and scale. In real-world logistics, demand patterns, customer locations, and fleet sizes shift dynamically over time.

Fine-tuning a pre-trained model on a new task leads to catastrophic forgetting—the model overwrites its previously learned parameters, causing performance on older tasks to plummet.

Conceptual demonstration of catastrophic forgetting

While some recent attempts address lifelong learning for VRPs, they rely on unrealistic assumptions, such as a fixed, known task order or the ability to freely generate new problem instances from past tasks at will. This paper tackles a more realistic scenario: sequential tasks with unpredictable changes in both scale and distribution, where instance generation is completely uncontrollable.

Methods

The authors propose LLR-BC (Lifelong Learning Router with Behavior Consolidation), which integrates three core innovations into standard DRL training for routing:

  1. Fine-Grained Experience Replay: Instead of storing entire problem instances, LLR-BC stores state-behavior pairs $\langle s, \mathcal{P} \rangle$, where $s$ is a partial routing solution and $\mathcal{P}$ is the action probability distribution over candidate nodes. A fixed-size experience buffer is maintained using reservoir sampling to ensure all past experiences are equally likely to be retained.
  2. Confidence-Aware Experience Weighting (CaEW): Not all past decisions are equally important. Decisions made with low confidence (low variance in the action probability distribution) are highly susceptible to drifting during fine-tuning. CaEW assigns higher consolidation weights to these low-confidence experiences, forcing the model to focus on stabilizing critical decision points.
  3. Decision-Seeking Behavior Consolidation (DsBC): Standard knowledge distillation uses forward Kullback-Leibler Divergence (KLD), which forces the model to spread probability mass across all actions. Because constructive VRP solvers greedily pick the highest-probability node next, DsBC minimizes Reverse KLD (RKLD) instead. This encourages "mode-seeking" behavior, ensuring the model accurately preserves the exact top choices from past tasks.
Figure 2: LLR-BC in the lifelong learning scenario where new tasks with different distributions and scales sequentially arise over time. Tt: the task at time t. πθ: solver with model parameters θ. B: experience buffer. J : problem instances. {τ}: problem solving trajectories. E: experiences. wE: weights of experiences. a: action, i.e., node to visit. s: state. var: variance. P: behavior.

Datasets

  • Synthetic Routing Tasks: Six distinct spatial node distributions were evaluated: Uniform (U), Gaussian Mixture (GM), Explosion (E), Compression (C), Grid (G), and Ring (R). Distinct demand distributions were also designed for CVRP tasks.
  • Problem Scales: Tasks spanned three different sizes: 20 nodes (U, R), 50 nodes (G, E), and 100 nodes (C, GM).
  • Benchmark Datasets: Classic benchmarks TSPLIB and CVRPLIB were used exclusively to evaluate the model's zero-shot generalization capabilities after lifelong learning.

Key Insights and Ideas

  • Granularity Matters: Replaying fine-grained state-action distributions rather than full problem instances provides much richer instructive signals for stabilizing neural solvers.
  • The Vulnerability of Low Confidence: Decisions where the model is uncertain are the first to break when fine-tuning on a new task. Prioritizing these via CaEW provides a highly efficient way to manage limited buffer memory.
  • Mode-Seeking over Mean-Seeking: For autoregressive construction solvers, it doesn't matter if the entire probability distribution matches perfectly; what matters is that the best choice remains the best choice. Reverse KLD is mathematically tailored for this exact requirement, preventing catastrophic degradation in route lengths.

Key Results

  • Across five randomized task sequences, LLR-BC achieved an Average Performance (AP) score of 0.0042 for CVRP and 0.0034 for TSP, vastly outperforming standard fine-tuning (>0.023 for CVRP, >0.014 for TSP) and other lifelong learning baselines like EWC.
  • LLR-BC demonstrated exceptional stability, keeping Average Forgetting (AF) remarkably low (0.7 for CVRP, 0.8 for TSP) while maintaining the best plasticity (APl) among all methods.
Performance metrics and forgetting curves
  • On unseen real-world benchmarks (CVRPLIB/TSPLIB), LLR-BC achieved the best zero-shot generalization performance (e.g., a score of 7.88 on CVRPLIB compared to 27.38 for the next best lifelong baseline, Feng).

Limitations and Future Work

  • Fixed Sampling Size Limitations: LLR-BC uses a fixed number of sampled experiences ($|\mathcal{E}|$). When task scales differ drastically (e.g., scale 20 vs scale 100), a fixed sample size can cause old experiences to dominate small-scale tasks or new experiences to dominate large-scale tasks within a training batch.
  • Cross-Variant Learning: The current framework focuses on cross-distribution and cross-scale settings within the same problem type. Extending lifelong learning across entirely different problem variants (e.g., transitioning from TSP to CVRP) remains an open challenge for future research.

Summary updated

Abstract

Recent neural solvers have demonstrated promising performance in learning to solve routing problems. However, existing studies are primarily based on one-off training on one or a set of predefined problem distributions and scales, i.e., tasks. When a new task arises, they typically rely on either zero-shot generalization, which may be poor due to the discrepancies between the new task and the training task(s), or fine-tuning the pretrained solver on the new task, which possibly leads to catastrophic forgetting of knowledge acquired from previous tasks. This paper explores a novel lifelong learning paradigm for neural VRP solvers, where multiple tasks with diverse distributions and scales arise sequentially over time. Solvers are required to effectively and efficiently learn to solve new tasks while maintaining their performance on previously learned tasks. Consequently, a novel framework called Lifelong Learning Router with Behavior Consolidation (LLR-BC) is proposed. LLR-BC consolidates prior knowledge effectively by aligning behaviors of the solver trained on a new task with the buffered ones in a decision-seeking way. To encourage more focus on crucial experiences, LLR-BC assigns greater consolidated weights to decisions with lower confidence. Extensive experiments on capacitated vehicle routing problems and traveling salesman problems demonstrate LLR-BC's effectiveness in training high-performance neural solvers in a lifelong learning setting, addressing the catastrophic forgetting issue, maintaining their plasticity, and improving zero-shot generalization ability.
BibTeX
@inproceedings{pei2026lifelong,
  author = {Jiyuan Pei and Yi Mei and Jialin Liu and Mengjie Zhang and Xin Yao},
  title = {{Lifelong Learning with Behavior Consolidation for Vehicle Routing}},
  booktitle = {International Conference on Learning Representations},
  year = {2026},
  url = {https://openreview.net/forum?id=sEdGLzgf6s},
}
Figure