1、滴滴派单主要模式

业务场景： 一个订单被派给多个司机，司机根据自己的喜好选择接受或拒绝
目标： 最大化一次派单成单率
关键问题： estimate the probability of each driver's acceptance of an order
算法方案 ：步骤1，估计每个司机的接单概率；步骤2，将各个司机接单率作为输入，最大化派单成功率

2、参数选取

• 订单-司机关联特征：接驾里程、订单推送给多少个司机、订单是否与司机当前驾驶方向一致
• 订单特征：起点到终点的距离、ETA、终点类型（医院、机场、学校、商务区等）、规划路线的路况、目的地历史上的订单频率
• 司机特征：历史接单率、司机活跃地点、接驾里程偏好、最近接单率等
• 补充特征：特征日、特征小时、司机数、附近运单数

3、模型描述

使用LR和GBDT模型

约束表示，一个司机一个时刻最多只能派一单

目标是使这一批订单这一次派单的总体成单率最高。

使用启发式算法解上述问题。

初始解：对每个司机，派给他接单率最大的订单，然后计算每一单的成单率，得到平均成单率

迭代：对运单i，找到没有被派到i的司机集合U，对U的每个司机k，如果把i派给k，平均成单率提高，则改派

4、评估方案

• 成单率
• 平均接驾时长
• 平均派单时长
• 取消率
• 人均单量

二、Uber

1、算法概述

全局优化算法Dispatch Optimization

<1>降低燃料成本

当您了解调度总成本（包括影响真正节省燃料成本的隐藏成本）时，有效的燃料计划会显著提高。

获取实时数据以改变燃料需求，最大化批量折扣并规划最有利可图的路线。

<2>提高资产利用率

提高资产利用率的有效策略是从网络中获取正确的数据，以便在为未来需求做准备时做出实时决策。

通过更好的资源分配，最大化每日负载历程匹配正确的驱动程序以获得最佳负载并控制盈利能力。

<3>最小化空的里程

通过规划路线并匹配驾驶员的预计到达时间来最大化每日行驶里程数，以减少等待时间。

使用完整的产品套件来识别可能导致空里程的网络问题，使用精准数据平衡容量

<4>集成电子测井数据

通过为负载规划人员提供工具以提高网络可见性，使电子日志过渡更顺畅。

使用驱动程序和加载负载仪利用的预测装载计划驾驶室的数据并更改执行计划。

<5>管理服务时间

持续的安全性和合规性对企业有利。在整个规划过程中和在路上有效地使用每个司机的HOS。

使用完整的产品套件，可以获得可能影响盈利能力和负载征求的驱动程序HOS数据的端到端的可见性

<6>保留卡车司机

通过选择驾驶员首选路线（例如特定卡车停靠点）以及在周末关闭时将负载匹配到司机，与您的驾驶员建立牢固的关系。

让驾驶员准时回到家，同时考虑对燃料成本的影响，以保持领先的需求

<7>降低通行费用

当整个车队成倍增加时，通行费成本增加。获取有关路线的实时建议，以避免收费或提前准备通行费。

自动计算通行费用以确定最便宜的路线

2、Uber的算法解读

均可以随着数据量的不断增加进行学习~所以只会越来越准，只会越来越准，只会越来越准。

1.计算车辆预计到达的时间算法
一开始使用的算法是Google这个行业已有巨头开发出来的API算法，后来发现其算法的误差较大。对于出租车较多的城市，这般不准确很有可能会使得用户放弃二次使用。不妨设想下，你站在路边等你叫的Uber，这时一辆空车开过你身边，你看了下手机，Uber提示说“你的专车1分钟后到达”，你想想算了就一分钟，过了这一分钟后你发现车还没来···错过那辆车的后悔之情会让你的每一分钟都不好熬。

Uber想，那就自己来组建开发团队。然后招呼来了火箭研究科学家，计算神经学专家和核物理学家。听说一开始很不顺利，因为原始数据太少，不过像这种最终会得到真实数据的算法都能根据自己的预测和真实值之间的差别进行自主学习，so，预测会越来越准~他们最后捣鼓出来的算法将预测准确度提高了3分钟，更重要的是，这是个平均值。3可能是这般得出的：（2+2+2+2+2+2+2+2+2+12）/10=3，看到没，Google那个算法中12的大误差被消灭了哦，恭喜Uber，少损失了一个用户~

2.浮动溢价算法
设想下，一个演唱会结束的时候，公交车大都停运，而此时这附近的出租车肯定出于一种供不应求的状态。我们都嗨了，也都累了，贵点就贵点早点到家就行。所以，Uber的“特定区域随时浮动定价算法”对于土豪和次土豪而言是很不错的。而且，这个提价的信号一旦启动，对于附近稍远的司机而言是非常有诱惑的，不过，当你们来了之后还是不是这个价就另说了。高收益怎能没有点风险和机会成本。而且啊，Uber瞄准的这个市场，有效供给和有效需求太太容易被获得了，有什么理由不借助价格来推动供需平衡呢？

所以现在的情况是，在用户的等待时间出现相对陡峭的上升趋势时，便会触动提价算法。而这些情况大部分时候都是可以预测的~不过在这个算法神乎其神之前，遇到 这篇报道 中描述的问题的可能性也不低，超可怕~

不过真能做到的话就天下无敌啦~看看咱们现在的便利店，同一条街上卖矿泉水的都会定价不一样（没错，我就是在乎这几毛钱，而且当用百分数来考察时，5毛就是2元矿泉水的40%啊！）

