案例1：订单分配策略在线视频

OK 那接下来

就是我们会挑两个例子来

做一个展开

就是希望大家能通过这个例子

能够了解

就是说我们在我们这个场景下

怎么去把这些算法

把这些模型去落地解决问题

第一个是订单分配

订单分配这个问题

刚才也说了非常简单

就是我怎么样把一个订单

在正确的时间交给正确的人

这个相当于

是我怎么去分活分配任务

这个可以说

是影响我们的配送效率

非常重要的

一个关键的一个主要环节

就是它的意义很大

它对我们的用户体验骑手体验

等等都有非常大的影响

那这样说有点抽象

我在这截了一个图

这个图

是我们实际的一个配送场景

这个图上

每一个小圆点是一个骑手

当然这个图

其实就是中关村配送区

它的一个在中午的一个图

这个订单分配的这个意思是说

像中关村这种区域

可能每分钟在中午的时候

会有四五十个订单新产生

同时中关村配送区

可能大概会有三百个配送员

有三百个骑手左右

我怎么样

在一个非常短的时间里边

把这新产生的四五十个订单

分给这三百个配送员

使得他们整体的效率更高

用户体验更好

是这样的一个问题

所以这个从学术的角度

可以归到动态的VRP

这个问题的这个范畴

但是接下来可以看到

它其实比那个问题要更复杂

因为它有一些更多的场景

那其实来一个订单

我们要对这个订单

做一个合理分配的话

其实考虑的因素很多

除了说我分给要考虑说

是不是能够准时送达

我要分给这个骑手

还要考虑说他使用的工具

他是不是足够顺路

包括说他对这一块是不是熟

是不是来过这个商家

他对这块上下楼的情况怎么样

还有像一些品质要求

比如说像咱们点的冷饮面食

我们不希望有太长的配送时间

还有这个餐箱容量

等等这些因素

都是在这个配送里边需要考虑的

像早期也说了完全靠人工

你人工去做这样的一个分配

我们以前也调研

就是一个人来分配的话

最早可能得需要一分钟

他要看看这个订单

周边的人是谁比较合适

但是在这样的一个订单密度下

人工是不可行的

但是像早期

我们还试过一段时间抢单

就是把这个订单

直接扔给所有的配送员

他们谁想送哪一个就送哪一个

去抢

但这个模式优点也很显然

就是比较容易送

骑手的体验会比较好

但是它的缺点也非常明显

就是它的效率特别低

很多骑手在中午的时候

都在忙着去挑单

看哪一个比较好

那他们的体验太好了

反过来就会影响我们用户的体验

像早期的外卖都会很多订单在那

可能半小时40分钟都没有人抢

那这个时候

那这个用户的体验就会非常糟糕

前期可能承诺一个小时

但事实上得要两个小时才能送达

这是一个非常难处理的问题

从技术的角度它应该属于这种

多目标

另外一个是强随机

这样的一个动态优化问题

那在这样的一个场景下

其实简单来说

我们认为需要做四项核心的决策

第一个

是进行一个配送的路径规划

说白了就是说怎么送

就是如果这个订单

我给了这个骑手

他应该会怎么去规划线路

他应该是先去哪一单

再去送哪一单

就这个过程

这是一个独立的单元问题

第二个是订单指派

就是说我这个订单应该给谁

应该交给谁来送

这个是第二的决策问题

第三个是压单

也就是说

有些订单其实我并不是说

来了马上就要分给一个人

这个并不是最好的

因为比如说有些场景下

我给了他他也未必能马上送

但是可能过一段时间

有别人会比他更为适合

因为刚才也说了

我们这个场景

其实有大量的随机因素

所以说我们需要压单

那这个订单压到多长时间

什么时候应该去不压单了

这个也是一个独立的

一个这样的决策环节

那么第四个就是运单的改派

就是即便我把这一个订单

已经分成了一个骑手

但是有可能因为比如说

商家的出餐是有随机因素的

再比如说用户上下楼

