菜鸟驿站无人配送车物流路径规划算法实证研究

2022-02-15泸州职业技术学院人工智能与大数据学院四川泸州646000

物流科技 2022年16期

汪洋，孙剑（泸州职业技术学院人工智能与大数据学院，四川泸州 646000）

0 引言

菜鸟车辆路径规划算法[1]是基于满足多网点多线路不同车型的复杂性配送场景而研发的，是菜鸟网络自主研发的车辆路径优化算法，在技术上融合了大规模邻域搜索、超启发式算法、基因算法、分布式并行化和增强学习；在公开数据集上，该算法已全面超过广泛使用的开源产品Jsprit，在全球最权威的车辆路径问题（Vehicle Routing Problem, VRP）评测系统中创造了多项世界纪录。

菜鸟车辆路径规划算法已经应用于多项业务中。在车辆配送环节，车辆路径规划算法可以有效减少车辆使用数量和缩短车辆行驶距离；在仓库内部挑拣作业中，车辆路径规划算法可以缩短拣选人员的行走距离；在末端“最后一公里”校园配送中，车辆路径规划算法可以帮助无人配送车“小蛮驴”选择最优配送路线，有效缩短了车辆行驶距离，缩短了配送时间。

1 菜鸟车辆路径规划算法

1.1 车辆路径规划问题

车辆路径规划问题[2]是物流领域最经典的优化问题之一，具有极大的学术研究意义和实际应用价值。在此问题中，有若干个客户对某种货物有一定量的需求，车辆可以从仓库取货之后配送到客户手中。客户点与仓库点之间组成了一个配送网络，车辆可以在此网络中移动而完成配送任务。在求解此问题的过程中，需要优化的决策变量为每个客户的配送任务应该分配到哪一辆车上，以及每辆车完成客户配送任务的先后顺序，优化目标为最小化使用的车辆数和车辆总行驶距离。

以i，j表示配送网络中的节点（i，j∈{0，1，2,…，N})，其中0表示仓库点，其他表示客户点，以k表示车辆（k∈{1，2，…，K}），xijk为决策变量，表示车辆k是否从i点行驶到j点，则标准的车辆路径规划问题[3]可以使用以下数据规划形式描述，如公式（1）所示。

1.2 经典求解算法

车辆路径规划问题是典型的NP-hard问题，学术界和工业界对此类问题的优化算法的探索已经持续了几十年[4]。已有的经典求解算法可以分为精确解算法和启发式算法两大类。

在精确解算法方面，最基本的方法为分支定界算法[5]，虽然其能够从理论上保证在有限时间内获得最优解，但是在实际计算中存在计算耗时巨大的情况。为了提高求解效率，研究者们先后提出了多种Branch-and-Cut方法，大幅缩短了算法的求解时间。但是对于实际应用中较大规模的问题而言（例如超过200个点的问题），精确解算法依然无法能够在合理的时间内完成计算。

启发式算法[6]的思想为通过一系列启发式的规则来构造和改变解，从而逐步提升解的质量。对于VRP而言，较为经典的启发式算法为Clarke-Wright算法等。

1.3 菜鸟网络的车辆路径规划引擎

1.3.1 ALNS算法

菜鸟仓配智能化算法团队首先确定了以自适应大规模邻域搜索（Adaptive Large Neighborhood Search, ALNS）为核心算法进行算法引擎的建设。ALNS算法的优势有以下几点：算法框架易于拓展，除了求解标准的VRP之外，还能够求解VRPPD、MDVRP等变型问题；相对于普通的Local Search类型的算法，ALNS在每一步搜索过程中能够探索更大的解空间；ALNS算法在搜索过程中能够自适应地选择合适的算子，从而对于不同类型的问题数据有比较稳定的良好求解结果；通过设计实现不同类型的算子，ALNS可以实现不同的搜索策略，从而便于算法的升级拓展。

1.3.2 ALNS算法体系的丰富与升级

ALNS核心算法确定后，菜鸟仓配智能化算法团队不断对VRP优化引擎的核心算法组件进行丰富与升级，主要包括：a.完善功能：在原算法核心框架的基础上，增加了对车辆一边揽收一边派送(Pickup and Delivery)、车辆多趟派送（Multi Trip）等类型问题的支持；而且通过对实际业务问题的抽象，总结出了不同类型的优化目标方程（例如最小化阶梯定价的总成本、最小化配送时间等）以及约束条件（例如车辆行驶距离限制、车辆配送订单数限制、车辆跨区数限制等），从而使求解引擎能够求解的问题更加全面广泛。b.丰富算子：为了提升引擎的求解效果和稳定性，在VRP求解引擎中增加了更加丰富的优化算子，例如不同类型的局部搜索算子（例如Two-Opt，Three-Opt， Cross-Exchange等）、不同类型的中间结果接受策略（例如Greedy，Simulated Annealing等）。

1.3.3 ALNS算法并行化升级

对于大部分启发式算法而言，可以自然通过并行化计算来提升搜索效率和效果，例如并行计算评估多个相邻解的质量、向多个邻域方向搜索或者使用多种策略搜索等，甚至并行使用多种算法进行搜索等。所以为了进一步提升VRP引擎的求解质量，菜鸟仓配智能化算法团队对VRP引擎进行了并行化升级。在此过程中，先后研发实现了三套并行化算法架构，分别是Population Island，Parallel Memetic，Central Pool等。

1.4 菜鸟车辆路径规划算法应用评价