anyway，尊重市场的产品最终会得到了来自市场的回报，我就很讨厌说“罗斯福拯救美国经济那个论断”，都已经到了最低谷，谁来都会变好的。只是来的那个人，本身要能给人力量，说白了就是能忽悠。

3.如何在一个城市中部署最少的车，来有效满足全城的需求（travelling-salesman problem）

4.自动匹配算法
Uber采用的是一对一的自动匹配算法，国内滴滴的黑文说：Uber匹配的效率贼低啊！不如我们用户至上把需求发给好几个人让他们抢单。

先把滴滴这种模式的弊端放一放，我们来看看Uber算法到底是怎么样的：只把一个用户的需求发给一个司机，然后给司机15秒钟响应~如果不接的话就算接单失败，然后再发给另外一个司机，直至有司机接单为止。乍一看这个过程耗时很长，不过，当司机拒单的成本很大时，拒单情况基本不存在时，一对一派单的效率就很高了。而Uber是如何让司机拒单率保持在一个很低的水平？

方法如下：
用好补贴这个经济杠杆，人民司机啊，你不是对大额补贴趋之若鹜吗？如果拿到补贴的前提是1)不低于80%的接单率；2)较高的评分；3)几乎不存在的投诉；4)```其余各种各样保证用户体验的要求。那么一对一派单这个系统就有了最大的帮手~

首先看下第1点，80%的接单率需要你在5次系统派单中最多只能拒绝一个单，如果你拒绝了2次，也有办法补救，那就再跑5单呗，这个时候，系统给的任意5单你都不能拒绝。那么在这10次派单中，你一共接单8次（3+5）,唉，总算达到了补贴的门槛之一，且慢还有之二。

第2点评分。没错，和上面的道理差不多，为了达到4.8的综合评分，你需要尽量拿5分哦，万一4分拿多了怎么办？多跑跑，世界上还是好人多啊~

看到没，这个补贴的门槛让司机慎重选择上线等待客户这个状态，一旦上线就是Uber的人啦~于Uber而言，不用算法就筛选出了当下最有效的资源（那句老话怎么说的，占着茅坑不拉屎的人几乎没有~）。而当在线资源的可调度性很高时，全局资源优化就成了一件分外可行的事，听说最近Uber优化了派单系统，采用了一个能考虑全局指数的算法——Dispatch Optimization，不得不说这是很大一盘棋的起点。中国的孩儿们，光快有啥用呢？这个策略的远大作用还可以慢慢挖掘

滴滴的劣势。1)太不尊重人了，让司机总在神经紧绷；2)明明都是烧钱，看Uber顺便优化了司机素养。

滴滴的本质是提升接单率，所以把一单派给很多人抢，这样可以保证订单的消化，主要是考虑企业自身的盈利。

反看Uber出了溢价这个问题，其他大部分是以司机(用户)为主，保证推荐的司机没人跟他抢所以只派一个人，其他路线规划考虑的也是司机的利益，当然它的补贴也是变相的对司机进行控制，但是总体上还是比较人性的。

桔妹导读：HDFS中默认的3副本方案在存储空间和其他资源（例如网络带宽）上有200％的开销。对于冷数据，使用纠删码（ErasureCoding，EC）存储代替副本存储是一种非常不错的替代方... 一个简单的 派单 算法 。有一群可接单人员，来了一个单子，需要给他们 派单 。 派单 规则，就是均衡分配：找到谁手上的单子最少，就分配给TA；如果找到的人多于1位，则从中随机抽取1位 抛砖引玉，目前我的思路： 从正在执行的单子中，计算每个人手中的单子数量 遍历所有人中，找到持有最小单子数的人员集合 从集合中随机抽取一位，把单子分配给TA 有更好的 算法 ，麻烦提供一下，感谢！ public static void main(String[] args) { arrangeOrder( 本文作者：王犇 滴滴 | 首席 算法 工程师 导读：说到 滴滴 的 派单 算法 ，大家可能感觉到既神秘又好奇，从出租车扬召到司机在 滴滴 平台抢单最后到平台 派单 ，大家今天的出行体验已经发生了翻天覆地的变化，面对着每天数千万的呼叫， 滴滴 的 派单 算法 一直在持续努力让更多人打到车，本篇文章会着重介绍我们是如何分析和建模这个问题，并且这其中面临了怎样的 算法 挑战，以及介绍一些我们常用的 派单 算法 ，这些 算法 能够让我们不断的提升... 1 批量匹配（全局最优） 派单 策略主要的原则是：站在全局视角，尽量去满足尽可能多的出行需求，保证乘客的每一个叫车需求都可以更快更确定的被满足，并同时尽力去提升每一个司机的接单效率，让总的接驾距离和时间最短。 这个 算法 几乎是所有类似 派单 系统为了解决这个问题的最基础模型，在 Uber 叫做Batching Matching， 滴滴 叫做“全局最优” 或者 “延迟集中分单”。 2 基于供需预测的分单（大数据预测） 利用对未来的预测：如果我们预测出未来一个区域更有可能有更多的订单/司机，那么 白话解读离线learning部分本质上是将任意时刻任意空间位置离散化为时空网格，根据 派单 记录(含参加调度但无单的司机)计算该时空网格到当天结束时刻的预期收入。关键问题：怎么计算预期收入？动态规划思路：假设总共有时刻区间为[0, T)；先计算T-1时刻的所有网格的预期收入(此时未来收入为0，只有当前收入)，其本质就是计算当前收入的均值；然后计算T-2时刻的所有网格的预期收入；...；以此类推这样的话...