Multi-Vehicle Routing Problems with Soft Time Windows: A Multi-Agent Reinforcement Learning Approach

2020-02-13 · Ke Zhang, Meng Li, Zhengchao Zhang, Xi Lin, Fang He

Multi-vehicle routing problem with soft time windows (MVRPSTW) is an indispensable constituent in urban logistics distribution systems. Over the past decade, numerous methods for MVRPSTW have been proposed, but most are based on heuristic rules that require a large amount of computation time. With the current rapid increase of logistics demands, traditional methods incur the dilemma between computational efficiency and solution quality. To efficiently solve the problem, we propose a novel reinforcement learning algorithm called the Multi-Agent Attention Model that can solve routing problem instantly benefit from lengthy offline training. Specifically, the vehicle routing problem is regarded as a vehicle tour generation process, and an encoder-decoder framework with attention layers is proposed to generate tours of multiple vehicles iteratively. Furthermore, a multi-agent reinforcement learning method with an unsupervised auxiliary network is developed for the model training. By evaluated on four synthetic networks with different scales, the results demonstrate that the proposed method consistently outperforms Google OR-Tools and traditional methods with little computation time. In addition, we validate the robustness of the well-trained model by varying the number of customers and the capacities of vehicles.

📄 PDF Abstract BibTeX arXiv:2002.05513

Code (0)

등록된 구현이 없습니다.

Tasks

Computational Efficiency Decoder Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Genetic Algorithms with Neural Cost Predictor for Solving Hierarchical Vehicle Routing Problems

2023-10-22 · Abhay Sobhanan, Junyoung Park, Jinkyoo Park, Changhyun Kwon

When vehicle routing decisions are intertwined with higher-level decisions, the resulting optimization problems pose significant challenges for computation. Examples are the multi-depot vehicle routing problem (MDVRP), w…

Graph Neural Network

Learning a Transferable Scheduling Policy for Various Vehicle Routing Problems based on Graph-centric Representation Learning

2021-01-01 · Inwook Kim, Jinkyoo Park

Reinforcement learning has been used to learn to solve various routing problems. however, most of the algorithm is restricted to finding an optimal routing strategy for only a single vehicle. In addition, the trained pol…

Graph Neural Network reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)+2

Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attention

2020-06-16 · Jonas K. Falkner, Lars Schmidt-Thieme

Many real-world vehicle routing problems involve rich sets of constraints with respect to the capacities of the vehicles, time windows for customers etc. While in recent years first machine learning models have been deve…

Learning to Solve Soft-Constrained Vehicle Routing Problems with Lagrangian Relaxation

2022-07-20 · Qiaoyue Tang, Yangzhe Kong, Lemeng Pan, Choonmeng Lee

Vehicle Routing Problems (VRPs) in real-world applications often come with various constraints, therefore bring additional computational challenges to exact solution methods or heuristic search approaches. The recent ide…

Heuristic Search

Learning Vehicle Routing Problems using Policy Optimisation

2020-12-24 · Nasrin Sultana, Jeffrey Chan, A. K. Qin, Tabinda Sarwar

Deep reinforcement learning (DRL) has been used to learn effective heuristics for solving complex combinatorial optimisation problem via policy networks and have demonstrated promising performance. Existing works have fo…

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