美团、达达-京东到家、58速运、菜鸟的路径优化算法对比盘点

作者 | 物流麻将胡

来源 | 物流沙龙

上一篇我们分享了《人工智能的物流圈（一）：京东预测与计划&供应链产销协同、菜鸟算法与机器学习分析》，主要讲述了物流行业的智慧化平台，内容包括预测与计划、供应链产销协同、控制塔、供应链中台、算法与优化、大数据等。

今天来看一下人工智能的物流圈的第二篇文章，主要讲述的是路径规划的问题，目前这一领域少有现有的实践经验可以借鉴，问题的非标准化程度和复杂程度也要高于其它同类公司。以顺路判断为例，滴滴/uber在拼车时最多只需要考虑2单间的顺路情况，而外卖配送则可能同时配送5单以上订单。同时，即时物流配送相对于打车也有更强的时效要求和订单差异。 

我们选取了目前在这一方面做得比较优秀的几个企业，看看他们是怎样通过算法来得到最短的配送距离？

美团：外卖调度中关键难点之一订单分配

在过去一年多时间里，美团配送团队在机器学习、运筹优化、仿真技术等方面，持续发力，深入研究，并针对即时配送场景特点将上述技术综合运用，推出了用于即时配送的“超级大脑”O2O即时配送智能调度系统。

系统首先通过优化设定配送费以及预计送达时间来调整订单结构；在接收订单之后，考虑骑手位置、在途订单情况、骑手能力、商家出餐、交付难度、天气、地理路况、未来单量等因素，在正确的时间将订单分配给最合适的骑手，并在骑手执行过程中随时预判订单超时情况并动态触发改派操作，实现订单和骑手的动态最优匹配。

同时，系统派单后，为骑手提示该商家的预计出餐时间和合理的配送线路，并通过语音方式和骑手实现高效交互；在骑手送完订单后，系统根据订单需求预测和运力分布情况，告知骑手不同商圈的运力需求情况，实现闲时的运力调度。

在这一套调度流程中会遇到一个关键问题订单分配，下面就方案架构和关键要点来分析一下：

外卖订单的分配问题一般可建模为带有若干复杂约束的DVRP（Dynamic Vehicle Routing Problem）问题。这类问题一般可表述为：有一定数量的骑手，每名骑手身上有若干订单正在配送过程中，在过去一段时间（如1分钟）内产生了一批新订单，已知骑手的行驶速度、任意两点间的行驶距离、每个订单的出餐时间和交付时间（骑手到达用户所在地之后将订单交付至用户所需的时间），那么如何将这批新订单在正确的时间分配至正确的骑手，使得用户体验得到保证的同时，骑手的配送效率最高。

外卖配送场景下一个配送区域上众多骑手的分布示意图

美团外卖每天产生巨量的订单配送日志、行驶轨迹数据。通过对配送大数据进行分析、挖掘，会得到每个用户、楼宇、商家、骑手、地理区域的个性化信息，以及有关各地理区块骑行路径的有效数据，那么订单智能分配系统的目标就是基于大数据平台，根据订单的配送需求、地理环境以及每名骑手的个性化特点，实现订单与骑手的高效动态最优匹配，从而为每个用户和商家提供最佳的配送服务，并降低配送成本。

即时配送订单分配问题的优化目标一般包括希望用户的单均配送时长尽量短、骑手付出的劳动尽量少、超时率尽量低，等等。一般可表达为：

除了要考虑时间、地段等约束外，有时还需要考虑部分订单只能由具备某些特点的骑手来配送（例如火锅订单只能交给携带专门装备的骑手等）、载具的容量限制等。

即时配送大数据平台实现对骑手轨迹数据、配送业务数据、特征数据、指标数据的全面管理和监控，并通过模型平台、特征平台支持相关算法策略的快速迭代和优化。

