一文讲清楚什么是调度算法

作者：张嘉琦

近些年来，我们发现承接了国家大量人口就业的“外卖、网约车、快递”三大行业正在快速蓬勃发展，背后离不开以技术驱动的互联网平台所提供的智能技术，其中调度算法是其关键核心之一。由于本人上学时研究的是调度领域相关知识，且有幸跟随这波互联网浪潮，深耕物流配送领域应用多年，对调度技术积累了些许体会和见解，在此和大家分享一下。（如果哪里说的不够严谨，不喜勿喷，交流为主）

调度(scheduling)是运筹学的一个重要的应用领域，涉及到分单匹配、路径规划、排序/搜索/推荐等子问题，调度解决了如何将有限资源合理分配且按照最优顺序执行的问题，最终从全局视角实现目标最大化。很多实际中的复杂系统都可以抽象为调度系统，比如外卖配送系统实际上是关联了外卖订单与骑手之间的履约，网约车系统关联了乘客与司机之间的配对，物流运输关联了货物与车辆之间的分配，传统制造生产线则是关联了工件任务与机器之间的计划排程。

调度问题的复杂度和求解难度，通常与对应业务背景密切相关。根据调度信息是否会随着时间而动态变化，可以划分为静态调度（static）和动态调度（dynamic）; 根据调度链路过程是否含有不确定因素，可以划分为确定性调度（deterministic）和随机性调度（stochastic）；根据调度触发周期频率和时间长短，可以划分为实时调度（real-time）和非实时调度，调度触发方式可以是周期性时间，也有事件触发。对比打车和外卖调度系统谁更复杂，可以从以下几方面展开讲讲：（1）二者都是动态实时调度，打车的实时响应速度更快，快速分单减少乘客等待时间有利于促成完单交易，而外卖通常会蓄单半分钟甚至一分钟才会进行一次调度，因此调度单元所处理的订单规模更大。（2）二者都具有潮汐效应，打车订单主要集中在上下班时间段，外卖订单主要集中在午晚高峰，由于吃饭刚需频次更高，单量分布呈现会更明显。（3)从业务链路环节上看，打车连接司机和乘客两方，外卖会涉及用户、骑手和商家三方，流程链路比较长，任何取餐、行驶、交付环节出现问题都会影响到最终的履约，而且交通载具不同，骑手遇到的不确定因素相对更多。（4）打车大部分场景都是一对一的匹配，当司机即将完成当前乘客这一单之后才会接到下一单，即便是拼车场景，一辆车最多对应3个乘客，出发地和目的地最多6个节点，求解最优路径的复杂度依然不高；外卖场景一般是多对一的匹配，骑手在执行配送过程中会同时背付多单，单多的时候在10~20单，而路径规划属于NP-hard组合优化问题，随着规划任务点增多，最优路径的搜索空间和耗时是指数级倍数增长的，那些相对较晚执行的任务会累计误差, 对评价准确度带来了不小的挑战。因此，相比较之下调度技术的难度显而易见。【1】

如何设计一个通用的调度派单求解器呢？一次派单求解过程又该包含哪些关键模块呢？分单匹配过程本质上在撮合双边交易成功完成满意的履约。匹配的数学模型可以用二部图来表示，匹配的双方在外卖配送领域是订单与骑手，在打车领域则是司机与乘客。首先需要确定是否存在匹配边的关系，这个部分是由过滤模块来决定，比如某种订单类型只能由某类骑手承接，骑手背单不能超过最大背单上限等等业务型约束，还有一种是防止出现不受控制的场景情况而增加的兜底条件，目的为了让结果趋于合理，属于效果型约束。然后当有了关系矩阵之后，需要由打分模块刻画二者之间的价值矩阵，即匹配边的权重。打车场景下由于司机接单前处于空车状态，所以接驾的距离、行进方向和导航顺路程度自然是首选考虑的因素，实际上70%~80%的分单也符合“就近分配”原则，距离因素比较直观地反映了平台分单的效率。除此之外，订单远近因素与平台获得利润GMV有关，未来价值因素根据不同区域冷热情况能够自适应调节未来供需变化，使得司机持续不断的有单派进来。以及通过精细化运营，对司机、乘客分层处理，根据司机的服务好坏、乘客的账号等级和偏好给予一定的倾斜分。外卖配送场景下骑手派单时可能处于空载状态，也可能已经背有数个订单，通过路径规划模块模拟新单分配给该骑手前后的变化过程，距离增量自然为首选因素，直观体现了行驶效率和空间上顺路程度，除此之外，订单超时风险因素尽量避免造成用户送达超时情况发生，派单图形因素融合了骑手直觉上满意度，派单均衡因素防止派单过于集中某个骑手的不公平现象，取送任务集中程度能降低取餐和送餐过程中的难度，以及还考虑了骑手熟悉度、订单难易度等等方面。当新单分配骑手时，对于决定追给当前正在执行波次还是未来波次，在许多打分设计上均有所区别处理。从上面可以看到，现实复杂系统往往是考虑了诸多的因素的多目标问题，通常做法会通过加权求和的方式转化为单一目标来指导决策。虽然权重可以依据实时供需特点动态变化，然而一旦考虑因素过多以后，很难覆盖某些极端场景而获得多方合理且满意的解，造成主次因素模糊不清。因此通过优先级模块将原有打分体系分层，例如，像同取同送这样的优质场景需要升级处理，像骑手背单严重超时的不良场景需要降级处理。这样在比较两个打分大小时，会首先判断优先级高低，其次在同个优先级分层下进行价值打分值的比较。最后到了核心的匹配模块，匹配环节会利用打分评价体系和比较选择策略做出决策判断，从双边各自的视角来看待匹配这件事会有不同的理解：从骑手角度来看，匹配是一个不断把相似、顺路、高效率订单汇聚在同个骑手身上的过程；而从订单角度来看，匹配是一个不断将候选骑手范围逐步缩小的过程，有点类似于推荐系统。匹配策略可以完全依赖打分排序最大化匹配边权重，常用的经典方法有匈牙利算法、KM算法、启发式等，但是每种方法都有其适用条件，比如匈牙利算法适用于解决最大匹配问题，KM算法适用于解决最大边权重的完美匹配问题，所以适合打车场景一对一匹配，却不适合外卖场景。此外技术选型还要考虑算法复杂度在大规模求解时的性能耗时和未来业务扩展性问题。由于对现实场景的打分评价并不是十分精准，匹配选择策略所得到订单最优解和次优解在一定范围内不能反映孰优孰劣，因此有必要考虑多个帕累托前沿最优解参与到选择中，同时结合先验知识选择偏好和稳定匹配思想，让选择的最终结果排名更加鲁棒。【2】【3】【4】