到用户这你给用户打完电话

用户说马上下来

事实上等了四五分钟再下来

这种情况也是可能发生的

所以这种随机因素都会导致说

这个订单在你这合适

但是再过一段时间

不一定最合理了

这时间就需要改派

当然有从路径规划到指派

到压单到改派

四个核心的决策问题

那么从技术复杂性来看的话

就是从建模 优化 评估这三个方面

应该说都有它自己的难点

比如说建模最主要的是说

我就解决这个问题

所需要的这个基础数据

应该说非常的不准确

再一个

就是优化目标是频繁变化的

它的目标是不稳定的

这个我觉得可能大家

如果做过一些实际的项目

会有这方面的体会

就是你的目标不稳定

那不同的时候怎么去定目标

这个目标怎么样去量化

这个其实往往是最头痛的问题

而且这个问题单纯从技术的角度

未必那么容易去解决

再一个是优化

优化的话这个难度比较容易刻划

它首先是一个NP-Hard

是一个组合优化问题

再之

它允许的这个运算时间比较短

我们内部是要求

基本上在3-5秒钟之内

必须是完成这所有的计算

这个原因也很容易理解

比如说我在采集数据的时候

我认为骑手是在一个位置

但他有可能过个一段时间

比如过个半分钟

他就已经走到了非常远的位置了

如果这个时候

我这个算法运营时间特别长了

那隔一段时间

再去把这个决策直接发给他

那这个解显然

就不是在这个新的时间下

显然就距离这个最优

就会比较远了

所以说这个

我们这时间的要求是非常高的

再一个是随机的因素多

就是未来会下什么订单

出餐时间

甚至骑手路上需要消耗多长时间

碰不碰红绿灯等等都是不定的

再一个是评估比较难

就是如果大家对这个互联网的评估

有所了解的话

就知道通用的是A/B test

我们这之所以

不能很好的用A/B test

主要是因为一个区域的配送

是互相耦合的

一个骑手不是只接一单

他是同时接很多个订单

那我们就没法按用户或者按骑手

或者按订单去分流做这样的评估

那我们只能按区域

那按区域的话问题就来了

我们这个几千个区域的量级

又不足以消除AA的影响

就是AAtest它没法做到正交

所以说这个是一个问题

和为了解决这个问题

后来我们做仿真

其实一个主要的出发点

就是为了解决一些订单的分配

或者压单改革改派

这样的策略到底好与不好

怎么评估这样的一个问题的

如果一个策略一个2.0的版本

假设比1.0的版本好很多

好很多的情况下

我前后一对比就能发现

它的一些KPI指标

有比较明显的变化

但是如果只好一点点

只好1%或者0.5%

那其实意义是很大的

但是问题在于一个区域

它的这个指标本身的波动

都往往有5%左右

就我们只看一些比如说准时率

配送时长这样的指标的话

波动很大

我们就没法说

只去通过前后对比去看这个问题

所以当然离线的评估

就是说我们怎么样

去更好地搭这么一个仿真平台

这个也是一个很困难的事情

就是因为真实的机理模型

真实的逻辑都是很复杂

我们很难用一个简单的模型

去刻划骑手的每一次配送过程

那围绕这些个问题

我们其实也做了

很多个版本的迭代

从早期1.0 2.0

基本上是说做一些单点的应用

让这个模式先让它跑起来

先让骑手可以

去把这个订单直接分配

先不考虑压单

改派或者说一些细分的场景

像其中是不是熟悉先不考虑

先让这个模式给它直接转起来

那么从2017年开始

我们就针对一些单元的问题

怎么去充分地优化

做了大量的工作

包括说怎么样

去考虑这个参数的随机性

做一个更好的一个评估和优化

再一个是自动改派 动态压单

这个在2017年给它最终上线了

另外一个就是要考虑未来的订单

就是目前这个地方

我这样分可能是合理的

但是如果说我预测未来

这个地方还有很多订单

那我就要考虑为未来预留运力

