苏子美，董红斌

哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨 150001

无人机路径规划的应用领域正变得越来越广。在军事领域方面无人机可以在战场物资投放、作战资源调度等方面使用[1−5]，无人机参与作战可大量减少战争伤亡，大大提高作战效率与成功率。在民用方面使用无人机进行快递配送、救灾物资投放和喷洒田地[6]也成为新的目标，因此在此方面所应用的技术具有巨大的市场潜力。

无人机在以上方面应用所产生的问题都可以归结为无人机路径规划问题，这类问题是一个NP难问题(NP-hard problem)，目前使用进化算法可以在这类问题上得到很好的解决[7−8]。文献[2]针对该问题提出了两阶段策略，使用贪心算法与遗传算法作为一、二阶段进行优化；文献[5]使用了单目标进化算法应用于无人机追捕罪犯；文献[9]使用极端拥挤的NSGA-II(EC-NSGA-II)作为第一阶段，求得近似Pareto前沿的极端解作为多目标遗传算法的初始粒子；文献[10]将MOEA/D(基于分解的多目标优化)引入粒子群优化算法中以更好地平衡多个目标函数解；文献[11]将基于集的粒子群优化算法(S-PSO)和综合学习粒子群优化(CLPSO)引入无人机路径规划问题中，其中，使用多目标粒子群优化算法求得的解，其多样性好且收敛速度快，因此在无人机路径规划上表现会更加有前景[12−13]。

1 无人机路径规划问题

假设无人机飞行在足够高的上空可以忽略障碍且用户位置不变的条件下，无人机路径规划的多种问题都可以归结为带时间窗的车辆路径规划(vehicle routing problems with time window，VRPTW)问题。……