【TKDE2024】首篇面向即时配送的服务路线和时效预测研究综述

近年来，即时配送服务（如食品配送和包裹配送）为消费者的日常生活带来了便利，实现了爆发式增长。在即时配送服务中一个新兴的研究领域是服务路径和时效预测（Route and Time Prediction，RTP），该研究旨在预测工作人员（如骑手、快递员等）对于未完成任务的路线安排和到达时间。RTP对于提高用户满意度和减少平台运营支出至关重要。尽管迄今为止研究人员提出了一些算法，但还没有系统、全面的综述来指导该领域的研究。为了填补这一空白，北京交通大学与浙江菜鸟网络技术有限公司、香港科技大学（广州）、新加坡国立大学等单位合作推出了首篇全面的综述，系统地对服务路线和时间预测方面的最新进展进行了分类。 论文网址: https://arxiv.org/abs/2309.01194。

0. 论文概述

即时配送服务（如食品配送和包裹配送）中的服务路径和时效预测（Route and Time Prediction，RTP）对于提高用户满意度和减少平台运营支出至关重要。尽管已经提出了大量算法，但还没有系统、全面的综述来指导该领域的研究。为了填补这一空白，本文提出了第一个全面的综述，系统地对服务路线和时间预测方面的最新进展进行了分类。

本文首先定义了RTP问题，然后介绍了常用的评价指标。并且对现有的RTP方法提出了一种全面的分类体系，根据三个标准对这些方法进行分类：i）任务类型：细分为仅路线预测、仅时间预测和路线与时间联合预测；ii）模型结构：包括基于序列的模型和基于图的模型；iii）学习范式：包括监督式学习（Supervised Learning，SL）和深度强化学习（Deep Reinforcement Learning，DRL）。最后，本文总结了当前研究的局限性，并且给出了未来可能的探索方向。

1. 引言

物流和外卖等即时配送服务在人们的日常需求中发挥着越来越重要的作用。截至2021年底，中国外卖平台处理订单约293亿，覆盖超过400万从业人员和4.6亿消费者。这些服务平台上的一项关键任务是服务路线和时间预测（RTP），其目的是根据工作人员未完成的任务来估计其未来的服务路线和到达时间。近年来，RTP问题越来越受到学术界和工业界的关注，因为它是构建智能服务平台（如菜鸟、京东等物流平台以及美团、GrabFood等外卖平台）的基础。例如，准确的到达时间预测可以很大程度上缓解顾客的等待焦虑，从而改善顾客的体验。此外，路线预测可以集成到调度系统中，优化工作人员路线附近的订单分配。鉴于上述益处，精确的RTP预测不仅可以提升用户体验，还可以降低运营成本，因此值得学术界进一步研究。

由于个人数字助理设备的广泛配备，配送系统记录了大量工作人员历史行为数据（如GPS位置、任务接受时间、任务完成时间等)，从而为学习工作人员的行为模式（如路线和预计到达时间预测）提供了数据基础。因此，近年来我们看到了许多基于深度学习的RTP模型。然而，目前还没有系统、全面的综述来总结和指导该领域的研究。这一不足影响了研究人员对该研究领域的现状和发展趋势的把握。为了满足这一需求，本文对RTP领域的最新工作进行了系统的概述与整理，形成了该领域的首篇综述。总的来说，本文贡献总结为以下三点： * RTP领域的首篇综述：据我们所知，本文是首次对RTP领域的最新进展进行全面的综述，旨在确保研究人员可以全面了解该领域的进展和演变。 * 系统的分类：本文从三个角度对现有RTP方法进行了系统地分类，旨在使研究人员可以更好地理解不同方法之间的关系。 * 局限性和未来方向：本文指出了当前工作的局限性，并讨论了路线和时间预测方面未来的潜在研究方向。

2. 背景