机器学习模块负责从数据中寻求规律和知识，例如对商家的出餐时间、到用户所在楼宇上下楼的时间、未来的订单、骑行速度、红绿灯耗时、骑行导航路径等因素进行准确预估，为调度决策提供准确的基础信息；而运筹优化模块则在即时配送大数据平台以及机器学习的预测数据基础上，采用最优化理论、强化学习等优化策略进行计算，做出全局最优的分配决策，并和骑手高效互动，处理执行过程中的问题，实现动态最优化。

达达-京东到家路径规划和派单算法

在10.22号举办的《中国python开发者大会》上，新达达配送算法团队负责人廖瑞奇首次分享了达达-京东到家在路径规划和派单算法方面的一些实践经验。

1）路径规划

在达达平台上，一个骑士可能会同时配送多个订单，如何规划骑士的配送路线，使得骑手的送货距离最短，优化骑士的配送效率，是平台要解决的一个核心问题。

对于单个骑手的路径规划问题，是一个典型的TSP问题： 

由于TSP是一个NP-hard问题，没有多项式时间内的确切解法。为了解决这个问题，新达达使用了启发式算法中的遗传算法，来快速获取骑士的较短配送路线，并且能够同时得到规划后的路线的最终配送距离。在待规划点超过10个以上的情况下，算法的运行时间也能保持在几毫秒，同时保证极高的准确性。 

有了这个基础算法，新达达就可以判断订单间的顺路情况，以及某个订单是否适合由某个骑士来配送。

2）订单指派

在新达达平台上，同时有订单的抢单和派单机制，来实现合理的订单分配。

在订单分配的过程中，不仅需要考虑顺路情况、配送效率等，也要考虑骑士的接单偏好、配送能力、活跃状况，以及订单分配的公平性等因素。

简单来说，订单指派是一个有限制的多目标优化问题，不仅需要考虑平台效率，也要考虑骑手的心理因素、运营的稳定性等。

目前，使用派单和抢单结合的方式，达达平台上绝大多数的订单，都能在发出后1分钟以内实现订单的合理分配。

58速运：战斧项目

2017年11月，58到家技术经理/58速运后端架构总负责人胡显波在《Gdevops 2017全球敏捷运维峰会广州站》介绍了58速运第三次技术演进：战斧项目。

1)智能模型训练

上图为智能模型训练图，首先58速运会将订单信息、用户信息、司机信息、客司关系信息、订单总体推送、司机接单等场景信息统一上传到大数据平台，通过这种归一化&分桶、XGBoost、特征组合、独热编码等将这些数据分析为特征数据。

针对分析出来特征数据，还需要对它进行训练，如：订单价格、订单距离等特征在整个订单派单中起到的权重。因为特征很多，计算出来的权重可能并不是一个完美的解，只能说是近优、最优的一个解法，通过不断地迭代优化，最终训练出来最终的模型。

2）订单-模型运用

下单阶段：在用户下单时，会采用这种用户订单定价的模型，观察这个订单所在的商圈的运力饱和度，如果司机少，而订单需求多，会进行一个订单的调价。

推送阶段：系统推送的过程中，会根据司机的接单意愿来捞取。有的司机喜欢高价格订单，有的司机喜欢短程订单，有的司机喜欢去中关村等。58速运会根据订单与司机意愿的匹配程度进行优先推送的排序。

抢单阶段：先预估这个订单的接单人数，计算出来订单的价值，如果订单的价值高（价格高、地点好）、那么这个订单不会发放补贴了，同时会扣取司机的一些积分或优先抢单次数等。如果订单价值比较低（价格低、偏远地区），会给这个订单适当地增加补贴，来确保订单的完成。

指派阶段：当司机抢完单以后，58速运会根据所有司机历史完成订单的数据，取司机的质量，来决定哪个司机中单，保证订单尽可能完成。

订单完成阶段：订单完成了以后预测这个用户的流失概率，如果可能流失，会送一些券或者其他权益吸引用户留在平台。

3）派单

