浅谈派单算法：滴滴出行里车主是如何接到平台派单的？( 三 ) _派单算法

想起前段时间的吐槽大会，大家提到文嵩曾说我们的派单问题比alpha go还要难，其实这两个问题还确实有点相似，都是在超大的搜索空间中找到一个近似最优的解，而alpha go则会在一个更加明确的游戏规则和环境中进行求解，它的难点在于博弈，而我们的派单问题难点在于未来供需不确定性&用户行为的不确定性。近年来在学界，已经有不少尝试在利用类似alpha go的技术进行VRP&TSP等方向的探索，强化学习结合运筹理论是未来运筹界非常前沿的方向之一（非技术同学可以跳过此处：））
3.派单算法简介上面我们已经描述了什么是订单分配问题，并且它所面临的各种挑战，那么在这里我们来
聊一聊我们线上的派单策略是如何解决其中一部分问题的。
在介绍具体策略之前，首先我们来说一下派单算法大的原则，目前派单策略主要的原则是：站在全局视角，尽量去满足尽可能多的出行需求，保证乘客的每一个叫车需求都可以更快更确定的被满足，并同时尽力去提升每一个司机的接单效率，让总的接驾距离和时间最短。
如何理解这个原则呢？我们说策略会站在全局的角度去达成全局最优，这样对于每一个独立的需求来看，派单可能就不是“局部最优 ” ，不过可以告诉大家的是，就算在这个策略下，仍然有70%~80%的需求也是符合当前距离最近的贪心派单结果的。
接下来，这里会拿两个重要的派单策略的来进行介绍。（这里的内容主要是讲清楚策略的motivation为主哈，细节不再展开）
▍批量匹配（全局最优）
派单策略中最为基础的部分，就是为了解决上一节所提到的时序问题。这个算法几乎是所有类似派单系统为了解决这个问题的最基础模型，在Uber叫做Batching Matching ，我们内部也叫做“全局最优” 或者 “延迟集中分单” 。
这个Idea其实也非常直观，由于用户订单的产生和司机的出现往往并不在同一时间点，在时间维度上贪婪的分单方式（即每个订单出现时即选择附近最近的司机派单）并不能获得全局最优的效果。一个自然的想法就是先让乘客和司机稍等一会，待收集了一段时间的订单和司机信息后，再集中分配。这样，有了相对较多、较密集的订单、司机后，派单策略即可找到更近更合理的派单方式了。
找寻司机和订单分配的全局最优是一个二分图匹配问题 (bipartite graph matching) ，一边是乘客、一边是司机，可用运筹优化中各种解决Matching问题的方法进行求解。
和再大家澄清一下，我们所采用的批量匹配的模式和大家所希望的， “把离我最近的司机派给我”的「就近派单模式」并不矛盾,我们也是寻求“乘客接驾时长最短”的最优解，大多数情况下也是指派离你最近的司机，但充分满足每一个乘客的“把离我最近的司机派给我”的个体需求, 有些时候反而会导致部分乘客的需求无法得到满足，比如说下面这种情况：
当编号1和2两个乘客同时叫车, 如果完全按照“就近派单”的模式, 虽然可以让1号乘客先被接单, 但是2号乘客会因为接驾距离较远, 导致等待时间变长, 甚至因为最近的司机超出平台派单距离, 导致2号乘客叫不到车。1、2号乘客总等待时长15分钟, 平均等待时长7.5分钟。