开通VIP，畅享免费电子书等14项超值服
首页
好书
留言交流
下载APP
联系客服
2019.09.22
说到滴滴的派单算法，大家可能感觉到既神秘又好奇，从扬召到抢单到派单，我们又是如何演进到今天大家的打车体验的呢，我们首先来看一看，好的派单算法为什么是出行行业不可或缺的能力？
回想几年前，当我们还没有滴滴的时候，只能在寒风或者酷暑中等待可能有、可能没有的扬招出租车，到后来可以从滴滴上呼叫一辆出租车，乘客可以在室内相对舒适的等待车辆的到达，从线上到线下，乘客的确定性得到第一次的提升，然而这还不够，抢单的模式注定我们的应答率天花板不会太高，在15年，滴滴上线快车业务，我们从抢单演进到了派单模式，乘客的应答率有了20个点以上的提升，很多时候能够全天能够高达90（高峰&局部供需紧张应答率会相对吃紧），乘客确定性再一次得到大幅的提升，由此可见，派单模式为滴滴创造了巨大用户价值。
再看近年来不断兴起的O2O业务，从国内外的网约车公司，包括我们的友商Uber、Lyft都基于派单的产品形态进行司机和乘客之间的交易撮合，Uber上市的时候把派单引擎也作为核心技术能力放在了招股书中；再看我们的国内的外卖平台，核心派单系统的优劣也决定了整个平台的交易效率（单均配送成本）和用户体验（配送时长）；最后，整个大物流行业近年来也不断在进行线上化的改造，如何撮合货物和司机，以及更好的拼单能力也是整个交易环节的关键和商业模式是否成立的前提。从运人到运物，派单引擎目前越来越多的被应用在现实的商业和生活中。
言归正传，这里我们也来看一下，滴滴网约车平台到底是怎么派单的。首先，我们来看下我们面对的是什么样的问题？
“订单分配即是在派单系统中将乘客发出的订单分配给在线司机的过程”
这是一个看似简单的，但实际上非常复杂的问题。说到这，可能有很多人就会问，能否就把我的订单分配给离我最近的司机就好了？
的确啊，实际上目前滴滴的派单算法最大的原则就是“就近分配”（70%~80%的订单就是分配给了最近的司机），据我所知，目前世界上其他的竞品公司（包括Uber），也均是基于这个原则分单的。
我们进一步来看这个问题，如果我们只按照就近分配，先到先得的贪心策略，是不是能最好的满足平台所有乘客和司机的诉求呢？答案是否定的，原因就在于，如果我们只基于当前时刻和当前局部的订单来进行决策，忽视了未来新的订单&司机的变化，还忽视了和你相邻的其他区域甚至整个城市的需求（注：在时序上来看，新的司机&订单的出现会导致，贪心策略反而违背了就近分配的目标）。这就是为什么这个问题依然是非常复杂的原因。
这里稍微有点抽象了，不过没关系，我们再来一步一步的拆解一下订单分配的问题，让大家有个更好的理解：
简单看，在我们的平台上，每一个时刻，都有N个订单在被乘客创建，同时有M个司机可以被我们用来进行分配，我们强大的平台能够为派单算法给出司机的实时的地理位置坐标，以及所有订单的起终点位置，并且告诉我们每一个司机接到订单的实时导航距离。
看上去似乎就非常简单了，我们直接把这个订单指派给这个司机就好了嘛。
“那么为什么有时候附近有辆空车却不能指派给你呢？”
实际线上的系统会比这里稍微复杂一点，原因一方面有可能是司机正好网络出现故障，或者正在和客服沟通等等导致司机无法听单，另一方面的原因是并不是所有的车都能够符合服务你订单的要求，最基本的策略其实是人工设定的规则过滤。举几个最基础的例子：
必须澄清的一点是这里的规则并不会造成分单时不公平的效果，而完全是为了业务能正常运行而设立的，这些策略承担着保证业务正确性的重要职责。
假设这两个司机都能够分配给这个订单，那么我们来看系统应该是如何分配的。
首先第一种情况是，同一时刻下，这两个司机和订单的距离都完全一样的情况下，系统应该如何分配？
刚才也说到，我们平台订单分配最大的原则是就近分配，当距离完全一样的情况下，当前我们系统上会主要考虑司机的服务分的优劣，服务分较高的司机会获取到这个订单（注：服务分对分单的影响，简单的理解可以换算为多少分可以换成多少米距离的优势，这块不是今天的重点就不展开介绍），再说明一下，系统用到的是地图的导航距离，而非人直观看到的直线距离，有时候差一个路口就会因为需要掉头导致距离差异很大；并且如果司机的定位出现问题，也会出现分单过远的情况。
那么我们来看第二种情况，如果A司机离的近，B司机离的远，系统怎么派？
这就简单了，根据就近分配的原则，我们会把A司机分配给这个订单。嘿嘿~~，假设我们再把问题设置的更加实际一点，当订单发出时，B司机已经在线并空闲，但是A司机还没有出现（没有上线，或者还在送乘客），但再过1s，离得更近的A司机突然出现可被分单了，假设我们使用先到先得的贪心策略，那么B司机就会被分给这个订单，那就违背我们希望就近分单的目标了：（。所以看上去简单，但实际情况下，算法还需要变的更好一些，这个问题我们把它叫做派单中的时序问题，我们后面再来看怎么解决。
最后我们来考虑最复杂的多对多的情况，这也是线上系统每天高峰期都需要面对的挑战，我们一般把这种情况会形式化为一个二部图的匹配问题，在运筹领域也叫做matching的问题，如图所示：
我们再把这个问题具象一点，假设这个时候我们有20个乘客，有20个司机，这些乘客都可以被这20个司机中的一个接驾，我们的系统需要把这20个乘客都分配出去，并且让大家的总体接驾的时长最短。听上去是不是有点复杂？我们套用下组合数学的知识，这其中可能的解法存在20的阶乘那么多，20的阶乘是什么概念呢？20*19*18*…*1=2432902008176640000，这个数巨大无比，想要完全的暴力搜索是绝对不可能的。这里需要更聪明的办法。
上面我们已经描述了什么是订单分配问题，并且它所面临的各种挑战，那么在这里我们来
聊一聊我们线上的派单策略是如何解决其中一部分问题的。
如何理解这个原则呢？我们说策略会站在全局的角度去达成全局最优，这样对于每一个独立的需求来看，派单可能就不是“局部最优”，不过可以告诉大家的是，就算在这个策略下，仍然有70%~80%的需求也是符合当前距离最近的贪心派单结果的。
接下来，这里会拿两个重要的派单策略的来进行介绍。（这里的内容主要是讲清楚策略的motivation为主哈，细节不再展开）
派单策略中最为基础的部分，就是为了解决上一节所提到的时序问题。这个算法几乎是所有类似派单系统为了解决这个问题的最基础模型，在Uber叫做BatchingMatching，我们内部也叫做“全局最优”或者“延迟集中分单”。
找寻司机和订单分配的全局最优是一个二分图匹配问题(bipartitegraphmatching)，一边是乘客、一边是司机，可用运筹优化中各种解决Matching问题的方法进行求解。
再和大家澄清一下，我们所采用的批量匹配的模式和大家所希望的，“把离我最近的司机派给我”的「就近派单模式」并不矛盾,我们也是寻求“乘客接驾时长最短”的最优解，大多数情况下也是指派离你最近的司机，但充分满足每一个乘客的“把离我最近的司机派给我”的个体需求,有些时候反而会导致部分乘客的需求无法得到满足，比如说下面这种情况：
我们采取的做法是,把距离较远的2号车派给1号乘客。
把1号车派给2号乘客,这样一来,1号乘客和2号乘客,平均等待时长缩短为5分钟,比就近派单,缩短了2.5分钟,总等待时长缩短为10分钟,比就近派单,缩短了足足5分钟。
通过提升全局的效率,才能转化为让更多乘客的需求得到满足。
刚才所说的批量匹配的方法，理论上能够保证那一个批次的匹配是最优的。但是这样就够了吗？
若想即时的获得最优派单结果，唯一的方法是利用对未来的预测，即进行基于供需预测的分单。这种想法说来玄妙，其实核心内容也很简单：如果我们预测出未来一个区域更有可能有更多的订单/司机，那么匹配的时候就让这个区域的司机/订单更多去等待匹配这同一个区域的订单/司机。
基于供需预测的分单有很大意义，但由于预测的不确定性，其实际效果很难得到保证。为此，我们使用了一种更有确定性的预测方式来进行派单，即连环派单。
“连环派单，即将订单指派给即将结束服务的司机，条件为如果司机的终点与订单位置很相近”
整个派单算法核心克服的是未来供需的不确定性，动态的时空结构的建模，以及用户行为的不确定性，对于这些不确定性我们现在更多采用深度学习方法对我们的时空数据&用户行为进行建模预测。
另外，我们的问题相对于传统推荐搜索领域，多了一层匹配决策，我们到底积攒多久的订单进行分配，对于每一个分配来说我们都面临着分或者不分，现在分还是未来分配，并且分给谁的问题，这个问题天生就可以建模为强化学习问题，目前在我们的系统中也引入了强化学习方法来优化更长期的收益。
除了不断去优化之前说到的派单问题，整个派单系统还面临着大量其他的挑战，包括如何利用快车优享等多个品类的运力进行跨层的最优分配，如何同时对用户&司机&平台短期长期等多个目标进行优化，如何同时优化预约&实时订单，如何在具备网络效应的场景下对算法进行评估，如果建立一个较为精准的仿真系统等等，这里既是挑战，也是AIForTransportation中大量新的重新定义问题和创新算法的机会。
总结
每天,我们的派单系统要面对超过3000万用户的叫车需求,高峰期每分钟接收超过6万乘车需求，平均每两秒就需要匹配几百到上千的乘客和司机。我们当前的派单策略相对于最初的派单策略版本，每天能够多满足百万以上乘客的出行需求。为了让更多人能更快、更确定的打到车，我们的交易策略团队将在更好的公平感知的前提下，不断地优化和打磨我们的派单算法，为乘客&司机创造更多价值。
当然当前的派单策略还有很多不够完善和完备的地方，本身也是一个相当复杂的问题和系统，一方面借此机会让大家对派单有更好的理解和认识，另一方面，也更欢迎大家对我们提出更多的宝贵意见，帮助我们进一步成长。