即时配送业务是典型的O2O业务，线上线下存在大量复杂的业务约束和多种决策变量。美团的智能配送系统负责订单和骑手资源的优化配置，致力于提升客户体验，降低配送成本。作为美团智能配送系统的核心技术之一，物流优化如何应用到各个业务场景中？本文根据王圣耀在ArchSummit全球架构师峰会上的演讲整理而成，供技术读者阅读。一、美团智能配送系统架构美团配送的业务场景是什么？下图这组数字是2019年5月美团外卖品牌发布时的数据。作为一个服务三方客户（包括商家、骑手、用户）的平台，我们每天完成的订单峰值量是远不止这个数字。单看这些数字可能没有意义，但如果你告诉大家，每年支付给骑手的工资都在百亿级别，你就会知道，在如此大规模的业务场景下，智能配送有多么重要。智能配送的核心是优化资源配置。外卖是典型的O2O场景。既有线上业务，也有复杂的线下业务。分销连接订单需求和产能供应。为了实现需求和供给的最佳平衡，不仅需要在线下运营商户和骑手，还需要在线上对这些需求和运力供给进行合理配置，以提高效率。只有最大限度地提高配送效率，才能带来良好的客户体验，降低配送成本。优化资源配置的过程实际上是分层的。按照我们的理解，可以分为三层：基础层是结构优化，它直接决定了配送系统效率的上限。这种基础结构的优化周期较长，频率较低，包括配电网规划和容量结构规划。中间层是市场调节，是比较短期的，主要是通过定价或者营销手段，使供需达到比较理想的平衡。上层是实时匹配，通过调度进行实时资源最优匹配。实时匹配频率最高，决策周期也最短。对于智能分发的三层体系，分发算法团队也是如此操作。图中右侧的三个子系统对应三层。底层是计划系统，中间层是定价系统，顶层是调度系统。同样非常重要的是，还要包括图中的其他四个子系统，它们在配送过程中进行准确的数据采集、感知和预测，为优化决策提供准确的参数输入，包括机器学习系统、物联网和感知系统，以及LBS系统，是配送系统中非常重要的环节，存在大量复杂的机器学习问题。二、实战项目1、智能区域规划为帮助您快速了解配电业务的基本背景，首先分享智能区域规划项目中遇到的问题及解决方案。分销由商家、客户、骑手连接，分销网络决定了这三者的连接关系。打开APP，哪些商家可以点餐由商家的送餐范围决定。每个商家的分销范围不同。看似是商家的颗粒决策，实际上直接影响到每个C端用户获得的业务流量的供给，这本身还是一个资源分配或资源抢夺的问题。商家的智能配送范围也是一个有趣的组合优化问题，不过这里说的是商家和骑手之间的连接关系。我在公司点餐时，哪一组骑手为我服务？它是如何确定的？这些由交付区域边界确定。配送区域边界是指对应部分商户收款的范围。为什么要划分区域边界？从优化的角度来看，对于一个确定的问题，约束越少，目标函数值越优的可能性就越大。做优化的同学当然不喜欢约束，但是分布区域的边界其实是对分布系统施加的约束。在传统物流中，影响终端配送效率的最关键点其实是配送员对所负责区域的熟悉程度。这也是为什么在传统的物流领域，配送站或派送员固定负责某些社区的原因之一。因为越熟悉，交付效率越高。即时配送的场景也类似，每个骑手都需要尽可能固定地熟悉一个商家或配送区域。同时，在管理上，现场管理的范围也比较明确。此外，如果有新商户上线，也很容易确定由哪个配送站提供服务。所以，这个问题里面有很多运营管理的诉求。区域规划的立项，其实是有很多问题需要解决。分三种情况：派送区内商户未聚合。这是一个典型的网站。商家主要集中在左下角和右上角。导致该地区接送餐的骑手地理位置十分分散。需要在两个商圈之间来回奔波，无效跑路很多。该区域形状奇特，空车现象严重。在门店之前的线上外卖平台发展过程中，很多地方没有商家，后来线上的商家就多了，而且都是作为一个单一的外卖区域。这种区域的形状可能是不规则的，导致骑手很多时候跑到区域之外。商家和骑手是绑定的。骑手只能服务于自己所在区域的商户。因此，骑手无法在配送区域外接到取餐任务，空驶率非常高。很多时候，骑手出去送餐后，只能空着手跑回去接受新的任务。场地大小不合理。图3中的站点每天只有一两百个订单。如果从骑手平均人数的角度来配置骑手，那么只能配置3到4个骑手。如果一两个人突然有事请假，可想而知站点的交付体验会很差，运营管理也很困难。反之，如果一个站点很大，站长不可能管理那么多的骑手。因此，需要为每个站点规划合理的单位体积。由于存在这么多问题，因此非常需要区域规划项目。优化的三个要素是目标、约束和决策变量。第一点是先确定优化目标。在很多稳定或者传统的业务场景中，目标是非常明确的。在区域规划场景下，如何定义优化目标？首先要考虑的是区域规划的主要影响是什么。从刚才对几类问题的分析，发现主要影响的是骑手的顺畅度和空驶率，即骑手为每笔订单支付的平均行程成本。因此，我们将问题的业务目标设定为优化骑手的平均行驶距离。基于已有的大量地区和站点积累的数据，在做大量的统计分析后，可以定义几个指标：商户聚集度、订单聚集度、商家之间的偏离度。订单重心和商家重心。数据分析结果表明，这些指标与平均行驶距离有很强的相关性。经过这一层建模改造，问题就很明显就是优化这三个指标了。第二点是梳理业务约束。在这方面，我们花费了大量的时间和精力。例如：区域订单有上限和下限；区域之间不能重叠，商家不能负责多个区域；所有AOI必须在某个区域无遗漏地覆盖，商家不能有站点服务。.最困难的问题之一实际上是区域边界必须沿着道路网络的要求。一开始我们很难理解，因为区域规划本质上就是对商户进行分类。它只是一个商家集合的概念。为什么要划界，要求沿界有路网？其实我刚才介绍的，区域边界就是回答，如果有新业务上线，它属于哪个站点。而且，在一线管理成本方面，我更习惯表达哪条路是东，哪条路是南，便于记忆和理解，提高管理效率。所以，有了这样的要求，我们希望区域界限“通俗易懂”。目标和约束条件确定后，整体技术方案分为三个部分：首先，根据三个目标函数，确定最优商户集合。这一步比较简单，因为做运筹学优化的同学可以很快解决这样的多目标组合优化问题。接下来就比较难了，区域的边界怎么画？为了解决这个问题，我们与美团地图团队合作。首先，利用路网信息，将城市切割成若干个不重叠的多边形，然后根据计算几何，将一组商户对应的多边形拼接成完整的区域边界。最后，利用美团自主研发的配送模拟系统，评估该区域规划对应的平均行驶距离和体验指标是否达到预期。因为在一线直接改动成本非常高，所以仿真系统在这里起到了很好的作用。以下是我们使用算法重新规划城市的实际案例。当然，这里必须强调的是，在这个过程中，人工干预还是非常有必要的。对于一些算法难以处理好的拐角场景，需要人工微调，让整个规划方案更加合理。中间的图是算法规划的结果。试点后，全市平均行驶距离下降5%，单人骑行平均行驶距离节省100多米。可以想象，在如此庞大的订单规模下，每笔订单平均减少100米，节省的总距离和节省的电瓶车电量都是非常可观的数字。更重要的是，骑手能明显感受到效率的提升。2.SmartRiderScheduling随着外卖的营业时间越来越长，衍生出这样一个项目。起初，外卖服务只在中午高峰到晚高峰提供，后来可以点夜宵和早餐，现在很多外卖点都有24小时服务。但是，骑手一天24小时工作是不可能的，劳动法也规定了每天的工作时长。此外，外卖场景的订单峰谷效应非常明显。上图是实际的订单输入曲线。全天24小时内，中午和晚高峰的订单量非常大，而休闲时间和宵夜的订单量相对较小。所以没办法按照每个人的工作时间来平均划分一天的24小时，需要轮班调度。对于轮班调度，有两类方案选择问题。很多业务的排班都是以人为维度的。优点是配置的粒度非常细。每个人的工作时间都是个性化的，每个人的诉求都可以考虑。不过，在配送场景上的短板也很明显。如果站长需要为大家规划工作时间，难度可想而知，也难以保证公平。我们最终选择了分组调度的方式，将所有骑手分成若干组，并指定每组的开始时间。然后大家可以分组轮换，每个人轮班一次。这个问题最大的挑战在于我们不是在做一个商业工具，而是在设计一个算法。算法必须有一个优化目标。调度的目标是什么？我们问站长他认为什么样的时间表好。他只是说，需要人的时候应该有人。但这不是算法语言，更不是模型语言。我们做的第一件事是设计决策变量。决策变量没有使用班次的起止时间和结束时间，决策空间太大。我们将时间离散化，以半小时为粒度。一天只有48个时间单位，决策空间大大缩小。然后目标是设置容量需求满足订单量的最大时间单位数。这是因为在相应的订单录入曲线下，无法保证现场人数能够满足各单元的产能需求，所以我们将业务约束转化为目标函数的一部分。这还有另一个好处，不需要知道网站上的总人数。在建模层面，标准化和通用模型都不错。因此，我们将人数归一化，算法将骑手的比例分配给每个班次，而不考虑人数。最后只需要输入站点的总人数就可以得到每个班次的人数。算法做决定的时候，不决定人数，只决定比例，这样单个数量也可以归一化。每个时间单位的订单量除以每天高峰时间单位的订单量，也是0到1之间的一个数。一定的时间单位大于单体体积的比例，则称该容量满足。这样，通过各种归一化，就变成了一个通用的问题，而不需要对每个场景单独处理。此外，这个问题还有大量复杂而强的约束条件，涉及到各种管理诉求和骑手体验。制约因素很多，比如每个工作时段要尽可能连续，每个工作时段的持续时间不能太短，不同工作时段之间的休息时间不能太短……这样的有很多业务约束。整理后发现，这个问题的约束条件太多了，要找到最优解甚至可行解太难了。另外，在使用调度工具时，站长希望能第一时间给出系统调度方案，然后快速进行后续微调，因此对算法的运行时间要求也很高。考虑到上述情况，我们最终基于约束条件和启发式算法构造了一个初始解，然后通过局部搜索对其进行迭代优化。这样求解速度在毫秒级，可以给出任意站的调度方案。优化指数还不错。当然，不保证一定是最优解，但是可以接受的满意解。该算法在自营场景中也得到了应用。和那些调度经验丰富的站长相比，效果基本一样，一线接受度比较高。最重要的是节省排班时间。每个班次都可以在几分钟内完成，让站长有更多的时间去做其他的管理工作。3.骑手路径规划骑手的路径规划问题不是路线规划，也不是从a到b走哪条路的问题。这个场景是一个骑手有很多送货任务，这些送货任务有各种约束。如何选择最优的交货顺序来完成所有任务。这是一个NP-hard问题。当有5个订单，10个任务点时，已经有超过11万个可能的订单。在高峰期，骑手往往会背5个以上的订单，有时甚至一个骑手可能同时有十几个订单。这时候，可行的取送货单是天文数字。从算法的应用场景来看，这是智能调度系统中最重要的环节。系统调度和系统重调度都依赖于路径规划算法；在骑手方面，为每个骑手推荐任务执行顺序；此外，在用户点外卖后，美团会实时显示骑手完成当前任务需要多少分钟，并为用户提供更多预估信息。这么多的应用场景，共同的需求就是对时效性要求非常高，算法运行时间越短越好。但是算法仅仅是快速就足够了吗？并不真地。因为这是调度和重调度的核心模块，所以算法的优化和求解能力也很重要。如果路径规划算法不能给出更好的路径，可想而知，上层的分配和重新分配很难做出好的决策。所以，要理清这个问题，核心要求就是优化效果要稳定好。不能说这次优化结果好，下次就不好；此外，运行时间必须短。在解决路径规划等问题时，很多公司的技术团队都经历过这样一个阶段：一开始使用了类似遗传算法的迭代搜索算法，但随着业务订单数量的增加，发现该算法太耗时，根本无法接受；然后，改为大规模邻域搜索算法，但该算法仍然具有很强的随机性，因为没有随机性，就没有办法得到更好的解。但是这种基于随机迭代的搜索策略带来了很强的不确定性，在问题规模较大的场景下会出现大量的badcase。此外，迭代搜索花费的时间太长。主要原因是随机迭代算法把组合优化问题当作一个简单的排列问题来解决，很少利用问题的结构特征。这些算法在求解TSP、求解VRP和求解调度时以相同的方式运行。这种“无脑”的方法很难取得优秀的优化效果。所以在这个项目中，基本上可以确定这样的技术路线。首先，只能做启发式定向搜索，不能在算法中加入随机扰动。不能允许相同的输入在不同的运行时给出不同的优化结果。然后，不能使用普通的迭代搜索，必须挖掘这个问题的结构特征来进行基于知识的定制化搜索。说起来容易做起来难，怎么做？最重要的是看这个问题的角度。这里的路径规划问题，对应的经典问题模型，是开环TSP问题，还是开环VRP的变种？它可能会也可能不会。我们做了一个有趣的建模转换，可以看成一个流水线调度问题：每个订单可以看成一个作业；一个订单的取餐和送餐两个任务，可以认为是一个作业操作；任意两个任务点之间的传输时间都可以认为是序列相关的准备时间；每个订单的交货时间，包括预购订单和即时订单，可以映射到流水线调度问题中的早晚惩罚。经过这样的建模转换，在流水线调度问题中就有了大量的启发式算法可以借鉴。我们根据问题的特点对一个经典的启发式算法进行了适当的改编和改进，可以得到很好的效果。与之前的算法相比，耗时减少了70%，优化效果还不错。因为这是一个确定性算法，无论运行多少次，结果都是一样的。但是我们的算法运行一次，优化效果相当于其他算法运行10次的最好结果。4.订单智能派送派送场景可以用数学语言来描述。它不仅是一个业务问题，也是一个标准的组合优化问题，一个马尔可夫决策过程。仅仅在某一时刻对一批订单进行最优分配是不够的，还需要考虑整个时间窗口维度，以及每次分配对未来的影响。每一个订单分布都会影响到每个骑手在后续时段的位置分布和行进方向。如果骑手的分布和方向不适合未来的订单结构，就相当于降低了后续调度矩的最优性上限。因此，应该考虑长期优化，而不是静态优化问题。为了便于理解，我们先来看某个调度时刻的静态优化问题。不仅仅是一个算法问题，还需要我们对工程架构有非常深刻的理解。因为，在拆解问题的输入数据时，你会发现算法的输入数据太大了。例如，我们需要任意两个任务点的导航距离数据。至于我们面临的问题规模，在前几年，只是区域维度的调度粒度。一个商圈每分钟有100多个订单的峰值，匹配了数百个骑手，但是这个产品关系对应的数据已经非常庞大了。现在因为业务场景比较多，比如跑腿、同城配送，会跨越很多商圈，甚至半个城市，我们只能做城市级的全局优化匹配。目前，调度系统处理问题的峰值规模为万余单、数万骑手的匹配。算法允许的运行时间只有几秒，内存消耗也很大。此外，配送和网约车的派单场景也不尽相同。出租车的调度是为了匹配司机和乘客。它本质上是一个二分图匹配问题，有一个最优的多项式时间算法：KM算法。打车场景的难点在于如何描述每一对火柴的权重。分发场景仍然需要解决。对于没有多项式时间最优算法的情况，如何在指数解空间中短时间内求出最优解。如果认为每个订单和每个骑手比赛都有不同的适应度，那么这个适应度不是线性叠加的。这意味着在多单对多的匹配方案中，任何一种匹配都只能重新计算适应度，其计算量可想而知。总结起来，这个问题有三类挑战：性能要求极高，需要秒级解决几万条订单。我们之前做过一些有趣的工作，比如使用机器学习模型根据历史最优分配的结果进行剪枝。大量的历史数据可以帮助我们省去很多无用的匹配方案评估。动态的。作为一个MDP问题，需要考虑动态优化场景，涉及到大量的估计。在只有当前未完成订单的情况下，骑手如何执行，如何预估每笔订单的完成时间，未来会进入什么样的订单结构，对业务指标和效率指标有什么影响……你可能觉得是这样的。一个典型的强化学习场景，但它的难点在于决策空间太大，甚至可以认为是无穷大。目前我们的思路是通过其他的建模转换方式来解决。分销业务中存在许多随机因素。例如，商家的送餐时间可能是一个长时间无法解决的随机数。即便是历史上每一个完成的订单，商家送餐时间的真实价值也很难获得，因为人为点击的数据无法保证准确完整。商户发货时间不确定。这种随机因素始终存在，极大地制约了配送效率的提高。此外，客户所在地的送达时间也不确定。写字楼工作日中午高峰时段，很难准确预估上下电梯的时间。当然，我们一直在努力使我们的估计更加准确，但随机性始终存在。对于骑手，平台无法规定每个骑手的任务执行顺序。骑手在送货过程中可以自由发挥，所以骑手执行的顺序也存在不确定性。为了解决这些问题，我们想用鲁棒优化或者说随机规划的思想。但是，如果是基于随机场景采样，计算量会明显增加。因此，需要基于学习的优化。优化不是纯粹的机器学习模型，也不是简单的启发式规则。优化算法是通过结合真实数据和算法设计者的经验来学习和演化的。只有这样，才能在对性能要求极高的业务场景中，快速获得健壮的优化方案。我们团队目前的研究方向不仅包括运维优化，还包括机器学习、强化学习、数据挖掘等领域。这里有很多非常具有挑战性的业务场景，非常欢迎大家加入我们。作者介绍美团资深算法专家王胜耀博士。毕业于清华大学自动化系。主要研究调度理论、运筹学优化和系统仿真。中国仿真学会智能仿真优化与调度专委会委员。目前负责美团配送智能调度算法团队的技术研发。
