2024年ESWA SCI1区TOP，带有机器人站点的无人机辅助车辆路径规划问题，深度解析+性能实测

1.摘要

本文提出了带有机器人站点的无人机辅助车辆路径规划问题（VRPD-RS），并将其建模为混合整数线性规划（MILP）问题，分析了卡车、无人机和机器人对配送车队的影响。针对该问题，本文提出了广义变邻域搜索算法（GVNS），并与模拟退火算法（SA）进行了对比。结果表明，GVNS在小规模实例中与求解器最优解接近，在大规模实例中提升了21.5%的最小完成时间和8.0%的运营成本，且在计算效率上优于SA。

2.带有机器人站点的无人机辅助车辆路径规划问题

本文提出了带有机器人站点的无人机辅助车辆路径规划问题（VRPD-RS），该问题扩展了传统的TSP-D-RS模型，考虑了多个卡车与无人机的协同工作，并引入机器人站点辅助配送。目标是最小化最小完成时间或运营成本。论文采用混合整数线性规划模型（MILP）进行求解，并提出了基于变量邻域搜索（VNS）的元启发式算法。算法考虑了多种约束，包括卡车、无人机、机器人之间的同步问题。

3.求解方法

广义变邻域搜索（GVNS）

GVNS通过变换邻域结构，结合卡车、无人机和机器人配送，进行局部搜索优化。算法首先构建初始解，然后通过一系列摇动算子生成随机解，并应用随机化邻域搜索（RVND）改进解。若找到更优解，则更新当前解并重置改进计数器。算法通过多次摇动和邻域搜索，探索解空间并在设定的最大迭代次数或运行时间内寻找最优解。

构造式启发式算法

构造式启发式算法包括三个阶段：构建VRP解决方案、插入无人机操作和插入机器人操作，通过k-means聚类和最便宜插入算法构建卡车路线，然后依照目标函数依次插入无人机和机器人。

随机变量邻域下降搜索（RVND）

RVND通过随机化邻域集的顺序进行局部搜索，探索多个邻域操作以改进VRPD-RS解。与VND启发式不同，RVND在每次改进时都会重新随机化邻域顺序。算法开始时初始化邻域集并进行探索，每次找到改进解时返回到初始状态。若新解改进了当前解，则更新解并重置邻域搜索；否则，继续尝试下一个邻域操作。

搜索算子

GVNS搜索算子包括2-opt、交换、转移到卡车、转移到无人机和转移到机器人等五种算法算子。算法生成随机邻域解，并应用这些算子来探索解空间。每个算子执行特定的搬移或交换操作，生成不同的邻域解。

4.结果展示

5.参考文献

[1] Morim A, Campuzano G, Amorim P, et al. The drone-assisted vehicle routing problem with robot stations[J]. Expert Systems with Applications, 2024, 238: 121741.

6.代码获取

xx

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

xx