如何评价阿里车辆路径规划算法入围Franz Edelman奖决赛？

jquave

看到中国物流今年首次入围Franz Edelman奖，中国物流算法在世界算是什么水平？

RecursiveFrog

根据美国运筹学与管理科学学会（INFORMS）信息显示，以菜鸟人工智能团队为核心研发的物流路径规划算法，已经入围具有运筹学“奥斯卡”之称的Franz Edelman杰出成就奖。这是全球运筹和管理科学界的最高工业应用奖。截止到目前，菜鸟已经在全球权威车辆路径规划（VRP）问题评测系统中的保持创造了41项世界记录，并且是国内首个问鼎该评测系统的研究机构。
0. 何为VRP问题

VRP问题是许多配送服务提供商的重要调度任务，如电子商务仓库、线上线下服务提供商和最后一公里配送公司。与VRP问题直接相关的例子，比如大名鼎鼎的欧洲卡车模拟游戏，需要玩家驾驶卡车在众多欧洲城中之间穿梭，包括英国、比利时、德国、意大利、荷兰、波兰等等，将重要的货物送往遥远的目的地，通过合理分配车辆规划路线使得运输费用最小经济效益最大化。从游戏的开始关卡，运输四种不同的货物的简单模式，在逐渐的运输过程中开始经营自己的运输事业，直至拥有自己的车队，实现所有公司货物运输至所有目的城市，让公司赚取更多的利益。






在VRP问题中，车辆的固定成本和由于汽油消耗造成的路径成本的总和通常是服务提供商所关心的，因此在规划车辆路线时，目的是使与车辆和行驶距离相关的成本最小化。对于实际规模的问题，即使只有几百个客户节点，常规的优化技术也需要几天甚至几年才能找到最优或接近最优的解决方案，然而菜鸟需要面对的客户节点数远不止几百个，而且每次的运输任务需要以毫秒级的时间内确定最优运输方案，因此常规方法在实际物流背景中难以实施。除了基本的VRP问题之外，还有许多变体，如CVRP（Capacitated VRP）限制配送车辆的承载体积、重量等；VRPTW（VRP with Time Windows）客户对货物的送达时间有时间窗要求；VRPPD（VRP with Pickup and Delivery）车辆在配送过程中可以一边揽收一边配送，在外卖O2O场景中比较常见；MDVRP（Multi-Depot VRP）配送网络中有多个仓库，同样的货物可以在多个仓库取货；SDVRP（Split Delivery VRP）同一个客户的货物，可由多辆车分拆送达等。通常，在解决实际车辆路径问题时，不仅需要考虑节点之间的实际距离，还需考虑许多复杂因素，如道路网络、交通条件和天气，而且菜鸟所面临的物流问题规模很大，多为上述VRP变体问题的混合问题，并且包含的决策变量和约束条件非常多，常规的求解方法非常耗时，一般很难在短时间内求解完并应用到线上。




众所周知，我国的快递业务非常繁杂，已经有大量的快递运输公司认识到了物流运输优化的重要性，并且投入了大量的人力和财力对车辆路径优化问题进行研究。其中，菜鸟作为龙头企业，依托阿里巴巴强大的生产数据和算法技术团队，可以有效地解决物流路径规划问题。据菜鸟网络资深算法专家胡浩源介绍，菜鸟人工智能部仓储智能化和车辆路径规划算法团队负责探索将优化搜索和机器学习技术进行有效融合，寻求最优的车辆路径优化方案，以提高物流配送效率降低成本。目前，菜鸟可以使用最少的车辆，行驶最短的里程，完成配送任务，并设计开发了相应的优化求解器Greed Solver，应用于企业的多项业务中。
相比于其他运输公司，菜鸟车辆路径规划有如下的特点：
1. 可以在合理的时间内生产高质量的解决方案

