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

• URL: http://arxiv.org/abs/2411.17080v1
• Date: Tue, 26 Nov 2024 03:41:01 GMT
• Title: DeepMDV: Learning Global Matching for Multi-depot Vehicle Routing Problems
• Authors: Saeed Nasehi, Farhana Choudhury, Egemen Tanin,
• Abstract summary: In recent years, companies have adopted the strategy of adding more depots. The presence of multiple depots introduces additional complexities, making existing VRP solutions suboptimal. Traditional methods for solving the MDVRP often require significant time, making them unsuitable for large-scale instances. We propose a novel solution for MDVRP using an attention mechanism, featuring a decoder with two key layers.
• Score: 1.0104586293349587
• License:
• Abstract: Due to the substantial rise in online retail and e-commerce in recent years, the demand for efficient and fast solutions to Vehicle Routing Problems (VRP) has become critical. To manage the increasing demand, companies have adopted the strategy of adding more depots. However, the presence of multiple depots introduces additional complexities, making existing VRP solutions suboptimal for addressing the Multi-depot Vehicle Routing Problem (MDVRP). Traditional methods for solving the MDVRP often require significant computation time, making them unsuitable for large-scale instances. Additionally, existing learning-based solutions for the MDVRP struggle with generalizability and fail to deliver high-quality results for scenarios involving a large number of customers. In this paper, we propose a novel solution for MDVRP. Our approach employs an attention mechanism, featuring a decoder with two key layers: one layer to consider the states of all vehicles and learn to select the most suitable vehicle based on the proximity of unassigned customers, and another layer to focus on assigning a customer to the selected vehicle. This approach delivers high-quality solutions for large-scale MDVRP instances and demonstrates remarkable generalizability across varying numbers of customers and depots. Its adaptability and performance make it a practical and deployable solution for real-world logistics challenges.

Related papers

• 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)
• 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)
• 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)
• 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.