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