菜鸟算法团队研发了基于深度强化学习的Greed DRL Solver，可以求解各种变种VRP(CVRP, SDVRP, SVPTW, PDVRP等), 及Batching, Assignment, Scheduling等多种OR问题。对于大规模的VRP问题(>=1000个Customers)，Greed DRL Solver可以在几十毫秒内输出高质量的解。目前在Gehring & Homberger Benchmark可以达到BKS(Best Known Solution)的97%~99%。该算法基于一种新的联合学习方法用来有效地解决实际的VRP问题，并撰写了论文《Efficiently Solving the Practical Vehicle Routing Problem: A Novel Joint Learning Approach》，发表于KDD 2020。团队提出了一种基于图卷积网络(GCN)的模型，该模型以VRP graph中的node和edge特征embeddings作为输入，利用两个独立的解码器来解码它们的embeddings。其中一个解码器为基于递归神经网络(RNN)的序列预测解码器，以node 和 edge embeddings为输入，输出一个序列作为VRP实例的解；另一个解码器为基于多层感知器的分类解码器，以edge的特征embeddings，输出概率矩阵。具体来说，概率矩阵中的值表示各edge作为车辆路线的概率，这也可以转换为VRP实例的解。团队使用顺序预测解码器的输出作为分类解码器输出的标签(监督)，这使得两个解码器的训练相互促进：使用一种具有rollout baseline的强化学习方式来训练顺序预测解码器，并利用一种具有策略采样的监督方式来训练另一个解码器。为了训练整个模型，采用了强化和监督学习相结合的策略。据胡浩源介绍，目前通过在零售通城配业务中应用车辆路径规划算法，订单配送成本已经降低了10.3%，并推动仓库货物流转效率的提升，仓库集货周转时间降低了57%。
2. 采用DSL特定语言

市面上有非常多的通用建模语言和优化求解的产品，如Chocosolver、Localsolver、Google的启发式优化求解器OR-Tools和常见的优化求解器Gurobi。Localsolver等是由国外技术研究团队开发的建模优化求解器，涉及到技术垄断，难以根据实际的物流背景进行修改，不适用于真实的企业环境；OR-Tools采用启发式的方法进行求解，但是求解效果与实际的最优解相差甚远；由于实际问题规模比较庞大，Gurobi也很难在合理的有效时间内解决问题。因此，上述求解器都不适用于菜鸟业务，在面对菜鸟业务中很常见的问题规模时，无法在给定时间内得到满意解，进而影响整体的物流工作。虽然基于通用的启发式算法可以在业务限定的时间内出解，但解的质量往往不够好，影响业务效果。所以，菜鸟选择了自主研发的道路，为了能够既拥有通用建模语言的强大表达能力和独立性(跟底层求解算法解耦)，又具备专用求解器的求解质量和速度，菜鸟研发了Greed Programming Language(GPL)，这门面向复杂组合优化业务场景的DSL。GPL支持Java和Kotlin进行建模，使用过程简洁直观，具体的编程程序和输出结果如图所示。




GPL已经应用于零售通的城配智能调度，使得原先耦合在求解算法当中的业务逻辑以一种相对简洁的表达方式独立的维护。盒马和Lazada的算法团队也通过GPL接入了Greed VRP Solver，获得了更好的求解质量和求解速度，并在深入更多的业务场景；菜鸟团队利用GPL实现了适配零售通智能调度、服务网络规划和AGV作业调度等业务。除了盒马和菜鸟，同城零售、LAZADA等平台均使用该算法提供服务，甚至有外国公司购买菜鸟算法。
3. 易于开发与维护

Greed Solver使用独立建模语言，强制分离核心算法开发人员和业务建模人员，强制业务线必须使用Greed Solver对接业务，快速反馈，快速解决，构建完善的工具链，自动部署、服务生成，让业务建模人员用的舒心。算法工程师可以创建和管理不同的业务场景，并针对不同的业务场景需求编写Schema，然后直接编译、部署、测试等一系列的可视化流程，发布上线，形成线上算法服务。
中国有全球最复杂的物流场景，涉及大量车辆、人员的配送拣选路径优化，随着数字物流时代的到来，新零售和即时送达需求更加旺盛。菜鸟注重算法的应用和普及，将帮助行业加快数字化升级，共同为一线人员创造更好的工作环境，提供更优质的物流服务。

FeastSC

Franz Edelman —— 运筹学界的奥斯卡

