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.

这篇论文提出了一种基于强化学习的名为 “Multi-Agent Attention Model” 的算法，能够利用较长的离线训练时间快速解决城市物流配送中必不可少的 “多车辆路径问题（MVRPSTW）”，该算法以车辆旅游生成过程为基础，提出了一种具有注意力层的编码器 - 解码器框架来迭代地生成多辆车的路径，通过对不同规模的合成网络进行评估，证明该算法的效果优于谷歌 OR-Tools 和传统方法，并验证了模型的稳健性。