论文标题
学会通过联合注意来解决时间窗口的车辆路由问题
Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attention
论文作者
论文摘要
许多现实世界中的车辆路线问题涉及有关车辆能力，客户的时间窗口等丰富的约束集，而近年来，第一个机器学习模型已开发出比优化启发式方法更快地解决基本车辆路由问题，但很少考虑复杂的限制。由于它们的一般程序是通过路由依次构建解决方案的一般程序，因此这些方法不利地将其推广到此类问题。在本文中，我们开发了一个政策模型，该模型能够通过对几次旅行的联合行动空间的关注来开始和扩展多个路线。这样，模型就可以选择路线和客户，从而学会在路线之间进行艰难的权衡。在有关时间窗口的车辆路由问题的三个变体的全面实验中，我们表明我们的模型称为JAMPR可以很好地适应不同的问题大小，并且胜过现有的最新建设性模型。对于三个变体中的两个，它也比可比的元式求解器创造了明显更好的解决方案。
Many real-world vehicle routing problems involve rich sets of constraints with respect to the capacities of the vehicles, time windows for customers etc. While in recent years first machine learning models have been developed to solve basic vehicle routing problems faster than optimization heuristics, complex constraints rarely are taken into consideration. Due to their general procedure to construct solutions sequentially route by route, these methods generalize unfavorably to such problems. In this paper, we develop a policy model that is able to start and extend multiple routes concurrently by using attention on the joint action space of several tours. In that way the model is able to select routes and customers and thus learns to make difficult trade-offs between routes. In comprehensive experiments on three variants of the vehicle routing problem with time windows we show that our model called JAMPR works well for different problem sizes and outperforms the existing state-of-the-art constructive model. For two of the three variants it also creates significantly better solutions than a comparable meta-heuristic solver.
