了解滴滴打车算法

滴滴算法

字数统计: 819阅读时长: 2 min

 2019/11/11 

问题点:
- 订单分配 就是在派单系统中将乘客发出的订单分配给在线司机的过程
问题细节拆分:
- 先到先得,就近分配的贪心策略: 缺点: 如果我们只基于当前时刻和当前局部订单进行决策,会议室了未来新的订单&司机的变化, 还忽视了和你相邻的其他区域甚至整个城市的需求.
- 特征集合订单起点(经纬度),终点(经纬度), 司机当前位置(经纬度), 司机到订单起点的距离.
- 案例一(一个司机一个订单): 看上去附近有一辆空车却不能指派给你,为什么呢?
  - 快车司机不接专车单
  - 司机接单后不会通过限行限号区域
  - 设定实时目的地的司机过滤不顺路区域
  - 只听预约单司机过滤实时订单
  - 同一个订单只会发给一个司机一次
  - …
- 案例二(两个司机一个订单):
  - 距离相同情况下,考虑服务分高低(简单理解多少分换成多少米导航距离优势)
  - A司机近,B司机远, 就近原则直接分配给A.
- 案例三(M个司机,N个订单)
  - 最原始暴力的搜索方法,20阶乘,天文数字,不适合,需要更有的算法
- 案例四(N个订单,M个司机,随后再来几个订单和司机)
  - 考虑时序进行分配: Dynamic VRP(Vehicle Routing Problem)
派单算法
- 批量匹配(全局最优) Batching Matching
- 基于供需预测的分单
- 连环派单:将订单指派给即将结束服务的司机. 条件为如果司机到终点的距离很近且上一订单终点与下一订单订单起点位置很近; 会命中连环派单逻辑
学习了解滴滴的派单算法
- 目标与关键问题
  - 目标: 最大化单次派单成功率
  - 关键问题: estimate the probability of each driver’s acceptance of an order(估计每个驾驶员接单的可能性)
- 构建模型步骤-特征筛选
  - 订单-司机关联特征: 接驾里程, 订单推送给多少司机, 订单是否与司机当前驾驶方向一致.
  - 订单特征: 起终点之间距离,ETA(Estimated Time of Arrival),终点类型,规划路线的情况,目的地历史上的订单频率
  - 司机特征: 历史接单率, 司机活跃地点, 接驾里程偏好, 最近接单率
  - 补充特征: 特征日, 特征小时, 司机数,附近运单数
- 可用模型(LR/GBDT)
  - 产出公式:(目标: 总体成单率最高, 约束表示一个司机一个时刻最多只能派一单)
  - 启发式算法解公式
  - 初始解：对每个司机，派给他接单率最大的订单，然后计算每一单的成单率，得到平均成单率
  - 迭代: 对运单i，找到没有被派到i的司机集合U，对U的每个司机k，如果把i派给k，平均成单率提高，则改派
- 评估模型/方案
  - 评估指标: 成单率,平均接驾时长,平均派单时间,取消率, 人均单量
转: 原文地址