导读
美团配送业务场景复杂，单量规模大。更直观的规模数字，可能是美团每年给骑手支付的薪水，目前早已达到几百亿这个量级。所以，在这么大规模的业务场景下，配送智能化就显得十分重要，而智能配送的核心就是做资源的优化配置。
美团配送业务场景复杂，单量规模大。
更直观的规模数字，可能是美团每年给骑手支付的薪水，目前早已达到几百亿这个量级。所以，在这么大规模的业务场景下，配送智能化就显得十分重要，而智能配送的核心就是做资源的优化配置。
资源优化配置
外卖配送是一个典型的O2O场景。既有线上的业务，也有线下的复杂营运。配送联接订单需求和运力供给。为了达到需求和供给的平衡，除了要在线下营运店家、运营骑手，还要在线中将这种需求和运力供给做合理的配置，其目的是提升整体的效率。只有将配送效率最大化，能够带来良好的客户体验，实现较低的配送成本。而做资源优化配置的过程，实际上是有分层的。按照我们的理解，可以分为三层：
基础层是结构优化，它直接决定了配送系统效率的上限。这些基础结构的优化，周期比较长，频度比较低，包括配送网路规划、运力结构规划等等。
中间层是市场调节，相对来说是中短期的，主要通过定价或则营销手段，使供需达到一个相对理想的平衡状态。
再下层是实时匹配，通过调度做实时的资源最优匹配。实时匹配的频度是最高的，决策的周期也最短。
智能配送系统构架
依照智能配送的这三层体系，配送算法团队也针对性地进行了运作。如上图所示，左边三个子系统分别对应这三层体系，最底层是规划系统，中间层是定价系统，最下层是调度系统。同样十分重要的还包括图中另外四个子系统，在配送过程中做精准的数据采集、感知、预估，为优化决策提供确切的参数输入，包括机器学习系统、IoT和感知系统、LBS系统，这都是配送系统中十分重要的环节，涉及大量复杂的机器学习问题。
而运筹优化则是调度系统、定价系统、规划系统的核心技术。接出来，将分享几个典型的运筹优化案例。
实战业务项目
智能区域规划
为了帮助你们快速理解配送业务的基本背景，这儿首先分享智能区域规划项目中常常碰到的问题及其解决方案。
配送网路基本概念
配送联接的是店家、顾客、骑手三方，配送网路决定了这三方的联接关系。当用户打开App，查看什么店家可以点餐，这由店家配送范围决定。每位店家的配送范围不一样，看似是店家细度的决策，但实际上直接影响每位C端用户得到的商流供给，这本身也是一个资源分配或则资源抢劫问题。店家配送范围智能化也是一个组合优化问题，而且我们这儿讲的是店家和骑手的联接关系。
用户在美团点外卖，为他服务的骑手是谁呢？又是如何确定的呢？那些是由配送区域边界来决定的。配送区域边界指的是一些店家集合所对应的范围。为何要界定区域边界呢？从优化的角度来讲，对于一个确定问题来说，约束条件越少，目标函数值更优的可能性就越大。做优化的朋友肯定都不喜欢约束条件，并且配送区域边界实际上就是给配送系统强加的约束。
在传统货运中，影响末端配送效率最关键的点，是配送员对他所负责区域的熟悉程度。这也是为何在传统货运领域，配送站或配送员，就会固定负责某几个新村的诱因之一。由于越熟悉，配送效率都会越高。
即时配送场景也类似，每位骑手须要尽量固定地去熟悉一片店家或则配送区域。同时，对于管理者而言，站点的管理范围也比较明晰。另外，若果有新店家上线，也很容易确定由那个配送站来提供服务。所以，这个问题有好多营运管理的诉求在其中。
区域规划影响配送效率
其实，区域规划项目的发起，存在好多问题须要解决。主要包括以下三种情况：
配送区域里的店家不聚合。这是一个典型站点，店家主要集中在左下角和右上角，导致骑手在区域里取餐、送餐时执行任务的地理位置十分分散，须要不停往返两个商圈，无效跑位十分多。
区域奇形怪状，空驶严重。之前在店面上线外卖平台的发展过程中，好多地方本来没有店家，后来上线的店家多了，就单独作为一个配送区域。这样的区域形状可能还会不规则，致使骑手好多时侯在区域外跑。而店家和骑手都有绑定关系，骑手只能服务自己区域内的店家，因而骑手未能接到配送区域外的取餐任务，空驶率特别高。好多时侯骑手送完餐以后，只能空跑回去才可能接到新任务。
站点的大小不合理。图三这个站点，每晚的单量只有一二百单。假如从骑手平均单量的角度去配置骑手的话，只能配置3~4个骑手。假如某一两个人忽然有事要事假，可想而知，站点的配送体验一定会显得十分差，营运管理难度会很高。反之，假如某一个站点显得十分大，站长也不可能管得了这么多的骑手，这也是一个问题。所以，须要给每位站点规划一个合理的单量规模。
既然存在如此多的问题，这么做区域规划项目就显得十分有必要。这么，哪些是好的区域规划方案？基于统计剖析的优化目标设定。
多目标优化问题
优化的三要素是：目标、约束、决策变量。
第一点，首先要确定优化目标。在好多比较稳定或则传统的业务场景中，目标十分确定。而在区域规划这个场景中，如何定义优化目标呢？首先，我们要思索的是区域规划主要影响的是哪些。从昨天几类问题的剖析可以发觉，影响的主要是骑手的顺路性、空驶率，也就是骑手平均为每一单付出的路程成本。所以，我们将问题的业务目标定为优化骑手的单均行驶距离。基于现有的大量区域和站点积累的数据，做大量的统计剖析后，可以定义出这样几个指标：店家聚合度、订单的聚合度、订单重心和店家重心的偏离程度。数据剖析结果说明，这几个指标和单均行驶距离的相关性很强。经过这一层的建模转化，问题明晰为优化这三个指标。
第二点，须要梳理业务约束。在这方面，我们耗费了大量的时间和精力。例如：区域单量有上限和下限。区域之间不能有重合，不能有店家归多个区域负责。所有的AOI不能有遗漏，都要被某个区域覆盖到，不能出现店家没有站点的服务。
基于业务场景的约束条件梳理
最难的一个问题，虽然是要求区域边界必须沿路网。原本我们很难理解，由于本质上区域规划只是对店家进行分类，它只是一个店家集合的概念，为何要画出边界，还要求边界沿路网呢？虽然刚刚介绍过，区域边界是为了回答假如有新店家上线究竟属于那个站点的问题。并且，从一线管理成本来讲，更习惯于哪条路以东、哪条路以南这样的叙述方法，以便记忆和理解，提升管理效率。所以，就有了这样的诉求，我们希望区域边界更“便于理解”。
整体方案设计
在目标和约束条件确定了以后，整体技术方案分成三部份：
首先，按照三个目标函数，确定店家最优集合。这一步比较简单，做运筹优化的朋友都可以快速地解决这样一个多目标组合优化问题。
前面的步骤比较难，如何把区域边界画下来呢？为了解决这个问题，配送团队和美团地图团队进行合作。先借助路网信息，把城市劈成若干互不重叠的六边形，之后按照估算几何，将一批店家对应的六边形拼成完整的区域边界。
最后，用美团自主研制的配送仿真系统，评测这样的区域规划对应的单均行驶距离和体验指标是否符合预期。由于一线直接变动的成本极其高，仿真系统就起到了极其好的作用。
下边是一个实际案例，我们用算法把一个城市做了重新的区域规划。其实，这儿必需要指出的是，在这个过程中，人工介入还是十分必要的。对于一些算法很难处理好的边角场景，须要人工进行微调，使整个规划方案愈发合理。中间的图是算法规划的结果。
经过试点后，测试城市整体的单均行驶距离增长了5%，平均每一单骑手的行驶距离节约超过100米。可以想像一下，在如此庞大的单量规模下，每单平均降低100米，总节约的路程、节省的电池车电量，都是一个十分可观的数字。更重要的是，可以让骑手自己显著觉得到自己的效率得到了提高。
落地应用疗效明显
智能骑手轮班
业务背景
这是随着外卖配送的营业时间越来越长而衍生出的一个项目。初期，外卖只服务午高峰到晚高峰，后来你们渐渐可以点早餐、点晚餐。到现在，好多配送站点早已提供了24小时服务。并且，骑手不可能全天24小时复工，劳动法对每晚的工作时长也有规定，所以这一项目势在必行。
另外，外卖配送场景的订单“峰谷效应”非常显著。上图是一个实际的进单曲线。可以看见全天24小时内，午晚高峰两个时段单量十分高，而闲时和烧烤相对来说单量又少一些。因而，系统也没办法把三天24小时依照每位人的工作时长做平均切分，也须要进行轮班。
对于轮班，存在两类方案的选型问题。好多业务的轮班是基于人的维度，用处是配置的细度十分精细，每位人的工作时段都是个性化的，可以考虑到每位人的诉求。并且，在配送场景的缺点也显而易见。假如站长须要为每位人去规划工作时段，其难度可想而知，也很难保证分配的公正性。
轮班方案选型
配送团队最终选用的是按组轮班的方法，把所有骑手分成几组，规定每位组的复工时段。之后你们可以按组轮岗，每位人的每位班次还会轮到。
这个问题最大的挑战是，我们并不是在做一项业务工具，而是在设计算法。而算法要有自己的优化目标，这么轮班的目标是哪些呢？假如你要问站长，怎样样的轮班是好的，可能他只会说，要让须要用人的时侯有人。但这不是算法语言，更不能弄成模型语言。
决策变量及目标设计
为了解决这个问题，首先要做设计决策变量，决策变量并没有选用班次的起止时刻和结束时刻，那样做的话，决策空间太大。我们把时间做了离散化，以半小时为细度。对于三天来讲，只有48个时间单元，决策空间急剧削减。之后，目标定为运力需求满足订单量的时间单元最多。这是由于，并不能保证站点的人数在对应的进单曲线情况下可以满足每位单元的运力需求。所以，我们把业务约束转化为带惩罚的目标函数。这样做还有一个用处，那就是没必要晓得站点的总人数是多少。
在建模层面，标准化和通用的模型才是最优选。所以，我们把人数做了归一化，算法分配每位班次的骑手比列，但不分人数。最终只须要输入站点的总人数，就得到每位班次的人数。在算法决策的时侯，不决策人数、只决策比列，这样也可以把单量进行归一化。每位时间单元的进单量乘以每天峰值时间单元的单量，也弄成了0~1之间的数字。这样就可以觉得，假如某个时间单元内人数比列小于单量比例，这么叫作运力得到满足。这样，通过各类归一化，弄成了一个通用的问题，而不须要对每种场景单独处理。
另外，这个问题涉及大量复杂的强约束，涉及各类管理的诉求、骑手的体验。约束有好多，例如每位工作时段尽量连续、每个工作时段持续的时间不过短、不同工作时段之间休息的时间不过短等等，有好多这样的业务约束。梳理以后可以发觉，这个问题的约束太多了，求最优解甚至可行解的难度太大了。另外，站长在使用轮班工具的时侯，希望能马上给出系统轮班方案，再快速做后续微调，因而对算法运行时间要求也比较高。
算法核心思想
基于约束条件的构造算法与局部搜索
综合考虑以上诱因，我们最终基于约束条件，按照启发式算法构造初始方案，再用局部搜索迭代优化。使用这样的形式，求解速率才能达到微秒级，并且可以给出任意站点的轮班方案。整体的优化指标还不错。其实，不保证是最优解，只是可以接受的满意解。
落地应用疗效
这些算法也在自营场景做了落地应用，跟这些轮班经验丰富的站长相比，疗效基本持平，一线的接受程度也比较高。最重要的是带来轮班时间的节约，每次轮班几分钟就搞定了，这样可以让站长有更多的时间去做其它的管理工作。
骑手路径规划
具体到骑手的路径规划问题，不是简单的路线规划，不是从a到b该走哪条路的问题。这个场景是，一个骑手头上有好多配送任务，这种配送任务存在各类约束，如何选择最优配送次序去完成所有任务。这是一个NP难问题，当有5个订单、10个任务点的时侯外卖配送系统，就存在11万多条可能的次序。而在高峰期的时侯，骑手常常背负的不止5单，甚至有时侯一个骑手会同时接到十几单，这时侯可行的取送次序就弄成了一个天文数字。
算法应用场景
再看算法的应用场景，这是智能调度系统中最为重要的一个环节。系统派单、系统改派，都依赖路径规划算法。在骑手端，给每位骑手推荐任务执行次序。另外，用户点了外卖然后，美团会实时展示骑手当前任务还须要执行几分钟，要给用户提供更多预估信息。如此多应用场景，共同的诉求是对时效的要求十分高，算法运行时间要越短越好。
然而，算法仅仅是快就可以吗？并不是。由于这是派单、改派这种环节的核心模块，所以算法的优化求解能力也十分重要。假如路径规划算法不能给出较优路径，可想而知，下层的委派和改派很难作出更好的决策。
所以，对这个问题做明晰的梳理，核心的诉求是优化疗效必须是稳定的好。不能此次的优化结果好，上次就不好。另外，运行时间一定要短。
核心设计思想
在求解路径规划这类问题上，好多公司的技术团队，都经历过这样的阶段：原本，采用类似遗传算法的迭代搜索算法，并且随着业务的单量变大，发觉算法历时太慢，根本不可接受。之后，改为大规模邻域搜索算法，但算法仍然有很强的随机性，由于没有随机性在就没办法得到比较好的解。而这些基于随机迭代的搜索策略，带来很强的不确定性，在问题规模大的场景会出现特别多的BadCase。
另外，迭代搜索历时太长了。主要的缘由是，随机迭代算法是把组合优化问题当作一个单纯的问题去求解，极少用到问题结构特点。这种算法，求解TSP时这样操作，求解VRP时也这样操作，求解还是这样操作，这种类似“无脑”的方法很难有出众的优化疗效。
所以，在这个项目中，基本可以确定这样的技术路线。首先，只能做启发式定向搜索，不能在算法中加随机扰动。不能容许同样的输入在不同运行时刻给出不一样的优化结果。之后，不能用普通迭代搜索，必须把这个问题结构特点挖掘下来，做基于知识的多样化搜索。
说上去容易，具体要怎样做呢？我们觉得，最重要的是看待这个问题的视角。这儿的路径规划问题，对应的精典问题模型，是开环TSP问题，或是开环VRP的变种么？可以是，也可以不是。我们做了一个有意思的建模转换，把它看作流水线调度问题：每位订单可以觉得是job；一个订单的两个任务取餐和送餐，可以觉得是一个job的。任意两个任务点之间的通行时间，可以觉得是序列相关的打算时间。每一单承诺的送达时间，包括预订单和即时单，可以映射到流水线调度问题中的提早和拖期惩罚上。
算法应用疗效
做了这样的建模转换以后，流水线调度问题就有了大量的启发式算法可以借鉴。我们把一个精典的基于问题特点的启发式算法做了适配和改进，就可以得到特别好的疗效。相比于之前的算法，历时增长70%，整体优化疗效不错。由于这是一个确定性算法，所以运行多少次的结果都一样。我们的算法运行一次，跟其它算法运行10次的最优结果相比，优化疗效是持平的。
订单智能调度
配送调度场景，可以用物理语言描述。它除了是一个业务问题，更是一个标准的组合优化问题，而且是一个“马尔可夫决策”过程。
调度问题的物理描述
并非对于某个时刻的一批订单做最优分配就足够，还须要考虑整个时间窗维度，每一次指聚会旁边的影响。每一次订单分配，都影响了每位骑手后续时段的位置分布和行进方向。假如骑手的分布和方向不适宜未来的订单结构，相当于增加了后续调度时刻最优性的天花板。所以，要考虑长周期的优化，而不是一个静态优化问题。
问题简化剖析
为了易于理解，我们还是先看某个调度时刻的静态优化问题。它不仅仅是一个算法问题，还须要我们对工程构架有特别深刻的理解。由于，在对问题输入数据进行拆解的时侯，会发觉算法的输入数据太庞大了。例如说，我们须要任意两个任务点的导航距离数据。
而我们面临的问题规模，前几年只是区域维度的调度细度，一个商圈一分钟峰值100多单，匹配几百个骑手，而且这些乘积关系对应的数据早已十分大了。如今，因为美团有更多业务场景，例如跑腿和全城送，会跨特别多的商圈，甚至跨越半个城市，所以只能做城市级的全局优化匹配。目前，调度系统处理的问题的峰值规模，是1万多单和几万名骑手的匹配。而算法容许的运行时间只有几秒钟，同时对显存的消耗也十分大。
另外，配送和网约车派单场景不太一样。打车的调度是做司机和旅客的匹配，本质是个二分图匹配问题，有方程时间的最优算法：KM算法。打车场景的难点在于，怎么描画每对匹配的权重。而配送场景还须要解决，对于没有方程时间最优算法的情况下，怎样在指数级的解空间，短时间得到优化解。假如觉得每一单和每位骑手的匹配有不同的适应度，这么这个适应度并不是可线性叠加的。也就意味着多单对多人的匹配方案中，任意一种匹配都只能重新运算适应度，其估算量可想而知。
总结一下，这个问题有三类挑战：
性能要求极高，要做到万单对千人的秒级求解。我们之前做了一些比较有意思的工作，例如基于历史最优委派的结果，用机器学习模型做分株。基于大量的历史数据，可以帮助我们节约好多无用的匹配方案评价。
动态性。作为一个MDP问题，须要考虑动态优化场景，这涉及大量的预估环节。在只有当前未完成订单的情况下，骑手怎样执行、每一单的完成时刻怎么预估、未来时段会进什么结构的订单、对业务指标和效率指标形成如何的影响……你可能会认为这是一个典型的加强学习场景，但它的难点在于决策空间太大，甚至可以觉得是无限大的。目前我们的思路，是通过其它的建模转换手段进行解决。
配送业务的随机诱因多。例如店家的出餐时间，其实是很长时间内都未能解决的随机性。就连历史上每一个已完成的订单，店家出餐时间的真值都很难获得，由于人为点击的数据并不能保证确切和完整。店家出餐时刻不确定，这个随机诱因永远存在，而且十分阻碍配送效率的提高。另外，在客户位置交付的时间也不确定。写字楼工作日的午高峰，上扶梯、下扶梯的时间，很难确切进行预估。其实，我们也在不断努力让预估显得更精准，但随机性永远存在。对于骑手来说，平台无法规定每位骑手的任务执行次序。骑手在配送过程中可以自由发挥，所以骑手执行次序的不确定性也仍然存在。
为了解决这种问题，我们尝试用鲁棒优化或是随机规划的思想。并且，假如基于随机场景取样的方法，运算量又会急剧降低。所以，我们须要进行基于学习的优化，优化不是单纯的机器学习模型，也不是单纯的启发式规则，优化算法是结合真实数据和算法设计者的经验，学习和演化而得。只有这样，就能在性能要求极高的业务场景下，快速地得到鲁棒的优化方案。
公众号
泛物流行业IT及营运知识分享传播、从业人士互帮互助外卖配送系统，覆盖快件快运/互联网货运平台/城配/即时配送/3PL/仓配/报关/冷链/货运软件公司/货运武器/货运手动化设备/货运机器人等细分行业。辨识两侧二维码即刻加入我们，假如你是以上行业公司中的从业人士加营运小哥微信（两侧二维码）后可入群交流。
知识星球
知识星球：包含期货/商业咨询机构的行业研究报告(超10000份，行业内相关报告超1000份)；行业内企业实战资料(产品研制、运营、企业管理一线实战资料超100G)。聚焦上游供应链、电商（含跨境）、零售及泛物流行业（快件快运、合同货运、电商仓配、跨境货运、园区、冷链等细分市场）。
行业研究报告+真实业内企业实战资料，加入星球后全部可下载。
如今添加营运小哥微信，可享限时惊喜特惠让利哦~
免责声明：部分文章信息来源于网络以及网友投稿，本站只负责对文章进行整理、排版、编辑，出于传递更多信息之目的，并不意味着赞同其观点或证实其内容的真实性，如本站文章和转稿涉及版权等问题，请作者在及时联系本站，我们会尽快为您处理。
