作者|货运扑克胡
来源|货运沙龙
上一篇我们分享了《人工智能的货运圈（一）：易迅预测与计划&供应链产销协同、菜鸟算法与机器学习剖析》，主要述说了物流行业的智慧化平台，内容包括预测与计划、供应链产销协同、控制塔、供应链中台、算法与优化、大数据等。
明天来看一下人工智能的货运圈的第二篇文章，主要述说的是路径规划的问题，目前这一领域少有现有的实践经验可以借鉴，问题的非标准化程度和复杂程度也要低于其它同类公司。以顺路判定为例，嘀嘀/uber在拼车时最多只须要考虑2套间的顺路情况，而外卖配送则可能同时配送5单以上订单。同时，即时货运配送相对于打车也有更强的时效要求和订单差别。
我们选定了目前在这一方面做得比较优秀的几个企业，瞧瞧她们是如何通过算法来得到最短的配送距离？
美团：外卖调度中关键难点之一——订单分配
在过去一年多时间里，美团配送团队在机器学习、运筹优化、仿真技术等方面，持续加码，深入研究，并针对即时配送场景特征将上述技术综合运用，推出了用于即时配送的“超级脑部”——O2O即时配送智能调度系统。
系统首先通过优化设定配送费以及预计送达时间来调整订单结构；在接收订单以后，考虑骑手位置、在途订单情况、骑手能力、商家出餐、交付难度、天气、地理路况、未来单量等诱因，在正确的时间将订单分配给最合适的骑手，并在骑手执行过程中随时预判订单超时情况并动态触发改派操作，实现订单和骑手的动态最优匹配。
同时，系统派单后，为骑手提示该店家的预计出餐时间和合理的配送线路，并通过语音形式和骑手实现高效交互；在骑手送完订单后，系统按照订单需求预测和运力分布情况，告知骑手不同商圈的运力需求情况，实现闲时的运力调度。
在这一套调度流程中会遇见一个关键问题——订单分配，下边就方案构架和关键要点来剖析一下：
外卖订单的分配问题通常可建模为带有若干复杂约束的DVRP（）问题。这类问题通常可叙述为：有一定数目的骑手，每名骑手头上有若干订单正在配送过程中，在过去一段时间（如1分钟）内形成了一批新订单，已知骑手的行驶速率、任意两点间的行驶距离、每个订单的出餐时间和交付时间（骑手抵达用户所在地以后将订单交付至用户所需的时间），这么怎样将这批新订单在正确的时间分配至正确的骑手，致使用户体验得到保证的同时，骑手的配送效率最高。
外卖配送场景下一个配送区域上诸多骑手的分布示意图
美团外卖每晚形成巨量的订单配送日志、行驶轨迹数据。通过对配送大数据进行剖析、挖掘美团骑手系统派单破解，会得到每位用户、楼宇、商家、骑手、地理区域的个性化信息，以及有关各地理区块徒步路径的有效数据，这么订单智能分配系统的目标就是基于大数据平台，依照订单的配送需求、地理环境以及每名骑手的个性化特性，实现订单与骑手的高效动态最优匹配，因而为每位用户和店家提供最佳的配送服务，并增加配送成本。
即时配送订单分配问题的优化目标通常包括希望用户的单均配送时长尽量短、骑手付出的劳动尽量少、超时率尽量低，等等。通常可抒发为：
不仅要考虑时间、地段等约束外，有时还须要考虑部份订单只能由具备个别特性的骑手来配送（比如烧烤订单只能交给携带专门武器的骑手等）、载具的容量限制等。
即时配送大数据平台实现对骑手轨迹数据、配送业务数据、特征数据、指标数据的全面管理和监控，并通过模型平台、特征平台支持相关算法策略的快速迭代和优化。
机器学习模块负责从数据中寻求规律和知识，比如对店家的出餐时间、到用户所在楼宇上下楼的时间、未来的订单、骑行速率、红绿灯历时、骑行导航路径等诱因进行确切预估，为调度决策提供确切的基础信息；而运筹优化模块则将至时配送大数据平台以及机器学习的预测数据基础上，采用最优化理论、强化学习等优化策略进行估算，作出全局最优的分配决策，并和骑手高效互动，处理执行过程中的问题，实现动态最优化。
达达-易迅到家——路径规划和派单算法
在10.22号举行的《中国开发者会议》上，新达达配送算法团队负责人廖瑞奇首次分享了达达-易迅到家在路径规划和派单算法方面的一些实践经验。
1）路径规划
在达达平台上，一个勇士可能会同时配送多个订单，怎么规划勇士的配送路线，致使骑手的送货距离最短，优化勇士的配送效率，是平台要解决的一个核心问题。
对于单个骑手的路径规划问题，是一个典型的TSP问题：
因为TSP是一个NP-hard问题，没有方程时间内的准确解法。为了解决这个问题，新达达使用了启发式算法中的遗传算法，来快速获取勇士的较短配送路线，而且还能同时得到规划后的路线的最终配送距离。在待规划点超过10个以上的情况下，算法的运行时间也能保持在几微秒，同时保证极高的确切性。
有了这个基础算法，新达达就可以判定订单间的顺路情况，以及某个订单是否适宜由某个勇士来配送。
2）订单委派
在新达达平台上，同时有订单的抢单和派单机制，来实现合理的订单分配。
在订单分配的过程中，除了须要考虑顺路情况、配送效率等，也要考虑勇士的接单偏好、配送能力、活跃状况，以及订单分配的公正性等诱因。
简单来说，订单委派是一个有限制的多目标优化问题，除了须要考虑平台效率，也要考虑骑手的心理诱因、运营的稳定性等。
目前，使用派单和抢单结合的形式，达达平台上绝大多数的订单，都能在发出后1分钟以内实现订单的合理分配。
58速运：战斧项目
2017年11月，58到家技术总监/58速运前端构架总负责人胡显波在《2017全球敏捷运维大会上海站》介绍了58速运第三次技术变迁：战斧项目。
1)智能模型训练
上图为智能模型训练图，首先58速运会将订单信息、用户信息、司机信息、客司关系信息、订单总体推送、司机接单等场景信息统一上传到大数据平台，通过这些归一化&分桶、、特征组合、独热编码等将这种数据剖析为特点数据。
针对剖析下来特点数据，还须要对它进行训练，如：订单价钱、订单距离等特点在整个订单派单中起到的权重。由于特点好多，估算下来的权重可能并不是一个完美的解，只能说是近优、最优的一个解法，通过不断地迭代优化，最终训练下来最终的模型。
2）订单-模型运用
下单阶段：在用户下单时，会采用这些用户订单定价的模型，观察这个订单所在的商圈的运力饱和度，若果司机少，而订单需求多，会进行一个订单的调价。
推送阶段：系统推送的过程中，会依照司机的接单意愿来捞取。有的司机喜欢高价位订单，有的司机喜欢近程订单，有的司机喜欢去中关村等。58速运会依照订单与司机意愿的匹配程度进行优先推送的排序。
抢单阶段：先预估这个订单的接单人数，估算下来订单的价值，假如订单的价值高（价钱高、地点好）、那么这个订单不会领取补助了，同时会扣取司机的一些积分或优先抢单次数等。假如订单价值比较低（价钱低、偏远地区），会给这个订单适当地降低补助，来确保订单的完成。
委派阶段：当司机抢完单之后，58速运会按照所有司机历史完成订单的数据，取司机的质量，来决定那个司机上单，保证订单尽可能完成。
订单完成阶段：订单完成了之后预测这个用户的流失机率，假如可能流失，会送一些券或则其他权益吸引用户留在平台。
3）派单
上图在智能派单时代的系统构架图。用户在下完单之后，订单会步入到58速运整体的策略系统，它包含推送系统、补贴系统、价格系统、任务系统等，之后通过特点匹配系统，估算出一个最优的订单调度解，将这个订单推送到司机的单队列引擎和订单的排序策略引擎，最终通过推送服务将订单推献给司机。
4）策略分流+检测
智能系统须要有不同的算法在线上实验，当一些新算法研制完成之后，肯定不能用100%的流量在线上进行验证算法的可行性，假如有问题，会中单上业务形成影响。58速运通常取5%或10%的流量在线上验证。通常按照用户手机号、设备码、用户属性等，以及取模、集合等方法。验证线上算法验证时，怎样实时的检测算法的疗效，防止错误算法中单上业务导致影响？
如上图所示，用户在APP的每位步骤、运用了那个算法，58速运就会将用户的ID、采用的算法ID通过日志上报的报到统计平台。业务监控平台会实时进行监控，对于出现异常的算法就手动关掉分流。
5）特点估算
特点数据中有40多万个特点，每位订单须要推献给好多个司机，须要进行进行上万次的运算，须要在几十微秒内给出估算结果，怎么保证估算的高性能呢？58速运采用的是这些阶段性风波驱动的估算方法来最大化增强并行估算的能力。
如图所示，这是58速运的估算链，上面包含多个Stage，包含打算阶段、转化阶段、取数阶段和估算阶段，每一个阶段都有自己独立的线程池，按照每位阶段的特点设置核心线程数，同时整个估算链做到了可拔插的方式，便捷业务调整。
6）监控平台
一个是立体化监控，目前早已做到的监控包含：关键字、接口、流量、端口，JVM、CPU、线程、缓存、DB所有的监控等等，同时还有服务整治，当服务节点发生异常，实时切换。
业务化的指标监控，渠道转化率、渠道取消率、渠道推送数目、异常订单数目等等，假若出现异常，第一时间预警。
另一个是调用跟踪系统，好多互联网公司都早已在使用，调用跟踪系统目的是须要见到的是APP发起的每位恳求在整个前端走过的所有过程，疗效右图所示，可以监控到每一步所调用的服务和历时。
新手：汽车路径规划
简单来说，就是通过算法+动态规划实时跟踪交通信息，以及调整运输路径，就是把那里的活、什么样的活、派给哪些样的车，货运配送的成本和效率做到最优。
新手网路人工智能部从自身业务出发，联合集团IDST、阿里巴巴云估算的力量，构建一款适宜中国复杂的业务需求，又在疗效上接近国际水准的分布式汽车路径规划求解引擎--STARKVRP，探求一条结合运筹优化、分布式估算、机器学习、人工智能结合的技术路线。
VRP问题目标，是给出一个确定的最优解，包含汽车以及她们的运输路径，来服务一个顾客集合的订单。这也是组合优化中研究最广，最重要的问题之一。
如你们所知，中国的货运情况尤为复杂，有自己好多奇特的场景，也衍生出了对应的VRP求解类型和分支。以下是STARKVRP现阶段支持以及开发中的VRP类型和对应的业务类型。
目前该算法正在部份农村货运网点使用。按照每日单量美团骑手系统派单破解，为农村的货运老司机规划配送路线，每晚实时更新，在保证时效的基础上，可节约汽车、人力、邮费。综合测算出来，农村领域的货运成本能降低30%以上。
技术选型-丰富多样的求解方法：
传统用于求解VRP的精确解法难以应对大规模数据集：
借助元启发式建立求解的基础框架：
过去都是人为固定好的线路，现今通过大数据来分配路线，系统会依照每晚实际入库量，生成一条智能配送线路，发送给农村配送司机。同时，每晚配送的线路都是按照单量实时更新。
STARKVRP不仅仅在新手内部的村淘、零售通、跨境、新能源车、仓内路径规划早已开始落地，并且更为广泛的开始服务于像日日顺这样的外部公司，为增加中国的货运成本，提高时效尽一份算法人员的能力。
免责声明：部分文章信息来源于网络以及网友投稿，本站只负责对文章进行整理、排版、编辑，出于传递更多信息之目的，并不意味着赞同其观点或证实其内容的真实性，如本站文章和转稿涉及版权等问题，请作者在及时联系本站，我们会尽快为您处理。