为未来考虑更好更高的合单概率

也就是说这个时候我们目标

变成不是说当前的一个静态最优

而是说累积下来一天下来

我们整体的KPI能够改进多少

所以在这个时候2017年

主要是做了

这种单元层面的优化工作

那其实从2017年底到2018年

我们进一步在多维度的协同

怎么样去做一个全局优化

这个层面上做了很多工作

包括说怎么样去更准确的

估计一些基础的数据

怎么样更好的

把这个定单的分配策略

和上游比如说区域规划

和商家的配送范围怎么划

这些信息之间需要协同起来

比如说我们通过

调度去提炼很多信息

再把这个信息反馈给他们

他们再更好地去优化配送范围

优化这个区域怎么划

这样的一些问题

再一个就是全城调

刚才也说了刚才就是

北京其实划成上百个区域

各个区域可能是独立的

但事实上独立也有它的问题

它虽然它的优势

是管理上比较方便

业务模式比较清晰

但是它的弊端

就是如果一个骑手跨区了

可能要空返回来再去接单

所以说怎么样

去解决这个层面的问题

我们就要做这个全城调度

但全城调度对这个技术

对工程的要求是相当大的

所以这个也是目前正在做的

一个比较重点的项目

OK 那接下来我会说一下

就是解决这个问题基本的一个架构

这个架构就是底层

我们会有大量的业务数据

特种工程的数据

还有轨迹数据

那在这个基础之上

大量的使用机器学习的方法

对一些订单分配需要的基础数据

做一个准确的估计

在这个基础之上

在下游

再利用运筹优化的这些算法

来解决像路径规划派单改派

这些层面的一个一个问题

具体举一些例子

比如说我们怎么样去准确的获取

这个分配决策需要的基础数据

在这至少我们把这个数据

分为这么几类

我们都管它叫用户画像

或者骑手画像或者商家画像

这些其实可以说

对于这个基础数据这一块

占了我们一半以上的时间

因为有些地方

可能我们认为它事实上

没有技术难度

但是要做的足够好

其实也是非常难的

比如说举一个例子

像商家的位置

商家的位置在哪儿

其实显然是一个非常基础的数据

但是最早期我们就会发现

其实很多商家标的位置是不准的

它有线下的很多因素

比如说这个就是业务管理

这个层面的一些问题

或者说它自己标

人工操作也不是那么精确

我们就需要利用这个骑手的行为

他什么时候

到这停下这个电动车了

什么时候取餐了

要利用这个信息

再利用矩列的方法

去确定说每个商家

大体上应该是在什么位置

就要用到一些这个方面的方法

再一个比如说两点之间的距离

这个也是一个很底层的数据

就是因为我们做这种派单

很关键的一个考虑点

就是要让骑手顺路

减少路上的消耗能够提升效率

那其实两个点之间的距离

可以说简单的

就是我们通过一些地图的引擎

比如说通过腾讯腾图去抓一些

那么从这个地址A到地址B

大概需要多少米

需要的时间大概是多少

这种做法大部分情况

都是没有问题的

但是可能1%的情况

或者千分之几的情况

它不是很准

但在早期这种做法

是没有什么问题的

但是到了后期

它这个问题就会变得比较大

就是我们怎么样

利用这个骑手轨迹

对这个非常小的这些case来矫正

这个也是一个很独立的课题

再比如像这个出餐时间

交付难度等等

在这进一步举一个例子

就是我们管它叫ETR

这个意思是说一个骑手

假设他要送三个订单

他会先取订单A再取订单B

再取订单C

然后再依次送订单的A B C

那这个数据确定了

这个时间大概是多少

他什么时候能完成订单A

什么时候能够从订单B这取餐成功

取餐完成

这个时间的估计

其实是非常重要的一个单元问题

那这个问题

我们就需要对骑手的这个行为

做一个非常细致的一个拆解

然后怎么样

去把这个骑手的每一段

你是从电动车上下来

上楼去取餐等餐到路上行驶