上图在智能派单时代的系统架构图。用户在下完单以后，订单会进入到58速运整体的策略系统，它包含推送系统、补贴系统、价格系统、任务系统等，然后通过特征匹配系统，计算出一个最优的订单调度解，将这个订单推送到司机的单队列引擎和订单的排序策略引擎，最终通过推送服务将订单推送给司机。

4）策略分流+监测

智能系统需要有不同的算法在线上实验，当一些新算法研发完成以后，肯定不能用100%的流量在线上进行验证算法的可行性，如果有问题，会对线上业务产生影响。58速运一般取5%或10%的流量在线上验证。一般根据用户手机号、设备码、用户属性等，以及取模、集合等方式。验证线上算法验证时，如何实时的监测算法的效果，避免错误算法对线上业务造成影响？

如上图所示，用户在APP的每个步骤、运用了哪个算法，58速运都会将用户的ID、采用的算法ID通过日志上报的报到统计平台。业务监控平台会实时进行监控，对于出现异常的算法就自动关闭分流。

5）特征计算

特征数据中有40多万个特征，每个订单需要推送给很多个司机，需要进行进行上万次的运算，需要在几十毫秒内给出计算结果，如何保证计算的高性能呢？58速运采用的是这种阶段性事件驱动的计算方式来最大化提高并行计算的能力。

如图所示，这是58速运的计算链，里面包含多个Stage，包含准备阶段、转化阶段、取数阶段和计算阶段，每一个阶段都有自己独立的线程池，根据每个阶段的特征设置核心线程数，同时整个计算链做到了可插拔的形式，方便业务调整。

6）监控平台

一个是立体化监控，目前已经做到的监控包含：关键字、接口、流量、端口，JVM、CPU、线程、缓存、DB所有的监控等等，同时还有服务治理，当服务节点发生异常，实时切换。

业务化的指标监控，渠道转化率、渠道取消率、渠道推送数量、异常订单数量等等，如果出现异常，第一时间预警。

另一个是调用跟踪系统，很多互联网公司都已经在使用，调用跟踪系统目的是需要看到的是APP发起的每个请求在整个Service后端走过的所有过程，效果下图所示，可以监控到每一步所调用的服务和耗时。

菜鸟：车辆路径规划

简单来说，就是通过算法+动态规划实时跟踪交通信息，以及调整运输路径，就是把哪里的活、什么样的活、派给什么样的车，物流配送的成本和效率做到最优。

菜鸟网络人工智能部从自身业务出发， 联合集团IDST、阿里巴巴云计算的力量， 打造一款适合中国复杂的业务需求， 又在效果上接近国际水准的分布式车辆路径规划求解引擎 -- STARK VRP，探索一条结合运筹优化、分布式计算、机器学习、人工智能结合的技术路线。

VRP问题目标， 是给出一个确定的最优解，包含车辆以及他们的运输路径， 来服务一个客户集合的订单。 这也是组合优化中研究最广， 最重要的问题之一。

如大家所知， 中国的物流情况尤为复杂， 有自己很多独特的场景， 也衍生出了对应的VRP求解类型和分支。以下是STARK VRP现阶段支持以及开发中的VRP类型和对应的业务类型。

目前该算法正在部分农村物流网点使用。根据每日单量，为农村的物流老司机规划配送路线，每天实时更新，在保证时效的基础上，可节省车辆、人力、邮费。综合测算下来，农村领域的物流成本能减少30%以上。

技术选型 - 丰富多样的求解方式：

传统用于求解VRP的精确解法无法应对大规模数据集：

利用元启发式构建求解的基础框架：

过去都是人为固定好的线路，现在通过大数据来分配路线，系统会根据每天实际入库量，生成一条智能配送线路，发送给农村配送司机。同时，每天配送的线路都是根据单量实时更新。

STARK VRP不仅仅在菜鸟内部的村淘、零售通、跨境、新能源车、仓内路径规划已经开始落地， 而且更为广泛的开始服务于像日日顺这样的外部公司， 为降低中国的物流成本， 提升时效尽一份算法人员的能力。

此文系作者个人观点，不代表物流沙龙立场

END