美团智能配送系统的运筹优化实战-笔记

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

本文为美团文章学习的笔记整理。

1. 美团智能配送系统架构

美团配送业务场景复杂,单量规模大。在大规模的业务场景下,配送智能化就变得非常重要,而智能配送的核心就是做资源的优化配置。

资源优化配置

外卖配送既有线上的业务,也有线下的复杂运营。配送连接订单需求和运力供给。为了达到需求和供给的平衡,不仅要在线下运营商家、运营骑手,还要在线上将这些需求和运力供给做合理的配置,其目的是提高整体的效率。只有将配送效率最大化,才能带来良好的顾客体验,实现较低的配送成本。资源优化配置的过程,实际上是有分层的。在美团的理解中,可以分为三层:

  1. 基础层是结构优化,它直接决定了配送系统效率的上限。这种基础结构的优化,周期比较长,频率比较低,包括配送网络规划、运力结构规划等等。
  2. 中间层是市场调节,相对来说是中短期的,主要通过定价或者营销手段,使供需达到一个相对理想的平衡状态。
  3. 再上层是实时匹配,通过调度做实时的资源最优匹配。 实时匹配的频率是最高的,决策的周期也最短。

Note:

  • 基础层:例如调整运力,周期较长,频率较低,运力调整需要考虑的因素较多
  • 中间层:动态定价,营销活动等,可以提前预估一定时间范围内的单量和运力,提前进行运力调度或动态定价
  • 更高层:骑手的实时调度、实时订单分配

智能配送系统架构

如上图所示,右边三个子系统分别对应这三层体系,最底层是规划系统,中间层是定价系统,最上层是调度系统。运筹优化是调度系统、定价系统、规划系统的核心技术。

Note:

  • 机器学习系统:例如ETA预估
  • 调度系统:根据订单进行骑手的分配
  • LBS系统:路径规划
  • 定价系统:根据时间、天气、运力情况进行动态定价
  • 规划系统:可以使用行政区域划分,在此基础上再进行调整

2. 实战业务项目

2.1 智能区域规划

配送网络基本概念

配送连接的是商家、顾客、骑手三方,配送网络决定了这三方的连接关系。当用户打开App,查看哪些商家可以点餐,这由商家配送范围决定,每个商家的配送范围不一样。用户在美团点外卖,为他服务的骑手是谁呢?又是怎么确定的呢?这些是由配送区域边界来决定的,配送区域边界指的是一些商家集合所对应的范围。

Note:

  • 商家:商家配送范围
  • 骑手:配送区域边界

在传统物流中,影响末端配送效率最关键的点,是配送员对他所负责区域的熟悉程度。越熟悉,配送效率就会越高。即时配送场景也类似,每个骑手需要尽量固定地去熟悉一片商家或者配送区域。对于管理而言,站点的管理范围也比较明确。如果有新商家上线,也很容易确定由哪个配送站来提供服务。所以,这个问题有很多运营管理的诉求在其中。

区域规划影响配送效率

区域规划项目要解决的问题:1.配送区域里的商家不聚合;2.区域奇形怪状,空驶严重;3.站点的大小不合理。什么是好的区域规划方案?基于统计分析的优化目标设定。

优化的三要素是:目标、约束、决策变量。

  1. 首先要确定优化目标。区域规划影响的主要是骑手的顺路性、空驶率,也就是骑手平均为每一单付出的路程成本。所以,将问题的业务目标定为优化骑手的单均行驶距离。基于现有的大量区域和站点积累的数据,做大量的统计分析后,可以定义出这样几个指标:商家聚合度、订单的聚合度、订单重心和商家重心的偏离程度。数据分析结果说明,这几个指标和单均行驶距离的相关性很强。经过这一层的建模转化,问题明确为优化这三个指标。
  2. 梳理业务约束。区域单量有上限和下限;区域之间不能有重合,不能有商家归多个区域负责;所有的AOI(area of interest)不能有遗漏,都要被某个区域覆盖到,不能出现商家没有站点的服务;区域边界必须沿路网。

在目标和约束条件确定了之后,整体技术方案分成三部分:

  1. 首先,根据三个目标函数,确定商家最优集合。
  2. 配送团队和美团地图团队进行合作。先利用路网信息,把城市切成若干互不重叠的多边形,然后根据计算几何,将一批商家对应的多边形拼成完整的区域边界。
  3. 最后,用美团自主研发的配送仿真系统进行仿真评测。

在区域规划过程中,人工介入还是非常必要的。

落地应用

2.2 智能骑手排班

