DeepMDV: Global Spatial Matching for Multi-depot Vehicle Routing Problems

• URL: http://arxiv.org/abs/2411.17080v3
• Date: Fri, 08 Aug 2025 01:27:26 GMT
• Title: DeepMDV: Global Spatial Matching for Multi-depot Vehicle Routing Problems
• Authors: Saeed Nasehi, Farhana Choudhury, Egemen Tanin, Majid Sarvi,
• Abstract summary: Rapid growth of online retail and e-commerce has made effective and efficient Vehicle Routing Problem (VRP) solutions essential.<n>To meet rising demand, companies are adding more depots, which changes the VRP problem to a complex optimization task of Multi-Depot VRP.<n>We propose a novel approach to solve MDVRP addressing these interdependencies, hence achieving more effective results.
• Score: 2.218667838700643
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The rapid growth of online retail and e-commerce has made effective and efficient Vehicle Routing Problem (VRP) solutions essential. To meet rising demand, companies are adding more depots, which changes the VRP problem to a complex optimization task of Multi-Depot VRP (MDVRP) where the routing decisions of vehicles from multiple depots are highly interdependent. The complexities render traditional VRP methods suboptimal and non-scalable for the MDVRP. In this paper, we propose a novel approach to solve MDVRP addressing these interdependencies, hence achieving more effective results. The key idea is, the MDVRP can be broken down into two core spatial tasks: assigning customers to depots and optimizing the sequence of customer visits. We adopt task-decoupling approach and propose a two-stage framework that is scalable: (i) an interdependent partitioning module that embeds spatial and tour context directly into the representation space to globally match customers to depots and assign them to tours; and (ii) an independent routing module that determines the optimal visit sequence within each tour. Extensive experiments on both synthetic and real-world datasets demonstrate that our method outperforms all baselines across varying problem sizes, including the adaptations of learning-based solutions for single-depot VRP. Its adaptability and performance make it a practical and readily deployable solution for real-world logistics challenges.

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-Agent Pointer Transformer: Seq-to-Seq Reinforcement Learning for Multi-Vehicle Dynamic Pickup-Delivery Problems [17.3780399150554]
  This paper proposes an end-to-end centralized decision-making framework based on sequence-to-sequence, named Multi-Agent Pointer Transformer (MAPT)<n>MAPT significantly outperforms existing baseline methods in terms of performance and substantial computational time advantages compared to classical operations research methods.
  arXiv  Detail & Related papers  (2025-11-21T17:32:10Z)
• 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)
• 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)
• 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)
• Rich Vehicle Routing Problem in Disaster Management enabling Temporally-causal Transhipments across Multi-Modal Transportation Network [1.1470070927586018]
  A rich vehicle routing problem is considered, allowing multiple trips of heterogeneous vehicles stationed at geographically distributed vehicle depots having access to different modes of transportation.<n>The problem arises from the real-world requirement of optimizing the disaster response time by minimizing the makespan of vehicular routes.<n>The superiority of the proposed cascaded minimization approach is demonstrated through our developed Mixed-Integer Linear Programming formulation.
  arXiv  Detail & Related papers  (2025-09-16T16:37:18Z)
• Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [55.78505925402658]
  Vehicle Routing Problems (VRP) are an extension of the Traveling Salesperson Problem and are a fundamental NP-hard challenge in Evolutionary optimization. We introduce a novel optimization framework that uses a reinforcement learning agent - trained on prior instances - to quickly generate initial solutions, which are then further optimized by genetic algorithms. For example, EARLI handles vehicle routing with 500 locations within 1s, 10x faster than current solvers for the same solution quality, enabling applications like real-time and interactive routing.
  arXiv  Detail & Related papers  (2025-04-08T15:21:01Z)
• Agent-Oriented Planning in Multi-Agent Systems [54.429028104022066]
  We propose AOP, a novel framework for agent-oriented planning in multi-agent systems. In this study, we identify three critical design principles of agent-oriented planning, including solvability, completeness, and non-redundancy. Extensive experiments demonstrate the advancement of AOP in solving real-world problems compared to both single-agent systems and existing planning strategies for multi-agent systems.
  arXiv  Detail & Related papers  (2024-10-03T04:07:51Z)
• Deep Reinforcement Learning for Traveling Purchaser Problems [63.37136587778153]
  The traveling purchaser problem (TPP) is an important optimization problem with broad applications.<n>We propose a novel approach based on deep reinforcement learning (DRL), which addresses route construction and purchase planning separately.<n> Experiments on various synthetic TPP instances and the TPPLIB benchmark demonstrate that our DRL-based approach can significantly outperform well-established TPPs.
  arXiv  Detail & Related papers  (2024-04-03T05:32:10Z)
• Multimodal Instruction Tuning with Conditional Mixture of LoRA [54.65520214291653]
  This paper introduces a novel approach that integrates multimodal instruction tuning with Low-Rank Adaption (LoRA) It innovates upon LoRA by dynamically constructing low-rank adaptation matrices tailored to the unique demands of each input instance. Experimental results on various multimodal evaluation datasets indicate that MixLoRA not only outperforms the conventional LoRA with the same or even higher ranks.
  arXiv  Detail & Related papers  (2024-02-24T20:15:31Z)
