浅谈滴滴派单算法

标签: 算法 | 发表时间:2019-09-13 17:13 | 作者:滴滴技术
出处:https://segmentfault.com/blogs

本文作者:王犇 滴滴 | 首席算法工程师

导读:说到滴滴的派单算法,大家可能感觉到既神秘又好奇,从出租车扬召到司机在滴滴平台抢单最后到平台派单,大家今天的出行体验已经发生了翻天覆地的变化,面对着每天数千万的呼叫,滴滴的派单算法一直在持续努力让更多人打到车,本篇文章会着重介绍我们是如何分析和建模这个问题,并且这其中面临了怎样的算法挑战,以及介绍一些我们常用的派单算法,这些算法能够让我们不断的提升用户的打车确定性。

1.为什么我们需要更好的派单算法

说到滴滴的派单算法,大家可能感觉到既神秘又好奇,从扬召到抢单到派单,我们又是如何演进到今天大家的打车体验的呢,我们首先来看一看,好的派单算法为什么是出行行业不可或缺的能力?

回想几年前,当我们还没有滴滴的时候,只能在寒风或者酷暑中等待可能有、可能没有的扬招出租车,到后来可以从滴滴上呼叫一辆出租车,乘客可以在室内相对舒适的等待车辆的到达,从线上到线下,乘客的确定性得到第一次的提升,然而这还不够,抢单的模式注定我们的应答率天花板不会太高,在15年,滴滴上线快车业务,我们从抢单演进到了派单模式,乘客的应答率有了20个点以上的提升,很多时候能够全天能够高达90+(高峰&局部供需紧张应答率会相对吃紧),乘客确定性再一次得到大幅的提升,由此可见,派单模式为滴滴创造了巨大用户价值。

再看近年来不断兴起的O2O业务,从国内外的网约车公司,包括我们的友商Uber、Lyft都基于派单的产品形态进行司机和乘客之间的交易撮合,Uber上市的时候把派单引擎也作为核心技术能力放在了招股书中;再看我们的国内的外卖平台,核心派单系统的优劣也决定了整个平台的交易效率(单均配送成本)和用户体验(配送时长);最后,整个大物流行业近年来也不断在进行线上化的改造,如何撮合货物和司机,以及更好的拼单能力也是整个交易环节的关键和商业模式是否成立的前提。从运人到运物,派单引擎目前越来越多的被应用在现实的商业和生活中。

2.派单问题初探

言归正传,这里我们也来看一下,滴滴网约车平台到底是怎么派单的。首先,我们来看下我们面对的是什么样的问题?

“订单分配 即是在派单系统中将 乘客发出的订单 分配给 在线司机 的过程”

这是一个看似简单的,但实际上非常复杂的问题。说到这,可能有很多人就会问,能否就把 我的订单分配给离我最近的司机就好了?

的确啊,实际上目前滴滴的派单算法最大的原则就是 “就近分配” (70%~80%的订单就是分配给了最近的司机),据我所知,目前世界上其他的竞品公司(包括Uber),也均是基于这个原则分单的。

我们进一步来看这个问题,如果我们只按照就近分配,先到先得的贪心策略,是不是能最好的满足平台所有乘客和司机的诉求呢?答案是否定的,原因就在于,如果我们只基于当前时刻和当前局部的订单来进行决策,忽视了未来新的订单&司机的变化,还忽视了和你相邻的其他区域甚至整个城市的需求(注:在时序上来看,新的司机&订单的出现会导致,贪心策略反而违背了就近分配的目标)。这就是为什么这个问题依然是非常复杂的原因。

这里稍微有点抽象了,不过没关系,我们再来一步一步的拆解一下订单分配的问题,让大家有个更好的理解:

简单看,在我们的平台上,每一个时刻,都有N个订单在被乘客创建,同时有M个司机可以被我们用来进行分配,我们强大的平台能够为派单算法给出司机的实时的地理位置坐标,以及所有订单的起终点位置,并且告诉我们每一个司机接到订单的实时导航距离。

▍如果是1个订单、1个司机

file

看上去似乎就非常简单了,我们直接把这个订单指派给这个司机就好了嘛。

“那么为什么有时候附近有辆空车却不能指派给你呢?”

实际线上的系统会比这里稍微复杂一点,原因一方面有可能是司机正好网络出现故障,或者正在和客服沟通等等导致司机无法听单,另一方面的原因是并不是所有的车都能够符合服务你订单的要求,最基本的策略其实是人工设定的规则过滤。举几个最基础的例子:

