An End-to-End Learning Approach for Solving Capacitated Location-Routing Problems

• URL: http://arxiv.org/abs/2511.02525v1
• Date: Tue, 04 Nov 2025 12:23:17 GMT
• Title: An End-to-End Learning Approach for Solving Capacitated Location-Routing Problems
• Authors: Changhao Miao, Yuntian Zhang, Tongyu Wu, Fang Deng, Chen Chen,
• Abstract summary: 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.
• Score: 8.616895584914579
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The capacitated location-routing problems (CLRPs) are classical problems in combinatorial optimization, which require simultaneously making location and routing decisions. In CLRPs, the complex constraints and the intricate relationships between various decisions make the problem challenging to solve. With the emergence of deep reinforcement learning (DRL), it has been extensively applied to address the vehicle routing problem and its variants, while the research related to CLRPs still needs to be explored. In this paper, we propose the DRL with heterogeneous query (DRLHQ) to solve CLRP and open CLRP (OCLRP), respectively. We are the first to propose an end-to-end learning approach for CLRPs, following the encoder-decoder structure. In particular, we reformulate the CLRPs as a markov decision process tailored to various decisions, a general modeling framework that can be adapted to other DRL-based methods. To better handle the interdependency across location and routing decisions, we also introduce a novel heterogeneous querying attention mechanism designed to adapt dynamically to various decision-making stages. Experimental results on both synthetic and benchmark datasets demonstrate superior solution quality and better generalization performance of our proposed approach over representative traditional and DRL-based baselines in solving both CLRP and OCLRP.

Related papers

• Deep Reinforcement Learning for Solving the Fleet Size and Mix Vehicle Routing Problem [8.127336287332783]
  The Fleet Size and Mix Vehicle Routing Problem (FSMVRP) is a prominent variant of the Vehicle Routing Problem (VRP)<n>We propose a deep reinforcement learning (DRL)-based approach for solving FSMVRP, capable of generating near-optimal solutions within a few seconds.<n>Our method exhibits notable advantages in terms of computational efficiency and scalability, particularly in large-scale and time-constrained scenarios.
  arXiv  Detail & Related papers  (2025-12-30T14:26:33Z)
• Multi-Task Vehicle Routing Solver via Mixture of Specialized Experts under State-Decomposable MDP [57.28979643999352]
  We propose a framework that enables unified solvers to perceive the shared-component nature across VRP variants.<n>We introduce a State-Decomposable MDP (SDMDP) that reformulates VRPs by expressing the state space as the Cartesian product of basis state spaces.<n>A Latent Space-based SDMDP extension is developed by incorporating both the optimal basis policies and a learnable mixture function.
  arXiv  Detail & Related papers  (2025-10-24T13:31:31Z)
• Preference Optimization for Combinatorial Optimization Problems [54.87466279363487]
  Reinforcement Learning (RL) has emerged as a powerful tool for neural optimization, enabling models learns that solve complex problems without requiring expert knowledge.<n>Despite significant progress, existing RL approaches face challenges such as diminishing reward signals and inefficient exploration in vast action spaces.<n>We propose Preference Optimization, a novel method that transforms quantitative reward signals into qualitative preference signals via statistical comparison modeling.
  arXiv  Detail & Related papers  (2025-05-13T16:47:00Z)
• CAMP: Collaborative Attention Model with Profiles for Vehicle Routing Problems [15.136899433821894]
  The profiled vehicle routing problem (PVRP) is a generalization of the heterogeneous capacitated vehicle routing problem (HCVRP)<n>We propose a novel approach that learns efficient solvers for PVRP using multi-agent reinforcement learning.
  arXiv  Detail & Related papers  (2025-01-06T12:37:56Z)
• Design Optimization of NOMA Aided Multi-STAR-RIS for Indoor Environments: A Convex Approximation Imitated Reinforcement Learning Approach [51.63921041249406]
  Non-orthogonal multiple access (NOMA) enables multiple users to share the same frequency band, and simultaneously transmitting and reflecting reconfigurable intelligent surface (STAR-RIS) deploying STAR-RIS indoors presents challenges in interference mitigation, power consumption, and real-time configuration. A novel network architecture utilizing multiple access points (APs), STAR-RISs, and NOMA is proposed for indoor communication.
  arXiv  Detail & Related papers  (2024-06-19T07:17:04Z)
• Leveraging Constraint Programming in a Deep Learning Approach for Dynamically Solving the Flexible Job-Shop Scheduling Problem [1.3927943269211593]
  This paper aims to integrate constraint programming (CP) within a deep learning (DL) based methodology, leveraging the benefits of both. We introduce a method that involves training a DL model using optimal solutions generated by CP, ensuring the model learns from high-quality data. Our hybrid approach has been extensively tested on three public FJSSP benchmarks, demonstrating superior performance over five state-of-the-art DRL approaches.
  arXiv  Detail & Related papers  (2024-03-14T10:16:57Z)
• 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)
• MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion Control in Real Networks [63.24965775030673]
  We propose a novel Reinforcement Learning (RL) approach to design generic Congestion Control (CC) algorithms. Our solution, MARLIN, uses the Soft Actor-Critic algorithm to maximize both entropy and return. We trained MARLIN on a real network with varying background traffic patterns to overcome the sim-to-real mismatch.
  arXiv  Detail & Related papers  (2023-02-02T18:27:20Z)
• GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyond [101.5329678997916]
  We study sample efficient reinforcement learning (RL) under the general framework of interactive decision making. We propose a novel complexity measure, generalized eluder coefficient (GEC), which characterizes the fundamental tradeoff between exploration and exploitation. We show that RL problems with low GEC form a remarkably rich class, which subsumes low Bellman eluder dimension problems, bilinear class, low witness rank problems, PO-bilinear class, and generalized regular PSR.
  arXiv  Detail & Related papers  (2022-11-03T16:42:40Z)
• Learning Collaborative Policies to Solve NP-hard Routing Problems [13.13675711285772]
  This paper proposes a novel hierarchical problem-solving strategy called learning collaborative policies (LCP) It can effectively find the near-optimum solution using two iterative DRL policies: the seeder and reviser. Extensive experiments demonstrate that the proposed two-policies collaboration scheme improves over single-policy DRL framework on various NP-hard routing problems.
  arXiv  Detail & Related papers  (2021-10-26T19:46:21Z)
• Hierarchical Deep CNN Feature Set-Based Representation Learning for Robust Cross-Resolution Face Recognition [59.29808528182607]
  Cross-resolution face recognition (CRFR) is important in intelligent surveillance and biometric forensics. Existing shallow learning-based and deep learning-based methods focus on mapping the HR-LR face pairs into a joint feature space. In this study, we desire to fully exploit the multi-level deep convolutional neural network (CNN) feature set for robust CRFR.
  arXiv  Detail & Related papers  (2021-03-25T14:03:42Z)
• Reinforcement Learning for Adaptive Mesh Refinement [63.7867809197671]
  We propose a novel formulation of AMR as a Markov decision process and apply deep reinforcement learning to train refinement policies directly from simulation. The model sizes of these policy architectures are independent of the mesh size and hence scale to arbitrarily large and complex simulations.
  arXiv  Detail & Related papers  (2021-03-01T22:55:48Z)

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.