1. 交易市场中的核心匹配问题是什么?
复杂一些,当一位乘客开始呼叫,而区域内有多名司机时,则应该为该乘客寻找最优的司机,比如离其最近的司机,或者服务最好的司机:
再复杂一些,当多位乘客都在呼叫,而区域内只有一位司机时,将为该司机匹配更加合适的乘客订单:
双边匹配技术问题
2. 滴滴业务场景的部分匹配技术
静态双边匹配
过去采用:贪心算法匹配
过去采用:最大权匹配
稳定双边匹配:GS算法
在采用最大权匹配的应用中,我们发现,该种匹配方式能够实现定义的某项收益最大化,但并没有充分考虑个体需求,对部分司机和乘客造成了一定的困扰。
在保障了司乘意愿的约束条件下,为实现更加公平、高效、鲁棒、提升司乘整体效率,实现更好的匹配方法,是我们不断探索的方向。
拓展到一对多匹配场景
以上例子仅为滴滴最常见场景下的基础双边匹配问题,由于在多种多样的出行服务业务和场景之中存在复杂而多变的双边匹配情况,限于篇幅,不再过多展开。
司乘相互偏好程度
动态双边匹配和司乘价值
动态双边匹配
最优停止问题
动态双边匹配的一种简化解法是最优停止问题(Optimal Stopping,也称之为秘书问题),在该问题的原始版本描述中,描述如下:公司要聘请一名秘书,共有 n 个应聘者,每次面试一人,面试官总能将其与之前所有应聘者比较,面试后立即决定是否雇佣他,如果决定不雇佣,则无法未来挽回。这种情况下应该怎么决策,能够使得选中最佳人选的概率最大?
基于强化学习决策的动态双边匹配
司乘价值
路径订单规划
PDP/VRP 问题
排队体验与资源分配
【北京某日排队入队间隔的假设检验结果】
原假设:队列入队间隔分布与负指数分布一致
检验结果:
Kolmogorov-Smirnov检验:pvalue=0.45 >= 0.05
Wilcoxon检验:pvalue=0.41 >= 0.05
Kruskal-Wallis检验:pvalue=0.09 >= 0.05
结论:原假设成立,即【队列入队间隔分布服从负指数分布】
仿真与数字孪生
3. 总结
4.参考资料
延展阅读
END
作者及部门介绍
招聘信息
高级研发工程师
高级算法工程师