Travelling Salesman Problem for UAV Path Planning with Two Parallel Optimization Algorithms

摘要

To solve the travelling salesman problem (TSP) for unmanned aerial vehicle (UAV) path planning, we propose two parallel optimization algorithms. One is the improved genetic algorithm (IGA), and the other is the particle-swarm-optimization-based ant colony optimization algorithm (PSO-ACO). As an indispensable part of UAV cooperative mission assignment, the research of UAV path planning has attracted much attention of scholars. In this paper, according to the characteristics of UAV path planning, we firstly establish a corresponding multi-objective multi-constrained combinatorial optimization model-TSP. In the TSP model, the UAV is considered as the travelling salesman, and the mission target is regarded as the travelling city. Then, considering that TSP is a complex NP-hard problem, this paper carries out two optimization algorithms as IGA and PSO-ACO to solve the TSP model, which both can obtain effective and reasonable UAV path planning schemes. IGA is a kind of evolutionary algorithm with implicit parallel ability and global optimization ability. Through the rational selection of encoding mode and fitness function, and valid setting of selection operator, crossover operator and mutation operator, IGA can solve the TSP with great convergence. PSO-ACO is a swarm intelligence optimization algorithm with inherently parallel ability and self-organizing ability, which is perfect for solving TSP. Adopting the idea of particle optimization into ant colony optimization algorithm, ants in PSO-ACO system have the particle characteristics that can adjust the local optimal solution and global optimal solution after completing every single traversal. Finally, in the simulation part, based on the stochastic dynamic map, this paper builds the TSP model for UAV path planning. Through the comprehensive analyses of the optimization results of two proposed parallel optimization algorithms and one contrast approach, we can conclude that the proposed IGA and PSO-ACO algorithms are more rational and effective for solving UAV path planning problem compared with the contrast approach.