滴水调度算法_从算法模型构想到评估方案 - 详细 - 4. 总结

每天, 我们的派单系统要面对超过3000万用户的叫车需求, 高峰期每分钟接收超过6万乘车需求，平均每两秒就需要匹配几百到上千的乘客和司机 。我们当前的派单策略相对于最初的派单策略版本，每天能够多满足百万以上乘客的出行需求。为了让更多人能更快、更确定的打到车，我们的交易策略团队将在更好的公平感知的前提下，不断地优化和打磨我们的派单算法，为乘客&司机创造更多价值。

当然当前的派单策略还有很多不够完善和完备的地方，本身也是一个相当复杂的问题和系统，一方面借此机会让大家对派单有更好的理解和认识，另一方面，也更欢迎大家对我们提出更多的宝贵意见，帮助我们进一步成长。

滴滴派单算法

背景

• 业务场景：一个订单被派给多个司机，司机根据自己的喜好选择接受或拒绝
• 目标：最大化一次派单成单率
• 关键问题：estimate the probability of each driver's acceptance of an order
• 算法方案：步骤1，估计每个司机的接单概率；步骤2，将各个司机接单率作为输入，最大化派单成功率

司机接单率模型

• 订单-司机关联特征：接驾里程、订单推送给多少个司机、订单是否与司机当前驾驶方向一致
• 订单特征：起点到终点的距离、ETA、终点类型（医院、机场、学校、商务区等）、规划路线的路况、目的地历史上的订单频率
• 司机特征：历史接单率、司机活跃地点、接驾里程偏好、最近接单率等
• 补充特征：特征日、特征小时、司机数、附近运单数

使用LR和GBDT模型，LR模型比GBDT略好一些，北京市的准确率为0.7822，AUC是0.8680；上海市的准确率是0.7632，AUC是0.8470。

约束表示，一个司机一个时刻最多只能派一单

目标是使这一批订单这一次派单的总体成单率最高。

使用启发式算法解上述问题。

初始解：对每个司机，派给他接单率最大的订单，然后计算每一单的成单率，得到平均成单率

迭代：对运单i，找到没有被派到i的司机集合U，对U的每个司机k，如果把i派给k，平均成单率提高，则改派

评估方案

指标：

• 成单率
• 平均接驾时长
• 平均派单时长
• 取消率
• 人均单量

案例：

云服务器ECS地址：阿里云·云小站