Lifelong Learner: Discovering Versatile Neural Solvers for Vehicle Routing Problems

• URL: http://arxiv.org/abs/2508.11679v1
• Date: Fri, 08 Aug 2025 16:54:43 GMT
• Title: Lifelong Learner: Discovering Versatile Neural Solvers for Vehicle Routing Problems
• Abstract summary: This paper presents a novel lifelong learning framework that incrementally trains a neural solver to manage VRPs in distinct contexts.<n>The inter-context self-attention mechanism is proposed within LL to transfer the knowledge obtained from solving preceding VRPs into the succeeding ones.<n>Our LL is capable of discovering effective policies for tackling generic VRPs in varying contexts, which outperforms other neural solvers and achieves the best performance for most VRPs.
• Score: 29.57042055083142
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Deep learning has been extensively explored to solve vehicle routing problems (VRPs), which yields a range of data-driven neural solvers with promising outcomes. However, most neural solvers are trained to tackle VRP instances in a relatively monotonous context, e.g., simplifying VRPs by using Euclidean distance between nodes and adhering to a single problem size, which harms their off-the-shelf application in different scenarios. To enhance their versatility, this paper presents a novel lifelong learning framework that incrementally trains a neural solver to manage VRPs in distinct contexts. Specifically, we propose a lifelong learner (LL), exploiting a Transformer network as the backbone, to solve a series of VRPs. The inter-context self-attention mechanism is proposed within LL to transfer the knowledge obtained from solving preceding VRPs into the succeeding ones. On top of that, we develop a dynamic context scheduler (DCS), employing the cross-context experience replay to further facilitate LL looking back on the attained policies of solving preceding VRPs. Extensive results on synthetic and benchmark instances (problem sizes up to 18k) show that our LL is capable of discovering effective policies for tackling generic VRPs in varying contexts, which outperforms other neural solvers and achieves the best performance for most VRPs.

Related papers

• Reinforcement Learning Enhanced LLM Agents for Complex Vehicle Routing Problems [22.538946344456857]
  Vehicle Routing Problems (VRPs) are fundamental optimization problems with widespread applications in various scenarios.<n>We propose Reinforcement Learning Enhanced LLMAgents(RLEA), a multi-agent framework designed to automate the modeling of complex VRPs.
  arXiv  Detail & Related papers  (2026-09-01T07:56:15Z)
• Learning with Foresight: Enhancing Neural Routing Policy via Multi-Node Lookahead Prediction [53.32115440294569]
  Multi-node Lookahead Prediction (MnLP) is a novel training strategy that extends the supervised learning paradigm to predict multiple future nodes simultaneously.<n>We incorporate myopic causal and discardable MnLP modules that operate exclusively during training, facilitating contextual models to anticipate multi-step decisions.<n> Experimentally, MnLP outperforms existing training methods, improving the generalization capability of neural policies across various problem sizes, distributions, and real-world benchmarks.
  arXiv  Detail & Related papers  (2026-05-19T15:19:59Z)
• A Unified Knowledge Embedded Reinforcement Learning-based Framework for Generalized Capacitated Vehicle Routing Problems [8.968947174938942]
  Capacitated Vehicle Routing Problem (CVRP) is a fundamental NP-hard problem with broad applications in logistics and transportation.<n>Recent reinforcement learning approaches have shown promise in optimization, yet they rely on end-to-end learning and lack explicit problem-solving knowledge.<n>We propose a knowledge-embedded framework inspired by the Route-First Cluster-Seconds problem.
  arXiv  Detail & Related papers  (2026-05-14T06:05:22Z)
• TACO: Think-Answer Consistency for Optimized Long-Chain Reasoning and Efficient Data Learning via Reinforcement Learning in LVLMs [50.820065021136024]
  DeepSeek R1 has significantly advanced complex reasoning for large language models (LLMs)<n>Recent methods have attempted to replicate R1's reasoning capabilities in multimodal settings.<n>We propose TACO, a novel reinforcement learning algorithm for visual reasoning.
  arXiv  Detail & Related papers  (2025-05-27T06:30:48Z)
• Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [53.75036695728983]
  Vehicle Routing Problems (VRP) are a fundamental NP-hard challenge in Evolutionary optimization.<n>We introduce an optimization framework where a reinforcement learning agent is trained on prior instances and quickly generates initial solutions.<n>This framework consistently outperforms current state-of-the-art solvers across various time budgets.
  arXiv  Detail & Related papers  (2025-04-08T15:21:01Z)
• Joint Admission Control and Resource Allocation of Virtual Network Embedding via Hierarchical Deep Reinforcement Learning [69.00997996453842]
  We propose a deep Reinforcement Learning approach to learn a joint Admission Control and Resource Allocation policy for virtual network embedding. We show that HRL-ACRA outperforms state-of-the-art baselines in terms of both the acceptance ratio and long-term average revenue.
  arXiv  Detail & Related papers  (2024-06-25T07:42:30Z)
• Decentralized Learning Strategies for Estimation Error Minimization with Graph Neural Networks [94.2860766709971]
  We address the challenge of sampling and remote estimation for autoregressive Markovian processes in a wireless network with statistically-identical agents.<n>Our goal is to minimize time-average estimation error and/or age of information with decentralized scalable sampling and transmission policies.
  arXiv  Detail & Related papers  (2024-04-04T06:24:11Z)
• Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policy [24.91781032046481]
  Many neural construction methods for Vehicle Routing Problems(VRPs) focus on synthetic problem instances with specified node distributions and limited scales. We design an auxiliary policy that learns from the local transferable topological features, named local policy, and integrate it with a typical construction policy to form an ensemble policy. With joint training, the aggregated policies perform cooperatively and complementarily to boost generalization.
  arXiv  Detail & Related papers  (2023-08-27T13:22:50Z)
• Towards Omni-generalizable Neural Methods for Vehicle Routing Problems [14.210085924625705]
  This paper studies a challenging yet realistic setting, which considers generalization across both size and distribution in VRPs. We propose a generic meta-learning framework, which enables effective training of an model with the capability of fast adaptation to new tasks during inference.
  arXiv  Detail & Related papers  (2023-05-31T06:14:34Z)
• Learning to Solve Soft-Constrained Vehicle Routing Problems with Lagrangian Relaxation [0.4014524824655105]
  Vehicle Routing Problems (VRPs) in real-world applications often come with various constraints. We propose a Reinforcement Learning based method to solve soft-constrained VRPs. We apply the method on three common types of VRPs, the Travelling Salesman Problem with Time Windows (TSPTW), the Capacitated VRP (CVRP) and the Capacitated VRP with Time Windows (CVRPTW)
  arXiv  Detail & Related papers  (2022-07-20T12:51:06Z)
• Learning Dynamics and Generalization in Reinforcement Learning [59.530058000689884]
  We show theoretically that temporal difference learning encourages agents to fit non-smooth components of the value function early in training. We show that neural networks trained using temporal difference algorithms on dense reward tasks exhibit weaker generalization between states than randomly networks and gradient networks trained with policy methods.
  arXiv  Detail & Related papers  (2022-06-05T08:49:16Z)
• Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
  We propose Deep Policy Dynamic Programming (D PDP) to combine the strengths of learned neurals with those of dynamic programming algorithms. D PDP prioritizes and restricts the DP state space using a policy derived from a deep neural network, which is trained to predict edges from example solutions. We evaluate our framework on the travelling salesman problem (TSP) and the vehicle routing problem (VRP) and show that the neural policy improves the performance of (restricted) DP algorithms.
  arXiv  Detail & Related papers  (2021-02-23T15:33:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.