可能大家对Franz Edelman奖不是非常熟悉哈，所以我这里首先科普一下Franz Edelman奖是世界上最负盛名的分析与运筹学成就奖，也是全球运筹和管理科学界的最高工业应用奖。打个比方来说这个奖的地位就相当于运筹学领域里的奥斯卡奖。Franz Edelman 杰出成就奖每年颁发一次，从1972年开始，到2021年是第50届。奖项设立五十年来，获奖者都是因为处理世界上最复杂的问题并且产生了重大的应用价值，据统计获奖项目已累计产生 2500 多亿美元价值。
那么中国企业在Franz Edelman 奖的战绩如何呢？在历史上一共只有三家中国企业入围，他们分别是中国石油、宝钢集团和工商银行。令人激动的是阿里研发的VRP路径规划算法，已经入围 2021 年 Franz Edelman 杰出成就奖的finalist。在阿里供应链与运筹优化技术小组的牵线之下，该算法已经在阿里集团内部开源，并被各个不同业务的算法团队敞开怀抱接纳：盒马、菜鸟、Lazada等平台早已应用多时并且参与开源建设。而这也是该奖项设立 50 年来，今年首次有中国科技企业入围。我们不得不感叹中国企业在运筹优化算法实际应用落地的能力已经有了飞速发展。


现实中的物流车辆路径问题非常复杂！

