引言
无人机(UAV)在末端配送、巡检及应急响应中发挥着日益重要的作用(Das, Sewani, Wang, Tiwari, 2021, Otto, Agatz, Campbell, Golden, Pesch, 2018, Rejeb, Rejeb, Zailani, 2021, Wang, Liu, Li, 2023, Zhou, Ye, He, 2025)。相应的规划问题通常被建模为无人机路径问题(UAVRP)(Li, Chen, Wang, Bai, 2021, Yuan, Zhu, Li, Huang, Wu, 2021):续航能力和载重能力主导可行域,且车辆不受道路网络约束(Agatz, Bouman, Schmidt, 2018, Gerdes, Z?pfel, 2022, Song, Li, 2019)。该建模设定在多个方面与传统车辆路径问题有所不同(Li, Yan, Yu, Li, & Liu, 2024)。
尽管无人机部署具有明显的运营优势,机队构成仍是主要关切。早期研究通常关注同质机队;将重型无人机分配给小包裹会造成载重和能源浪费(Ghassemi & Chowdhary, 2020)。越来越多的文献因此研究了异构机队,其成员在载重、速度和续航方面存在差异(Bhuiyan, Walker, Roni, Ahmed, 2024, Chen, Wang, Lian, Leng, 2024, Murray, Raj, 2020, Wang, Mansouri, Sentouh, 2024, Wen, Wu, Li, Wang, 2024)。
这一选择将简单的分配问题("哪架无人机执行哪项任务")转变为一个耦合的匹配与调度问题:哪一类型适合哪项任务,以何种顺序执行(Chen et al., 2024)。额外的组合代价通常被接受,因为混合机队可以实现资源与需求的匹配;算法则必须在该更大的决策空间中导航。
本文针对该耦合的匹配与调度问题展开研究。以下三项贡献的范围设定使得相关工作部分阐述差距、结论部分报告实验发现;它们不是同一段落的三次重述。
- 1.
针对HUAV-MTDP的混合整数线性规划模型,联合编码分配、车辆-任务匹配及多趟次路径规划,精确求解器可在小规模实例上求解。
- 2.
完全规格化的两阶段求解器(解码器、排序重组、信息传递映射)。提供完整规格说明以保障可复现性。在中规模实例(,30个种子)上,混合算法未超越代际遗传算法;因此,这些机制不作为排序搜索算子提出。
- 3.
等预算对比协议:九条搜索分支、四种经典交叉算子、小规模n上的Gurobi/HiGHS求解器及三层统计方法,全部基于同一染色体表示和同一解码器。第5节报告该对比结果。
本文其余部分组织如下。第2节回顾相关工作并阐述建模与算法差距。第3节将HUAV-MTDP建模为混合整数线性规划并分离非凸条件。第4节规格化两阶段算法、共享解码器、信息传递桥接和重组算子。第5节报告实验协议与结果。第6节总结全文。