门畅 徐哲 刘春阳 滴滴技术

桔妹导读：如何解决供需不平衡问题呢？一个自然的想法就是调度空闲的在线司机到需求较多的区域。滴滴网约车团队近期发表在万维网大会WWW 2020 Research Track的Oral长文《When Recommender Systems Meet Fleet Management: Practical Study in Online Driver Repositioning System》提出了在线司机调度系统的一种有效的解决方案。本文是对该论文的详细解读。

随着移动互联网的兴起，网约车逐渐成为了大众常用的一个出行选择。但在网约车平台上经常出现这种情况：有时候乘客抱怨打不到车，与此同时其他地方的司机却没有订单接，长时间空驶。这就是典型的供需不平衡问题，即乘客和司机的自然分布出现了错配。这一方面让很多乘客的出行需求得不到满足，另一方面也让很多司机空驶等待，运力资源没有充分利用。如何解决供需不平衡问题呢？一个自然的想法就是调度空闲的在线司机到需求较多的区域。以下与大家分享对于本篇论文的详细解读。

论文地址：

https://dl.acm.org/doi/abs/10.1145/3366423.3380287\\\**

背景

出租车为人们提供了方便灵活的出行服务，在公共交通中扮演了重要角色。出租车在道路上空载行驶寻找乘客的过程，称为空车巡游过程。这一过程可能会占到出租车司机工作时间的50%以上，降低了出租车的运营效率。

在网约车平台上，司机和乘客向平台上报他们的实时位置，平台通过集中决策机制来完成司机和乘客间的匹配。在这种情况下，司机可以在实际见到乘客前就接到该乘客的订单，因而空车巡游的目的不再是寻找乘客，而是寻找一个接到订单概率更高的地理区域或者路线。

本质上来说，空车巡游是由供给和需求间的不平衡导致的。例如图1中，在早高峰司机将一位乘客从家送到办公室后，由于此刻办公区域乘客需求很少，司机必须再次回到住宅区才能有比较大的机会接到下一单。

图1. 司机调度问题背景

在本文中，我们研究司机调度问题。所谓“司机调度”，是指平台会通过一定的交互过程打断司机自发的空车巡游过程，将他们引向一个更可能接到单的目的地。受益于供需两侧丰富的实时信息，平台可以通过调度改善司机个人的体验，同时提高平台整体的效率。

什么是“调度任务”

实际场景中，空闲司机往往依赖个人经验来决定空车巡游的目的地，主观性强。经验不准确时可能会前往接单概率较低的区域，既影响司机的个人收入和接单体验，也会影响乘客需求的满足率。因此，本文中我们利用司机和平台之间的实时信息通道来为司机发送即时的调度任务，帮助空闲司机找到最佳的空车巡游目的地。

在本文中，当司机停留在空闲状态时会触发调度任务,如图2所示。调度任务会以卡片消息的形式在司机的APP上弹出。如果司机点击导航按钮，会直接进入以调度终点为目的地的导航页面。为帮助司机尽快接到下一个订单，在司机前往调度终点的途中，始终可以被分配订单。

图2. 调度任务的产品交互形式

一次调度任务包括三个步骤：

(1) 告知司机一个明确的调度目的地。

(2) 在下发调度任务后追踪司机的行为，判定调度任务是否成功。

(3) 在调度任务失败时为司机提供补偿。

在这里，需要对调度任务的判定标准进行更具体的说明。一个调度任务有四种可能的结束状态，如图3所示。

图3. 调度任务的结束状态

  • 状态1：司机没有接受调度任务，并且向反方向行驶。
  • 状态2：司机接受调度任务并驶向调度终点，在途中被分配了一个订单。
  • 状态3：司机接受调度任务并到达调度终点，然后在一个固定的时间窗口内接到了订单。
  • 状态4：司机接受调度任务并到达调度终点，在终点停留一段时间，但在一个固定的时间窗口内一直都没有接到订单。

如果一次调度任务以状态2和状态3结束，那么被视作一次成功的调度；如果以状态4结束，则会被视作一次失败的调度。由于接受调度任务会给司机带来额外的空驶成本，因此，在调度任务失败的情况下，应当为司机提供一定的补偿。这是在司机和平台之间建立信任的关键措施。

方法

本文提出的解决框架分为三阶段，如图4所示。受到推荐系统的启发，前两个阶段的作用是产生候选调度任务集并为每一个候选调度任务打分；受到车队管理方法的启发，第三阶段应用规划算法来实现多司机间的协作，产生最终向司机下发的调度任务。

图4. 框架示意图

▍第一阶段：产生候选调度任务

一个调度任务包含四个元素：司机、调度终点、过期时间、补偿金额。

首先，筛选空闲时间超过一定阈值的司机作为候选司机。一般来说，空闲一段时间的司机更需要在听单方面的帮助，也会更愿意接受调度。

然后，为每个候选司机筛选合适的候选调度终点。候选调度终点的产生方式有三种：(1) 司机所在位置周边格子，这些格子距离司机较近，司机更有可能前往；（2）在历史行驶轨迹中连续出现的格子，用于找到一些离当前位置较远、但是由于路网关系可以很快到达的地点；（3）全城热点格子，用于找到一些需求密集的地点。对于每一个候选终点格子，我们会从格子内选择一个POI点作为调度的终点，然后根据司机当前位置到调度终点的预计到达时间（ETA）来设置调度任务的过期时间。

最后，为了保证良好的用户体验，我们引入了失败概率预测模型，只保留失败概率不大于一定阈值的候选调度任务，并在任务失败的情况下为司机提供一定的补偿。补偿金额与调度任务起终点间的距离有关。

▍第二阶段：任务评分

任务评分阶段度量了每一个候选调度任务可能为平衡供需分布、提高平台效率所带来的收益。

对于一个时空状态，用分段线性函数拟合应答率（被应答订单数与全部呼叫订单数之比）与供需比（空闲司机数与呼叫订单数之比）的函数关系：

依据这一函数，可以计算出向调度终点时空增加一个空闲司机可能会带来的边际增益，以此作为每一个候选调度任务的评分结果，即

依据拟合结果，我们可以推导出另外一个有应用价值的结果：每个时空状态的司机缺口数量。通过设定一个目标应答率，我们可以计算出达到这一目标所需增加的司机数量，也即运力缺口数：

▍第三阶段：规划

在第一阶段产生的候选调度任务集，并且在第二阶