The unmanned aerial vehicle (UAV) has drawn increasing attention in recent years, especially in executing tasks such as natural disaster rescue and detection, and battlefield cooperative operations. Task assignment and path planning for multiple UAVs in the above scenarios are essential for successful mission execution. But, effectively balancing tasks to better excavate the potential of UAVs remains a challenge, as well as efficiently generating feasible solutions from the current one in constrained explosive solution spaces with the increase in the scale of optimization problems. This paper proposes an efficient approach for task assignment and path planning with the objective of balancing the tasks among UAVs and achieving satisfactory temporal resolutions. To be specific, we add virtual nodes according to the number of UAVs to the original model of the vehicle routing problem (VRP), thus make it easier to form a solution suitable for heuristic algorithms. Besides, the concept of the universal distance matrix is proposed to transform the temporal constraints to spatial constraints and simplify the programming model. Then, a Swap-and-Judge Simulated Annealing (SJSA) algorithm is therefore proposed to improve the efficiency of generating feasible neighboring solutions. Extensive experimental and comparative studies on different scenarios demonstrate the efficiency of the proposed algorithm compared with the exact algorithm and meta-heuristic algorithms. The results also inspire us about the characteristics of a population-based algorithm in solving combinatorial discrete optimization problems.

Unmanned aerial vehicle (UAV) path planning is crucial in UAV mission fulfillment, with the aim of finding a satisfactory path within affordable time and moderate computation resources. The problem is challenging due to the complexity of the flight environment, especially in three-dimensional scenarios with obstacles. To solve the problem, a hybrid differential symbiotic organisms search (HDSOS) algorithm is proposed by combining the mutation strategy of differential evolution (DE) with the modified strategies of symbiotic organism search (SOS). The proposed algorithm preserves the local search capability of SOS, and at the same time has impressive global search ability. The concept of traction function is put forward and used to improve the efficiency. Moreover, a perturbation strategy is adopted to further enhance the robustness of the algorithm. Extensive simulation experiments and comparative study in two-dimensional and three-dimensional scenarios show the superiority of the proposed algorithm compared with particle swarm optimization (PSO), DE, and SOS algorithm.