2025年COR SCI2区，基于多种配送模式的无人机自主配送车辆路径问题，深度解析+性能实测

---

1.摘要

自动配送车辆（ADV）和无人机因其高效、环保和便捷性在最后一公里配送中受到了广泛关注。此外，ADV与无人机之间的协同配送十分复杂，而现有的大多数研究主要集中在卡车与无人机之间单一配送模式下的协同配送。因此，本文提出了一种针对由ADV和异质无人机组成、基于多种配送模式的无人配送系统的新的车辆路径问题。针对该问题构建了一个以最小化成本为目标的混合整数规划（MIP）模型，称为基于多种配送模式的无人机自主配送车辆路径问题（ADVRPD-MDM）。为求解该模型，本文设计了一种结合了12种特定邻域结构、随机变量邻域下降（RVND）机制和随机扰动策略的随机变量邻域搜索算法（RVNS）。通过改进的Solomon算例评估了各算子在应用中的效果，并验证了RVNS算法的有效性。

2.数学模型

本文关注在无人配送系统中，自动配送车辆（ADV）与无人机协同为不同需求的客户提供高效配送服务。整个系统以有向无环图建模，节点包括所有客户和两个仓库节点（起点和终点）。根据协作模式，无人机分为两类：

• 协同无人机：由ADV搭载，ADV到达客户节点时可发射或回收。协同无人机在满足载重与续航条件下，可一次为多个客户服务，且必须由同一台ADV发射和回收。无人机在ADV上可进行无线充电，直至再次发射；

• 并行无人机：可从仓库直接出发，独立完成配送任务后返回仓库，并可自动更换电池。

本文建立了一个以最小化总成本为目标的混合整数规划模型（MIP），用于解决基于多种配送模式的无人机自主配送车辆路径问题（ADVRPD-MDM），模型综合考虑服务、路径、载重、续航、时间和充电等六类约束。目标函数分为两部分：一是ADV、协同无人机和并行无人机在运输过程中产生的距离相关成本；二是配送服务中除运输费用外的固定成本（如管理、设施和人工费用）。模型的优化目标是最小化这两部分成本的总和，实现系统的经济高效运行。

3.RVNS算法

作为车辆路径问题（VRP）的扩展，ADVRPD-MDM问题由于引入了多架协同无人机和并行无人机，导致模型约束和求解难度大幅提升。为此，本文采用可变邻域搜索算法（VNS）来高效求解该问题。VNS算法具有结构简单、收敛性强、参数少、适合处理复杂离散问题等优势，并能够通过灵活切换邻域结构，在庞大的解空间中迅速找到高质量解。

解决方案表示

采用整数编码方法对问题进行建模，该编码分为三部分：第一部分为ADV的路线，用一串整数表示，数字顺序即为ADV的投递顺序；第二部分为协同无人机的路线，每行对应一架协同无人机，每一小段表示一次飞行，包括起飞节点、服务节点和回收节点；第三部分为并行无人机的路线，每一小段同样表示一次飞行，且其起飞和回收节点均为仓库。

初始解的构建

本文提出了一种基于整数编码的初始解构建方法，首先根据客户需求和无人机从仓库到客户节点的往返时间，将所有客户划分为两类：一类由并行无人机负责，另一类由ADV与协同无人机协作完成。对于并行无人机配送的客户，采用CW算法生成配送路径；对于需ADV和协同无人机协作的客户，则设计了一个两阶段算法：第一阶段利用CW算法为ADV生成初始路径，第二阶段通过贪心策略，在满足载重与续航约束的前提下，将合适的客户节点分配给协同无人机，优先选择能节省成本最多的任务插入协同无人机的配送路径，直至所有任务分配完成。最终，得到一条包含ADV、协同无人机及并行无人机的完整初始配送路径。

邻域算子

邻域算子的设计是RVNS算法中最重要的部分。根据操作阶段的不同，邻域算子分为两类：局部搜索算子和扰动（shaking）算子。其中，每一部分又包含ADV路径算子和ADV与无人机路径算子。ADV路径算子仅针对ADV的配送模式进行搜索，而ADV与无人机路径算子则在两种无人机配送模式与ADV配送模式之间进行交互式搜索。

• ADV重定位算子

根据影响范围的不同，重定位算子分为两种：内部重定位算子（intra-relocate operator）和外部重定位算子（inter-relocate operator）。N1为内部重定位算子，指的是将ADV路径中的某一客户节点插入到同一路径的其他位置。被重定位的客户节点又可分为两类：普通节点与起飞/回收节点。

N2为外部重定位算子，即将一个ADV路径中的客户节点插入到另一条ADV路径中。所选客户节点同样分为普通节点和起飞/回收节点。

• ADV交换算子

根据影响范围的不同，ADV交换算子分为两类：路内交换算子和路间交换算子。N3算子为路内交换算子，指的是在同一条ADV路径中交换两个客户节点的位置。该交换可分为三种类型：普通节点之间的交换、普通节点与发射或回收节点之间的交换，以及发射节点与回收节点之间的交换。

N4算子为路间交换算子，指的是选取不同ADV路径中的两个客户节点进行交换。该交换分为两种类型：普通节点之间的交换，以及包含发射或回收节点的交换。

还有其他算子，略。

4.结果展示

5.参考文献

[1] Kong J, Wang H, Xie M. Autonomous delivery vehicle routing problem with drones based on multiple delivery modes[J]. Computers & Operations Research, 2025, 179: 107032.

6.代码获取

xx

7.算法辅导·应用定制·读者交流