Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routing

Abstract

Value-function-based methods have long played an important role in reinforcement learning. However, finding the best next action given a value function of arbitrary complexity is nontrivial when the action space is too large for enumeration. We develop a framework for value-function-based deep reinforcement learning with a combinatorial action space, in which the action selection problem is explicitly formulated as a mixed-integer optimization problem. As a motivating example, we present an application of this framework to the capacitated vehicle routing problem (CVRP), a combinatorial optimization problem in which a set of locations must be covered by a single vehicle with limited capacity. On each instance, we model an action as the construction of a single route, and consider a deterministic policy which is improved through a simple policy iteration algorithm. Our approach is competitive with other reinforcement learning methods and achieves an average gap of 1.7% with state-of-the-art OR methods on standard library instances of medium size.

References in corpus (12)

• Playing Atari with Deep Reinforcement Learning
• Learning Combinatorial Optimization Algorithms over Graphs
• DeepMind Control Suite
• Evaluating Robustness of Neural Networks with Mixed Integer Programming
• Safe Exploration in Continuous Action Spaces
• Challenges of Real-World Reinforcement Learning
• An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
• Input Convex Neural Networks
• Attention, Learn to Solve Routing Problems!
• Learn What Not to Learn: Action Elimination with Deep Reinforcement Learning
• Horizon: Facebook's Open Source Applied Reinforcement Learning Platform
• Approximate Policy Iteration Schemes: A Comparison

Cited by in corpus (6)

• Reinforcement Learning for Ridesharing: An Extended Survey
• Dynamic resource matching in manufacturing using deep reinforcement learning
• Deep Reinforcement Learning for Demand Driven Services in Logistics and Transportation Systems: A Survey
• Smart Feasibility Pump: Reinforcement Learning for (Mixed) Integer Programming
• Where the Action is: Let's make Reinforcement Learning for Stochastic Dynamic Vehicle Routing Problems work!
• Fast Approximate Solutions using Reinforcement Learning for Dynamic Capacitated Vehicle Routing with Time Windows