Reinforcement Learning for Solving the Vehicle Routing Problem

By M. Nazari, Afshin Oroojlooy, Lawrence V. Snyder, Martin Takác. Neural Information Processing Systems, 2018

1,162 citations recorded by the source corpus.

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.

Subfields: Automotive Engineering, Building and Construction, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/0366b6396610708a77540564050a90a761a28937

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Automotive Engineering

In Building and Construction

In Industrial and Manufacturing Engineering

Citations in the corpus

Deep Reinforcement Learning for Multiagent Systems: A Review of Challenges, Solutions, and Applications (2018, background): “advances of the deep RL have been extended to solve NP-hard problems such as vehicle routing problem, which is critical in logistics [19], [20].”
Flight-connection Prediction for Airline Crew Scheduling to Construct Initial Clusters for OR Optimizer (2019, background): “Although many recent papers used ML to solve combinatorial problems similar to CPPs, to our knowledge, previous studies focused only on small-scale vehicle routing with up to 100 customers) [38, 33] and airline crew scheduling problems with up to 714 flights [15].”
Combinatorial optimization and reasoning with graph neural networks (2021, background): “GNN Architectures Deudon et al. [2018], Nazari et al. [2018], and Kool et al. [2019] were perhaps the ﬁrst to use attention-based models for routing problems.”
An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem (2019, methodology): “Similar learning-based techniques have been proposed for generalizations of TSP such as the Vehicle Routing Problem [Nazari et al., 2018, Kool et al., 2019] and the multiple TSP [Kaempfer and Wolf, 2018], as well as other combinatorial problems such as the Minimum Vertex Cover Problem and the…”
Deep Reinforcement Learning for Multiobjective Optimization (2019, methodology): “2) Model: In this part, the above problem is modeled using a modiﬁed Pointer Network [17].”
Attention, Learn to Solve Routing Problems! (2018, positive): “Nazari et al. (2018) replace the LSTM encoder of the PN by element-wise projections, such that the updated embeddings after state-changes can be effectively computed.”
Deep Learning for Intelligent Transportation Systems: A Survey of Emerging Trends (2020, methodology): “Within the applications we have surveyed, attention has been used to perform message passing within graph NNs [31], [54], to focus on different nodes within combinatorial problems [95], [13], [75], and to aggregate context across local trajectory segments when estimating the travel time [97].”
DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization (2023, background): “…87, 114, 109, 18], improved training strategies [59, 7], and for a wider range of NPC problems such as Capacitated Vehicle Routing Problem (CVRP) [83], Job Shop Scheduling Problem (JSSP) [122, 89], Maximal Independent Set (MIS) problem [57, 1, 80, 92], and boolean satisfiability problem (SAT)…”
A review of cooperative multi-agent deep reinforcement learning (2019, background): “With the motivation of recent success on deep reinforcement learning (RL)—super-human level control on Atari games [92], mastering the game of Go [121], chess [122], robotic [65], health care planning [82], power grid [42], routing [98], and inventory optimization [101]—several researches have been ”
Learning to Perform Local Rewriting for Combinatorial Optimization (2018, methodology): “[35] and AM [29]) over the test set of: (a) expression simplification; (b) job scheduling; (c) vehicle routing.”
Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning (2020, background): “travelling salesman problem) [12, 13, 14, 15, 16, 17], graph optimization problems [18, 19], and the satisfiability problem (SAT) [20, 21, 22].”
Learning Improvement Heuristics for Solving Routing Problems (2019, background): “Based on elaborately designed deep structures such as recurrent neural network (RNN) [14], [15], [16] and attention mechanism [17], [18], [19], these methods are able to learn heuristics that can produce high-quality solutions.”
Differentiation of Blackbox Combinatorial Solvers (2019, background): “, 2017) or its vehicle routing variants (Nazari et al., 2018).”
Solving Mixed Integer Programs Using Neural Networks (2020, methodology): “…deep learning has been applied to the Travelling Salesman Problem (Vinyals et al. 2015, Bello et al. 2016), Vehicle Routing (Kool et al. 2019, Nazari et al. 2018), Boolean Satisfiability (Selsam et al. 2019), and general graph-structured combinatorial optimization problems (Khalil et al.…”
Finding key players in complex networks through deep reinforcement learning (2020, methodology): “One can further improve FINDER’s performance by tailoring the training data towards the target network with the configuration model (CM) 37 (Supplementary Tables 19 and 22), or by employing the reinsertion technique 38 (Supplementary Fig.”
Large Language Models as Optimizers (2023, background): “…including heuristic algorithms and solvers (Rosenkrantz et al., 1977; Golden et al., 1980; Optimization et al., 2020; Applegate et al., 2006; Helsgaun, 2017), and approaches based on training deep neural networks (Kool et al., 2019; Deudon et al., 2018; Chen & Tian, 2019; Nazari et al., 2018).”