2023年IEEE TIV，GA-LNS算法+直升机救援调度，深度解析+性能实测-育师

1.摘要

本文研究多直升机、多往返任务的航空救援路径规划问题（ARRP），弥补了以往研究忽略实际救援流程与燃油消耗差异的不足。为此，本文构建了可模拟不同机型、补给方式、资源位置与灾害场景的时间域仿真模型。基于该模型，本文提出混合遗传算法与大邻域搜索方法的GA-LNS，通过距离贪心与载荷比策略有效避免局部最优。算法采用基于任务序列的染色体编码、单点交叉以及最差移除与首/尾插入等算子。

2.航空救援路线问题（ARRP）

ARRP 通过有向图建模，多架异构直升机需从不同机场出发执行三类救援任务（转运灾民、运送救援人员、运送物资），并满足各灾害点的任务需求。模型综合考虑直升机载荷、飞行时间、上下机时间、燃油消耗、加油行为及任务顺序等实际约束。目标是最小化机队整体救援完成时间。

3.GA-LNS算法

本文提出一种基于 GA 与 LNS 融合的启发式方法（GA-LNS），并结合程序化仿真进行求解。算法包含三阶段：首先利用仿真随机生成一批可行解作为 GA 的初始种群；随后执行包含选择、交叉、变异以及染色体预处理与修复的 GA 操作，通过距离贪心策略快速形成较优结构；由于该策略可能造成运力浪费，第三阶段引入基于载荷比策略的大邻域搜索（LNS），通过破坏—修复机制进行局部优化，以纠正容量利用不足的问题并提升整体解质量。

程序化仿真用于在时间域动态模拟直升机的任务执行过程，通过任务分配与状态转移两部分更新直升机的油量、载荷与位置等变量，并生成可行的初始解。任务分配采用距离贪心策略以加速收敛，但可能造成运力浪费，因此需在后续 LNS 优化中纠偏。仿真输出的染色体代表机队任务序列，由于任务可多次执行、染色体长度不一，后续 GA 会对其进行预处理与修复。

选择阶段采用轮盘赌确保高适应度个体被优先继承；由于染色体长度不一致，需通过填充None实现等长化后再进行单点交叉，以最大程度保留距离贪心策略形成的结构特征；变异通过交换基因位置提升局部搜索能力。交叉与变异后，PSCR 会移除无效任务、补充漏掉的任务并重新按时间域仿真评估个体适应度，确保解的可行性；若染色体导致燃油不足则判为不可行。

LNS作为局部算子，在部分世代对少量高适应度个体执行最差任务移除 + 首尾插入修复的操作，通过载荷比策略调整任务分配并借助 PSCR 评估更新，使解能够跳出距离贪心造成的局部最优与容量浪费。

4.结果展示

5.参考文献

[1] Cheng J, Gao Y, Tian Y, et al. GA-LNS optimization for helicopter rescue dispatch[J]. IEEE Transactions on Intelligent Vehicles, 2023, 8(7): 3898-3912.