讲到这里，一次匹配过程所包括的最基本要素已经够实现订单与骑手的关联了。此外还有没有其他可以做的事情呢？从更长时间维度来看，调度是一个多阶段决策、时序滚动优化的过程，当前调度时刻即便是最优解未必是全天调度的最优解。一般设计一个复杂的优化求解器会在核心操作环节前后增加预处理和后处理组成部分，预处理是把数据处理成我们想要的样子，减少大量无谓的计算；后处理是原有结果的修正和补充，避免出现不想要的情况。在外卖配送调度系统中，我们会在预处理和后处理环节增添合单和压单模块。为什么要有他们呢？因为我们场景是基于时空维度（spatio-temporal）下的数学建模优化，合单模块可以理解为空间维度下组成当前有收益的调度单元，压单模块可以理解为时间维度下形成未来有潜力的调度单元。说说合单的好处：1、按订单打包指派保证了指派给同个骑手，减轻打分和选择带来的偏差；2、以订单包作为匹配维度降低了求解规模大小，减少了路径规划调用评价次数。3、订单包指派有利于提高骑手作业满意度，带来了履约指标的质的飞跃。4、更多相似度高的订单包创造了降本的空间。说说压单的好处：1、挖掘订单未来价值，通过延迟调度提高订单池中高价值订单密度。2、通过延迟指派释放时刻减少了卡餐、单飞、反向等不理想分单情况发生，在动态多变的不确定环境下起到一定的容错作用。并不是说压单越长越好，一旦时间过长会直接影响到用户订单的留存转化率以及骑手的满意率，所以“A little delay is all we need”。【5】

综上所述，“合单、压单、过滤、打分、比较、选择”是长期探索和建设调度系统所应具备的重要组成模块，是处理实际遇到问题促使达成预期效果的手段。每种武器都有其策略作用强弱大小和适用范围，过滤属于较强的一种，增加过多的过滤条件虽然会避免掉某些情况出现，但也会造成可用资源极大减少和浪费，最终迟迟无法分单。打分属于较弱的一种，增加过多的打分项不但不能缓解问题，而且还会影响到原有主要考量因素，导致“跷跷板”效应。举个优化同取同送场景的例子（不仅限于同个用户下单同一家店，还包括同AOI取送集中）, 目标提高同取同送订单由同个骑手配送的比例，提升配送效率和骑手满意度。我们可以在合单环节把同取同送订单优先打包，由于该类型订单包质量很好，订单包容量大小可以略大一些。在压单环节预测未来出现同取同送订单的概率，通过时间延迟释放，让他们有机会出现在同一个时间片下，这样有利于促成合单。在过滤环节我们会时刻判断骑手是否达到背单上限，一旦超出范围，便不再继续派单，但是对于多个同取同送这类订单在某种程度上可以视为同一个订单，根据场景特点适当放宽过滤条件，有利于将单子派出去。在打分评价环节，对比新派单与骑手当前背单是否存在同取同送的情况，通过打分函数给予一定的奖励或惩罚，通过高优先级确保定位到要选择的那类骑手身上。此外我们还可以设计有倾向性的选择策略，将同取同送订单更多派给空载骑手或者新骑手，让骑手每次出发都能以较好的方式开始。

最近在面试找工作过程中常常会被问到为什么不使用专用求解器来解决这类问题，似乎精确求解建模方法显得更高级更具有难度挑战。现实世界中处理复杂系统问题时往往会将其拆解为多个子问题，同时技术选型会衡量很多方面：小规模还是大规模问题、不确定性程度怎么样、工程实现难度和性能时效要求，业务改造扩展性和灵活性，技术投入产出比等等。技术不分高低贵贱，只有充分理解了业务当前和未来发展趋势的基础上，设计出一套合适的技术框架，才能最大化获得目标成果。技术也不全是完美的，某项技术既有它的特长也有短板，扬长避短是我们技术人需要在工作中不断积累的宝贵经验。

参考文章：

1. 外卖调度算法复杂度更高，滴滴的“打车逻辑”难套用
2. 浅谈滴滴派单算法
3. 即时配送的订单分配策略：从建模和优化
4. 美团智能配送系统的运筹优化实战
5. 延迟对在线决策的益处