摘要
本文介绍了在餐饮外卖物流调度领域，运用大数据技术解决订单调度问题的系统解决方案和工具平台。其中包含的云端调度计算模式、深度学习预测算法和可视化大数据的广泛运用，为城市物流配送行业应用智能大数据技术提供了可供参考的算法技术、解决案例和工具软件等实际应用经验。
一、背景
餐饮 O2O行业连接线上线下的订餐需求，将传统的到店消费模式改造成更加灵活便捷的到家消费模式，极大降低了用户的消费成本和商户的固定成本。外卖平台在这里扮演角色除了促进线上需求向线下转化，也包括达成订单的最后一公里任务--物流配送。高效的物流配送能力是决定外卖平台商业模式成败的关键，也是O2O经济区别于传统经济的根本，即运用大数据相关的云计算、深度学习和可视化技术提升行业效率，创造并满足新的民生需求。
因此，智能调度系统是外卖物流的最核心环节，依托海量历史订单数据、骑士定位数据、精准的商户特征数据，针对骑士实时情景（任务量、配送距离、并单情况、评级），对订单进行智能匹配，实现自动化调度以及资源的全局最优配置，在保证系统效率的前提下，最大限度地提高用户体验。
然而在外卖物流调度的真实场景中，用户点了餐就希望能按时送到，骑士上了路就希望每趟路线能多配送几单，商家接了餐就希望骑士快来取餐，平台则关心如何以最小的运力承接最大的配送压力，而且能扛住高峰时段突如其来的订单量。更加困难的是，这些目标有时就是互相矛盾的，满足了一方，势必会影响另一方，调度订单是非常复杂的多目标动态规划决策过程。
智能调度系统需要将以上所有因素统统考虑在内，实时采集整个商圈里各方的动态数据，在1毫秒内做出在时间跨度和空间范围内的最优分配序列，让骑士轨迹能无缝衔接起整个配送流程，让每个环节耗费的时间降到最低，让分摊到有限运力上的配送成本费用降到最低。
实践证明，在智能物流调度系统实施之前，物流订单分配需要由调度员手工分配，每个骑士每天最多配送10单，每单配送时长超过一个小时。实施之后，百度物流调动每天所有订单都由算法自动选择最优化的方案调配，每个骑士的配送效率翻倍，收入翻数倍，每单配送时长节省50%以上，覆盖全国100多个城市。
二、物流调度的云端计算模式
影响订单分配的因素很多，从订单生成那一刻开始，调度系统就要考虑到订单的取餐地址、用户的配送地址、商圈内的骑士数量和状态、订单的预期送达时间。每一个订单并不是孤立地存在，要想得到全局最优的配送方案，还要必须考虑到这一时段内其他订单的配送情况，尽可能做合并，提高整体的配送效率。如果再考虑到不同城市、商圈、天气、节假日、工作日和商圈骑士运力配置等情况，事情就变得更加复杂起来。
这是一个极其复杂的多目标动态优化问题，可以表示为：
直接计算的复杂度太高，需要采取逐层建模的方式来降低复杂度，其基本逻辑是：
1、将通用的参数变量，比如时间、距离，在底层作为基本限制条件进行采集和转换，尽可能地对代价函数进行降维，减少计算复杂度。
假设在时间T有一笔订单O要分配给候选的骑士R1,R2,…,Rn，需要分别预估假设由骑士Rx配送这笔订单的实际开销，比如：骑士的到店时间、等餐时间、送餐时间、交付时间、配送里程，通过下面公式计算出单次分配的综合代价打分。
2、将多变的场景变量，比如商圈、天气、整体运力，在高层作为调优参数进行优化，尽可能地模拟多维限制条件下的真实约束情况。
模拟系统会分商圈、分时间地统计每个调度场景下的订单分布数据，解析成从骑士在岗率、平均压单数、订单出单位置密度等角度的基础物理分布函数，作为刻画该调度场景的约束条件组。模拟系统还可以进一步调整这些分布函数的参数，达到出人工设定的约束条件组，从而模拟出更复杂丰富的设定场景。
以这些动态场景作为调度算法的输入约束条件，优化算法就能求解出多目标下的最优解。
3、在真实场景中，基于单次分配代价函数，采用二分图最大匹配算法求解多次分配下的最优解，尽可能地找出多个骑士和多笔订单间的最优组合，提高并单率或骑士人效，减少骑士空驶率。
假设可分配骑士为R1,R2,…,Rn，待分配订单为O1,O2,…,On，已经分别计算出每一组分配的代价得分，需要找出全局最优的骑士-订单分配组合，使得总代价最低。问题可以转化成传统的完备匹配下的最大权匹配问题：在一个二分图内，左边的骑士节点为X，右边的订单节点为Y，对于每组左右连接XiYj有权Wij，即配送代价得分，求一种匹配使得所有Wij的和最大，即总配送代价得分最小。
4、将待分配订单存储在云端服务器，维护订单分配的虚拟队列，通过设定压单时间窗口来调控虚拟调度订单转为真实派单的节奏。
云分配算法同时维护实际分配订单队列（下发到骑士客户端，不可更改）、虚拟分配订单队列（对应虚拟分配的骑士，可以随时更改）和待分配订单队列（未关闭压单时间窗口或未找到合适分配时机）。这样可以避免订单过早被分配给骑士后，因为情况发生变化，比如某个订单的延误导致后续配送代价函数估算失效，原先最优的分配不再成立。
最终，为了衡量调度系统优化效果，需要将系统配送效率和用户配送体验结合起来，统计在存在并单的情况下，系统为了完成订单配送实际耗费的时间成本，才能反映调度系统的整体效果。举个例子：并单配送的2单，40分钟送到，单均耗时是40分钟，单均成本则是40/2=20分钟，比只送1单提升了1倍效率。但如果并单效率不高，过于分离的2单被并联在一起，第1单30分钟送到，第2单50分钟送到，虽然节省了部分配送路程，但迟送到的那单会拖慢整个订单分组的单均成本，单均成本是50/2=25分钟。
按照这个计算方法统计一下调度系统上线前后的效果，可以看到从以有效时间计算的单均成本从40多分钟下降到20多分钟的明显改善。
以上复杂的调度规划，海量的数据建模和实时的平台响应，都需要有强大的计算能力在背后支撑。举例来说，为了得到最合适的订单调配，指派时机可能有多个。每个指派时机上各种可能的组合也会随着商圈订单规模的增大而呈指数级膨胀。为了尽可能的选择最优指派时机，系统还可能会做预测，尝试各种分支副本情况下的优化空间。如此一来，后台系统需要的计算能力就会非常高。可以说，物理上计算能力的容量，决定了系统最终效果能做到的天花板。
为此，我们依托百度云计算积累下来的技术优势，结合百度外卖的实际应用场景，设计了分布式、高并发、大容量的流式计算框架外卖配送系统，尽可能将独立的计算任务拆分到不同的机群上运行，得到整体上最优的计算效果。
经测算，目前的计算框架完全可以支撑百度外卖未来每天千万级订单，秒级10亿次计算的动态调度、数据建模和实时平台响应的运算规模。
三、深度学习智能预测算法
百度外卖每天百万级的订单量，为大数据深度分析技术提供了理想的应用场景。具体来说，调度算法的最终效果除了云端的规划计算能力之外，非常依赖每一个基础变量的预估值是否准确，尤其是在不同环节耗费的时间。
相比配送环节而言，商户出餐环节的耗时更长，也更不可控。菜品类型、价格、数量，商户品牌、规模、堂客食比，下单日期、时段都会影响商户出餐时间。如果估算不准的话，骑士到店时间过早则会白白浪费运力，过晚又会延误本可以早点取餐的订单，还会损伤一些菜品的品相和口感。
为了解决这个难题，我们采用深度学习方法， 让系统自动学习利用并组合产生新特征的方法，借助深层次神经网络模型， 能够更加智能地利用不同层次的特征，对样本数据中蕴含的规律进行更加准确、有效的表达。
具体来说，在以下几个方面结合餐饮O2O领域特点做出了开创性贡献：
1、从百度外卖平台的历史订单数据中抽取出千万级训练样本，其中难点在于如何认定这些订单的实际出餐时间，需要借助骑士轨迹、停驻坐标等数据清洗出由于商户和骑士操作不规范导致的干扰数据。
2、构建全面的商户和菜品标签体系，获取商户在竞品和本品的运营信息，作为系统的输入特征。比如，通过商户的品牌、营业面积等信息可以估算该商户的产能，通过菜品在材料、价格、烹饪方法上的差异可以估算制作时间。
3、系统对不同出餐时长区间的菜品的预估时间要求误差是不同的，处于中段区间的菜品，对预估时间的要求误差最严。为此设计了对不同时长区间样本敏感的深度学习评估框架。
最终在十万级测试订单样本上，深度学习模型对出餐时间的预估准确率在不同时长区间上，相比原有模型分别能有3%~14%幅度的提升，在95%的订单上能将37分钟的平均送餐时间再缩短约0.8分钟。
为了衡量调度系统优化效果，计算整体的配送时间平均值变化还不够。举个例子：10笔订单的平均配送时间缩短1分钟，有可能配送最慢的2单各延迟了1分钟，配送最快的3单各缩短了4分钟，但这并不是预期的理想效果，反而有可能会有更多的用户体验离开满意时间区间。还需要统计所有用户等待配送时间的整体占比变化，观察是否有越来越多的用户体验进入满意时间区间，更加全面地衡量调度系统优化效果。
按照这个计算方法统计一下调度系统上线前后的效果，可以看到等待配送时间分布曲线明显地向等餐时间更短的左方偏移，调度效果得到全面改善。
细点线=改进前，粗点线=改进后
四、可视化平台
物流调度逻辑非常抽象，但又会切实影响整个环节参与者的感受。可视化技术能够将复杂的数据和逻辑转化为可以理解和交互的图形界面，帮助骑士、用户和开发人员更好地理解和使用整个调度系统。好的可视化技术能够建立骑士和用户对调度系统的信任感，降低开发人员发现、定位并解决系统问题的成本，进一步发挥出大数据在提高物流调度平台效率外卖配送系统，改进用户消费体验方面的作用。
具体来说，百度外卖物流调度平台在可视化方面的成果包括：
1、实时回传服务器并向用户展现骑士的运行轨迹，其中难点在于：在骑士端采集骑士定位数据需要在精度和性能两者之间进行平衡，在用户端需要有稳定的长连接技术保证轨迹数据的有效性和及时性；
2、采集并存储每一次调度所用到的所有参数数据，方便事后可以回溯定位到任意一笔订单的分配理由。系统能够回放出当时将订单A分配给骑士B的所有细节参数和判断理由，方便相关骑士和研发人员定位排查调度算法逻辑错误或底层采集的数据问题。只需要调整可能有问题的特征值或权重，平台就能从那个时间点出发，按照新的模型重新演算一遍调度分配过程，验证效果。
3、调度系统在掌握了商圈内每个商户所有订单的地理分布和配送效果之后，能够绘制出商户配送范围内的配送效率分布图。由于受到地理位置、道路特点和业务密集程度等因素的影响，这份地形图并不是基于商户地址的同心圆，而是类似衡量山丘高度的等高线图，可以清晰明了地告知业务人员影响物流配送效率的瓶颈在哪里，该如何更合理地划分商户配送范围，调整商圈运力分布。
这些可视化技术降低了相关角色，比如：用户、骑士、研发和业务人员，使用和理解调度平台的难度，用更直观易懂的方式将背后复杂海量的大数据规律呈现出来，基于App客户端和Web页面的人机交互技术则可以帮助使用者进一步调控和分析所感兴趣的过程和维度。从某种意义上讲，放大了云端调度计算和深度智能学习的能力和效果。
五、结语
百度外卖物流智能调度系统采用云计算和人工智能深度学习技术，将复杂的调度问题分层处理，并在日益增长的物流配送大数据的基础上，不断精细化调度模型依赖的状态预估数值，不断提高调度模型的多目标规划能力，同时通过大量运用平台可视化技术，以实时、图表化和可交互化的方式将系统运行状态呈现出来，最终在平台运力效率和用户体验时间上得到优化效果。
展望未来，更加智能的调度系统需要依赖人工智能技术从物流配送大数据中主动发现可以改进的方向，能够有针对性的解决用户体验和平台效率中存在的普遍问题和长尾问题。比如：利用深度学习模型对大量基础特征的组合训练能力，自动构造打分算法所依赖调度因素的组合或约束结构，形成多层反馈神经网络，找出最优的分配方案；从历史调度数据中找出制约整体效果指标和影响特定场景体验的案例，作为训练学习的负面样本，结合线下仿真系统的模拟演练，自动修正机器学习模型的优化方向，从而取代低效的人工修正方式。
文章介绍的智能调度系统来自智能物流研发团队，智能物流研发团队隶属于百度外卖商业智能中心，主要负责智能物流调度算法、数据挖掘和分析、分布式实时计算架构的研究与开发工作，打造了业界第一个智能物流调度系统，并申请物流核心技术专利数十篇，开创了物流实时调度、落地配融合调度等多领域的先河。
免责声明：部分文章信息来源于网络以及网友投稿，本站只负责对文章进行整理、排版、编辑，出于传递更多信息之目的，并不意味着赞同其观点或证实其内容的真实性，如本站文章和转稿涉及版权等问题，请作者在及时联系本站，我们会尽快为您处理。
