准时交货的订单分配策略：来自建模和优化
本文以订单分配问题为例，阐述了该问题的本质特征、模式转变、方案结构和关键点，为大家解决业务优化问题提供案例参考。
近两年，外卖市场规模持续高速发展。近日，美团的外卖订单达到1600万单，成为全球最大的外卖平台。目前，各外卖平台正从优质货源、外卖体验、软件体验等多个维度展开全方位竞争。其中，配送时效和准点率作为衡量合同履约情况的重要指标，是外卖平台的核心竞争力之一。
要想提高用户的配送时效和准时率，最直接的办法就是增派配送人员，扩大运力规模，但这也意味着配送成本会很高。因此，外卖平台一方面要追求良好的送餐体验，另一方面又受限于送餐的人工成本。如何在配送体验和配送成本之间取得最佳平衡，是即时配送平台生存的基础和关键。
随着互联网时代上半场的结束，用户增长红利驱动的粗放式发展模式已经难以适应下半场的竞争。如何用技术手段让美团外卖平台上的40万多骑手高效工作，降低配送成本，提高骑手满意度，在用户满意度持续提升的同时，推动配送系统自动化、智能化。团队一直在努力解决难题。
近一年多来，美团配送团队在机器学习、运营优化、仿真技术等方面持续发力和深入研究，并根据即时配送场景的特点，综合应用上述技术，并推出了即时交付新技术。“超级大脑”——O2O实时配送智能调度系统。
系统首先通过优化配送费用和预计配送时间来调整订单结构；
收到订单后，综合考虑骑手所在位置、在途订单情况、骑手能力、商家用餐、送货难度、天气、地理路况、未来订单量等因素，将订单分配给最合适的骑手在正确的时间。在执行过程中，可随时预测订单超时，动态触发重调度操作，实现订单与骑手的动态最优匹配；同时，系统发出订单后，会提示骑手预计的用餐时间和商家合理的送餐路线，并通过语音与骑手进行高效互动；
骑手下单后，系统根据订单需求预测和运力分布情况，通知骑手不同商圈的运力需求，实现空闲时间的运力调度。
通过上述技术和模式的引入，用户体验和交付成本不断提升：
订单的平均送达时间从2015年的41分钟下降到32分钟，进一步缩短到28分钟。另一方面，在骑手工资稳步提升的前提下，一个订单的平均配送成本也降低了20%以上。
本文将以上述外卖场景调度过程中的关键问题之一——订单分配问题为例，阐述该问题的本质特征、模式变化、解决方案架构和关键点，并提供为大家解决业务优化问题的案例。参考。
一、外卖订单分配问题说明
外卖订单的分配问题通常可以建模为具有多个复杂约束的 DVRP（动态车辆路由问题）问题。
此类问题一般可以表示为：
有一定数量的骑手，每个骑手在配送过程中有几个订单，过去一段时间（比如1分钟）产生了一批新订单。每个订单的用餐时间和送餐时间（骑手到达用户位置后，骑手将订单送至用户的时间），那么如何将这批新订单分配给右边正确的骑手时间，从而保证用户体验。同时，骑手的配送效率最高。
下图是外卖配送场景下一个配送区域内众多骑手的分布示意图。
2. 即时配送订单分配模型的演进
在O2O领域，订单与服务商的匹配是一个非常关键的问题。
外卖行业发展初期，主要依靠骑手的抢单模式和人工派单模式。
抢单模式的优点是开发难度较小，服务商（如司机和骑手）自由度较高，可以根据自己的需要抢单，但缺点也很明显：骑手/drivers 只考虑自己的场景需求，做出局部接近最优的选择。
但是，由于每个骑手的信息有限，只能根据自己的兴趣来做决定，因此配送的整体效率很低。从用户的角度来看，仍有大量订单没有被抢或被抢，导致服务质量无法保证（因为有些骑手如果无法准确预测自己的配送服务能力），用户体验是比较穷。
从订单分配的结果来看，人工派单方式普遍优于抢单方式。
在订单和骑手数量相对较少的情况下，有经验的调度员可以根据订单的属性、骑手的能力、骑手的订单状态、环境因素等，一一对比骑手，挑选更合适的骑手交付。一般来说，人工排单通常至少需要半分钟才能完成。
但随着外卖订单规模的不断扩大，在热门商圈（半径约3公里）高峰时段，1分钟内可能会有超过50个订单。显然不可能在 2 秒内做出合理的调度决策。
另一方面，由于即时配送过程的复杂性，需要做出合理的匹配决策，需要调度员确定配送范围内每个商家的配送速度和每个用户地址的配送难度。 （例如，有些写字楼在下午高峰时段要等很长时间）。长期电梯），每个骑手自己的送货工具/熟悉的商家和用户范围/工作习惯等应该有非常深入的了解配送决策方法，在此基础上，他们应该有协调和优化的能力，考虑到因素比如未来的接单量，减少空车。，做出近乎最优的选择，这对于人类调度员来说是一项极其艰巨的任务。
此外，美团外卖还有上千个外卖区。如果采用人工调度，每个区域都需要配备调度器，会消耗非常高的人工成本。
问题虽然复杂，但还是有一定规律的。尤其是在移动互联网高度发达的今天，我们在骑手配送订单的过程中拥有大量的历史数据（例如骑手的位置、订单状态、天气数据、LBS数据）。使用这些数据辅以相关数学工具，可以实现计算机系统。可以自动发送订单。
系统调度具有以下优点：
因此，随着数据采集的不断完善和人工智能技术的不断成熟，通过人工智能方式进行订单分配具有巨大的效益，已成为各配送平台研究的热点之一。
三、订单智能配送系统的基本结构
美团外卖每天都会产生海量的订单配送日志和行车轨迹数据。通过对分布大数据的分析和挖掘，得到每个用户、建筑、商户、骑手、地理区域的个性化信息，以及每个地理街区的骑行路径的有效数据。那么智能订单配送系统的目标就是基于大数据平台，根据订单的配送需求、地理环境和每个骑手的个体特点，实现订单与骑手之间的高效动态优化匹配。可以实现，从而为每个用户和商家提供最好的配送服务，减少配送时间。成本。
实时配送大数据平台实现对骑手轨迹数据、配送业务数据、特征数据、指标数据的综合管理和监控，并通过模型平台和特征平台支持相关算法策略的快速迭代和优化。
机器学习模块负责从数据中寻求规律和知识，比如准确预测商家用餐时间、用户所在大楼上下楼时间、未来订单、骑行速度等因素，耗时的红绿灯和自行车导航路径。运筹优化模块基于实时配送大数据平台和机器学习预测数据，采用优化理论、强化学习等优化策略进行计算，做出全局最优的分配决策，与骑手高效互动，处理问题在执行过程中，实现动态优化。
1. 问题分析与建模：高效解决问题的第一步
学术研究领域有很多经典的优化问题（如旅行商问题TSP、装箱问题BP、车辆路径问题VRP等），它们的决策变量、优化目标和约束条件往往非常明确和简单。这在学术研究中是必要的，因为它简化了问题并使研究人员能够专注于如何设计有效的算法。
然而，由于实际工业场景的复杂性，很难如此简单地描述大多数实际场景的决策优化问题。会导致我们得到的所谓“最优解”在实践中应用后“无法接受”，最终被大量抱怨甚至放弃。
因此，我们说准确的建模是实际决策优化项目的第一步，也是最关键的一步。
准确的建模涉及两个问题：
我们正确理解实际业务场景的优化问题，并通过一定的形式语言准确描述；我们建立的模型所涉及的各种参数和数据都可以准确的得到。
在以上两个前提下，使用相应的高效优化算法求解模型得到的最优解就是满足实际场景需求的最优决策方案。第一个问题一般是通过业务研究、分析和建模工具得到的；而要解决第二个问题，更需要依靠数据分析、机器学习、数据挖掘技术结合领域知识对模型进行准确建模。量化的表达。
决策优化问题的数学模型通常包括三个要素：
决策变量优化目标约束
其中，决策变量描述了我们希望算法帮助我们做出哪些决策；优化目标是指通过调整决策变量来优化哪些指标；约束是优化决策过程中考虑的各种约束。性因素。
为了说明即时交付场景下的订单分配问题，我们首先介绍一些符号定义：
在即时配送调度场景中，决策变量包括分配给每个订单的乘客和乘客建议的旅行路线。
即时配送订单分配问题的优化目标一般包括希望用户的平均配送时间尽可能短、骑手支付的人工尽可能少、加班率尽可能低尽可能，等等。一般可以表示为：
对于实际场景中的配送顺序分配问题，设定使用哪些指标作为目标函数是一个比较复杂的问题。
原因在于两个方面：
优化问题是多目标的，每个目标在不同的时间段和不同的环境中都会有所不同。例如，有经验的调度员想在负载低的空闲时间给不熟悉该地区地形的骑手发单，锻炼骑手的能力；在恶劣天气的情况下，他们希望能够容忍一定的超时率。多地发送drop-in order，提高订单消化速度等。这些考虑都是合理的，需要在优化目标中体现出来。缺乏数据来帮助量化优化目标。如果有足够多的标注数据，并且假设调度员的能力足够好，则可以通过数据挖掘的方式得到优化目标的量化表达。很遗憾，这些前提都不成立。针对这个问题，我们首先通过深入研究明确业务痛点和目标。在此基础上，我们采用机制和数据相结合的方式手动设置目标函数的结构，并使用仿真系统（下文介绍）和实际数据进行结构设置。确定目标函数的参数以确定目标函数的最终形式。
即时交货调度问题的约束至少包括以下几种：
除了以上限制外，有时还需要考虑到部分订单只能由具有一定特征的骑手下单（例如火锅订单只能给有特殊装备的骑手等），运力的限制车辆等
以上只是对给定批次订单的匹配决策优化问题建模时需要考虑的一些因素。
事实上，在外卖配送场景中，我们希望的不是单一决策的最优性，而是策略在应用一段时间后的最大累积收益。
也就是说，我们并不追求某个订单的最优分配，而是希望最终所有订单分配的结果整体上都是全局最优的。
这进一步增加了问题建模的难度。原因是算法在做出订单分配决策时，未来的订单信息是不确定的。如下图所示，在时间t做决策时，既要考虑已经确定的Orders，也需要考虑未来尚未确定的订单。
运筹学优化领域的马尔可夫决策过程描述了这种不确定和不完全信息环境下的顺序决策优化问题。
2. 问题建模中的机器学习
过去，在信息化水平不高的环境下，很多产业运筹优化项目都不成功。重要原因之一是缺乏足够的基本数据收集工具。大量数据是凭经验人工设置的，准确性难以保证。，并且难以随环境的变化进行自适应调整，使模型的优化结果逐渐变得不切实际。
机器学习领域有句谚语“garbage in,garbage out”，这说明了准确的基础数据对于人工智能项目的重要性。
即时交货订单分配场景中的数据包括两类：
直接通过业务系统收集可用数据，如订单数据、骑手负荷数据、骑手状态数据等。无法直接收集、只能通过预测或统计获得的数据，如商家送餐时间、用户停留时间（骑手到达用户处将订单配送给用户的时间），以及骑手的配送能力。
第一类数据的获取一般由骑手端的业务系统和APP直接给出，通过提高工程质量或运营规范可以有效保证其准确性；而第二类数据的获取是实时配送调度的关键难点之一。
在订单配送过程中，骑手到商家和用户取餐和送餐的时间将占整个订单配送时间的一半以上。准确预估餐点和送餐时间，可以减少额外的等待骑手，避免“餐等人”现象。
商家送餐的时间长短与品类、时间段、天气等因素有关，送餐时间比较复杂。用户在哪个楼层，是否是下午高峰时间，是否有电梯等，都会影响骑手（到达用户位置后）将订单交付给用户的时间。对于这两类数据，单纯通过机制是无法做出预测的，因为无法收集到相关数据（比如今天有多少厨师值班，用户办公楼的电梯是否开着， ETC。）。
为了解决这些问题，我们利用机器学习工具，利用骑手到店、候餐、取餐的历史数据，充分考虑天气等外部因素的影响，建立预测模型，充分体现用餐能力，并通过实时分析。校正尺寸特征以获得准确的用餐/交货时间估计。
进一步，我们建立了调度模型的自学习机制，利用多变量控制理论的思想，根据估计偏差不断调整估计模型中的相关参数。通过以上工作，我们使用调度模型来估计骑手的送餐行为（取餐和送餐的时间），平均偏差小于4分钟，10分钟置信度达到90%以上，即有效提高了投放效果和用户满意度。花费。
3.订单-骑手匹配优化
如果上述建模过程的目标是构建与实际业务相匹配的解空间，那么优化算法的作用就是在我们构建的解空间中找到最优策略。配送调度问题是典型的NP-Hard离散系统优化问题，解空间巨大。
取一段时间内产生的50个订单，一个区域200个骑手，每个骑手5个订单，对应的调度问题解空间规模会达到pow(200,50)*10（有些是不可行解），即一个天文数字！
因此配送决策方法，如何设计一个好的优化算法，从巨大的解空间中寻找到满意的解（由于问题的NP-Hard特性，几乎不可能得到最优解）是一个很大的挑战。即时交付优化算法的另一个要求是实时性高。该算法只允许运行 2 到 3 秒，并且必须给出最终决策，这与传统物流场景的优化完全不同。
为了应对这一挑战，我们采用了两个关键思想。一是问题特征分析。运筹学优化领域有句话叫“No Free Lunch Theory”，没有免费的午餐，意思是如果没有对问题的抽象分析并用在算法中，那么没有算法会更好而不是随机算法。
换句话说，我们必须对问题的特征和结构进行深入分析，才能设计出性能优越的算法。
运筹学优化领域的各种基础算法也有较多的思路，如单纯形法、梯度下降法、遗传算法、模拟退火、动态规划等，其本质是假设问题具有一定的特征（如动态贝尔曼方程计划的假设，遗传算法的构建块假设等），并将这些假设用于算法设计。
那么对于配送调度的场景，这个问题可以分解为两个层次：骑手路径的优化和订单分配方案的优化。
骑手路径优化问题要解决的问题是：新订单分配给骑手后，确定骑手的最佳配送路线；而订单分配优化问题中要解决的问题是：将一批订单分配给对应的骑手，使我们关注的指标（如交货时间、准时率、骑手的行驶距离等）是最优的.
这两个问题的关系是：先用顺序分配优化算法进行初始顺序分配，再用骑手路径优化算法得到每个骑手的最优行车路线。然后，订单分配优化算法根据乘客路径优化结果调整分配方案。
这两个层次反复迭代，最终得到满意的解。
第二个思路是跨学科融合。
行业内订单分配问题有两种方法。第一种方法是将顺序分配问题转化为图论中的二部图匹配问题来解决。
但是，在标准的二分图匹配问题中，一个人只能被分配一个任务，所以常用的方法是先将订单打包，将一个人可以完成的多个订单组合成一个任务，然后使用二分图匹配算法（匈牙利算法，KM算法）来解决。这种方法是一个很好的近似方案。优点是计算简单快速，缺点是会丢失一部分满意的解。
第二种方法是直接使用个性化算法优化订单分配方案。优点是不失去获得满意解的可能性，但实际上做起来难度更大。
我们结合领域知识、优化算法、机器学习策略和相关的图论算法，基于分解和协调的思想设计了一个骑手路径优化算法和一个订单分配优化算法。进一步，我们利用强化学习的思想，引入了离线学习和在线优化相结合的机制。离线学习用于获取策略模型，在线通过策略迭代不断寻求更好的解决方案。通过对算法的不断改进，算法优化效果提高50%以上，同时减少了时间消耗。
我们在大量实际数据集上进行评估和验证。在超过 99% 的情况下，骑手路径优化算法可以在 30ms 内给出最优解。
为了有效减少算法运行时间，我们将优化算法并行化，利用并行计算集群进行快速处理。
一个区域的调度计算将在数百台计算机上同步执行，在2~3秒内返回满意的结果，每天的路径规划次数超过50亿次。
4. 处理强随机性
即时配送流程的一个突出特点是线下有很多意想不到的因素，影响很大，比如商家送餐速度异常慢、无法联系到用户、车坏了、临时交通管制等等。
这些突发事件造成的一个不好的结果是，虽然被指派的骑手在下订单的时候是合理的，但是一段时间后，由于骑手的状态、订单等的变化，就会变得不合理。不合适的骑手会导致订单超时，骑手需要额外的等待时间才能完成订单，影响配送效率和用户体验的提升。
当上述不确定因素导致订单派送计划变得不合理时，现有的方法主要是人工完成，即派送站站长/派送员在派送信息中检查每个骑手的位置和订单的订单状态系统。状态和商家/用户位置/预计送达时间等，并回答骑手的电话重新分配请求。在此基础上，分析哪些订单需要重新分配，哪些骑手需要重新分配，并执行操作。
鉴于即时交付的强不确定性，我们提出两项创新：
一是延迟调度策略，即在某些场景下，可能无法分配订单，可以延迟决策而不影响订单超时；
二是系统的自动重新分配策略，即即使订单已经派发给骑手，后台的智能算法仍然会实时评估每个骑手的位置和订单情况，帮助骑手分析并确定是否存在加班风险。如果是这样，系统会评估是否有更好的骑手来运送。
延迟调度的好处，一方面是在动态和不确定的环境中寻找订单分配的最佳时机，以提高效率；通过这两种策略，订单调度流程更加立体和全面，覆盖订单履行过程全生命周期的主要优化环节，实现订单与骑手的动态优化匹配。
5. 模拟系统
工业系统非常重视监控和评估，“没有测量，没有改进”。在工业优化场景中，如何准确评估一个算法的好坏与设计一个好的算法同样重要。
但由于线下可能有多个订单由同一个骑手配送，订单之间存在耦合关系，无法对订单维度进行A/B测试。区域维度指标受天气、订单结构、骑手等级等外部随机因素影响，波动较大。算法效果容易被随机因素湮没，无法准确评估。
为此，我们建立了相应的仿真模型，开发了即时配送场景的配送仿真系统。系统可以模拟真实的配送过程和在线调度逻辑，按照一定的配送策略给出最终的结果。仿真过程与实际离线导航和地理数据完全一致。同时，系统可以根据实际分布数据进行模型自学习，不断提高仿真精度。
一个高精度的配送模拟系统，除了能够准确评估和优化配送调度算法，实现高效的策略准入控制之外，另一个巨大的价值是可以辅助优化配送相关的上下游策略，包括分配。范围优化、订单结构优化、产能配置优化、配送成本评估等，其应用的想象空间非常大。
4。结论
美团配送智能调度系统应用后，取得了很好的应用效果。下图展示了两个具有相似订单结构的白领区域的 A/B 测试结果。
5月6日，中关村配电站切换调度模式及相应算法，大望路配电站调度策略保持不变。
可以看到，切换后，中关村平均配送时间减少了2.9分钟，严重加班率下降了4.7个百分点（与对比地区相比）。
同时，在更广的区域进行了测试，结果表明，新策略在体验指标不变的前提下，可以降低19%的容量消耗。
也就是说，以前5个人做的事情，现在4个人可以做。因此，智能调度在降低成本方面具有很大的价值。
美团配送的目标之一是成为本地化的物流配送平台。那么，效率、体验和成本将成为平台追求的核心指标。人工智能技术在美团配送中有很多成功的应用。利用大数据和人工智能打造高效、智能、动态、协同优化的本地智慧物流平台，可显着提升本地及同城物流配送效率。提升配送体验，降低配送成本。
