Multi-Vehicle Routing Problems with Soft Time Windows: A Multi-Agent Reinforcement Learning Approach
Multi-Vehicle Routing Problems with Soft Time Windows: A Multi-Agent Reinforcement Learning Approach
复制标题
DOI：
10.1016/j.trc.2020.102861
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
Kecheng Zhang;Meng Li;Zhengchao Zhang;Xi Lin;Fang He
中科院分区：
文献类型：
--
作者：
Kecheng Zhang;Meng Li;Zhengchao Zhang;Xi Lin;Fang He
带软时间窗的多车辆路径问题(MVRPSTW)是城市物流配送系统中不可或缺的组成部分。在过去的十年中，已经提出了许多MVRPSTW方法，但大多数都是基于启发式规则，需要大量的计算时间。随着当前物流需求的快速增长，传统的求解方法在计算效率和求解质量之间产生了两难的矛盾。为了有效地解决这一问题，我们提出了一种新的强化学习算法--多智能体注意力模型，该算法可以立即解决路由问题，并受益于长时间的离线训练。具体地说，将车辆路径问题视为一个车辆行程生成过程，提出了一种具有关注层的编解码器框架，用于迭代生成多辆车的行程。在此基础上，提出了一种具有无监督辅助网络的多智能体强化学习方法用于模型训练。在4个不同规模的合成网络上的测试结果表明，该方法在计算时间较短的情况下，性能一致优于Google OR-Tools和传统方法。此外，我们通过改变客户数量和车辆容量来验证经过良好训练的模型的稳健性。
Multi-vehicle routing problem with soft time windows (MVRPSTW) is an indispensable constituent in urban logistics distribution systems. Over the past decade, numerous methods for MVRPSTW have been proposed, but most are based on heuristic rules that require a large amount of computation time. With the current rapid increase of logistics demands, traditional methods incur the dilemma between computational efficiency and solution quality. To efficiently solve the problem, we propose a novel reinforcement learning algorithm called the Multi-Agent Attention Model that can solve routing problem instantly benefit from lengthy offline training. Specifically, the vehicle routing problem is regarded as a vehicle tour generation process, and an encoder-decoder framework with attention layers is proposed to generate tours of multiple vehicles iteratively. Furthermore, a multi-agent reinforcement learning method with an unsupervised auxiliary network is developed for the model training. By evaluated on four synthetic networks with different scales, the results demonstrate that the proposed method consistently outperforms Google OR-Tools and traditional methods with little computation time. In addition, we validate the robustness of the well-trained model by varying the number of customers and the capacities of vehicles.