Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routing
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.
Code (1)
Tasks
Combinatorial OptimizationDeep Reinforcement Learningreinforcement-learningReinforcement LearningReinforcement Learning (RL)Similar Papers 제목 키워드 기반
Combinatorial Optimization enriched Machine Learning to solve the Dynamic Vehicle Routing Problem with Time Windows
With the rise of e-commerce and increasing customer requirements, logistics service providers face a new complexity in their daily planning, mainly due to efficiently handling same day deliveries. Existing multi-stage st…
Combinatorial OptimizationStochastic OptimizationWhere the Action is: Let's make Reinforcement Learning for Stochastic Dynamic Vehicle Routing Problems work!
There has been a paradigm-shift in urban logistic services in the last years; demand for real-time, instant mobility and delivery services grows. This poses new challenges to logistic service providers as the underlying …
Reinforcement Learning (RL)An Attention-LSTM Hybrid Model for the Coordinated Routing of Multiple Vehicles
Reinforcement learning has recently shown promise in learning quality solutions in a number of combinatorial optimization problems. In particular, the attention-based encoder-decoder models show high effectiveness on var…
Combinatorial OptimizationComputational EfficiencyDecoderTraveling Salesman ProblemEnhancing Column Generation by Reinforcement Learning-Based Hyper-Heuristic for Vehicle Routing and Scheduling Problems
Column generation (CG) is a vital method to solve large-scale problems by dynamically generating variables. It has extensive applications in common combinatorial optimization, such as vehicle routing and scheduling probl…
Combinatorial OptimizationSchedulingA Deep Reinforcement Learning Approach for Solving the Traveling Salesman Problem with Drone
Reinforcement learning has recently shown promise in learning quality solutions in many combinatorial optimization problems. In particular, the attention-based encoder-decoder models show high effectiveness on various ro…
Combinatorial OptimizationComputational EfficiencyDecoderDeep Reinforcement Learning+3