规则A:快车司机不能接专车订单
规则B:保证司机接单后不会通过限行限号区域
规则C:为设定实时目的地的司机过滤不顺路区域
规则D:为只听预约单司机过滤实时订单
规则E:同一个订单只会发给一个司机一次
......

必须澄清的一点是这里的规则并不会造成分单时不公平的效果,而完全是为了业务能正常运行而设立的,这些策略承担着保证业务正确性的重要职责。

▍如果是1个订单和2个司机

假设这两个司机都能够分配给这个订单,那么我们来看系统应该是如何分配的。

首先第一种情况是,同一时刻下,这两个司机和订单的距离都完全一样的情况下,系统应该如何分配?

file

刚才也说到,我们平台订单分配最大的原则是就近分配,当距离完全一样的情况下,当前我们系统上会主要考虑司机的服务分的优劣,服务分较高的司机会获取到这个订单(注:服务分对分单的影响,简单的理解可以换算为多少分可以换成多少米距离的优势,这块不是今天的重点就不展开介绍),再说明一下,系统用到的是地图的导航距离,而非人直观看到的直线距离,有时候差一个路口就会因为需要掉头导致距离差异很大;并且如果司机的定位出现问题,也会出现分单过远的情况。

那么我们来看第二种情况,如果A司机离的近,B司机离的远,系统怎么派?

file

