论文标题
向驾驶员学习以应对亚马逊最后一英里路线研究挑战
Learning from Drivers to Tackle the Amazon Last Mile Routing Research Challenge
论文作者
论文摘要
亚马逊最后一英里路由研究挑战的目标是将亚马逊驱动程序的现实经验整合到最佳路线计划和优化的解决方案中。本文提出了我们的方法，该方法通过层次结合机器学习和传统的旅行销售人员问题（TSP）解决方案来应对这一挑战。我们的方法从两个世界中获得了好处。一方面，我们的方法通过从区域级别的历史路线中学习一个顺序概率模型来编码驱动程序的知识，每个区域都包含一些包裹停止。然后，它使用单个步骤策略迭代方法（称为推出算法）来生成从学习概率模型中采样的合理区域序列。另一方面，我们的方法利用了丰富的TSP文献中开发的验证方法来有效地在每个区域内停止。这种组合的结果似乎很有希望。我们的方法获得了0.0374美元的评估评分，这与前三支球队在官方挑战排行榜上取得的成就相当。此外，我们基于学习的方法适用于可能在此挑战范围之外表现出明显的顺序模式的驾驶路线。我们方法的源代码可在https://github.com/aws-samples/amazon-sagemaker-amazon-routing-challenge-challenge-sol上公开获得
The goal of the Amazon Last Mile Routing Research Challenge is to integrate the real-life experience of Amazon drivers into the solution of optimal route planning and optimization. This paper presents our method that tackles this challenge by hierarchically combining machine learning and conventional Traveling Salesperson Problem (TSP) solvers. Our method reaps the benefits from both worlds. On the one hand, our method encodes driver know-how by learning a sequential probability model from historical routes at the zone level, where each zone contains a few parcel stops. It then uses a single step policy iteration method, known as the Rollout algorithm, to generate plausible zone sequences sampled from the learned probability model. On the other hand, our method utilizes proven methods developed in the rich TSP literature to sequence stops within each zone efficiently. The outcome of such a combination appeared to be promising. Our method obtained an evaluation score of $0.0374$, which is comparable to what the top three teams have achieved on the official Challenge leaderboard. Moreover, our learning-based method is applicable to driving routes that may exhibit distinct sequential patterns beyond the scope of this Challenge. The source code of our method is publicly available at https://github.com/aws-samples/amazon-sagemaker-amazon-routing-challenge-sol