可以毫不夸张地说，中国有着全球最复杂的物流场景，例如双十一剁手血拼的背后是有着强大的物流系统作为支撑的，而这样复杂的物流系统里边必然涉及大量车辆、人员的配送拣选路径优化。随着数字物流时代的到来，继包裹数字化之后，物流枢纽、物流车辆、物流末端和物流人员的数字化接踵而至。同时随着新零售和即时送达需求更加旺盛，智能路径规划算法成为新零售发展的关键技术支撑之一。传统的车辆路径规划问题（Vehicle Routing Problem, VRP）是物流领域最经典的优化问题之一，有着极大的学术研究意义和实际应用价值。
这里为不熟悉的盆友插播科普一下 “VRP领域最权威的测评平台”，这是由欧洲独立研究机构SINTEF发起并管理的世界最好解榜单（Best Known Solution）是检验求解VRP问题算法效率的最权威的评测对比平台，其中VRPTW的数据集包括了对Solomon实例（1987年提出）和Gehring & Homberger实例（1999年提出）共356份测试数据的世界纪录，PDPTW的数据集包括了Li & Lim实例（2001年提出）的360份数据的世界纪录。全世界最顶尖的优化算法学者（例如Jakub Nalepa, D. Pisinger, Yuichi Nagata等）以及优化技术公司（例如Quintiq等）都不断地在此平台上刷新世界纪录，近二十年间，英国、波兰等全球顶级的研究机构、知名学者、老牌物流企业不断创造纪录，又打破纪录，长期占据榜首，智慧的脑袋们将车辆路径规划领域的技术逐渐地推向极致。菜鸟车辆路径规划团队成立4年，目前保持着41项世界纪录，高峰时期甚至有8、90项世界纪录，也是国内唯一在榜的物流公司。
而菜鸟的车辆路径规划团队在这样的世界性顶尖优化算法学者聚集的地方崭露头角，甚至可以说是出类拔萃，可以非常骄傲地说作为中国物流领域的代表企业之一，菜鸟团队的荣誉也预示着中国物流算法已经足以在某些领域走在世界前列啦。为啥这么激动呢，相信不论是身处学界还是业界我们多多少少都能感同身受到凭自己的努力设计的算法有一天最终实际落地于社会的运作，并且产生了巨大的社会价值是一件多么自豪的事情，在产生实际价值的基础上还产生了巨大的科研价值，就更加令人兴奋。所以接下来就想详细跟大家谈谈这两方面产生的令人称赞的价值。
l 实际应用价值
现实中的VRP问题有多难呢？打个比方以一家物流公司需要向1000个网点进行配送为例，其配送路径不计其数，如果能找到一条最高效的配送路径，将会大为提高物流效率降低成本，但是如果调用全球50亿台计算机共同计算，按每台计算机每秒计算20亿次，逐一验证每一条配送路径的效率，需要至少1万亿亿年，这是一个根本不可能完成的任务，但是菜鸟的VRP算法很好的解决了实际中遇到的复杂VRP问题。
他们旨在为一线人员创造更好的工作环境的同时为顾客提供更优质的物流服务。并且菜鸟车辆路径规划算法已经落地于多项业务中。比如，在车辆配送环节，车辆路径规划算法就可以有效降低车辆使用数量和车辆行驶距离；在仓库内部拣选作业中，车辆路径规划算法可以降低拣选人员的行走距离。此外，车辆路径规划算法帮助外卖配送员规划配送路线，从而提升客户体验、大幅度降低配送成本，最广为人知的就有菜鸟创造的 30 分钟—2 小时内送达的新商业业态。据不完全数据统计，目前通过在零售通城配业务中应用车辆路径规划算法，菜鸟的订单配送成本已经降低了10.3%，并推动仓库货物流转效率的提升，仓库集货周转时间降低了57%。
对于一个大型企业来说，这样的成本降低与效率提升成果所带来的实际应用价值是十分巨大的，个人感觉这也是阿里能够获得此次Franz Edelman奖提名的重要原因之一。
l 学术研究价值
正如前面所说，虽然菜鸟的车辆路径优化团队是一支成立不久的非常年轻的团队，但是他们在这些年间硕果累累，他们对优化算法的不断迭代升级，不断地对算法进行探索打磨，在工程架构上不断的更新完善，使得本源于解决实际VRP问题的算法形成一套完整的技术框架在技术沉淀上获得了重大成果。这也就完成了从实际应用价值到学术价值的升华与跨越。
菜鸟智能路径规划算法在前面说到的“VRP领域最权威的测评平台”上，自 2018 年开始率先打破 60 余项 VRPTW 和 PDPTW 计算模型的世界纪录，并在之后的两年里持续排名世界第二，但是在此之前，中国研究者无一能跻身榜单，个人认为这不仅是对中国物流算法水平最好的诠释，更是菜鸟此次获提名奖的重要伏笔。
记得在菜鸟官网的相关报道里曾经提到，其实菜鸟的VRP团队一路走来也并非都是都是十分顺畅，曾经菜鸟追平这一榜单的多项世界纪录后长达半年时间内一直无法进一步突破。但是数据集的测试显然对菜鸟的实际算法落地肯定也起到了重要的作用，个人认为通过数据集来验证算法的可靠性是必须的，毕竟在验证之后才能高效地将算法应用到实际业务中去。
比如为了进一步提升VRP引擎的求解质量，对其进行并行化升级，先后研发实现了三套并行化算法架构：包括基于odps-graph实现的island分布式模型，基于spark实现的central pool模型，最后是充分利用GPU并行计算的优势，使用原生的CUDA C编程接口，将计算和数据更新等并行度较高的模块放在GPU上执行。在大规模数据集上测试发现，相比于直接使用矩阵运算库CUBLAS，这一方案可以获得40倍的加速，相对于原先的单机版本，可以加速近一千倍。
而后菜鸟通过将机器学习思想融合到搜索策略的控制中，基于预测的概率来平衡搜索的广度和深度，从而可以大幅度缩减需要搜索的空间，同时又保留跳出局部最优的能力，最终，在2018年9月，该团队的算法终于获得了比世界纪录更好的结果，并经过了平台的验证，向全世界的研究者进行了公开。脱离了硬件水平的限制，以实际算法落地为根本，真正用心钻研出高质量高效率的算法，这种专注务实的精神是十分令人敬佩与感动的。
需要指出的是，最终的技术方案看起来还是比较符合直觉的，但其中技术的分叉线路非常庞杂，如何在不同的算法技术路线做取舍，资源投入做取舍，并行化重点优化的部分做取舍，就类似几何题的添加辅助线，每一次都是艰难的选择。
学术研究与实际应用总是相辅相成相互成就的，而菜鸟车辆路径优化团队深刻的诠释了学术与应用之间不可切分的联系，阿里闯进2021 年 Franz Edelman 杰出成就奖决赛圈是很振奋人心的，作为中国本土物流算法开拓者的代表之一，不仅向世界展示了我们的实力而且也相信也一定程度上能调动起物流行业内更大活力。
阿里提名Franz Edelman 杰出成就奖的背后其实更值得我们关注的是随着国内经济社会运作大环境的改变，运筹学的重要性日益彰显，其中之一便是我们一直提到的运筹学在物流领域的应用与普及，菜鸟所做的VRP问题又是运筹学应用于物流领域众多方向之一。从1947年Danzig提出求解线性规划问题的单纯形法，到如今发展成为包括线性，非线性规划，整数规划，动态规划，博弈论，决策论，排队论，存储论等等诸多领域与方法的学科，运筹学一路走来，在实践需求中诞生，以数学的根基为依托不断进行理论发展，最终又回归于实践。
从市场需求预测到合同的签订，从原材料采购与供应到产品的加工与调度，从订单的接收到产品的运输与配送，等等。在物流与供应链领域运筹学所能应用到的地方无处不在，当运筹学的方法与实际问题背景联系起来，通过对实际问题的分析与建模，而后选择合适的运筹学方法进行求解，我们就将曾今的纯定性分析与准确的定量分析方法结合起来，实践证明这样的技术进步是具有重大意义和作用的。因此不论我们是做整数规划研究优化了一条生产线的原料分配还是通过存储论为企业确定了一个不错的订货计划，或者等等其他，我们都像是运筹学的传道士，将这种科学的技术应用于我们的生产生活。我们应该坚信会有越来越多的“菜鸟车辆路径优化团队”在科学技术飞速发展，运筹学日益朝气蓬勃的今天显现，我们也都要有理想朝着这个方向努力。

