中国物流供应链“零的突破”！阿里路径规划算法入围运筹学“奥斯卡”

AI资讯1年前 (2023)发布 AI工具箱

268 0 0

最新消息，中国物流力量，刚在全球运筹和管理科学界的最高荣誉中，实现零的突破！

1月15日，国际运筹学与管理科学学会（INFORMS）公布了2021年Franz Edelman杰出成就奖总决赛名单，阿里巴巴凭借领先的路径规划算法及新零售实践，首度闯进总决赛。

INFORMS评价称，阿里开创了新零售模式，通过技术优化了仓配流程，可在极短时间内实现80%~90%的最优性能。

Franz Edelman杰出成就奖，是全球运筹和管理科学界的最高工业应用奖，被誉为运筹学的“奥斯卡”。该奖项重点奖励世界各国、地区，在运筹和管理学领域做出突出贡献、并带来重大应用价值的研究项目或成果。

入围者不仅要在学术上有创新，还要经过业界的检验，在实际落地的过程中明确产生价值。

在以往的获奖名单中，物流领域有过美国亚马逊、沃尔玛等企业的项目成果，普遍在实际业务中产生了数亿美元以上的效益。自该奖项1972年首次颁发以来，获奖项目更是已累计产生2500多亿美元价值。

但该领域内，中国在此之前尚属空白地带，奖项设立50年来，这是首次有中国物流供应链领域企业入围。

所以阿里物流供应链拿出的究竟是怎样的算法？又能给我们的日常生活带来了怎样的改变？

阿里因何获奖？

物流路径规划问题，属于典型的NP-hard问题。

结合零售场景简单来解释，其实就是如何快速实时地规划仓内的拣货路线，以及骑手的配送路线的问题。

具体而言，在仓内，路径规划算法需要综合消费者订单、商品在货架的位置、拣选员传输给打包员的悬挂链速度等因素，指引拣货员进行更合理的工作。

在仓外，算法又需靠考虑配送员与商家的距离、商家备货时间等动态因素，分配距离近、工作量合理的配送员取货。

这里挑战主要在于以下三点：

不确定性：首先，在即时仓储配送模式下，顾客随时可能下单，需求存在随机性；其次，城市交通拥堵问题会带来通行时间的不确定性；最后，到达顾客所在位置后的配送交付同样存在不确定性，比如登记信息、等待电梯等带来的耗时。
在仓内空间有限的情况下，规划符合业务需求的路径：在仓内作业阶段，以盒马为例，每个批次有2-5个客户订单，每个客户订单包含任意4-8种商品，这些商品分散在仓内各个分区内，每个分区拣选完通过悬挂链传送到质检台打包，派送地址相近的订单还要进行集包，而后传输出库。因此仓内路径的优化需要同时考虑拣货路径和配送路径，并尽可能同时到达悬挂链，不在这个过程中造成堵塞。
严格的求解时间：由于订单即时性的需求，这样的路径优化需要在极短时间内完成，以留下足够的实际操作时间。

为此，阿里协同旗下菜鸟、盒马、Lazada等各业务方，打造了基于大规模领域搜索和深度强化学习的路径规划算法方案，实现了用＜0.01秒的时间，得到最优解98%~99%的最优性。

阿里巴巴供应链与运筹优化小组介绍，阿里VRP路径规划，雏形始于2016年菜鸟，并在丰富的仓储和配送协同中持续打磨，可支持半小时到2小时内送达的新业态，在预测、库存等方向处于业界前沿，未来将探索新零售更多可能。

自适应大规模邻域搜索算法框架

自适应大规模邻域搜索算法（ALNS），是2016年菜鸟开始建设路径规划算法系统之初，就择定的技术路线。

当时，国内外行业内的多数玩家选择的都是成熟的开源算法，比如jsprit和opt-planner等。但出于对后期技术发展天花板被限制的担忧，菜鸟还是选择了自主开发的路径。

而自适应大规模邻域搜索（ALNS）算法框架的优势在于：

易于拓展，除了求解标准的VRP（车辆路径规划）之外，还能够求解其各种变型问题；
相对于局部搜索类型的算法，ALNS在每一步搜索过程中能够探索更大的解空间；
ALNS算法在搜索过程中能够自适应地选择合适的算子，对于不同类型的数据都能有比较鲁棒的求解效果；
便于算法升级拓展，通过设计实现不同类型的算子，ALNS可以实现不同的搜索策略。

