Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routing
| Title: | Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routing |
|---|---|
| Authors: | Delarue, Arthur, Anderson, Ross, Tjandraatmadja, Christian |
| Publication Year: | 2020 |
| Collection: | Computer Science Mathematics Statistics |
| Subject Terms: | Computer Science - Machine Learning, Computer Science - Artificial Intelligence, Mathematics - Optimization and Control, Statistics - Machine Learning |
| More Details: | 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. |
| Document Type: | Working Paper |
| Access URL: | http://arxiv.org/abs/2010.12001 |
| Accession Number: | edsarx.2010.12001 |
| Database: | arXiv |
| Description not available. |