外卖订单

外卖配送场景的订单“峰谷效应”非常明显。上图是一个实际的进单曲线。

排班方案选型

配送团队最终选用的是按组排班的方式,把所有骑手分成几组,规定每个组的开工时段。然后大家可以按组轮岗,每个人的每个班次都会轮到。算法要有自己的优化目标,为了解决这个问题,首先要做设计决策变量,把时间做了离散化,以半小时为粒度。对于一天来讲,只有48个时间单元,决策空间大幅缩减。然后,目标定为运力需求满足订单量的时间单元最多。在建模层面,标准化和通用的模型才是最优选。美团把人数做了归一化,算法分配每个班次的骑手比例,但不分人数。在算法决策的时候,不决策人数、只决策比例,这样也可以把单量进行归一化。每个时间单元的进单量除以每天峰值时间单元的单量,也变成了0~1之间的数字。如果某个时间单元内人数比例大于单量比例,叫作运力得到满足。

决策变量及目标设计

算法核心思想:基于约束条件,根据启发式算法构造初始方案,再用局部搜索迭代优化。

2.3 骑手路径规划

骑手的路径规划问题,不是简单的路线规划,一个骑手身上有很多配送任务,这些配送任务存在各种约束,怎样选择最优配送顺序去完成所有任务,这是一个NP难问题。当有5个订单、10个任务点的时候,就存在11万多条可能的顺序。系统派单、系统改派,都依赖路径规划算法。在骑手端,给每个骑手推荐任务执行顺序。路径规划算法核心的诉求是优化效果必须是稳定的好。不能这次的优化结果好,下次就不好。另外,运行时间一定要短。

核心设计思想

求解路径规划这类问题经历过的阶段:起初,采用类似遗传算法的迭代搜索算法,但是随着业务的单量变大,发现算法耗时太慢,根本不可接受。然后,改为大规模邻域搜索算法,但算法依然有很强的随机性,因为没有随机性在就没办法得到比较好的解。而这种基于随机迭代的搜索策略,带来很强的不确定性,在问题规模大的场景会出现非常多的Bad Case。另外,迭代搜索耗时太长了。在这个项目中,基本可以确定这样的技术路线。首先,只能做启发式定向搜索,不能在算法中加随机扰动。不能允许同样的输入在不同运行时刻给出不一样的优化结果。然后,不能用普通迭代搜索,必须把这个问题结构特性挖掘出来,做基于知识的定制化搜索。

美团认为,最重要的是看待这个问题的视角。这里的路径规划问题,对应的经典问题模型,是开环TSP问题,或是开环VRP的变种么?可以是,也可以不是。美团做了一个有意思的建模转换,把它看作流水线调度问题:每个订单可以认为是job;一个订单的两个任务取餐和送餐,可以认为是一个job的operation。任意两个任务点之间的通行时间,可以认为是序列相关的准备时间。每一单承诺的送达时间,包括预订单和即时单,可以映射到流水线调度问题中的提前和拖期惩罚上。

问题建模转换

美团把一个经典的基于问题特征的启发式算法做了适当适配和改进,得到了非常好的效果。相比于之前的算法,耗时下降70%,优化效果不错。

2.4 订单智能调度

配送调度场景,可以用数学语言描述。它不仅是一个业务问题,更是一个标准的组合优化问题,并且是一个马尔可夫决策过程。并非对于某个时刻的一批订单做最优分配就足够,还需要考虑整个时间窗维度,每一次指派对后面的影响。要考虑长周期的优化,而不是一个静态优化问题。

调度问题的数学描述

这个问题的挑战:

  1. 性能要求极高,要做到万单对万人的秒级求解。
  2. 动态性。作为一个MDP问题,需要考虑动态优化场景,这涉及大量的预估环节。目前的思路,是通过其它的建模转换手段进行解决。
  3. 配送业务的随机因素多。比如商家的出餐时间,也许是很长时间内都无法解决的随机性。就连历史每一个已完成订单,商家出餐时间的真值都很难获得。商家出餐时刻不确定,这个随机因素永远存在,并且非常制约配送效率的提升。另外,在顾客位置交付的时间也不确定。写字楼工作日的午高峰,上电梯、下电梯的时间,很难准确进行预估。对于骑手来说,平台没法规定每个骑手的任务执行顺序。骑手在配送过程中可以自由发挥,所以骑手执行顺序的不确定性也一直存在。

问题挑战

Reference

  1. 美团智能配送系统的运筹优化实战
如果有收获,可以请我喝杯咖啡!