这样的选择，其实有点无知者无畏的态度在里面。

该小组核心成员友竹在事后回想时，这样说道。

好在以ALNS算法为核心的第一版VRP优化引擎研发完成后，研发人员们很快看到了效果：对比测试结果表明，其求解效果和效率显著优于jsprit等国际上流行的开源VRP Solver。

在此之后，团队又从两方面出发，进一步对VRP优化引擎的核心算法组件进行了丰富和升级。

一方面是功能上的扩展。

比如在原算法核心框架的基础上，增加了对Pickup and Delivery（车辆一边揽收一边派送）、Multi Trip（车辆多趟派送）等类型问题的支持；并且通过对实际业务问题的抽象，总结出不同类型的优化目标方程（例如最小化阶梯定价的总成本、最小化配送时间等）以及约束条件（例如车辆行驶距离限制、车辆配送订单数限制、车辆跨区数限制等），从而使求解引擎能够求解的问题更加全面广泛。同时，还研发了一套领域特定语言（DSL），调用者仅需定义相应的业务逻辑，与数据和核心算法相解耦，即可完成问题的求解。

另一方面则是技术上的探索。

比如为了进一步提升VRP引擎的求解质量，对其进行并行化升级，先后研发实现了三套并行化算法架构：

包括基于odps-graph实现的island分布式模型，基于spark实现的central pool模型，最后是充分利用GPU并行计算的优势，使用原生的CUDA C编程接口，将计算和数据更新等并行度较高的模块放在GPU上执行。在大规模数据集上测试发现，相比于使用CUBLAS，这一方案可以获得40倍的加速，相对于原先的单机版本，可以加速近一千倍。

深度强化学习算法框架

在启发式算法的路线之外，阿里路径规划算法系统还引入了另一条技术路线，就是深度强化学习（DRL）。

核心原因同样是业务场景的需求：比如外卖、打车这样的场景，需要在毫秒级的时间内返回结果。

深度强化学习算法框架，提供了一系列基于图神经网络的增强学习算法来求解VRP。

其中，图神经网络算法以点（坐标和需求）和边（点间距离和时间）作为输入，配合两类解码器分别解码这两类特征，并结合有监督学习的方法来训练相应模型。

另外，研究人员还将深度强化学习和自适应大规模邻域搜索进行了组合，以ALNS算法结果作为样本来训练DRL模型，更快速地求解VRP问题。

这样的组合拳之下，阿里VRP优化引擎实际早已霸气外露。

在入围Franz Edelman杰出成就奖之前，该引擎已经拿下不少世界第一。

比如2018年9月，在VRP算法领域最权威的评测对比平台——欧洲独立研究机构SINTEF发起并管理的Best Known Solution榜单上，路径规划算法就在VRPTW（客户对货物的送达时间有时间窗要求）上打破了世界纪录。

而截至2020年10月，VRP路径规划算法在这一榜单上取得了36个VRPTW实例和23个PDVRPTW实例的已知最优解，是国内首家在这两个问题上同时取得如此多世界纪录的物流供应链公司。

但既然能入围Franz Edelman杰出成就奖，自然还得在产业应用中有真章。

在阿里供应链&运筹优化技术小组的牵线之下，该算法已经在阿里集团内部开源，并被各个不同业务的算法团队敞开怀抱接纳：盒马、菜鸟、Lazada等平台早已应用多时。算法带来的价值正不断在这些深入人们生活的业务场景中积累，而对于技术人员而言，亦省却了重复造轮子的负担。

深入生活的算法

点一份盒马，足不出户，30分钟到1小时内就能有高品质生鲜菜品下锅。

你如今已经习以为常的便捷背后，正是路径规划算法这样的AI技术在发挥作用。

阿里供应链与运筹优化技术小组介绍，以仓库拣货为例，由于商品分布在仓库里各个不同的库位上，如果没有合理的路径规划，拣货员难免在反复寻找的过程中浪费很多时间、精力。

在用上了路径规划算法之后，拣货员就可以走最短的路，拣最快的货：原来一天要走2万多步，现在只需要走1万多步。

