每个周日的上午，都要送闺女去上早教课，由于孩子的磨磨蹭蹭，基本上都是急急忙忙的出门。边跑边打开滴滴APP，但每次打开APP准备输入目的地的时候，第一个推荐的条目就是我想要去的地方(上早教课的地方)，极大的节约了我的时间，发出乘车请求后，看着显示的时间，就开始等待的士车的到来。上车后，在APP上可以看到到达目的地的预估时间，每次看到能在上课时间之前到达目的地时，才放下心来。
这所有的行为看起来都很平常，但滴滴为了完成上面的所有动作，可以说是操碎了心。
据相关资料显示，从2017年开始，滴滴连续三年都有论文入选国际数据挖掘领域的顶级会议KDD，其全称为ACM SIGKDD(The Association for Computing Machinery's Special Interest Group on Knowledge Discovery and Data Mining)，从这些论文可以让我们能够一窥全豹，了解滴滴在出行领域做了哪些重要的贡献。
滴滴出行背后需要解决的三个核心问题
在百度输入框中输入需要查询的内容后，后台的搜索算法在百亿级的数据库中找出你想要的内容，但要在茫茫车海中匹配到一辆能够载你去目的地的车会更加复杂，主要表现在以下几个方面：
1.车辆属于高速移动的物体，乘客和司机的相对位置一直在实时变化。
2.乘客和车辆数量多，系统需要全局考虑区域内的用车需求及供给，并以毫秒级的速度进行计算。
3.需要充分考虑司机的预期收入，让收入最大化，进行最合理的派单。
4.需要充分考虑乘客的出行体验，等待时间不宜过长。
滴滴所做的一切，都是为了解决三个问题：最合理的分单、最大化用户的出行效率和体验、最大化司机的预期收入。
只有解决了这三个核心问题，这次司机和乘客之间的撮合才算成功。
常人眼中的解决方案
自动获取当前上车地点，然后输入目的地，当发出订单请求后，在APP的地图上，以上车点为圆心，有一个不断向外扩展的圆，可能大部分人都会觉得，此时就是把我的用车请求发给附近所有的空的士，然后等待的士抢单。如果没有人接单或者没有空的士，然后再扩大搜索半径。如果长时间没有人接单，此时滴滴会询问你是否是加红包，让更远的的士来接你。
这是我们普通常人，通过APP上的表现来推测的滴滴可能的做法。这只是猜对了一半，因为司机和乘客的匹配，远比我们想象的复杂，如接驾距离、道路拥堵情况、目的地是热区还是冷区等因素。
可能离你远一点的车，走另外一条不拥堵的道路，立马就可以到达乘车点。离你更近一点的空车，由于拥堵在路上，也无法掉头，可能需要更长的时间抵达乘车点。如果仅是按照上述的理解，滴滴把订单请求发给了堵在路上的的士车，对于司机来说，反正有一单生意，不接白不接，即使乘客取消，自己也不损失什么。这种我们认为的解决方案，没有考虑以上三个核心问题：如何让司机的利益最大化？如何让乘客利益最大化？
滴滴出行的解决方案
当你在乘车地点，打开手机的时候，根据历史记录和乘车行为，分析出此时你可能最要去的地点列表，供你选择，免去输入文字的烦扰。当你发出订单请求后，滴滴采用全局最优派单模型，在秒级时间内计算出所有可能的司机乘客匹配情况，然后由算法综合考虑接驾距离、道路拥堵、冷热区等因素，自动将订单匹配给最合适的司机接单，让乘客接驾时间最短。对于上述场景，滴滴会毫不犹豫的是将订单请求发送给更远距离的空车。同时还会告诉乘客，司机需要多长时间到达乘车点。在你坐上车的一刹那，根据最佳行车路线，预估出到达时间，给乘车者一个明确的预期。
而这些所有一切的背后，都是靠机器学习和深度学习AI算法在支撑，为人们提供最佳的出行体验。
基于贝叶斯进行目的地预测
滴滴基于平台海量的历史数据进行分析，发现人们的出行往往有一定的规律可寻，在同一个时间段到达相同的地方，基于这一发现，滴滴使用了贝叶斯公式建立用户目标的概率分布模型：
根据历史数据分析显示，用户目的地的出发时刻的频率直方图往往呈现正态分布，于是滴滴采用了循环正态分布，建成一个优化模型，通过求解，得到了期望的平均值和方差。
其算法流程为：首先根据用户的历史订单，依次计算每个目的地对应的发单时刻的期望和方差；然后根据当前时间计算每个目的地概率的中间数据；第三步用贝叶斯框架计算每个目的地的概率；最后确定阈值，满足阈值的计算结果在首屏展示，也就是此时最有可能你想要到达的地方。
利用深度学习进行预估到达时间
滴滴设计了一种使用深度神经网络来预测预估到达时间（ETA）的方案，提出 Wide-deep-recurrent（WDR）模型，能在给定出发时间和路线的情况下更加准确地预测。
ETA技术在滴滴平台应用十分广泛，无论是行程前的预估接驾时间、预估价格显示，还是派单、调度、拼车等系统决策，或是行程中的预计到达终点的时间计算等，离不开 ETA 的辅助。
其WDR模型为：
其中，Wide 和 Deep 模块对行程的整体信息进行建模，而 Recurrent 模块对行程的轨迹进行细致的建模，可以捕捉到每条路段、每个路口的信息。在最终汇总时，Wide 模块通过仿射变换把输出变到合适维度，Deep 模块直接把顶层 hidden state 作为输出，而 Recurrent 模块将 LSTM 的最后一个 hidden state 作为输出。三个模块的输出向量被拼接起来，进入最终的 Regressor 进行预测，得到 ETA 值。
基于深度强化学习与半马尔科夫决策过程的智能派单
派单可以看成一个系列决策问题，将其建模为带有时间延展性的马尔科夫决策过程，也称为Semi-MDP。与标准MDP类似，司机从一个状态 (时间、地点、情景式特征) 出发，通过接单或者空车游走的动作 (option)，转移到下一个状态，并获得相应奖励 。
在Semi-MDP的框架下可以得出强化学习中价值函数的定义，表示司机从一个状态出发，在给定的派单策略下，直到一天结束的期望收益
基于价值函数的一步转移Bellman方程
使用神经网络来表示上面定义的价值函数，训练通过Bellman方程的价值迭代，滴滴提出了四个技术上的创新：
1.Cerebellar Embedding
2.Lipschitz正则化 (regularization)
3.情景随机化 (contextrandomization)
4.多城市迁移学习 (multi-city transfer learning)
来保证非线性迭代的稳定性以及状态空间的表达。
以上具体的技术细节可参考KDD 2019《A Deep Value-networkBased Approach for Multi-Driver Order Dispatching》一文。
总结
滴滴在智慧出行领域，基于机器学习人工智能技术，不断深耕，从多维度，多角度来有效的撮合司机和乘客之间的匹配，最合理的派单、最大化用户的出行效率和出行体验、最大化司机的预期收入，达到多赢的局面。
为了方便乘客的出行，可谓是操碎了心。
科技改变生活！
可能你还喜欢