滴滴司机调度系统实践 _滴滴

1.
【滴滴司机调度系统实践】背景
出租车为人们提供了方便灵活的出行服务，在公共交通中扮演了重要角色。出租车在道路上空载行驶寻找乘客的过程，称为空车巡游过程。这一过程可能会占到出租车司机工作时间的50%以上，降低了出租车的运营效率。
在网约车平台上，司机和乘客向平台上报他们的实时位置，平台通过集中决策机制来完成司机和乘客间的匹配。在这种情况下，司机可以在实际见到乘客前就接到该乘客的订单，因而空车巡游的目的不再是寻找乘客，而是寻找一个接到订单概率更高的地理区域或者路线。
本质上来说，空车巡游是由供给和需求间的不平衡导致的。例如图1中，在早高峰司机将一位乘客从家送到办公室后，由于此刻办公区域乘客需求很少，司机必须再次回到住宅区才能有比较大的机会接到下一单。

文章插图

图1. 司机调度问题背景
在本文中，我们研究司机调度问题。所谓“司机调度”，是指平台会通过一定的交互过程打断司机自发的空车巡游过程，将他们引向一个更可能接到单的目的地。受益于供需两侧丰富的实时信息，平台可以通过调度改善司机个人的体验，同时提高平台整体的效率。
2.
什么是“调度任务”
实际场景中，空闲司机往往依赖个人经验来决定空车巡游的目的地，主观性强。经验不准确时可能会前往接单概率较低的区域，既影响司机的个人收入和接单体验，也会影响乘客需求的满足率。因此，本文中我们利用司机和平台之间的实时信息通道来为司机发送即时的调度任务，帮助空闲司机找到最佳的空车巡游目的地。
在本文中，当司机停留在空闲状态时会触发调度任务,如图2所示。调度任务会以卡片消息的形式在司机的App上弹出。如果司机点击导航按钮，会直接进入以调度终点为目的地的导航页面。为帮助司机尽快接到下一个订单，在司机前往调度终点的途中，始终可以被分配订单。

文章插图

图2. 调度任务的产品交互形式
一次调度任务包括三个步骤：
(1) 告知司机一个明确的调度目的地。
(2) 在下发调度任务后追踪司机的行为，判定调度任务是否成功。
(3) 在调度任务失败时为司机提供补偿。
在这里，需要对调度任务的判定标准进行更具体的说明。一个调度任务有四种可能的结束状态，如图3所示。

文章插图

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

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

如果一次调度任务以状态2和状态3结束，那么被视作一次成功的调度；如果以状态4结束，则会被视作一次失败的调度。由于接受调度任务会给司机带来额外的空驶成本，因此，在调度任务失败的情况下，应当为司机提供一定的补偿。这是在司机和平台之间建立信任的关键措施。
3.
方法
本文提出的解决框架分为三阶段，如图4所示。受到推荐系统的启发，前两个阶段的作用是产生候选调度任务集并为每一个候选调度任务打分；受到车队管理方法的启发，第三阶段应用规划算法来实现多司机间的协作，产生最终向司机下发的调度任务。

文章插图

图4. 框架示意图
▍第一阶段：产生候选调度任务
一个调度任务包含四个元素：司机、调度终点、过期时间、补偿金额。
首先，筛选空闲时间超过一定阈值的司机作为候选司机。一般来说，空闲一段时间的司机更需要在听单方面的帮助，也会更愿意接受调度。
然后，为每个候选司机筛选合适的候选调度终点。候选调度终点的产生方式有三种：(1) 司机所在位置周边格子，这些格子距离司机较近，司机更有可能前往；（2）在历史行驶轨迹中连续出现的格子，用于找到一些离当前位置较远、但是由于路网关系可以很快到达的地点；（3）全城热点格子，用于找到一些需求密集的地点。对于每一个候选终点格子，我们会从格子内选择一个POI点作为调度的终点，然后根据司机当前位置到调度终点的预计到达时间（ETA）来设置调度任务的过期时间。