Reinforcement Learning for Solving the Vehicle Routing Problem
Reinforcement Learning for Solving the Vehicle Routing Problem
复制标题
DOI：
--
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
M. Nazari;Afshin Oroojlooy;L. Snyder;Martin Takác
中科院分区：
文献类型：
--
作者：
M. Nazari;Afshin Oroojlooy;L. Snyder;Martin Takác
我们提出了一个端到端的框架，用于解决车辆路径问题（VRP）使用强化学习。在这种方法中，我们只通过观察奖励信号和遵循可行性规则来训练一个模型，该模型可以为从给定分布中采样的问题实例找到接近最优的解决方案。我们的模型代表了一个参数化的随机策略，通过应用策略梯度算法来优化其参数，经过训练的模型在真实的时间内产生一系列连续动作的解决方案，而不需要为每个新的问题实例重新训练。在容量受限的VRP上，我们的方法在中等规模的实例上的解决方案质量优于经典的算法和Google的OR工具，并且计算时间相当（训练后）。我们展示了我们的方法可以处理问题的分割交付，并探讨这种交付的解决方案质量的影响。我们提出的框架可以适用于其他变种的车辆路径规划，如随机车辆路径规划，并有可能被应用到更普遍的组合优化问题。
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.