外卖订单调度系统

调度系统定义

依托海量历史订单数据、骑士的定位数据、精准的商户特征数据，针对骑士实时情景（任务量、配送距离、并单情况、评级），对订单进行智能匹配，实现自动化调度以及资源的全局最优配置，在保证系统效率的情况下，最大限度地提高用户体验。

相关方的诉求

1. 用户：订餐能够在时间窗内尽快送达；
2. 骑士：每趟路线尽配送可能多的订单；
3. 商家：接单骑士尽快取餐；
4. 平台：以最小运力承担最大的配送压力，能够承担高峰时段激增的订单量；

要考虑的因素

1. 订单相关
   • 商户、用户位置
   • 用户期望时间
   • 预计出餐时间
2. 骑士相关
   • 现有订单的配送路线
   • 新增订单后配送路线的改变情况
   • 历史取送餐速速
   • 完成每个订单的预计时间
3. 环境相关
   • 当前配送的繁忙程度

系统发展历程

系统计算模式

外卖订单调度系统目的在于得到全局最优的配送方案，需要综合考虑上文提到的各个因素。这是一个极其复杂的多目标动态优化问题，可以表示为：

min(f1(x),f2(x),⋯,fn(x)),s.t.g(x)≤0

• fn(x) 表示单个指标的优化目标，例如：
  • f1(x): 即时订单的配送时间越少越好；
  • f2(x): 每单的配送距离越短越好；
  • f3(x): 骑士每天配送的单数越多越好；
  • f4(x): 订单的并行率越高越好；
• g(x) 表示业务的约束条件，例如：
  • 配送时间不能超过 30 分钟；
  • 单个骑士同时配送的订单上限；
  • 新骑士配送订单的最低保障；

需要解决的核心问题

一、路径规划

• 动态规划最优配送路线，合理并单，以最低运力配送成本最大化满足用户配送体验；
• 考虑用户期望时间的TSP问题；
• 构建模型综合评估用户体验与配送成本打分；
• 采用动态规划和模拟退火算法，求最优路线；

二、时间预估

数据 & 特征工程

• 特征 = 基础特征 + 组合特征 + 统计特征 + 稀疏特征

• 基础特征：订单信息，如商户ID、菜名、下单时间、未出餐订单、前序订单误差等

• 组合特征：核心基础特征的组合

• 统计特征：订单信息的数据统计特征，如均值、方差

• 稀疏特征：采用one-hot编码，各个菜品、商户、周几等作为特征维，构造稀疏矩阵

• 降维：PCA降维，减少内存消耗并在一定程度上避免过拟合

补充知识

• one-hot编码：

  • 定义：one-hot编码，又称为一位有效编码，主要是采用N位状态寄存器来对N个状态进行编码，每个状态都由独立的寄存器位，并且在任意时候只有一位有效。例如：

    自然状态码为：000,001,010,011,100,101
    one-hot编码：000001,000010,000100,001000,010000,100000

  • 解释：可以这样理解，对于每一个特征，如果它有m个可能值，那么经过独热编码后，就变成了m个二元特征（如成绩这个特征有好，中，差变成one-hot就是100, 010, 001）。并且，这些特征互斥，每次只有一个激活。因此，数据会变成稀疏的。

  • • 解决了分类器不好处理属性数据的问题；
    • 在一定程度上也起到了扩充特征的作用；
