摘要
本文提出了带有机器人站点的无人机辅助车辆路径规划问题（VRPD-RS），并将其建模为混合整数线性规划（MILP）问题，分析了卡车、无人机和机器人对配送车队的影响。针对该问题，本文提出了广义变邻域搜索算法（GVNS），并与模拟退火算法（SA）进行了对比。结果表明，GVNS 在小规模实例中与求解器最优解接近，在大规模实例中提升了 21.5% 的最小完成时间和 8.0% 的运营成本，且在计算效率上优于 SA。
问题定义
本文提出了带有机器人站点的无人机辅助车辆路径规划问题（VRPD-RS），该问题扩展了传统的 TSP-D-RS 模型，考虑了多个卡车与无人机的协同工作，并引入机器人站点辅助配送。目标是最小化最小完成时间或运营成本。论文采用混合整数线性规划模型（MILP）进行求解，并提出了基于变量邻域搜索（VNS）的元启发式算法。算法考虑了多种约束，包括卡车、无人机、机器人之间的同步问题。
求解方法
广义变邻域搜索（GVNS）
GVNS 通过变换邻域结构，结合卡车、无人机和机器人配送，进行局部搜索优化。算法首先构建初始解，然后通过一系列摇动算子生成随机解，并应用随机化邻域搜索（RVND）改进解。若找到更优解，则更新当前解并重置改进计数器。算法通过多次摇动和邻域搜索，探索解空间并在设定的最大迭代次数或运行时间内寻找最优解。
构造式启发式算法
构造式启发式算法包括三个阶段：构建 VRP 解决方案、插入无人机操作和插入机器人操作，通过 k-means 聚类和最便宜插入算法构建卡车路线，然后依照目标函数依次插入无人机和机器人。
随机变量邻域下降搜索（RVND）
RVND 通过随机化邻域集的顺序进行局部搜索，探索多个邻域操作以改进 VRPD-RS 解。与 VND 启发式不同，RVND 在每次改进时都会重新随机化邻域顺序。算法开始时初始化邻域集并进行探索，每次找到改进解时返回到初始状态。若新解改进了当前解，则更新解并重置邻域搜索；否则，继续尝试下一个邻域操作。
搜索算子
GVNS 搜索算子包括 2-opt、交换、转移到卡车、转移到无人机和转移到机器人等五种算法算子。算法生成随机邻域解，并应用这些算子来探索解空间。每个算子执行特定的搬移或交换操作，生成不同的邻域解。
实验结果
