Reinforcement Learning for Solving the Vehicle Routing Problem

2018-02-12 · NeurIPS 2018 12 · Mohammadreza Nazari, Afshin Oroojlooy, Lawrence V. Snyder, Martin Takáč

We present an end-to-end framework for solving the Vehicle Routing Problem (VRP) using reinforcement learning. In this approach, we train a single model that finds near-optimal solutions for problem instances sampled from a given distribution, only by observing the reward signals and following feasibility rules. Our model represents a parameterized stochastic policy, and by applying a policy gradient algorithm to optimize its parameters, the trained model produces the solution as a sequence of consecutive actions in real time, without the need to re-train for every new problem instance. On capacitated VRP, our approach outperforms classical heuristics and Google's OR-Tools on medium-sized instances in solution quality with comparable computation time (after training). We demonstrate how our approach can handle problems with split delivery and explore the effect of such deliveries on the solution quality. Our proposed framework can be applied to other variants of the VRP such as the stochastic VRP, and has the potential to be applied more generally to combinatorial optimization problems.

📄 PDF Abstract BibTeX arXiv:1802.04240

Code (4)

DeepLearningCUCS/RLVRP tf

Nina-Konovalova/TSP-RL-Skoltech_project pytorch

OptMLGroup/VRP-RL tf

ajayn1997/RL-VRP-PtrNtwrk pytorch

Tasks

Combinatorial Optimizationreinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

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)

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

Reinforcement Learning for Solving Stochastic Vehicle Routing Problem

2023-11-13 · Zangir Iklassov, Ikboljon Sobirov, Ruben Solozabal, Martin Takac

This study addresses a gap in the utilization of Reinforcement Learning (RL) and Machine Learning (ML) techniques in solving the Stochastic Vehicle Routing Problem (SVRP) that involves the challenging task of optimizing …

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Neural Combinatorial Optimization with Reinforcement Learning : Solving theVehicle Routing Problem with Time Windows

2021-09-29 · Abdelhakim Abdellaoui, Issmail El Hallaoui, Loubna Benabbou

In contrast to the classical techniques for solving combinatorial optimization problems, recent advancements in reinforcement learning yield the potential to independently learn heuristics without any human interventions…

Combinatorial Optimization reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Deep Reinforcement Learning for Solving the Fleet Size and Mix Vehicle Routing Problem

2025-12-30 · Pengfu Wan, Jiawei Chen, Gangyan Xu arxiv

The Fleet Size and Mix Vehicle Routing Problem (FSMVRP) is a prominent variant of the Vehicle Routing Problem (VRP), extensively studied in operations research and computational science. FSMVRP requires simultaneous deci…

Computational Efficiency Reinforcement Learning Graph Embedding