ccDNCA: A Dual-Neighborhood Search Based Dual-Population Coevolutionary Algorithm for Multi-UAV Task Allocation Problems With Complex Constraints

Solving the multi-UAV task allocation problem with complex constraints (MTAPCc) by means of the constrained multi-objective evolutionary algorithms (cMOEAs) is novel research in the field of Operation Research. Its advantages mainly consist of two aspects. One is that it can find feasible solutions that satisfy the constraints within an acceptable time. The other is that the obtained Pareto solution set can offer more options for decision-makers. This paper presents a dualneighborhood search based dual-population coevolutionary algorithm (ccDNCA), which can specifically solve the constrained multi-objective combinatorial optimization problems (cMCOPs) based on permutation encoding, including the MTAPCc. The dual-population coevolutionary framework and the multistrategy collaborative constraint handling method of ccDNCA can effectively improve the efficiency of constraint handling and the ability of finding better solutions. The dual-neighborhood alternating local search (DN-ALS) framework can effectively increase the proportion of feasible solutions during the evolution and enhance the quality of the final solution set. The strategy pool integrated with multiple local search strategies can push the search towards regions with better objective values and constraint values, while enhancing the generalization ability of ccDNCA. In the experimental part, by comprehensively comparing the solution results of ccDNCA with those of other advanced algorithms, it is demonstrated that ccDNCA has significant superiority when dealing with cMCOPs based on permutation encoding, such as the MTAPCc and the Vehicle Routing Problem with Time Window constraints (VRPTW).