• Deep Reinforcement Learning for Multi-Truck Vehicle Routing Problems with Multi-Leg Demand Routes [0.9423257767158634]
  We develop new extensions to existing encoder-decoder attention models which allow them to handle multiple trucks and multi-leg routing requirements. Our models have the advantage that they can be trained for a small number of trucks and nodes, and then embedded into a large supply chain to yield solutions for larger numbers of trucks and nodes.
  arXiv  Detail & Related papers  (2024-01-08T21:13:07Z)
• TOP-Former: A Multi-Agent Transformer Approach for the Team Orienteering Problem [47.40841984849682]
  Route planning for a fleet of vehicles is an important task in applications such as package delivery, surveillance, or transportation. We introduce TOP-Former, a multi-agent route planning neural network designed to efficiently and accurately solve the Team Orienteering Problem.
  arXiv  Detail & Related papers  (2023-11-30T16:10:35Z)
• Safe Model-Based Multi-Agent Mean-Field Reinforcement Learning [48.667697255912614]
  Mean-field reinforcement learning addresses the policy of a representative agent interacting with the infinite population of identical agents. We propose Safe-M$3$-UCRL, the first model-based mean-field reinforcement learning algorithm that attains safe policies even in the case of unknown transitions. Our algorithm effectively meets the demand in critical areas while ensuring service accessibility in regions with low demand.
  arXiv  Detail & Related papers  (2023-06-29T15:57:07Z)
• Flexible Job Shop Scheduling via Dual Attention Network Based Reinforcement Learning [73.19312285906891]
  In flexible job shop scheduling problem (FJSP), operations can be processed on multiple machines, leading to intricate relationships between operations and machines. Recent works have employed deep reinforcement learning (DRL) to learn priority dispatching rules (PDRs) for solving FJSP. This paper presents a novel end-to-end learning framework that weds the merits of self-attention models for deep feature extraction and DRL for scalable decision-making.
  arXiv  Detail & Related papers  (2023-05-09T01:35:48Z)
• Modeling routing problems in QUBO with application to ride-hailing [0.0]
  We focus on one such routing problem, the Ride Pooling Problem (RPP), where multiple customers can request on-demand pickups and drop-offs from shared vehicles within a fleet. The task is to optimally pool customer requests using the limited set of vehicles, akin to a small-scale flexible bus route.
  arXiv  Detail & Related papers  (2022-12-09T14:55:34Z)
• 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)
• Off-line approximate dynamic programming for the vehicle routing problem with stochastic customers and demands via decentralized decision-making [0.0]
  This paper studies a variant of the vehicle routing problem (VRP) where both customer locations and demands are uncertain. The objective is to maximize the served demands while fulfilling vehicle capacities and time restrictions. We develop a Q-learning algorithm featuring state-of-the-art acceleration techniques such as Replay Memory and Double Q Network.
  arXiv  Detail & Related papers  (2021-09-21T14:28:09Z)
• Value Function is All You Need: A Unified Learning Framework for Ride Hailing Platforms [57.21078336887961]
  Large ride-hailing platforms, such as DiDi, Uber and Lyft, connect tens of thousands of vehicles in a city to millions of ride demands throughout the day. We propose a unified value-based dynamic learning framework (V1D3) for tackling both tasks.
  arXiv  Detail & Related papers  (2021-05-18T19:22:24Z)
• Flatland Competition 2020: MAPF and MARL for Efficient Train Coordination on a Grid World [49.80905654161763]
  The Flatland competition aimed at finding novel approaches to solve the vehicle re-scheduling problem (VRSP) The VRSP is concerned with scheduling trips in traffic networks and the re-scheduling of vehicles when disruptions occur. The ever-growing complexity of modern railway networks makes dynamic real-time scheduling of traffic virtually impossible.
  arXiv  Detail & Related papers  (2021-03-30T17:13:29Z)
• 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)
• A Three-Stage Algorithm for the Large Scale Dynamic Vehicle Routing Problem with an Industry 4.0 Approach [3.6317403990273402]
  Industry 4.0 is a concept which concentrates on mobility and real-time integration. The aim of this research is to solve large-scale DVRP (LSDVRP)
  arXiv  Detail & Related papers  (2020-08-26T10:39:36Z)
• Learning What to Defer for Maximum Independent Sets [84.00112106334655]
  We propose a novel DRL scheme, coined learning what to defer (LwD), where the agent adaptively shrinks or stretch the number of stages by learning to distribute the element-wise decisions of the solution at each stage. We apply the proposed framework to the maximum independent set (MIS) problem, and demonstrate its significant improvement over the current state-of-the-art DRL scheme.
  arXiv  Detail & Related papers  (2020-06-17T02:19:31Z)
• A Quantum Annealing Approach for Dynamic Multi-Depot Capacitated Vehicle Routing Problem [5.057312718525522]
  This paper presents a quantum computing algorithm that works on the principle of Adiabatic Quantum Computation (AQC) It has shown significant computational advantages in solving optimization problems such as vehicle routing problems (VRP) when compared to classical algorithms. This is an NP-hard optimization problem with real-world applications in the fields of transportation, logistics, and supply chain management.
  arXiv  Detail & Related papers  (2020-05-26T01:47:39Z)

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.