这就简单了,根据就近分配的原则,我们会把A司机分配给这个订单。嘿嘿~~,假设我们再把问题设置的更加实际一点,当订单发出时,B司机已经在线并空闲,但是A司机还没有出现(没有上线,或者还在送乘客),但再过1s,离得更近的A司机突然出现可被分单了,假设我们使用先到先得的贪心策略,那么B司机就会被分给这个订单,那就违背我们希望就近分单的目标了:(。所以看上去简单,但实际情况下,算法还需要变的更好一些,这个问题我们把它叫做派单中的时序问题,我们后面再来看怎么解决。

▍如果有N个乘客、M个司机

最后我们来考虑最复杂的多对多的情况,这也是线上系统每天高峰期都需要面对的挑战,我们一般把这种情况会形式化为一个二部图的匹配问题,在运筹领域也叫做matching的问题,如图所示:

file

我们再把这个问题具象一点,假设这个时候我们有20个乘客,有20个司机,这些乘客都可以被这20个司机中的一个接驾,我们的系统需要把这20个乘客都分配出去,并且让大家的总体接驾的时长最短。听上去是不是有点复杂?我们套用下组合数学的知识,这其中可能的解法存在20的阶乘那么多,20的阶乘是什么概念呢?20 1918 1= 2432902008176640000,这个数巨大无比,想要完全的暴力搜索是绝对不可能的。这里需要更聪明的办法。

▍如果有N个乘客、M个司机,一会再来几个乘客和司机?

这就是派单问题最大的挑战,我们不仅仅需要当前这个时刻的最优,我们要考虑未来一段时间整体的最优,新来的司机和乘客会在整个分配的网络中实时插入新的节点,如何更好的进行分配也就发生了新的变化,所以如何考虑时序对我们非常重要,这个问题在业内也被称为Dynamic VRP问题,这个Dynamic也就是随时间时序变化的意思,这也就是为什么,滴滴的派单问题远复杂于物流行业的相对静态的货物和路线的规划问题。假设我们知道了未来供需的完全真实的变化,仿真告诉我们,我们的系统有可能可以利用同样的运力完成1.2~1.5倍的需求量,这也是派单算法的同学持续为之努力的方向。

想起前段时间的吐槽大会,大家提到文嵩曾说我们的派单问题比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分钟。

file

我们采取的做法是, 把距离较远的2号车派给1号乘客。

把1号车派给2号乘客, 这样一来, 1号乘客和2号乘客, 平均等待时长缩短为5分钟, 比就近派单,缩短了2.5分钟, 总等待时长缩短为10分钟, 比就近派单, 缩短了足足5分钟。

file

通过提升全局的效率,才能转化为让更多乘客的需求得到满足。

▍基于供需预测的分单

“如果有先知告诉我们未来每一个订单的生成时间&地点,每一个司机的上线时间&地点,派单就会变成非常轻松的一件事”

刚才所说的批量匹配的方法,理论上能够保证那一个批次的匹配是最优的。但是这样就够了吗?

很遗憾,以上所述的延迟集中分单的策略只能解决部分的问题,仍不是一个完全的方案。其最大的问题,在于用户对系统派单的 响应时间 容忍度有限,很多情况下短短的几秒钟即会使用户对平台丧失信心,从而取消订单。故实际线上我们只累积了几秒钟的订单和司机信息进行集中分单,而这在大局上来说仍可近似看做时间维度上的贪婪策略。

若想即时的获得最优派单结果,唯一的方法是利用对未来的预测,即进行基于供需预测的分单。这种想法说来玄妙,其实核心内容也很简单:如果我们预测出未来一个区域更有可能有更多的订单/司机,那么匹配的时候就让这个区域的司机/订单更多去等待匹配这同一个区域的订单/司机。

▍连环派单

基于供需预测的分单有很大意义,但由于预测的不确定性,其实际效果很难得到保证。为此,我们使用了一种更有确定性的预测方式来进行派单,即 连环派单。

“连环派单,即将订单指派给 即将结束服务 的司机,条件为如果司机的终点与订单位置很相近”

file

与预测订单的分布相反,连环派单预测的是下一时刻空闲司机的所在位置。由于高峰期空闲司机多为司机完成订单后转换而来,预测司机的位置就变成了一个相对确定性的问题,即监测司机到目的地的距离和时间。当服务中的司机距终点很近,且终点离乘客新产生的订单也很近时,便会命中连环派单逻辑。司机在结束上一单服务后,会立刻进入新订单的接单过程中,有效地压缩了订单的应答时间、以及司机的接单距离。

▍如何做的更好

整个派单算法核心克服的是未来供需的不确定性,动态的时空结构的建模,以及用户行为的不确定性,对于这些不确定性我们现在更多采用深度学习方法对我们的时空数据&用户行为进行建模预测。

另外,我们的问题相对于传统推荐搜索领域,多了一层匹配决策,我们到底积攒多久的订单进行分配,对于每一个分配来说我们都面临着分或者不分,现在分还是未来分配,并且分给谁的问题,这个问题天生就可以建模为强化学习问题,目前在我们的系统中也引入了强化学习方法来优化更长期的收益。

除了不断去优化之前说到的派单问题,整个派单系统还面临着大量其他的挑战,包括如何利用快车优享等多个品类的运力进行跨层的最优分配,如何同时对用户&司机&平台短期长期等多个目标进行优化,如何同时优化预约&实时订单,如何在具备网络效应的场景下对算法进行评估,如果建立一个较为精准的仿真系统等等,这里既是挑战,也是AI For Transportation中大量新的重新定义问题和创新算法的机会。

4.总结

每天, 我们的派单系统要面对超过3000万用户的叫车需求, 高峰期每分钟接收超过6万乘车需求,平均每两秒就需要匹配几百到上千的乘客和司机 。我们当前的派单策略相对于最初的派单策略版本,每天能够多满足百万以上乘客的出行需求。为了让更多人能更快、更确定的打到车,我们的交易策略团队将在更好的公平感知的前提下,不断地优化和打磨我们的派单算法,为乘客&司机创造更多价值。

当然当前的派单策略还有很多不够完善和完备的地方,本身也是一个相当复杂的问题和系统,一方面借此机会让大家对派单有更好的理解和认识,另一方面,也更欢迎大家对我们提出更多的宝贵意见,帮助我们进一步成长。

最后,滴滴技术祝大家中秋节快乐!

同时也欢迎大家关注滴滴技术公众号,我们会及时发布最新的开源信息和技术资讯!

clipboard.png

相关 [滴滴 算法] 推荐:

浅谈滴滴派单算法

- - SegmentFault 最新的文章
本文作者:王犇 滴滴 | 首席算法工程师. 导读:说到滴滴的派单算法,大家可能感觉到既神秘又好奇,从出租车扬召到司机在滴滴平台抢单最后到平台派单,大家今天的出行体验已经发生了翻天覆地的变化,面对着每天数千万的呼叫,滴滴的派单算法一直在持续努力让更多人打到车,本篇文章会着重介绍我们是如何分析和建模这个问题,并且这其中面临了怎样的算法挑战,以及介绍一些我们常用的派单算法,这些算法能够让我们不断的提升用户的打车确定性.

滴滴打车的架构变迁

- - 行业应用 - ITeye博客
2012年成立的滴滴打车,仅用了三年时间就书写了:覆盖300个城市,用户数从2200万增到1.5亿,月活跃用户增长了600多倍(2014年平安夜当天,全国用滴滴打车出行人数超过了3000万人),打车成功率高于90%……这些永远会被铭记在移动互联网历史中的神奇记录. 而不为人知的是,支撑滴滴打车如此庞大用户数量的架构,以及那些曾无数次不眠不休应对挑战的技术伙伴们.

Apache与Nginx的点点滴滴

- - 开源软件 - ITeye博客
1、Apache默认是采用HTTP1.0的,开启HTTP1.1的方式如下:. 2、采用反向代理的参数:ProxyRequests off;. 3、通过Apache代理目标系统,可以修改目标系统response中Set-Cookie中的参数,.   如:domain、path等的修改,格式如下:.    例如:ProxyPassReverseCookieDomain .cnd.com .10.3.20.205.

滴滴顺风车设计总结

- - 人人都是产品经理
产品GM反复和我们强调业务使命,私家车出行在滴滴体系中的角色,私家车市场规模,业务模式概述,业务模式关键词,目标体系.. 使得我们很快明确了顺风车的产品定义,目标用户,主要功能,产品场景,产品特色和竞品的差异化以及未来顺风车的产品走向. 未来它将是一个每天改变千万人次出行的产品,它能让共享私家车成为一种连接人与人的生活方式..

滴滴从KV存储到NewSQL实战

- - DockOne.io
【编者的话】本文讲诉滴滴在分布式NoSQL存储Fusion之上构建NewSQL的实践之路. 详细描述Fusion-NewSQL的特性,应用场景,设计方案. Fusion-NewSQL是由滴滴自研的在分布式KV存储基础上构建的NewSQL存储系统. Fusion-NewSQ兼容了MySQL协议,支持二级索引功能,提供超大规模数据持久化存储和高性能读写.

自信源于生活的点点滴滴

- 大胡 - 左岸读书_blog
6.1是孩子的节日,我们可以向孩子们学习单纯、好奇、勇敢、跌倒了再爬起来,哭完便笑,懂得放下最爱的玩具,并且不断地成长. 虽然“初生牛犊不畏虎”,孩子却很容易在我们这个复杂的世界中一点点地失去“自信”,尤其是父母的言行举止. 当他在电话里满怀期望地提出:“妈妈,牛奶. ”你在外面一时不能满足他,告诉他具体时间:“回到家,妈妈给你拿,好吗?”经常忽视孩子的需要,会让他因不被重视而失去信心.

教育部介入戀愛 嬌滴滴申請國賠

- ĐƋɳƞѵїχ - 國寶級白目馮光遠在此
民進黨立委賴坤成質詢內政部長,女性消防員愈來愈多,女生向來「嬌滴滴」,如何救火. 這種歧視的言論,只好再勞民進黨女性消防員們出來滅火了. 教育部預定明年出版《二五必讀》手冊,教年輕人如何談戀愛、經營家庭及婚後將面臨的課題. 公部門介入戀愛,以後失戀者將有機會申請國賠. 不過如果提升到副總統候選人的規格來談這件事,建議還是學吳敦義,畫出拆房子的大餅,然後再說那是一個夢.

浅析表单设计的点点滴滴(一)

- - 百度MUX
表单,主要是负责数据采集的功能,需要访问者自己去填写,如访问者的姓名、邮箱、性别、地址、留言建议、设置密码、管理个人账户等等. 时下表单无处不在,成功的表单设计不仅能提高用户的满意度,更能收集更加精确的数据,相反失败的表单设计只会收集到错误杂乱的信息,可能会最终导致潜在用户的流失. 一、 组织表单的内容,给用户一个友好的引导.

如何看待滴滴收购 Uber 中国?

- - 知乎每日精选
看着那么多人不爽,那我就多说几条吧:. 1、一个半月以前,我曾经做了如上图的预测. 基于过往滴滴和快的之间的竞争、融资节奏和合并时间点;基于当年雅虎和阿里巴巴的交易模式;也基于出行市场的非零和博弈模式,做出这个预测本身并不难. 相信很多人都能想得到,只不过我碰巧给说出来了. 好几个媒体让我分析我为什么做出如此预测的,其实就是这么简单的逻辑,最后拍下脑袋,发条朋友圈啊…….

我对滴滴和UBER中国合并的垄断判断

- - 付亮的竞争情报应用
1、滴滴和UBER中国合并需经过商务部的反垄断调查,这个程序不能省. 2、滴滴、UBER中国合并是两个实体之间的市场行为,是保护股东利益的最佳选择. 3、 商务部无理由阻止滴滴、UBER中国的合并,网约出租车和传统的巡游出租车本身就有很强的替代关系,因此很难简单判定这一合并具有垄断性. 其实,传统的巡游出租车运营包含多种复杂的垄断在内.