到用户那去交付

这样的一个过程

就怎么样去准确的估计

是这样的一个问题

那对于这样的一个问题

其实我们也是利用

这个机器学习和优化算法

相结合的这个策略

机器学习基于这个骑手的

这些大量的轨迹数据

来估计一个商家什么时候出餐

上下楼时间 路上的时间

包括骑手如果熟悉这个地方

他会花多少时间

如果没有来过他又花多少时间

如果只来过一次两次

大概会花多少时间

这些信息都要有一个准确的估计

然后通过一个优化算法

再去优化里边的一些大量参数

就说我们先建立一个带有

大量未知参数的一个机理模型

然后再利用实际的骑手轨迹数据

对这个参数一个最优估计

那这个估计的效果也是比较好的

现在可以说我们后台来看

我们估计给你一个任务

大概估计你什么时候能够取餐

这个平均的误差

也就在4分钟左右

那么下一个点就是说

想说一下这个优化算法

因为刚才其实是属于我们

怎么样去准确地估计一些值

那么第二个就是优化算法

优化算法我相信大家

如果大家学过机器学习

包括运筹

对这个方面是有一些深入理解的

应该说像基本的原则

就是从我的角度来体会的话

就是我们如果

要想得到一个高效的算法

必须和这个问题特征

和一个算法的机制

做一个高效的融合

其实这个理念

应该说是比较普世的

就是像我们这个场景下

因为这个问题太复杂

它不是一个简单的线性规划

或者简单的一个混合指数规划

这样的一个问题

它的目标函数

和一些约数都是非线性的

那在这个场景下怎么去

快速地优化

因为我们又是一个实时优化问题

容许的运行时间非常短

所以在这个时候

我们要想让这个算法

做到足够的好

就必须是要融入大量的

跟问题有关的信息

包括跟这个算法的机制相结合

说多一点其实像大家

可能日常用的像线性规划

它其实也是这样的一个原则

它利用线性模型的

一些最优解的特征

然后设计一个机制

去最快的找到它

在一些复杂的问题的这个场景下

这个理念仍然是非常适用的

再一个场景就是说

我们怎么样去提升整体的效率

这个点是说我们的配送系统

其实不是说你有一个好的算法

就能最后产生好的效果

它最终的执行是要靠骑手

一单一单的去完成配送

所以从一个控制系统的角度

就是你的执行机构

是一个一个的人

那么怎么样要这批人

他们能够充分的和系统

做到一个高效的交互

也是一个非常关键的问题

那其实可能大家在以后

在接触工业界问题的时候

这个也是一个

非常基础的思维习惯

就是不是专门关注算法本身

不是说唯算法为王

而是需要

更系统地去思维一个问题

怎么样去达成

一个业务层面的目标

那我们这其实就在骑手交互这

做了很多工作

比如说要给他进行

尽量好的信息展示

给他一些决策建议

应该怎么走

如果他没有单的时候

告诉他哪些地方单比较多

他应该过去去接单等等

然后这个地方就是说

我们就是做了一个骑手智能助手

这个主要的任务

就是说让骑手在路上

不用看手机能够完成

整个接单配送这样的一个过程

甚至在这个场景下

也有很多人工智能

可以融入的地方

比如说我们就做了

一个骑手推荐打电话

就是骑手

如果说我们在一些场景下

需要用户下楼去取

但如果骑手到楼下再给你打电话

用户就会下来需要一些时间

那这个对骑手来说就要浪费

两分钟或者三分钟的时间

那我们就希望说根据这个数据

来判定说骑手快到的时候

应该给他打电话

就这个最优的时间推荐

骑手可以拒绝也可以同意

就通过若干这种很细小的环节

其实都是提升效率的点

最终这个骑手的效率

都是这么一分钟一分钟去压缩

去给它做这个优化出来的

那这样的一个策略最终基本上

我们就每一个订单的执行

我们就优化骑手

大概一分钟的时间

这个其实也是一个非常可观的