【笔记】从架构到算法，详解美团外卖订单分配内部机制

外卖订单分配内部机制"/>

【笔记】从架构到算法，详解美团外卖订单分配内部机制

案例来源：微信公众号@机器之心 案例地址：=MzA3MzI4MjgzMw==&mid=2650732373&idx=4&sn=d497cd5ba2fde7f0fece157876443ae9&chksm=871b332bb06cba3d1e1d8322b5d3d8970c3842cc8646da1b5bb4d57f6ac18f0f066da3099b06&scene=0#rd （以下为案例的简要概述，便于之后能快速检索到相关内容。部分文字与图片可能直接来自原文，如有侵权请告知，谢谢）
0. 背景 1）美团旗下40万骑手，峰值配送1600万单，提高配送效率意义重大，因此美团推出了用于即时配送的「超级大脑」——O2O 即时配送智能调度系统 2）最简单的订单分配方式是抢单模式，但因为每个骑手的信息匮乏，容易陷入局部最优解；中心化的人工调度一般优于抢单模式，但效率低，且人力成本高 3）系统需求：在正确的时间将订单分配给最合适的骑手，设计最优配送路线，并预估超时情况及时进行改派操作，实现订单和骑手的最优匹配
1. 基本架构 1）数据平台：包括骑手轨迹数据、配送业务数据、实时环境数据等基础数据 2）机器学习：出餐时间估计、交付时间估计、未来订单估计、路径耗时估计等预测数据 3）运筹优化：基于基础数据与预测数据，进行系统派单、路径规划、自动改派、仿真系统等
2. 问题建模 决策优化的数学模型包括三个要素： 1）决策变量：表示可以进行的决策。订单分配的决策变量是“订单分配给哪个骑手”、“骑手的建议行驶路线” 2）优化目标：表示通过调整决策变量，我们希望优化的指标。这里可以分为两个维度，对用户而言，“最少配送时间”、“最小超时率”；对骑手而言，“最小化单均行驶距离”、“最小化单均消耗时间”。 多优化目标情况下，美团采用人工设定目标函数结构，仿真系统+实际数据设定目标函数参数的方式，来确定最终的优化目标函数。 3）约束条件：一个骑手分配任务的时间限制等。 以上只是单任务的优化，但实际目标是全局优化，因此还要考虑未来可能产生的订单。
3. 机器学习 配送过程中，商家取餐与交付用户占到配送时长的一半以上。准确预测取餐和交付时间，可以减少骑手等待时间。 1）商家出餐受到品类、时段、天气等因素影响。 2）用户交付受到楼层、是否处于高峰时段、有没有电梯等。 这两个时间使用机器学习的方式进行预测。进一步，美团建立调度模型的自学习机制，借鉴多变量控制理论的思想，调整模型中的相关参数。模型平均预估偏差小于4分钟，10分钟置信度达到90%以上。
4. 运筹优化 将配送问题划分为两个层次： 1）订单分配方案优化：把一批订单分配至骑手，使目标（如配送时长、准时率等）最优。 2）骑手路径优化：已知订单的情况下，确定最佳配送线路。 解决思路有三种： 1）采用迭代的方式，通过订单分配优化算法进行初始的订单分配，然后通过骑手路径优化算法获取各骑手的最佳行驶路线，进而，订单分配优化算法根据骑手路径优化结果调整分配方案。这两个层次不断反复迭代，最终获得比较满意的解 2）二分图解：先对一个人可以完成的订单打包成一个任务，然后用二分图匹配算法（匈牙利算法、KM算法）解决 3）强化学习：引入了离线学习和在线优化相结合的机制，离线学习得到策略模型，在线通过策略迭代，不断寻求更优解。通过不断地改进算法，在耗时下降的同时，算法的优化效果提升 50% 以上。【具体思路？】
5. 应对突发情况 常见的突发情况有：商家出餐异常慢、联系不上用户、车坏了、临时交通管制等。 解决方案有两种： 1）延时调度：某些情况下订单可以不立即分配，在不影响订单超时的情况下，寻找最优指派时间。 2）自动改派：实时评估骑手的位置和订单完成情况，分析是否有超时风险，及时改派。
6. 仿真系统 系统能够模拟真实的配送过程和线上调度逻辑，并给出按照某种配送策略下的最终结果。该模拟过程和线下的实际导航、地理数据完全一致，系统同时能够根据实际配送数据进行模型自学习，不断提升仿真精度。
7. 应用效果 1）中关村配送站在 5 月 6 日切换了派单模式和相应的算法，大望路配送站的调度策略维持不变。可以看出，在切换后，中关村的平均配送时长有了 2.9 分钟的下降，严重超时率下降了 4.7 个百分点（相比较对比区域）。 2）在更广泛的区域上进行了测试，结果表明，在体验指标不变的前提下，新策略能够降低 19% 的运力消耗。换言之，原来 5 个人干的活，现在 4 个人就能干好，所以说，智能调度在降低成本上价值是很大的。