johnsoncodehk

1 车辆路径规划问题简介

对于不熟悉运筹学的童鞋，我们这里先科普一下什么是车辆路径规划问题（VRP）。车辆路径规划问题（VRP）是运筹优化领域最经典的优化问题之一。在此问题中，有若干个客户对某种货物有一定量的需求，车辆可以从仓库取货之后配送到客户手中。客户点与仓库点组成了一个配送网络，车辆可以在此网络中移动从而完成配送任务。在求解此问题过程中，需要优化的决策变量为每个客户的配送任务应该分配到哪一辆车上，以及每辆车完成客户配送任务的先后顺序，优化目标为最小化车辆总行驶距离和使用的车辆数。


上面介绍的仅仅是车辆路径规划问题最基本的形式，在实际场景中往往要根据实际应用问题的需求进一步添加约束和目标函数构成新的变形的车辆路径规划问题，其中比较常见的有 CVRP：Capacitated VRP, 限制配送车辆的承载体积、重量等。VRPTW：VRP with Time Windows, 客户对货物的送达时间有时间窗要求。VRPPD：VRP with Pickup and Delivery, 车辆在配送过程中可以一边揽收一边配送，在外卖O2O场景中比较常见。MDVRP： Multi-Depot VRP, 配送网络中有多个仓库，同样的货物可以在多个仓库取货。SDVRP（Split Delivery VRP）同一个客户的货物，可由多辆车分拆送达。
2 自适应大规模领域搜索算法求解VRP问题

车辆路径规划问题是典型的NP-hard问题，非常具有挑战性。车辆路径规划问题在学术界和工业界也已经研究了几十年。以branch and cut and price 为代表的数学优化算法能给出质量较好的解，但在面对较大规划问题的时候其求解时间难以满足实际应用的需求。启发式和元启发式算法被证明在求解VRP方面具有很好的效果和效率。一些经过精心设计的元启发式算法，例如模拟退火、禁忌搜索、遗传算法、蚁群算法、变邻域搜索、自适应大规模邻域搜索算法（ALNS）等在求解VRP上有着非常好的表现。
因此在求解VRP问题中选用了ALNS算法。ALNS算法属于邻域搜索算法的一种。邻域搜索算法（或称为局部搜索算法）是一类非常常见的改进算法，其在每次迭代时通过搜索当前解的“邻域”找到更优的解。ALNS算法的基本流程如下图所示：