2018年9月，菜鸟仓配智能化算法团队研发的车辆路径规划算法首次获得了比世界纪录更好的结果，并经过了平台的验证。2018—2022年期间菜鸟智能路径规划算法已陆续打破60余项VRPTW和PDPTW计算模型的世界纪录。这标志着菜鸟在这项领域的技术进入了世界顶尖水平，为菜鸟赢得了巨大的技术影响力。

菜鸟研发的车辆路径规划算法应用于菜鸟无人物流车“小蛮驴”后，大幅提升了车辆的环境精细化理解能力，使车辆能够识别“厘米级”障碍物。比如车辆在行驶途中遇到临时拉起的警戒线，即便线宽仅有3厘米，物流车也能轻松识别并绕道而行。目前菜鸟无人物流车“小蛮驴”已在国内多个高校实现L4级别的日常运营，为消费者“无接触配送”快递。包裹收取时间从常规的2小时缩短到30分钟左右。

2 算法实证研究

2.1 实证研究对象

2.1.1 泸州职业技术学院菜鸟驿站

泸州职业技术学院菜鸟驿站是由泸州职业技术学院和阿里巴巴校企合作、统一规划打造的生产性实训基地，提供收件、派件、客服、代理记账等多个实习实训岗位，为物流管理等相关专业学生提供真实实训环境，提高学生的实践技能。目前该菜鸟驿站已拥有人工货架50个、智能柜10个、无人配送物流车“小蛮驴”3辆，服务于全校近2万名师生。据统计，目前该菜鸟驿站全年快递单量已超过200万件，平均每天快递单量超过5 000件。2021年，泸州职业技术学院菜鸟驿站成功入选“全国百强标杆站点”，荣获2021年度“全国好服务标杆站点”称号，成为全国首批达成4A好服务的校企站点。

2.1.2 菜鸟无人配送车“小蛮驴”

菜鸟已在全国300所高校校园中部署了无人配送物流车“小蛮驴”，执行配送任务的无人车已接近600 辆，成为全球较大的一支快递无人车队。目前泸州职业技术学院菜鸟驿站拥有3辆无人配送物流车“小蛮驴”，如图1所示。行驶在校园道路上的“小蛮驴”均搭载了菜鸟自主研发的最先进的车辆路径规划算法，实现了L4 级无人驾驶，可以根据情景自动生成最优配送路线，并将包裹准确派送到目的地（比如学生宿舍楼或教师办公楼）。

图1 行驶在校园中的菜鸟无人物流车“小蛮驴”

消费者通过使用支付宝“菜鸟”小程序，选择“无人车上门取件”并填写相关信息即可完成无人车预约服务。无人配送物流车“小蛮驴”可以每天在工作时间内不间断循环往复地完成“预约、装件、出发、返回”等任务，一天内每辆无人车可以跑近100公里，最多派送500件快递。通过无人车派送可以缓解菜鸟驿站库容压力，提升用户取件体验，让离驿站较远的同学在楼下就能取件。新冠疫情期间，还可以缓解同学们到菜鸟驿站取件造成聚集的压力。

2.1.3 泸州职业技术学院校园整体布局

泸州职业技术学院目前占地面积1 504亩，建筑总面积60万平方米，整个校园整体布局呈典型的“日”字型结构，道路属于典型的棋盘式布局，如图2所示。校园用地划分较为整齐，有利于建筑布置，适合各类型车辆在其中穿梭行驶。校园中不同建筑物间点对点的直达行驶路线往往有多条。

图2 泸州职业技术学院校园布局图

2.2 实证研究目的

由于无人配送物流车“小蛮驴”搭载的菜鸟车辆路径规划算法不开源，无法获取到源代码，如何凭借现有条件在校园中验证该算法的有效性是本文开展实证研究的重点。根据查阅文献得知，目前尚未有人针对菜鸟在高校投放的无人车选择最优配送路线的车辆路径规划算法开展实证研究。我们通过设计对比实验，在泸州职业技术学院校园内开展菜鸟车辆路径规划算法的实证研究，得出的结论可以有力证明菜鸟车辆路径规划算法的有效性，填补了该算法实证的相关空白。

3 对比实验

3.1 对比实验设计

本文采用常见的“黑盒测试”方式来设计对比实验。通过设置“出发地—目的地”，观察、测算无人车“小蛮驴”选取的点对点派送路径，即视为车辆路径规划算法经过计算得出的“最优选择路径”。以“点对点”其他派送路径为实验参照对象组，参照对象组实验车辆可以选择跟“小蛮驴”相同行驶速度的电动自行车代替。选取“派送时间”作为对比实验中不同派送路径的评价指标。

以泸州职业技术学院综合楼坐班教师小王需要使用无人车“小蛮驴”派送快递为实验模拟场景，“出发地—目的地”即为“菜鸟驿站—综合楼”。通过提前观察，发现从菜鸟驿站到达综合楼，可以有4条路线供选择，如表1所示。小王老师通过“菜鸟”小程序，选择“无人车上门取件”后，通过观察发现“小蛮驴”选取的是路线②作为车辆配送行驶路线。

表1 “菜鸟驿站—综合楼”可供选择配送路径

3.2 对比实验结果

首先通过观察、计时测试了菜鸟物流无人车“小蛮驴”在正常状态下行驶的平均速度为2.43m/s。首先测试菜鸟物流无人车“小蛮驴”在行驶路径②状态下花费的时间，然后选取电动自行车，给予车辆同样2.43m/s的配速用以测试行驶路径①③④状态下花费的时间。为了尽可能确保测试得到的车辆行驶花费时间的准确性，将每条路径的行驶测试次数设定为10次，然后求取10次结果的平均值，从而得到每条路径的平均花费时间，对比实验结果如表2所示。