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
this https URL

本研究旨在将 Amazon 司机的实践经验融入到最佳路线规划中，我们提出了一种机器学习和传统 TSP 求解器结合的分层方法来处理这个挑战。该方法在历史路线的区域级别学习了一个顺序概率模型，并使用 Rollout 算法生成从学习的概率模型中采样的可信区域序列来编码驱动程序的专业知识，并有效地排序每个区域的站点，该方法取得了 0.0374 的评估分数。