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

• URL: http://arxiv.org/abs/2605.14416v1
• Date: Thu, 14 May 2026 06:05:22 GMT
• Title: A Unified Knowledge Embedded Reinforcement Learning-based Framework for Generalized Capacitated Vehicle Routing Problems
• Abstract summary: 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.
• Score: 8.968947174938942
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Capacitated Vehicle Routing Problem (CVRP) is a fundamental NP-hard problem with broad applications in logistics and transportation. Real-world CVRPs often involve diverse objectives and complex constraints, such as time windows or backhaul requirements, motivating the development of a unified solution framework. Recent reinforcement learning (RL) approaches have shown promise in combinatorial optimization, yet they rely on end-to-end learning and lack explicit problem-solving knowledge, limiting solution quality. In this paper, we propose a knowledge-embedded framework inspired by the Route-First Cluster-Second heuristics. It incorporates knowledge at two levels: (1) decomposing CVRPs into the route-first and cluster-second subproblems, and (2) leveraging dynamic programming to solve the second subproblem, whose results guide the RL-based constructive solver to solve the first problem. To mitigate partial observability caused by problem decomposition, we introduce a unified history-enhanced context processing module. Extensive experiments show that this framework achieves superior solution quality compared with state-of-the-art learning-based methods, with a smaller gap to classical heuristics, demonstrating strong generalization across diverse CVRP variants.

Related papers

• Enhancing Cross-Problem Vehicle Routing via Federated Learning [26.83758750752992]
  Vehicle routing problems (VRPs) constitute a core optimization challenge in modern logistics and supply chain management.<n>This paper offers an innovative "Multi-problem Pre-train, then Single-problem Fine-tune" framework with Federated Learning (MPSF-FL)
  arXiv  Detail & Related papers  (2026-04-12T13:58:47Z)
• Vehicle-as-Prompt: A Unified Deep Reinforcement Learning Framework for Heterogeneous Fleet Vehicle Routing Problem [12.469727665338603]
  Heterogeneous Fleet Vehicle Routing Problem (HFVRP) involves heterogeneous fixed costs, variable travel costs, and capacity constraints.<n>We develop a unified Deep Reinforcement Learning framework capable of solving the problem across various variant settings.
  arXiv  Detail & Related papers  (2026-04-06T21:48:52Z)
• Multi-Agent DRL for V2X Resource Allocation: Disentangling Challenges and Benchmarking Solutions [51.22818149833102]
  Multi-agent reinforcement learning (MARL) has emerged as a promising approach for radio resource allocation in vehicle-to-everything (C-V2X) networks.<n>However, the multifaceted challenges inherent to MARL are often intertwined, making it difficult to understand their individual impact on performance in vehicular environments.<n>We bridge this gap by formulating C-V2X RRA as a sequence of multi-agent interference games with progressively increasing complexity.
  arXiv  Detail & Related papers  (2026-02-18T14:46:56Z)
• Search-R2: Enhancing Search-Integrated Reasoning via Actor-Refiner Collaboration [49.9937230730202]
  We propose Search-R2, a novel Actor-Refiner collaboration framework that enhances reasoning through targeted intervention.<n>Our approach decomposes the generation process into an Actor, which produces initial reasoning trajectories.<n>We show that Search-R2 consistently outperforms strong RAG and RL-based baselines across model scales.
  arXiv  Detail & Related papers  (2026-02-03T15:32:09Z)
• An End-to-End Learning Approach for Solving Capacitated Location-Routing Problems [8.616895584914579]
  We propose an end-to-end learning approach for the capacitated location-routing problems (CLRPs)<n>In particular, we reformulate the CLRPs as a markov decision process tailored to various decisions.<n>We also introduce a novel heterogeneous querying attention mechanism designed to adapt dynamically to various decision-making stages.
  arXiv  Detail & Related papers  (2025-11-04T12:23:17Z)
• An Agentic Framework with LLMs for Solving Complex Vehicle Routing Problems [66.60904891478687]
  We propose an Agentic Framework with LLMs (AFL) for solving complex vehicle routing problems.<n>AFL directly extracts knowledge from raw inputs and enables self-contained code generation.<n>We show that AFL substantially outperforms existing LLM-based baselines in both code reliability and solution feasibility.
  arXiv  Detail & Related papers  (2025-10-19T03:59:25Z)
• Boost, Disentangle, and Customize: A Robust System2-to-System1 Pipeline for Code Generation [58.799397354312596]
  Large language models (LLMs) have demonstrated remarkable capabilities in various domains, particularly in system 1 tasks.<n>Recent research on System2-to-System1 methods surge, exploring the System 2 reasoning knowledge via inference-time computation.<n>In this paper, we focus on code generation, which is a representative System 2 task, and identify two primary challenges.
  arXiv  Detail & Related papers  (2025-02-18T03:20:50Z)
• An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem [67.92544792239086]
  We introduce an NN-based solver to significantly narrow the gap with advanced metaheuristics. First, we propose direction-aware facilitating attention model (DaAM) to incorporate directionality into the embedding process. Second, we design a supervised reinforcement learning scheme that involves supervised pre-training to establish a robust initial policy.
  arXiv  Detail & Related papers  (2024-03-11T02:17:42Z)
• Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHF [82.73541793388]
  We introduce the first principled algorithmic framework for solving bilevel RL problems through the lens of penalty formulation. We provide theoretical studies of the problem landscape and its penalty-based gradient (policy) algorithms. We demonstrate the effectiveness of our algorithms via simulations in the Stackelberg Markov game, RL from human feedback and incentive design.
  arXiv  Detail & Related papers  (2024-02-10T04:54:15Z)
• 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)
• Solving the vehicle routing problem with deep reinforcement learning [0.0]
  This paper focuses on the application of RL for the Vehicle Routing Problem (VRP), a famous problem that belongs to the class of NP-Hard problems. In a second phase, the neural architecture behind the Actor and Critic has been established, choosing to adopt a neural architecture based on the Convolutional neural networks. Experiments performed on a wide range of instances show that the algorithm has good generalization capabilities and can reach good solutions in a short time.
  arXiv  Detail & Related papers  (2022-07-30T12:34:26Z)

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.