CAJ | 학술논문

带时间窗的多无人机（Unmanned Aerial Vehicles，简称UAV）航迹规划问题是一类重要的NP-Hard问题，相关启发式算法研究一直是该问题的研究重点和难点。建立了问题的UAV流模型，并提出了一种两阶段启发式算法用于问题求解。算法的第一阶段提出了一种基于“最迟完成服务优先”规则的航迹构造算法，用于获取问题的初始解；第二阶段利用模拟退火算法对初始解进行改进。最后基于Solomon Benchmark数据集对算法进行了测试，实验结果表明该启发式算法可以有效地求解带时间窗的多UAV航迹规划问题。
대시간창적다무인궤（Unmanned Aerial Vehicles，간칭UAV）항적규화문제시일류중요적NP-Hard문제，상관계발식산법연구일직시해문제적연구중점화난점。건립료문제적UAV류모형，병제출료일충량계단계발식산법용우문제구해。산법적제일계단제출료일충기우“최지완성복무우선”규칙적항적구조산법，용우획취문제적초시해；제이계단이용모의퇴화산법대초시해진행개진。최후기우Solomon Benchmark수거집대산법진행료측시，실험결과표명해계발식산법가이유효지구해대시간창적다UAV항적규화문제。
Path planning of Multi-UAV with time windows is a class of important NP-Hard problems,and the researches on the heuristic methods of the problem are always the key point. In this paper,a UAV-flow model is built,and a two-stage heuristic method is proposed to solve it. In the first phase,a path construction heuristic based on “latest-service-finished-first”is proposed to gain the initial solution,and then the simulated annealing algorithm is used to improve it. Finally the heuristic method is tested on the Solomon Benchmark instances,and the experiment results showed that the method can solve the problem efficiently.