Reinforcement Learning for Solving the Vehicle Routing Problem

Abstract

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.

more results and illustrations

References in corpus (6)

• Sequence to Sequence Learning with Neural Networks
• Show, Attend and Tell: Neural Image Caption Generation with Visual Attention
• Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation
• Learning Combinatorial Optimization Algorithms over Graphs
• Discriminative Embeddings of Latent Variable Models for Structured Data
• ABC-CNN: An Attention Based Convolutional Neural Network for Visual Question Answering

Cited by in corpus (10)

• Deep Reinforcement Learning for Combinatorial Optimization: Covering Salesman Problems
• Reward Design for Driver Repositioning Using Multi-Agent Reinforcement Learning
• Learning the Multiple Traveling Salesmen Problem with Permutation Invariant Pooling Networks
• A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization
• The Transformer Network for the Traveling Salesman Problem
• TAP-Net: Transport-and-Pack using Reinforcement Learning
• Deception in Social Learning: A Multi-Agent Reinforcement Learning Perspective
• Set-to-Sequence Methods in Machine Learning: a Review
• USCO-Solver: Solving Undetermined Stochastic Combinatorial Optimization Problems
• A review of approaches to modeling applied vehicle routing problems