• PCA降维：
  • 降维：
    • 降维可以缓解维度灾难问题；
    • 降维可以在压缩数据的同时让信息损失最小化；
    • 理解上百个维度的数据结构很困难，两三个维度的数据通过可视化更容易理解；
  • 简介：Principal Component Analysis，主成分分析，是一种探索高维数据结构的技术。通常用于高维数据集的探索和可视化，还可以用于数据压缩，数据预处理等。PCA可以把可能具有相关性的高维变量合成线性无关的低维变量，称为主成分。新的低维数据集会尽可能的保留原始数据的变量。
  • 理解：例如：二维数据集降维就是把点投射成线，数据集的每一个样本都可以用一个值表示不需要两个值。三维数据集可以降成二维，就是把变量映射成一个平面。
  • 计算：
    • 第一步：用样本方差减去样本均值；
    • 第二步：计算数据的主成分，主成分是其协方差矩阵的特征向量按照对应特征值大小排序得到的；
      • 方法一：计算数据协方差矩阵；
      • 方法二：用数据矩阵的奇异值分解找协方差矩阵的特征向量和特征值的平方根
    • 第三步：把数据映射到主成分上，第一主成分是最大特征值对应的特征向量，要建一个转换矩阵，它的每一列都是主成分的特征向量。如果我们要把5维数据降成3维，那么我们就要用一个3维矩阵做转换矩阵。在本例中，将二维数据映射成一维，只需要用特征向量中的第一主成分作为转换矩阵。最后，用数据矩阵右乘转换矩阵。

• DNN模型：
  • 通过引入非线性映射，并包含多层感知器，海量的出餐时间训练数据，学习有用特征；
  • PCA降维影响小，但时间复杂度高；
• XGBoost模型：
  • 采用近似求解算法，找出可能的分裂点，避免选用贪心算法的过高时间复杂度；
  • 计算采用不同分裂点是，叶子打分函数的增益，选择增益最高的分裂点，作为新迭代树的最终分裂节点，构造新的迭代树；
  • 通过调节迭代树数目、学习倍率、迭代树最大深度、L2正则化参数等进一步避免过拟合；

补充知识

• L1正则化：权值向量 w 中各个元素的绝对值之和，通常表示为 ‖w‖1；可以产生稀疏权值矩阵，即产生一个稀疏模型，可以用于特征选择；
• L2正则化：权值向量 w 中各个元素的平方和，通常表示为 ‖w‖2；可以防止模型过拟合；

三、决策模型

• 骑士体验：
• 用户体验：
  • 订单剩余时间
  • 骑士完成时间
  • 订单准时性
• 配送效率：

四、分配方案

Greedy + 多轮 KM 算法方案：

• Greedy分配解决特殊业务需求相关；
• KM算法找到其余全局最优的分配方案；

KM求解骑士和订单全局最优的分配：

调度系统先对骑士和订单组（根据骑士位置、身上的单量等）打分，得到订单组和骑士的打分矩阵，然后根据业务需求优先分配指定订单，其他的根据KM算法找到骑士和订单的最优分配方案。

补充知识

• 二分图：是一种特殊的图，它的顶点可以被分成两个不相交的集合（U 和 V），并且同属一个集合内的点两两不相连（EU=EV=∅）。

  • 匹配（Matching）：是边的集合（M⊂E），其中任意两条边不共点（∀e1,e2∈M s.t. e1∩e2=∅）。

  • 最大匹配：如果二分图里的某一个匹配包含的边的数量，在该二分图的所有匹配中最大，那么这个匹配称为最大匹配。

  • 完备匹配：如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配。

  • 增广路径（Agumenting path）：如果一条路径的首尾是非匹配点，路径中除此之外（如果有）其他的点均是匹配点，那么这条路径就是一条增广路径。

• 匈牙利算法：

  • 核心思想：由于二分图的最大匹配必然存在（比如，上限是包含所有顶点的完全匹配），所以，在任意匹配的基础上，如果我们有办法不断地搜寻出增广路径，直到最终我们找不到新的增广路径为止，我们就有可能得到二分图的一个最大匹配。

  • 具体例子: 男女生搭配问题

五、供需平衡

配送时长预估计模型

• 基于现有状况、订单增速、消化速度、天气、当前手段等多维特征，使用XGBoost模型回归预测未来五分钟进单的平均配送时长

• 分商圈、分时段、多模型的精细化预估

• 分布式、多线程、并行计算最佳分割点，满足海量数据的实时性要求

• 在供需失衡之前，即实施调控手段

单量调控模型

• 通过价格平衡未来的进单量和系统可承载的单量

• 基于GBRT对未来进入单量的实时预测

• 贪心算法求解系统最佳承载单量

• 根据当前系统状态匹配最佳的溢价手段使之回归至最大可承载单量的调控模型

• 在供需失衡之时，实施最有效的调控手段

---