创作者：北京清华大学操纵科学合理与工程博士，在职美团点评研究者@郝井华 ，与此同时也是『运筹帷幄OR运等』交通出行与货运物流版面的编写/见刊。热烈欢迎原连接分享，付钱转截请前去 @留德华叫兽 的首页获得信息，盗用必究。敬请期待和蔓延本栏目及同名的微信公众号，会邀约全世界著名专家学者相继公布计量经济学、人工智能化中优化理论等有关干货知识、知乎问答Live及行业资讯：『运筹帷幄OR运等』互联网大数据人工大数据时代的计量经济学--知乎专栏
责编：@留德华叫兽系英国克莱姆森大学计量经济学研究生，Ph.D. Candidate，后换工作至欧盟国家玛丽居里博士研究生新项目，期内前去西班牙IBM Cplex见习大半年，法国巴黎综合性工院学术研究浏览一季，在职德国海德堡高校交叉科学计算中心、组合优化试验室研究者，主要机器视觉、（医药学）图象处理。
【业内】系列产品文章内容为『运筹帷幄OR运等』全新发布的版面，目地是因为提升学界与学术界的深层沟通交流，在这里热烈欢迎工业领域的技术性文文章投稿，用精英团队技术性案例讲话，文尾能付简洁明了招聘职位。
文中先发于：【揭密】美团日订单数破1600万身后的“超强大脑”之订单分派，受创作者授权委托转截如下所示。
编者按
美团点评日前进行全新一轮股权融资，估价做到300亿美金。此次股权融资后可能在人工智能化、没有人配送等前沿科技产品研发上加大力度。但人们并并不是为技术性而技术，实际上，人工智能技术早已在支撑点着大家诸多业务场景。
以日订单量刚提升1600万的送餐业务流程为例子，智能化调度系统软件便是全部网站的“超强大脑”，充分发挥了极为重要的功效。大家将根据一系列的内容来为我们解开这身后的商业秘密。今天系列产品的第一篇，解读外卖送餐调度中重要难题之一——订单分派。
前言近期2年，外卖送餐的市场容量不断以较快速率发展趋势。最近美团订单量最高值做到1600万，是全世界范围较大的外卖APP。现阶段各外卖APP已经高品质提供、配送感受、手机软件感受等各层面进行全面的市场竞争，在其中，配送时效性、按时率做为履行合同阶段的主要指标值，是外卖APP的核心竞争优势之一。
要提高消费者的配送时效性和按时率，最立即的办法是配置较多的配送员，扩张运输能力经营规模，殊不知这也代表着配送成本费会很高。因此，外卖APP一方面要追求完美好的配送感受，另一方面又被配送的人工成本制约。怎样在配送感受和配送成本费中间获得最好的均衡，是及时配送服务平台存活的基石和根本所在。
伴随着网络时代的前半场完毕，用户增长收益推动的粗放型发展模式早已无法融入下一场的争夺。怎样根据方式方法，让美团服务平台超出40万的骑手高效工作，在用户满意度不断增强的与此同时，减少配送成本费、提升骑手满意率、推动配送系统软件的智能化和智能化系统，是美团外卖配送技术性精英团队自始至终专注于处理的难点。
在过去的一年多時间里，美团外卖配送精英团队在人工神经网络、运筹帷幄提升、模拟仿真等层面，持续发力，深入分析，并对于及时配送情景特性将以上技术性灵活运用，发布了用以及时配送的“超强大脑”——O2O及时配送智能化调度系统软件。
系统最先根据提升设置配送费及其预估送到時间来调节订单构造；在接受订单以后，考虑到骑手部位、在途订单状况、骑手工作能力、店家上餐、交货难度系数、气温、自然地理实时路况、将来订单数等要素，在恰当的时长将订单分派给最好的骑手，并在骑手实行环节中随时随地预测订单请求超时状况并动态性开启报到证改派实际操作，完成订单和骑手的信息最佳配对。
与此同时，系统软件接单后，为骑手提醒该企业的预估上餐時间和合理性的配送路线，并根据视频语音方法和骑手完成高效率互动；在骑手送完订单后，系统软件依据订单市场需求分析和运输能力遍布状况，告之骑手不一样商业圈的运输能力要求状况，完成闲暇时的运输能力调度。
根据以上技术性和策略的引进，持续改进了客户体验和配送成本费：订单的均值配送时间从2015年的41分鐘，降低到32分鐘，进一步减少至28分鐘，另一方面，在骑手薪酬稳步提升的条件下，单均配送成本费也拥有20%以上的减缩。
文中将之外卖情景下以上调度步骤中的重要环节之一——订单分配问题为例子，论述该问题的实质特性、方式变化、计划方案构架和重要关键点，为各位在处理业务流程优化问题上带来一个实例参照。
外卖送餐订单分派问题描述外卖送餐订单的分配问题一般可模型为含有多个繁杂管束的DVRP（Dynamic Vehicle Routing Problem）问题。这类问题一般可表达为：有一定数目的骑手，每名骑手的身上有多个订单已经配送全过程中，在过去的一段时间（如1分鐘）内形成了一批新订单，已经知道骑手的行进速率、随意2点间的行车间距、每一个订单的上餐時间和交货時间（骑手抵达客户所在城市以后将订单交货至客户需要的時间），那麼如何把这批新订单在恰当的时长分派至恰当的骑手，促使客户体验获得保障的与此同时，骑手的配送高效率最大。
下面的图是外卖送餐配送情景下一个配送地区上诸多骑手的遍布平面图。
及时配送订单分配方式的演变在O2O行业，订单和服務给予方的配对问题是一个十分核心的问题。在外卖行业发展趋势前期关键依靠骑手抢单方式和人工接单方式。抢单模式的优点是开发设计难度系数低，生产经营者（如驾驶员、骑手）的可玩性较高，可以根据自己的必须开展抢单，但其缺陷也很显著：骑手/驾驶员只考虑到自己的情景要求，作出一个部分近优的挑选，殊不知因为每一个骑手把握的数据比较有限又只从自己权益考虑来决策，造成配送总体高效率不高，从局端看来，还存有很多订单没有人抢或是抢了之后导致服务水平没法确保（由于一部分骑手没法精确预测自身的配送服务能力）的情景，客户体验非常差。
人工接单的方法，从订单分派的結果上看来，一般好于抢单方式。在订单量、骑手数相对性较为少的情况下，有工作经验的调度员可以依据订单的特性特点、骑手的工作能力、骑手已接单子状况、环境要素等，在骑手中逐一核对，依据多个工作经验标准选择一个适宜的骑手来配送。一般而言，人工调度一个订单通常最少必须一两分钟上下的时间段能够进行。
殊不知，伴随着外卖送餐订单经营规模的日益提高，在受欢迎商业圈（周围3千米上下）的高峰期，1min的時间内很有可能会出现50单以上，在这样的情况下，规定人工调度员每1-2秒左右作出一次有效的调度决策，显而易见是不太可能的。
另一方面，因为及时配送全过程的多元性，要作出有效的配对决策，规定调度员对配送范畴内各店家的上餐速率、各客户详细地址的配送难度系数（例如有的办公楼午高峰期要等很长期的电梯轿厢）、各骑手本身的配送专用工具/了解的店家和客户范畴/工作习惯这些要有特别深层次的掌握，在这个基础上具有综合提升工作能力，考虑到将来进订单数、降低空驶等要素，作出全局性近优的挑选，这对人工调度员来讲，又是一项极为艰巨的任务。此外，美团有数千个配送地区，假如选用人工调度方法则每一个地区均必须配备调度员，会耗费十分高的人工成本。
该问题尽管繁杂，但仍具有一定的周期性。尤其是移动互联高度发达的今日，大家有着骑手配送订单全过程中的各种很多历史记录，e.g. 骑手的部位、订单情况、天气信息、LBS数据信息，运用这一些数据信息佐以有关数学软件促使完成计算机软件的全自动接单变成很有可能。
系统软件接单具有如下所示优点：
系统软件可以在全局性方面上把握和配送相关的骑手、店家、客户、订单等各种信息内容，在这个基础上，可以作出全局性较好的计划方案，进而提高配送高效率和配送感受，降低配送成本费；明显缓解人工调度员的工作中，进而减少人工成本费，人工调度员只要在一些出现意外情景（如配送员发生紧急状况没法再次配送等）产生的情况下开展干涉就可以。因此，伴随着数据采集的逐步完善和人工智能技术的持续完善，根据人工智能化的办法来开展订单的分派，具备较大的盈利，变成每个配送服务平台科学研究的焦点之一。
订单智能化分派系统软件的基础构架美团每日造成大量的订单配送日志、行车运动轨迹数据信息。根据对配送互联网大数据开展剖析、发掘，会获得每一个客户、房屋、店家、骑手、地理区域的差异化信息内容，及其相关各自然地理区块链骑车途径的高效数据信息，那麼订单智能化分派系统软件的目的是根据数据管理平台，依据订单的配送要求、地形地貌及其每名骑手的人性化特性，完成订单与骑手的高效率动态性最佳配对，进而为每一个客户和店家给予最好的配送服务项目，并减少配送成本费。
及时配送数据管理平台完成对骑手运动轨迹数据信息、配送业务流程数据信息、特点数据信息、指标值信息的全方位工作管理和监管，并利用实体模型服务平台、特点服务平台适用有关优化算法对策的快速迭代和提升。
人工神经网络控制模块承担从统计数据中寻找规律性和专业知识，例如对店家的上餐時间、到客户所属房屋上下楼梯的時间、将来的订单、骑行速度、交通信号灯用时、骑车导航栏途径等原因开展精准预计，为调度决策给予精确的基础信息；而运筹帷幄提升控制模块则在及时配送数据管理平台及其机器学习算法的预测分析数据信息基本上，选用最优化理论、增强学习等优化策略开展测算，作出全局性最优化的分派决策，并和骑手高效率互动交流，解决实行环节中的问题，完成动态性最优控制。
问题分析和模型：高效率求得问题的第一步理论研究行业有很多传统的优化问题（如旅行商问题TSP、装箱问题BP、车子途径问题VRP等），他们的决策自变量、提升总体目标和约束方程通常十分确立、简易。这在科学研究中是很有必要的，因为它简单化了问题，让学者把心力放到怎样设计方案高效率优化算法上。
殊不知，因为具体工业生产情景的多元性，绝大多数具体情景的决策优化问题难以叙述的如此简易，这时，如果不具体分析具体工作全过程特性而异常地创建了和具体情景不符合的实体模型，当然会导致大家得到的所说“最优解”运用于具体后也会“水土不服情况”，最终被很多埋怨乃至抛下。因此大家说，精确模型是具体决策提升新项目的第一步，也是最重要的一步。
精确模型，包含2个层面的问题：
大家正确认识了具体业务场景的优化问题，而且根据某类流于形式语言表达实现了精确叙述；大家创建的模式中，涉及到的各种主要参数和数据信息，可以精确得获得。在以上2个前提条件下，选用对应的高效率蚁群算法求得实体模型所获得的最优解，便是切合实际情景要求的最佳决策计划方案。第一个问题，一般是根据业务流程调查、剖析并融合建模软件来获得；而处理第二个问题，则越来越多地要依靠数据统计分析、人工神经网络、数据挖掘算法融合行业专业知识，模型拟合开展准确的量化分析表述。
一个决策优化问题的数学分析模型，一般包含三个因素：
决策自变量提升总体目标约束方程在其中，决策自变量表明了大家期待优化算法来协助大家做什么决策；提升总体目标则指的是大家根据调节决策自变量，促使什么指标值获得提升；而约束方程则是在提升决策的历程中所考虑到的各种约束性要素。
为了更好地表明及时配送情景下的订单分配问题，大家先引进多个标记界定：
在及时配送调度情景下，决策自变量包含每个订单必须调整的骑手，及其骑手的提议行车路线。
及时配送订单分配问题的改进总体目标一般包含期待客户的单均配送时间尽可能短、骑手投入的工作尽量避免、请求超时率尽可能低，这些。一般可表示为：
针对实际情景下的配送订单分配问题，设定什么指标值做为目标函数是一个比较繁杂的问题。
缘故取决于2个层面：
1）该优化问题是多方向的，且每个总体目标在差异时间段、不一样自然环境下会出现区别。举例说明，阅历丰富的调度员期待在负荷较低的空余时间段，将订单派给这些不了解地区地貌的骑手，以锻练骑手工作能力；在气温极端的情形下，期待可以忍受一定的请求超时率大量地派顺道单，以提升订单消化吸收速率等。这种考虑有其合理化，必须在提升总体目标中进行反映。
2）欠缺有利于量化分析提升总体目标的数据信息。假如带标签数据充足多，与此同时假定调度员的工作能力充足好，那麼可以根据大数据挖掘的方式获得提升总体目标的量化分析表述。遗憾的是，这两个前提条件也不创立。大家对于该难点，最先根据深层次调查确立业务流程困扰和总体目标，在这个基础上，选用原理和数据信息紧密结合的方法，由人工设定目标函数公式的构造，根据模拟仿真系统软件（下面详细介绍）和真实数据信息去设定目标函数公式的主要参数，来确认最后选用的目标函数形状。
及时配送调度问题的约束方程最少包含如下所示几类种类：
除开以上管束外，有时候还要考虑到一部分订单只有由具有一些特征的骑手来配送（例如火锅店订单只有交到带上专业武器装备的骑手等）、移动载具的容积限定等。
以上仅仅对于给出的一批订单开展配对决策的优化问题在模型时需需考虑到的一部分要素。实际上，在外卖送餐配送情景中，大家期待的并不是一次决策的最佳，反而是对策在一段时间运用后的积累盈利较大。
也就是说，我们不追求完美某一个订单的分派是最好的，反而是期待一天出来，全部的订单分派結果总体上是全局性最优化的。这进一步扩大了问题模型的难度系数，缘故取决于优化算法在做订单分派决策的情况下，将来的订单信息内容是不确定性的，如下图所示，在t时时刻刻开展决策的情况下，既必须考虑到已确认的订单，还要考虑到将来的并未明确的订单。运筹帷幄提升行业中的马尔可夫决策全过程描写的就这样的一类在不确定性、信息内容不完备自然环境下的条件随机场决策优化问题。
问题模型中的人工神经网络以往，在信息化管理水准较低的条件下，许多工业生产运筹帷幄提升类的新项目失败，关键因素之一便是缺乏充足完备的数据采集基本专用工具，很多数据信息由人工依据工作经验设置，其精确性很难确保，且无法伴随着环境破坏而响应式调节，从而造成模型的优化结果渐渐变得不符合实际。机器学习领域有个谚语“Garbage in，garbage out”， 说明了精准的基础数据对于人工智能类项目的重要性。
即时配送订单分配场景下的数据包括两类：
直接通过业务系统采集可获取的数据，例如订单数据、骑手负载数据、骑手状态数据等。无法直接采集得到，需要预测或统计才能获取的数据，如商户出餐时间、用户驻留时间（骑手到达用户处将订单交付给用户的时间）、骑手配送能力等。第一类数据的获取一般由业务系统、骑手端App直接给出，其精度通过提升工程质量或操作规范可有效保证；而第二类数据的获取是即时配送调度的关键难点之一。
在订单的配送过程中，骑手在商家、用户处的取餐和交付时间会占到整个订单配送时长的一半以上。准确估计出餐和交付时间，可以减少骑手的额外等待，也能避免“餐等人”的现象。商家出餐时间的长短，跟品类、时段、天气等因素都有关，而交付时间更为复杂，用户在几楼，是否处于午高峰时段，有没有电梯等等，都会影响骑手（到了用户所在地之后）交付订单给用户的时间。
对这两类数据，无法单纯通过机理来进行预测，因为相关数据无法采集到（如商家今天有几个厨师值班、用户写字楼的电梯是否开放，等等）。为解决这些问题，我们利用机器学习工具，利用历史的骑手到店、等餐、取餐的数据，并充分考虑天气等外部因素的影响，建立了全面反映出餐能力的预测模型，并通过实时维度的特征进行修正，得到准确的出餐/交付时间估计。
进一步，我们建立了调度模型的自学习机制，借鉴多变量控制理论的思想，不断根据预估偏差调整预估模型中的相关参数。通过以上工作，我们通过调度模型来预估骑手的配送行为（取餐时间和送达时间），平均偏差小于4分钟，10分钟置信度达到90%以上，有效地提升了派单效果和用户满意度。
订单-骑手的匹配优化如果说上述建模过程的目标是构建和实际业务吻合的解空间，优化算法的作用则是在我们构建的解空间里找到最优的策略。配送调度问题属于典型的NP-Hard类离散系统优化问题，解空间巨大。以一段时间内产生50个订单， 一个区域有200骑手，每个骑手身上有5个订单为例，那么对应的调度问题解空间规模将达到pow(200,50)*10（部分为不可行解），这是一个天文数字！
所以，如何设计好的优化算法，从庞大的解空间中搜索得到一个满意解（由于问题的 NP-Hard特性，得到最优解几乎是不可能的），是一个很大的挑战。即时配送对于优化算法的另一个要求是高实时性，算法只允许运行2~3秒钟的时间必须给出最终决策，这和传统物流场景的优化完全不同。
针对此难题，我们采用了两个关键思路。一是问题特征分析。运筹优化领域有个说法叫“No Free Lunch Theory”，没有免费的午餐，含义是说如果没有对问题的抽象分析并在算法中加以利用，那么没有算 ** 比一个随机算法好。
换句话说，就是我们必须对问题特点和结构进行深入分析，才能设计出性能优越的算法。在运筹优化领域中的各类基础性算法也是这样的更多思路，如单纯形、梯度下降、遗传算法、模拟退火、动态规划等，它们的本质其实是假定了问题具备某些特征（如动态规划的贝尔曼方程假设，遗传算法的Building Blocks假设等），并利用这些假设进行算法设计。那么，针对配送调度的场景，这个问题可以被分解为两个层次：骑手路径优化和订单分配方案的优化。
骑手路径优化问题要解决的问题是：在新订单分配至骑手后，确定骑手的最佳配送线路；而订单分配优化问题要解决的问题是：把一批订单分配至相应的骑手，使得我们关注的指标（如配送时长、准时率、骑手的行驶距离等）达到最优。这两个问题的关系是：通过订单分配优化算法进行初始的订单分配，然后通过骑手路径优化算法获取各骑手的最佳行驶路线，进而，订单分配优化算法根据骑手路径优化结果调整分配方案。这两个层次不断反复迭代，最终获得比较满意的解。
第二个思路是跨学科结合。订单分配问题在业内有两类方法，第一类方法是把订单分配问题转换成图论中的二分图匹配问题来解决。但是由于标准的二分图匹配问题中，一个人只能被分配一项任务，所以常用的一个方法是先对订单进行打包，将可以由一个人完成的多个订单组成一个任务，再使用二分图匹配算法（匈牙利算法、KM 算法）来解决。
这种做法是一个不错的近似方案，优点是实现简单计算速度快，但它的缺点是会损失一部分满意解。第二类方法是直接采用个性化的算法进行订单分配方案的优化，优点是不损失获得满意解的可能性，但实际做起来难度较大。我们结合领域知识、优化算法、机器学习策略以及相关图论算法，基于分解协调思想，设计了骑手路径优化算法和订单分配优化算法。
进一步，我们利用强化学习的思想，引入了离线学习和在线优化相结合的机制，离线学习得到策略模型，在线通过策略迭代，不断寻求更优解。通过不断地改进算法，在耗时下降的同时，算法的优化效果提升50%以上。
我们在大量的实际数据集上进行评估验证，99%以上的情况下，骑手路径优化算法能够在30ms内给出最优解。为了有效降低算法运行时间，我们对优化算法进行并行化，并利用并行计算集群进行快速处理。一个区域的调度计算会在数百台计算机上同步执行，在2~3秒内返回满意结果，每天的路径规划次数超过50亿次。
应对强随机性即时配送过程的一个突出特点是线下的突发因素多、影响大，例如商家出餐异常慢、联系不上用户、车坏了、临时交通管制等等。这些突发事件造成的一个恶劣结果是， 虽然在指派订单的时刻，所指派的骑手是合理的，然而过了一段时间之后，由于骑手、订单等状态发生了变化，会变得不够合理。订单交给不合适的骑手来完成，会造成订单超时，以及骑手需要额外的等待时间来完成订单，影响了配送效率和用户体验的提升。
在出现上述不确定因素造成派单方案变得不合理的情况时，现有方法主要通过人工来完成，即：配送站长/调度员在配送信息系统里，查看各个骑手的位置、手中订单的状态及商户/用户的位置/期望送达时间等等信息，同时接听骑手的电话改派请求，在此基础上，分析哪些订单应该改派，以及应该改派给哪位骑手，并执行操作。
我们针对即时配送的强不确定性特点，提出了两点创新：一是延迟调度策略，即在某些场景订单可以不被指派出去，在不影响订单超时的情况下，延迟做出决策；二是系统自动改派策略，即订单即便已经派给了骑手，后台的智能算法仍然会实时评估各个骑手的位置、订单情况，并帮助骑手进行分析，判断是否存在超时风险。如果存在，则系统会评估是否有更优的骑手来配送。
延迟调度的好处一方面是在动态多变的不确定环境下，寻求最佳的订单指派时机，以提高效率；另一方面是在订单高峰时段存在大量堆积时，减轻骑手的配送压力。有了这两项策略，订单的调度过程更加立体、全面，覆盖了订单履行过程全生命周期中的主要优化环节，实现订单和骑手的动态最优化匹配。
仿真系统工业系统非常看重监控和评估，“No measurement, No improvement”。在工业优化场景中，如何准确评估算法的好坏，其重要性不亚于设计一个好的算法。然而，由于多个订单在线下可能会由同一名骑手来配送，订单与订单之间存在耦合关系，导致无法做订单维度的A/B测试。
而区域维度指标受天气、订单结构、骑手水平等外在随机因素影响波动比较大，算法效果容易被随机因素湮没从而无法准确评估。为此，我们针对即时配送场景，建立了相应的仿真模型，开发了配送仿真系统。
系统能够模拟真实的配送过程和线上调度逻辑，并给出按照某种配送策略下的最终结果。该模拟过程和线下的实际导航、地理数据完全一致，系统同时能够根据实际配送数据进行模型自学习，不断提升仿真精度。
一个高精度的配送仿真系统，除了能够对配送调度算法进行准确评估和优化，从而实现高效的策略准入控制外，另一个巨大的价值在于能够对配送相关的上下游策略进行辅助优化，包括配送范围优化、订单结构优化、运力配置优化、配送成本评估等等，其应用的想象空间非常大。
结语美团配送智能调度系统在应用之后，取得了非常不错的应用效果。下图说明了在订单结构比较类似的两个白领区域上的A/B测试结果。中关村配送站在5月6日切换了派单模式和相应的算法，大望路配送站的调度策略维持不变。可以看出，在切换后，中关村的平均配送时长有了2.9分钟的下降，严重超时率下降了4.7个百分点（相比较对比区域）。
同时，在更广泛的区域上进行了测试，结果表明，在体验指标不变的前提下，新策略能够降低19%的运力消耗。换言之，原来5个人干的活，现在4个人就能干好，所以说，智能调度在降低成本上价值是很大的。
美团配送的目标之一是做本地化的物流配送平台，那么，效率、体验和成本将成为平台追求的核心指标。人工智能技术在美团配送的成功应用有很多，通过大数据、人工智能手段打造一个高效、智能化、动态协同优化的本地智慧物流平台，能显著提高本地、同城范围内的物流配送效率，持续提升配送体验，降低配送成本。
本文为美团配送智能调度技术团队一年多时间的集体智慧结晶，感谢团队每一名成员的努力付出。同时，团队长期招聘运筹优化、机器学习算法工程师，感兴趣的同学请联系 @郝井华 haojinghua@meituan.com。
如果你是运筹学/人工智能硕博或在读，请在下图的公众号后台留言：“加微信群”。系统会自动辨认你的关键字，并提示您进一步的加群要求和步骤，邀请您进全球运筹或AI学者群（群内学界、业界大佬云集）。
同时我们有：【运筹学|优化爱好者】【供应链|物流】【人工智能】【数据科学|分析】千人QQ群，想入群的小伙伴可以关注下方公众号点击“加入社区”按钮，获得入群传送门。
学术界|工业界招聘、征稿等信息免费发布，请见下图：
扫码咨询与免费使用
申请免费使用