而在城配方面，对一个仓所覆盖的订单进行调度，最早是地图上人工框选来完成的，甚至是通过Excel按照文本地址来进行分组。由于配送点数众多，再加上实时落单的特性，调度时需兼顾车辆的装载率、里程、对区域的熟悉度等因素，花费的决策时间长达30-40分钟。而对AI而言，分钟级即可完成调度，这就给仓库留下了足够的生产时间，也通过更优的组合，提高了车效。

还不仅仅是零售、城配等领域。

实际上，物流路径规划算法背后的技术积累，可以说打造出了一把能用在各个不同业务中的“屠龙宝刀”。

以阿里自身的业务为例，大规模邻域搜索算法和深度强化学习算法这两套通用框架，同样可以解决犀牛智造的机器加工调度问题，为自动化生产规划最佳的加工路线。

同样，这套算法也可以迁移到打车领域的调度、拼车决策上。

在阿里内部的欢行打车平台上，由于路径规划算法的引入，在同样的运力下，可以使下班高峰期的打车成单率，从60%提高到90%。

所以如果更加简单粗暴理解，这一套算法，就让菜鸟展现出了“头部外卖平台+头部打车平台”具备的核心技术实力。

“贴地飞行”的科学家

阿里供应链与运筹优化技术小组中，有不少博士毕业后就致力于让技术在实际业务场景中产生价值的研发人员。而此次入围运筹学“奥斯卡”决赛圈，对于他们而言无疑是极大的鼓励。

但其实对于团队而言，这个成绩一开始并不在意料之中，一切也并非为获奖而立项。

值得指出的是，早在2016年，菜鸟就开启了物流路径规划算法系统的研发工作，不是为了刷榜，不是为了拿奖，就是为了解决实际业务中的痛点而已。

团队成员坦言，在项目成立之初，不会想到今天的成绩。

一开始，研发人员其实只是想要求解最简单的单仓发多点的问题，因为在当时的业务场景下，这样的情况占到了百分之六七十。

而当算法在应用之中，价值得到验证，更多的业务需求也就被提到了研发人员面前，比如多仓发货，比如外卖同时取送货……研发人员也就在这个过程中不断地去分解目标，通过打榜验证求解效果，不断迭代、完善功能。

归根结底，最开始是从业务痛点出发，为了解决实际场景的问题。

我们去打破各种Best Known Solution，主要是为了验证算法的价值。

不过，回首向来萧瑟处，一切也都是对菜鸟团队几年如一日下苦功的奖赏。

团队透露，在菜鸟人工智能部有上百名员工，博士就占了1/3，一直希望用最前沿的科学技术方法，求解现实业务中的最优解。

而无论菜鸟还是整个阿里经济体，正恰如其分地提供了最好的演武场，让他们得以实现“贴地飞行”的务实理想。

比如场景的丰富度。从各种淘系订单，到四通一达的包裹，再到各种社区零售店的日常补货，每一个来到菜鸟的研发人员，都有在实际大流量场景中，检验算法好坏的机会。

当然，还有一些凡尔赛式的总结。

前面也说道，VRP问题属于典型的NP-hard问题，在面对实际状况时，不仅问题规模大，求解难度也十分巨大。

举个例子，在求解n!复杂度问题时（即TSP，VRP退化最简单的情形），若n=30，每秒运算100亿亿次的超级计算机就得花上8万年的时间。

而现在利用上阿里本身丰富的软硬件资源，加上高效的搜索策略，算法研发人员就可以更低成本地打造高性能、高可靠的解决方案。比如基于阿里云的MaxCompute（原ODPS）数据仓库，或菜鸟自研的Minas包裹数据引擎，对于实际场景中的大规模问题，研发人员可以避免传统的人工干预和模型简化，直接从数据库中读取原生问题进行建模，然后直接导入高可靠的分布式求解器GreedSolver，在较小的延迟内获取高精度解，为业务提效赋能。

还有团队成员结合自身经历发出这样的感慨：

以应届博士生身份进入菜鸟人工智能团队时，一开始不会被设置明确的KPI，能享受到一个比较宽松的技术环境，有充分的空间去思考去观察，并发起自己认为有意义、感兴趣的研究项目。

而在这个成长的过程中，得益于阿里的业务土壤，又能够以战养战，让技术在实际业务中快速得到检验。

所以菜鸟在这次奖项中，能够为中国物流领域实现里程碑式的成绩，天时地利人和，缺一不可。