深入各个产业已经成为互联网目前的主攻方向，线上和线下存在大量复杂的业务约束和多种多样的决策变量，为运筹优化技术提供了用武之地。作为美团智能配送系统最核心的技术之一，运筹优化是如何在美团各种业务场景中进行落地的呢？本文根据美团配送技术团队资深算法专家王圣尧在2019年ArchSummit全球架构师峰会北京站上的演讲内容整理而成。
美团配送业务场景复杂，单量规模大。下图这组数字是2019年5月美团配送品牌发布时的数据。
更直观的规模数字，可能是美团每年给骑手支付的工资，目前已经达到几百亿这个量级。所以，在如此大规模的业务场景下，配送智能化就变得非常重要，而智能配送的核心就是做资源的优化配置。
外卖配送是一个典型的O2O场景。既有线上的业务，也有线下的复杂运营。配送连接订单需求和运力供给。为了达到需求和供给的平衡，不仅要在线下运营商家、运营骑手，还要在线上将这些需求和运力供给做合理的配置，其目的是提高整体的效率。只有将配送效率最大化，才能带来良好的顾客体验，实现较低的配送成本。而做资源优化配置的过程，实际上是有分层的。根据我们的理解，可以分为三层：
根据智能配送的这三层体系，配送算法团队也针对性地进行了运作。如上图所示，右边三个子系统分别对应这三层体系，最底层是规划系统，中间层是定价系统，最上层是调度系统。同样非常重要的还包括图中另外四个子系统，在配送过程中做精准的数据采集、感知、预估，为优化决策提供准确的参数输入，包括机器学习系统、IoT和感知系统、LBS系统，这都是配送系统中非常重要的环节，涉及大量复杂的机器学习问题。
配送连接的是商家、顾客、骑手三方，配送网络决定了这三方的连接关系。当用户打开App，查看哪些商家可以点餐，这由商家配送范围决定。每个商家的配送范围不一样，看似是商家粒度的决策，但实际上直接影响每个C端用户得到的商流供给，这本身也是一个资源分配或者资源抢夺问题。商家配送范围智能化也是一个组合优化问题，但是我们这里讲的是商家和骑手的连接关系。
用户在美团点外卖，为他服务的骑手是谁呢？又是怎么确定的呢？这些是由配送区域边界来决定的。配送区域边界指的是一些商家集合所对应的范围。为什么要划分区域边界呢？从优化的角度来讲，对于一个确定问题来说，约束条件越少，目标函数值更优的可能性就越大。做优化的同学肯定都不喜欢约束条件，但是配送区域边界实际上就是给配送系统强加的约束。
在传统物流中，影响末端配送效率最关键的点，是配送员对他所负责区域的熟悉程度。这也是为什么在传统物流领域，配送站或配送员，都会固定负责某几个小区的原因之一。因为越熟悉，配送效率就会越高。
即时配送场景也类似，每个骑手需要尽量固定地去熟悉一片商家或者配送区域。同时，对于管理而言，站点的管理范围也比较明确。另外，如果有新商家上线，也很容易确定由哪个配送站来提供服务。所以，这个问题有很多运营管理的诉求在其中。
当然，区域规划项目的发起，存在很多问题需要解决。主要包括以下三种情况：1.配送区域里的商家不聚合。这是一个典型站点，商家主要集中在左下角和右上角，造成骑手在区域里取餐、送餐时执行任务的地理位置非常分散，需要不停往返两个商圈，无效跑动非常多。2.区域奇形怪状，空驶严重。之前在门店上线外卖平台的发展过程中，很多地方原本没有商家，后来上线的商家多了，就单独作为一个配送区域。这样的区域形状可能就会不规则，导致骑手很多时候在区域外跑。而商家和骑手都有绑定关系，骑手只能服务自己区域内的商家，因此骑手无法接到配送区域外的取餐任务，空驶率非常高。很多时候骑手送完餐之后，只能空跑回来才可能接到新任务。3.站点的大小不合理。图三这个站点，每天的单量只有一二百单。如果从骑手平均单量的角度去配置骑手的话，只能配置3~4个骑手。如果某一两个人突然有事要请假，可想而知，站点的配送体验一定会变得非常差，运营管理难度会很高。反之，如果某一个站点变得非常大，站长也不可能管得了那么多的骑手，这也是一个问题。所以，需要给每个站点规划一个合理的单量规模。
既然存在这么多的问题，那么做区域规划项目就变得非常有必要。那么，什么是好的区域规划方案？基于统计分析的优化目标设定。
优化的三要素是：目标、约束、决策变量。
基于业务场景的约束条件梳理
最难的一个问题，其实是要求区域边界必须沿路网。起初我们很难理解，因为本质上区域规划只是对商家进行分类，它只是一个商家集合的概念，为什么要画出边界，还要求边界沿路网呢？其实刚才介绍过，区域边界是为了回答如果有新商家上线到底属于哪个站点的问题。而且，从一线管理成本来讲，更习惯于哪条路以东、哪条路以南这样的表述方式，便于记忆和理解，提高管理效率。所以，就有了这样的诉求，我们希望区域边界更“便于理解”。
在目标和约束条件确定了之后，整体技术方案分成三部分：
下面是一个实际案例，我们用算法把一个城市做了重新的区域规划。当然，这里必须要强调的是，在这个过程中，人工介入还是非常必要的。对于一些算法很难处理好的边角场景，需要人工进行微调，使整个规划方案更加合理。中间的图是算法规划的结果。经过试点后，测试城市整体的单均行驶距离下降了5%，平均每一单骑手的行驶距离节省超过100米。可以想象一下，在这么庞大的单量规模下，每单平均减少100米，总节省的路程、节省的电瓶车电量，都是一个非常可观的数字。更重要的是，可以让骑手自己明显感觉到自己的效率得到了提升。
业务背景
另外，外卖配送场景的订单“峰谷效应”非常明显。上图是一个实际的进单曲线。可以看到全天24小时内，午晚高峰两个时段单量非常高，而闲时和夜宵相对来说单量又少一些。因此，系统也没办法把一天24小时根据每个人的工作时长做平均切分，也需要进行排班。
对于排班，存在两类方案的选型问题。很多业务的排班是基于人的维度，好处是配置的粒度非常精细，每个人的工作时段都是个性化的，可以考虑到每个人的诉求。但是，在配送场景的缺点也显而易见。如果站长需要为每个人去规划工作时段，其难度可想而知，也很难保证分配的公平性。
配送团队最终选用的是按组排班的方式，把所有骑手分成几组，规定每个组的开工时段。然后大家可以按组轮岗，每个人的每个班次都会轮到。
这个问题最大的挑战是，我们并不是在做一项业务工具，而是在设计算法。而算法要有自己的优化目标，那么排班的目标是什么呢？如果你要问站长，怎么样的排班是好的，可能他只会说，要让需要用人的时候有人。但这不是算法语言，更不能变成模型语言。
算法核心思想
综合考虑以上因素，我们最终基于约束条件，根据启发式算法构造初始方案，再用局部搜索迭代优化。使用这样的方式，求解速度能够达到毫秒级，而且可以给出任意站点的排班方案。整体的优化指标还不错，当然，不保证是最优解，只是可以接受的满意解。
落地应用效果
具体到骑手的路径规划问题，不是简单的路线规划，不是从a到b该走哪条路的问题。这个场景是，一个骑手身上有很多配送任务，这些配送任务存在各种约束，怎样选择最优配送顺序去完成所有任务。这是一个NP难问题，当有5个订单、10个任务点的时候，就存在11万多条可能的顺序。而在高峰期的时候，骑手往往背负的不止5单，甚至有时候一个骑手会同时接到十几单，这时候可行的取送顺序就变成了一个天文数字。
但是，算法仅仅是快就可以吗？并不是。因为这是派单、改派这些环节的核心模块，所以算法的优化求解能力也非常重要。如果路径规划算法不能给出较优路径，可想而知，上层的指派和改派很难做出更好的决策。
在求解路径规划这类问题上，很多公司的技术团队，都经历过这样的阶段：起初，采用类似遗传算法的迭代搜索算法，但是随着业务的单量变大，发现算法耗时太慢，根本不可接受。然后，改为大规模邻域搜索算法，但算法依然有很强的随机性，因为没有随机性在就没办法得到比较好的解。而这种基于随机迭代的搜索策略，带来很强的不确定性，在问题规模大的场景会出现非常多的BadCase。另外，迭代搜索耗时太长了。主要的原因是，随机迭代算法是把组合优化问题当成一个单纯的Permutation问题去求解，很少用到问题结构特征。这些算法，求解TSP时这样操作，求解VRP时也这样操作，求解Scheduling还是这样操作，这种类似“无脑”的方式很难有出色的优化效果。
所以，在这个项目中，基本可以确定这样的技术路线。首先，只能做启发式定向搜索，不能在算法中加随机扰动。不能允许同样的输入在不同运行时刻给出不一样的优化结果。然后，不能用普通迭代搜索，必须把这个问题结构特性挖掘出来，做基于知识的定制化搜索。
算法应用效果
做了这样的建模转换之后，流水线调度问题就有大量的启发式算法可以借鉴。我们把一个经典的基于问题特征的启发式算法做了适当适配和改进，可以得到非常好的效果。相比于之前的算法，耗时下降70%，优化效果不错。因为这是一个确定性算法，所以运行多少次的结果都一样。我们的算法运行一次，跟其它算法运行10次的最优结果相比，优化效果是持平的。
配送调度场景，可以用数学语言描述。它不仅是一个业务问题，更是一个标准的组合优化问题，并且是一个马尔可夫决策过程。
为了便于理解，我们还是先看某个调度时刻的静态优化问题。它不仅仅是一个算法问题，还需要我们对工程架构有非常深刻的理解。因为，在对问题输入数据进行拆解的时候，会发现算法的输入数据太庞大了。比如说，我们需要任意两个任务点的导航距离数据。
总结一下，这个问题有三类挑战：
目前，美团配送团队的研究方向，不仅包括运筹优化，还包括机器学习、强化学习、数据挖掘等领域。这里具有很多非常有挑战的业务场景，欢迎大家加入我们。