在一个典型的即时配送服务场景中，比如外卖配送，客户首先在在线平台上创建一个任务（订单），该订单需满足一定的时空要求，比如送餐地点和需求的时间窗口，如上午9:00至上午9:30。然后，平台将此订单分派给相应的工作人员。最后，工作人员在确保满足时间和地点要求的前提下完成配送任务。

3. 模型分类

本文对目前 RTP 任务的最新模型进行了全面的调查，并其进行了系统的分类，如下图所示。

本文从三个维度对即时服务中的 RTP 算法进行了分类和总结：（i）从任务的角度来看，包括仅路线预测、仅时间预测和路线与时间预测。（ii）从模型结构的角度来看，包括基于序列的模型和基于图的模型; （iii）从学习范式的角度来看，包括监督式学习（SL）和深度强化学习（DRL）。

4. 最新进展

4.1 现有RTP方法

下表展示了现有路线和时间预测模型的神经网络结构。本文中对以下方法各个组成部分进行了详细阐述，如有兴趣请阅读论文原文。

4.2 应用

为了直观地展示 RTP 方法在现实世界系统的应用，本文举例说明了两个应用，如图所示。

订单智能排序服务为快递员在揽收包裹的过程提供帮助。在真实场景下，揽收任务是随机生成的，并且用户可以随时下单。这要求快递员根据收到的任务频繁更新其路线规划。通过智能排序，订单列表能更好地与快递员的工作习惯保持一致，从而减轻了快递员路线规划的负担。 * 提供更准确的预计到达时间（ETA）预测。通过改进的路线和时间预测模型，平台为用户提供了更可靠、更准确的ETA服务，从而提升用户体验。

5. 局限性和未来研究方向

5.1 局限性

虽然目前的方法已经取得了良好的性能，但仍然存在以下几方面的局限性： * 循环解码机制：首先，大多数路线/时间预测解码器采用循环体系结构，如DeepRoute、DeepRoute+、Graph2Route等。这些解码器通过逐步计算预测目标，将前一步的输出作为下一步的输入。然而，循环体系结构可能会遇到效率问题。特别是在现实世界的情况下，例如物流场景，一个工作人员在同一时间可能承担着50个甚至更多的任务。 * 缺乏对道路网络的建模：其次，当前所有的模型都没有充分考虑到道路网络的影响。它们中的大部分仅对已完成或未完成的任务的时空特征进行建模。部分研究还对附加的地理信息进行了建模，例如社区信息或 AOI 信息。然而，道路网络作为一种自然且重要的空间信息，却被当前大部分研究所忽视。 * 时间预测中的误差累积：第三，现有的 RTP 解决方案通常将路线预测结果作为时间预测的输入，如I2Route、M2G4RTP等。如果路线预测错误，时间预测的准确性也会受到影响。此外，路线预测中的误差还会累积并削弱时间预测的性能。

5.2 未来研究方向

未来的研究有以下几个潜在的研究方向： * 更高效的路线预测解码技术：一个可行的研究方向是开发一种更高效的解码机制。为实现这一目标，我们可以从两个途径着手。首先，从模型结构的角度出发，研究一种能够同时生成多个输出的非自回归解码器。其次，从模型压缩的角度出发，探索一种更轻量级的模型，以加快推理速度。 * 道路网络的建模：道路网络蕴含着丰富的空间信息，同时也是工作人员完成任务的关键地理空间。因此，未来的发展方向之一就是在模型设计中对路网进行深入建模。 * 路线和时间联合分布的建模：两个预测问题作为一个整体进行考虑，开发更高效的路线和时间联合预测模型仍然是一个具有潜力的未来发展方向。 * RTP 概率预测：现有的工作主要关注点估计的研究。然而，这些预测方法往往只给出一个单一的点估计或路线估计，无法量化预测的不确定性。这对于需要在不确定性下进行风险评估或决策的下游任务至关重要。因此，如何开发路线和时间预测的概率预测模型，也是未来的一大方向。