Step1：使用一定的规则构造一个初始解（即Initial过程）；
Step2：基于算子的权重，选择此次迭代过程中使用的Ruin算子和Insert算子；
Step3：对此次迭代的初始解执行Ruin操作，即将部分已经被车辆服务的客户点删除，使初始解成为一个不可行解；
Step4：对步骤（3）获得的解执行Insert操作，即对于还没有被车辆服务的客户点，将其插入到解中，尽量获得一个可行解；
Step5：基于优化目标函数评估步骤（4）获得的新的解，并根据一定的策略决定是否接受新解；
Step6：判断是否达到终止条件。如果是，则终止计算，返回当前找到的最好解；否则，基于此轮计算中算子的表现，更新算子的权重，并返回到步骤（2）。
相对于其它算法，ALNS算法的优势包括：
1 算法框架易于拓展，除了求解标准的VRP之外，还能求解VRPPD，MDVRP等变型问题
2 相对于普通的Local search 类型的算法，ALNS在每一步搜索过程能够探索更大的解空间
3 ALNS算法在搜索过程中能够自适应地选择合适的算子，从而对于不同类型的问题数据能够有比较稳定的良好求解结果
4 通过设计不同类型的算子，ALNS可以实现不同的搜索策略，从而便于算法的升级和拓展。
对于大部分启发式算法而言，可以天然地通过并行化计算来提升搜索效率和效果，例如并行地计算评估多个相邻解的质量、向多个邻域方向进行搜索或者使用多种策略进行搜索等，甚至并行地使用多种算法进行搜索等。所以为了进一步提升VRP引擎的求解质量，菜鸟仓配智能化算法团队对VRP引擎进行了并行化升级。算法并行化加速的策略有以下三种：
（1）Population Island在算法执行过程中，有若干个Island并行执行计算，每个Island独立地进行演化，其中各有一个Master和若干Worker，其中Worker负责具体的搜索任务的计算执行，Master负责任务的分配协调以及与其它Island之间的通信等。每隔一定的计算步数，各个Island的Master之间会相同通信，分享搜索过程中获得的知识，从而提升整体的搜索效率。


（2）Parallel Memetic整个算法可以分为两个阶段，第一个阶段的计算重点在于减少使用的车辆数（Delete Route），在此阶段中，若干个Worker并行计算，并每隔一定的步数相互通信分享信息。第一阶段结束之后，会获得若干中间结果，将这些结果作为第二阶段中每个Worker上的初始演化种群进行计算。第二阶段的计算重点在于降低车辆行驶距离（Reduce Distance），第二阶段的Worker之间同样有相互通信分享知识的机制，而且可以通过控制演化过程中父代个体的选择机制来进行动态地调节Exploration与Exploitation。


（3）Central Pool在算法中有若干个Worker负责具体的搜索任务，并将搜索得到的解返回到Central Pool中，由Central Manager对解进行排序、筛选、聚类等处理，然后Central Manager会依据当前Central Pool中的解集情况生成新的计算任务并发送给Worker执行。Central Manager可以对解空间进行合理的刻画，并通过计算任务的管控分配在Exploration与Exploitation之间进行平衡，从而提升求解效率。


3 GCN-NPEC求解 VRP问题

此外，菜鸟算法团队还研发了基于深度强化学习的Greed DRL Solver，可以求解各种变种VRP(CVRP, SDVRP, SVPTW, PDVRP等), 及Batching, Assignment, Scheduling等多种OR问题。对于大规模的VRP问题(>=1000个Customers)，Greed DRL Solver可以在几十毫秒内输出高质量的解。目前在Gehring & Homberger Benchmark可以达到BKS(Best Known Solution)的97%~99%。
该算法基于图卷积网络的，采用联合强化学习和监督学习的算法进行训练，模型表述为GCN-NPEC（Graph Convolutional Networks with Node
Sequential Prediction and Edge Classification），如下图所示：


首先采样图卷积网络对CVRP问题进行编码。将编码后的结果输出给解码器。解码器有2个，其中一个解码器是 sequential prediction decoder，采样递归神经网络来实现，其输出为一个序列（即VRP问题的一个解）。另外一个解码器采用多层感知器来实现，将另外一个解码器sequential prediction decoder的输出作为label来训练。详细的算法内容可见参考文献【1】
参考文献：
【1】Duan L, Zhan Y, Hu H, et al. Efficiently Solving the Practical Vehicle Routing Problem: A Novel Joint Learning Approach[C] Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2020: 3054-3063.
【2】世界冠军之路：菜鸟车辆路径规划求解引擎研发历程

fwalker

不只阿里。京东和联想都入围了。

ChuanXin

入围的因素优先级别

业界影响力精细化运营技术思路