美团智能配送系统的运筹优化实战
美团智能配送系统的运筹优化实战
深⼊各个产业已经成为互联⽹⽬前的主攻⽅向，线上和线下存在⼤量复杂的业务约束和多种多样的决策变量，为运筹优化技术提供了⽤武之地。作为美团智能配送系统最核⼼的技术之⼀，运筹优化是如何在美团各种业务场景中进⾏落地的呢？本⽂根据美团配送技术团队资深算法专家王圣尧在2019年ArchSummit全球架构师峰会北京站上的演讲内容整理⽽成。
美团智能配送系统架构
美团配送业务场景复杂，单量规模⼤。下图这组数字是2019年5⽉美团配送品牌发布时的数据。
更直观的规模数字，可能是美团每年给骑⼿⽀付的⼯资，⽬前已经达到⼏百亿这个量级。所以，在如此⼤规模的业务场景下，配送智能化就变得⾮常重要，⽽智能配送的核⼼就是做资源的优化配置。
外卖配送是⼀个典型的O2O场景。既有线上的业务，也有线下的复杂运营。配送连接订单需求和运⼒供给。为了达到需求和供给的平衡，不仅要在线下运营商家、运营骑⼿，还要在线上将这些需求和运⼒供给做合理的配置，其⽬的是提⾼整体的效率。只有将配送效率最⼤化，才能带来良好的顾客体验，实现较低的配送成本。⽽做资源优化配置的过程，实际上是有分层的。根据我们的理解，可以分为三层：
1. 基础层是结构优化，它直接决定了配送系统效率的上限。这种基础结构的优化，周期⽐较长，频率⽐较低，包括配送⽹络规划、运⼒
结构规划等等。
2. 中间层是市场调节，相对来说是中短期的，主要通过定价或者营销⼿段，使供需达到⼀个相对理想的平衡状态。
3. 再上层是实时匹配，通过调度做实时的资源最优匹配。 实时匹配的频率是最⾼的，决策的周期也最短。
根据智能配送的这三层体系，配送算法团队也针对性地进⾏了运作。如上图所⽰，右边三个⼦系统分别对应这三层体系，最底层是规划系统，中间层是定价系统，最上层是调度系统。同样⾮常重要的还包括图中另外四个⼦系统，在配送过程中做精准的数据采集、感知、预估，为优化决策提供准确的参数输⼊，包括机器学习系统、IoT 和感知系统、LBS系统，这都是配送系统中⾮常重要的环节，涉及⼤量复杂的机器学习问题。
⽽运筹优化则是调度系统、定价系统、规划系统的核⼼技术。接下来，我们分享⼏个典型的运筹优化案例。
实战业务项⽬
智能区域规划
为了帮助⼤家快速理解配送业务的基本背景，这⾥⾸先分享智能区域规划项⽬中经常遇到的问题及其解决⽅案。
配送连接的是商家、顾客、骑⼿三⽅，配送⽹络决定了这三⽅的连接关系。当⽤户打开App，查看哪些商家可以点餐，这由商家配送范围决定。每个商家的配送范围不⼀样，看似是商家粒度的决策，但实际上直接影响每个C端⽤户得到的商流供给，这本⾝也是⼀个资源分配或者资源抢夺问题。商家配送范围智能化也是⼀个组合优化问题，但是我们这⾥讲的是商家和骑⼿的连接关系。
⽤户在美团点外卖，为他服务的骑⼿是谁呢？⼜是怎么确定的呢？这些是由配送区域边界来决定的。
配送区域边界指的是⼀些商家集合所对应的范围。为什么要划分区域边界呢？从优化的⾓度来讲，对于⼀个确定问题来说，约束条件越少，⽬标函数值更优的可能性就越⼤。做优
化的同学肯定都不喜欢约束条件，但是配送区域边界实际上就是给配送系统强加的约束。
在传统物流中，影响末端配送效率最关键的点，是配送员对他所负责区域的熟悉程度。这也是为什么在传统物流领域，配送站或配送员，都会固定负责某⼏个⼩区的原因之⼀。因为越熟悉，配送效率就会越⾼。
即时配送场景也类似，每个骑⼿需要尽量固定地去熟悉⼀⽚商家或者配送区域。同时，对于管理⽽⾔，站点的管理范围也⽐较明确。另外，如果有新商家上线，也很容易确定由哪个配送站来提供服务。所以，这个问题有很多运营管理的诉求在其中。
当然，区域规划项⽬的发起，存在很多问题需要解决。主要包括以下三种情况： 1. 配送区域⾥的商家不聚合。这是⼀个典型站点，商家主要集中在左下⾓和右上⾓，造成骑⼿在区域⾥取餐、送餐时执⾏任务的地理位置⾮常分散，需要不停往返两个商圈，⽆效跑动⾮常多。 2.区域奇形怪状，空驶严重。之前在门店上线外卖平台的发展过程中，很多地⽅原本没有商家，后来上线的商家多了，就单独作为⼀个配送区域。这样的区域形状可能就会不规则，导致骑⼿很多时候在区域外跑。 ⽽商家和骑⼿都有绑定关系，骑⼿只能服务⾃⼰区域内的商家，因此骑⼿⽆法接到配送区域外的取餐任务，空驶率⾮常⾼。很多时候骑⼿送完餐之后，只能空跑回来才可能接到新任务。 3. 站点的⼤⼩不合理。图三这个站点，每天的单量只有⼀⼆百单。如果从骑⼿平均单量的⾓度去配置骑⼿的话，只能配置3~4个骑⼿。如果某⼀两个⼈突然有事要请假，可想⽽知，站点的配送体验⼀定会变得⾮常差，运营管理难度会很⾼。 反之，如果某⼀个站点变得⾮常⼤，站长也不可能管得了那么多的骑⼿，这也是⼀个问题。所以，需要给每个站点规划⼀个合理的单量规模。
既然存在这么多的问题，那么做区域规划项⽬就变得⾮常有必要。那么，什么是好的区域规划⽅案？基于统计分析的优化⽬标设定。
优化的三要素是：⽬标、约束、决策变量。
第⼀点，⾸先要确定优化⽬标。在很多⽐较稳定或者传统的业务场景中，⽬标⾮常确定。⽽在区域规划这个场景中，怎么定义优化⽬标呢？⾸先，我们要思考的是区域规划主要影响的是什么。从刚才⼏类问题的分析可以发现，影响的主要是骑⼿的顺路性、空驶率，也就是骑⼿平均为每⼀单付出的路程成本。所以，我们将问题的业务⽬标定为优化骑⼿的单均⾏驶距离。基于现有的⼤量区域和站点积累的数据，做⼤量的统计分析后，可以定义出这样⼏个指标：商家聚合度、订单的聚合度、订单重⼼和商家重⼼的偏离程度。数据分析结果说明，这⼏个指标和单均⾏驶距离的相关性很强。经过这⼀层的建模转化，问题明确为优化这三个指标。
第⼆点，需要梳理业务约束。在这⽅⾯，我们花费了⼤量的时间和精⼒。⽐如：区域单量有上限和下限；区域之间不能有重合，不能有商家归多个区域负责；所有的AOI不能有遗漏，都要被某个区域覆盖到，不能出现商家没有站点的服务。
基于业务场景的约束条件梳理
最难的⼀个问题，其实是要求区域边界必须沿路⽹。起初我们很难理解，因为本质上区域规划只是对商家进⾏分类，它只是⼀个商家集合的概念，为什么要画出边界，还要求边界沿路⽹呢？其实刚才介绍过，区域边界是为了回答如果有新商家上线到底属于哪个站点的问题。⽽且，从⼀线管理成本来讲，更习惯于哪条路以东、哪条路以南这样的表述⽅式，便于记忆和理解，提⾼管理效率。所以，就有了这样的诉
求，我们希望区域边界更“便于理解”。
在⽬标和约束条件确定了之后，整体技术⽅案分成三部分：
外卖订单量怎么提升1. ⾸先，根据三个⽬标函数，确定商家最优集合。这⼀步⽐较简单，做运筹优化的同学都可以快速地解决这样⼀个多⽬标组合优化问
题。
2. 后⾯的步骤⽐较难，怎么把区域边界画出来呢？为了解决这个问题，配送团队和美团地图团队进⾏合作。先利⽤路⽹信息，把城市切
成若⼲互不重叠的多边形，然后根据计算⼏何，将⼀批商家对应的多边形拼成完整的区域边界。
3. 最后，⽤美团⾃主研发的配送仿真系统，评测这样的区域规划对应的单均⾏驶距离和体验指标是否符合预期。因为⼀线直接变动的成
本⾮常⾼，仿真系统就起到了⾮常好的作⽤。
下⾯是⼀个实际案例，我们⽤算法把⼀个城市做了重新的区域规划。当然，这⾥必须要强调的是，在这个过程中，⼈⼯介⼊还是⾮常必要
的。对于⼀些算法很难处理好的边⾓场景，需要⼈⼯进⾏微调，使整个规划⽅案更加合理。中间的图是算法规划的结果。经过试点后，测试
城市整体的单均⾏驶距离下降了5%，平均每⼀单骑⼿的⾏驶距离节省超过100⽶。可以想象⼀下，在这么庞⼤的单量规模下，每单平均减
少100⽶，总节省的路程、节省的电瓶车电量，都是⼀个⾮常可观的数字。更重要的是，可以让骑⼿⾃⼰明显感觉到⾃⼰的效率得到了提
升。
智能骑⼿排班
业务背景
这是随着外卖配送的营业时间越来越长⽽衍⽣出的⼀个项⽬。早期，外卖只服务午⾼峰到晚⾼峰，后来⼤家慢慢可以点夜宵、点早餐。到如今，很多配送站点已经提供了24⼩时服务。但是，骑⼿不可能全天24⼩时开⼯，劳动法对每天的⼯作时长也有规定，所以这⼀项⽬势在必⾏。
另外，外卖配送场景的订单“峰⾕效应”⾮常明显。上图是⼀个实际的进单曲线。可以看到全天24⼩时内，午晚⾼峰两个时段单量⾮常⾼，⽽闲时和夜宵相对来说单量⼜少⼀些。因此，系统也没办法把⼀天24⼩时根据每个⼈的⼯作时长做平均切分，也需要进⾏排班。
对于排班，存在两类⽅案的选型问题。 很多业务的排班是基于⼈的维度，好处是配置的粒度⾮常精细，每个⼈的⼯作时段都是个性化的，可以考虑到每个⼈的诉求。但是，在配送场景的缺点也显⽽易见。如果站长需要为每个⼈去规划⼯作时段，其难度可想⽽知，也很难保证分配的公平性。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。