14

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

 3 years ago
source link: https://www.zhihu.com/question/440079767/answer/1688213738
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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

0. 何为VRP问题

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

v2-c933af7dc6c38e427bf948754a7dbeaf_720w.jpg?source=1940ef5cv2-f84bf7ce97bf34df776859206c249610_720w.jpg?source=1940ef5c

在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进行建模，使用过程简洁直观，具体的编程程序和输出结果如图所示。

v2-2679a4c48ee47a603f0165aa8ddb7c0f_720w.jpg?source=1940ef5c

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

3. 易于开发与维护

Greed Solver使用独立建模语言，强制分离核心算法开发人员和业务建模人员，强制业务线必须使用Greed Solver对接业务，快速反馈，快速解决，构建完善的工具链，自动部署、服务生成，让业务建模人员用的舒心。算法工程师可以创建和管理不同的业务场景，并针对不同的业务场景需求编写Schema，然后直接编译、部署、测试等一系列的可视化流程，发布上线，形成线上算法服务。

中国有全球最复杂的物流场景，涉及大量车辆、人员的配送拣选路径优化，随着数字物流时代的到来，新零售和即时送达需求更加旺盛。菜鸟注重算法的应用和普及，将帮助行业加快数字化升级，共同为一线人员创造更好的工作环境，提供更优质的物流服务。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK