Fast Approximate Solutions using Reinforcement Learning for Dynamic Capacitated Vehicle Routing with Time Windows

2021-02-24 · Nazneen N Sultana, Vinita Baniwal, Ansuma Basumatary, Piyush Mittal, Supratim Ghosh, Harshad Khadilkar

This paper develops an inherently parallelised, fast, approximate learning-based solution to the generic class of Capacitated Vehicle Routing Problems with Time Windows and Dynamic Routing (CVRP-TWDR). Considering vehicles in a fleet as decentralised agents, we postulate that using reinforcement learning (RL) based adaptation is a key enabler for real-time route formation in a dynamic environment. The methodology allows each agent (vehicle) to independently evaluate the value of serving each customer, and uses a centralised allocation heuristic to finalise the allocations based on the generated values. We show that the solutions produced by this method are significantly faster than exact formulations and state-of-the-art meta-heuristics, while being reasonably close to optimal in terms of solution quality. We describe experiments in both the static case (when all customer demands and time windows are known in advance) as well as the dynamic case (where customers can pop up at any time during execution). The results with a single trained model on large, out-of-distribution test data demonstrate the scalability and flexibility of the proposed approach.

📄 PDF Abstract BibTeX arXiv:2102.12088

Code (0)

등록된 구현이 없습니다.

Tasks

Reinforcement Learning (RL)

Using Reinforcement Learning for the Three-Dimensional Loading Capacitated Vehicle Routing Problem

2023-07-22 · Stefan Schoepf, Stephen Mak, Julian Senoner, Liming Xu 외

Heavy goods vehicles are vital backbones of the supply chain delivery system but also contribute significantly to carbon emissions with only 60% loading efficiency in the United Kingdom. Collaborative vehicle routing has…

reinforcement-learning Reinforcement Learning

Learning to Deliver: a Foundation Model for the Montreal Capacitated Vehicle Routing Problem

2024-02-28 · Samuel J. K. Chin, Matthias Winkenbach, Akash Srivastava

In this paper, we present the Foundation Model for the Montreal Capacitated Vehicle Routing Problem (FM-MCVRP), a novel Deep Learning (DL) model that approximates high-quality solutions to a variant of the Capacitated Ve…

Language Modelling Large Language Model

Hybridising Reinforcement Learning and Heuristics for Hierarchical Directed Arc Routing Problems

2025-01-01 · Van Quang Nguyen, Quoc Chuong Nguyen, Thu Huong Dang, Truong-Son Hy

The Hierarchical Directed Capacitated Arc Routing Problem (HDCARP) is an extension of the Capacitated Arc Routing Problem (CARP), where the arcs of a graph are divided into classes based on their priority. The traversal …

ARC reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Diversity Optimization for Travelling Salesman Problem via Deep Reinforcement Learning

2025-01-01 · Qi Li, Zhiguang Cao, Yining Ma, Yaoxin Wu 외

Existing neural methods for the Travelling Salesman Problem (TSP) mostly aim at finding a single optimal solution. To discover diverse yet high-quality solutions for Multi-Solution TSP (MSTSP), we propose a novel deep re…

Decoder Deep Reinforcement Learning Diversity

Deep Reinforcement Learning for Routing a Heterogeneous Fleet of Vehicles

2019-12-06 · Jose Manuel Vera, Andres G. Abad

Motivated by the promising advances of deep-reinforcement learning (DRL) applied to cooperative multi-agent systems we propose a model and learning procedure to solve the Capacitated Multi-Vehicle Routing Problem (CMVRP)…

Deep Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)