中国物流领域首次!菜鸟路径规划算法有多厉害?

12 月 10 日,美国运筹学与管理科学学会信息显示,以菜鸟人工智能团队为核心研发的物流路径规划算法,已经入围 2021 年 Franz Edelman 杰出成就奖。这是全球运筹和管理科学界的最高工业应用奖,被称为运筹学的「奥斯卡」。奖项设立 50 年来,首次有中国物流供应链领域企业入围。

01物流路径规划算法价值有多大?

菜鸟车辆路径规划服务是基于满足多网点多线路不同车型的复杂性配送场景而进行研发的,是菜鸟网络自主研发的车辆路径优化算法,技术上融合了大规模邻域搜索、超启发式算法、基因算法、分布式并行化和增强学习,在公开数据集上,算法已全面超过广泛使用的开源产品Jsprit,在Gehring & Homberger数据集上(客户点规模达到1000),已经持平若干项世界纪录。

2018年10月菜鸟在全球最权威的车辆路径规划(VRP)问题评测系统中创造了26项世界纪录。菜鸟也成为中国首个问鼎该评测系统的研究机构。

现在,菜鸟车辆路径规划算法已经应用于多项业务中。在车辆配送环节,车辆路径规划算法可以有效降低车辆使用数量和车辆行驶距离;在仓库内部拣选作业中,车辆路径规划算法可以降低拣选人员的行走距离。此外,车辆路径规划算法还可以帮助外卖配送员规划配送路线,从而提升客户体验、大幅度降低配送成本。以村淘配送为例:

车辆路径规划问题是运筹优化领域最经典的问题之一。以一家物流公司需要向1000个网点进行配送为例,其配送路径不计其数,如果能找到一条最高效的配送路径,将会大为提高物流效率,降低成本。

02菜鸟车辆路径规划引擎研发历程

阶段一:核心基础算法研发

在研发之初,菜鸟仓配智能化算法团队充分调研了VRP领域的相关学术论文和软件产品等,最终确定了以自适应大规模邻域搜索(Adaptive Large Neighborhood Search, ALNS)为核心算法进行算法引擎的建设。相对于其它算法,ALNS算法的优势包括:

1、算法框架易于拓展,除了求解标准的VRP之外,还能够求解VRPPD,MDVRP等变型问题;

2、相对于普通的Local Search类型的算法,ALNS在每一步搜索过程中能够探索更大的解空间;

3、ALNS算法在搜索过程中能够自适应地选择合适的算子,从而对于不同类型的问题数据能够有比较稳定的良好求解结果;

4、通过设计实现不同类型的算子,ALNS可以实现不同的搜索策略,从而便于算法的升级拓展。

ALNS算法的主要步骤为:

1、使用一定的规则构造一个初始解(即Initial过程);

2、基于算子的权重,选择此次迭代过程中使用的Ruin算子和Insert算子;

3、对此次迭代的初始解执行Ruin操作,即将部分已经被车辆服务的客户点删除,使初始解成为一个不可行解;

4、对步骤(3)获得的解执行Insert操作,即对于还没有被车辆服务的客户点,将其插入到解中,尽量获得一个可行解;

5、基于优化目标函数评估步骤(4)获得的新的解,并根据一定的策略决定是否接受新解;

6、判断是否达到终止条件。如果是,则终止计算,返回当前找到的最好解;否则,基于此轮计算中算子的表现,更新算子的权重,并返回到步骤(2)。

以ALNS算法为核心,菜鸟仓配智能化算法团队完成了第一版VRP优化引擎的研发。对比测试结果表明其求解效果和效率显著优于jsprit等国际上流行的开源VRP Solver。在此基础上,菜鸟仓配智能化算法团队还对引擎进行了服务化,从而更方便地服务于公司内外部用户。

阶段二:算法体系丰富与升级

为了更好地服务于公司内外部用户,菜鸟仓配智能化算法团队不断对VRP优化引擎的核心算法组件进行了丰富与升级。主要体现在以下几个方面:

1、完善功能:在原算法核心框架的基础上,增加了对Pickup and Delivery(车辆一边揽收一边派送)、Multi Trip(车辆多趟派送)等类型问题的支持;而且通过对实际业务问题的抽象,总结出了不同类型的优化目标方程(例如最小化阶梯定价的总成本、最小化配送时间等)以及约束条件(例如车辆行驶距离限制、车辆配送订单数限制、车辆跨区数限制等)。从而使求解引擎能够求解的问题更加全面广泛。

2、丰富算子:为了提升引擎的求解效果和稳定性,菜鸟仓配智能化算法团队还在VRP求解引擎中增加了更加丰富的优化算子,例如不同类型的局部搜索算子(例如Two-Opt, Three-Opt, Cross-Exchange等)、不同类型的中间结果接受策略(例如Greedy, Simulated Annealing等)。

3、提升效果:菜鸟仓配智能化算法团队还尝试了多种算法来提升引擎的求解效果,主要包括:

✦ Guided ejection search (GES):此算法通过不断尝试删减一辆车,并将此辆车服务的客户添加到其它车辆上,从而实现降低车辆的使用数。此算法在降低车辆数方面具有非常好的效果;

✦ Fast local search (FLS): 在搜索过程中,只搜索那些有希望改善当前解的的邻域空间,从而大幅降低搜索计算量,提升算法求解速度;

✦ Guided local serach (GLS): 在搜索过程中对局部最优解的某些特征施加惩罚项,从而改变搜索方向,避免陷入局部最优;

✦ Edge assembly crossover (EAX): 一种基于两个解生成一个新的解的方法,新生成的解能够很好的继承父代个体的空间结构;

✦ Branch-and-Price-Based Large Neighborhood Search:此算法将VRPTW问题分解为了Restricted Master Problem和Subproblem。其中在Restricted Master Problem中,基于一系列可行的路径,通过求解Set Partition问题来获得原问题的解;在Subproblem中,通过Tabu Search来搜索新的可行的路径;

✦ Path-Relink:此算法的核心思想为通过从initial solution到guiding solution的逐步移动,探索两个解之间的广阔的邻域,从而有可能发现更好的解;

✦ Hybrid Cluster and Heuristics:此算法是针对超大规模的问题而设计,首先通过合适的聚类算法对客户点进行聚类,从而将原问题分解为多个小规模的子问题,然后并行求解,最终将子问题的解组装成为原问题的解。

阶段三:算法并行化升级

对于大部分启发式算法而言,可以天然地通过并行化计算来提升搜索效率和效果,例如并行地计算评估多个相邻解的质量、向多个邻域方向进行搜索或者使用多种策略进行搜索等,甚至并行地使用多种算法进行搜索等。

所以为了进一步提升VRP引擎的求解质量,菜鸟仓配智能化算法团队对VRP引擎进行了并行化升级。

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

注:部分图片来源于网络,若涉及版权问题,请与我们联系

ChinaIT.com 网站文章仅限于提供更多信息,不代表本网站立场观点。如需转载,请注明来源 。转载之文章来源于互联网,如有版权问题,请与我们联系:content@chinait.com。

下载 ChinaIT.com APP,随时掌握最新IT资讯