An Improved Strength Pareto Evolutionary Algorithm 2 with Adaptive Crossover Operator for Bi-Objective Distributed Unmanned Aerial Vehicle Delivery

Abstract

With the development of the e-commerce industry, using UAVs (unmanned aerial vehicles) to deliver goods has become more popular in transportation systems. This delivery method can reduce labor costs and improve the distribution efficiency, and UAVs can reach places that are difficult for humans to reach. Because some goods are perishable, the quality of the delivery will have an impact on the customer satisfaction. At the same time, the delivery time should also meet the needs of customers as much as possible. Therefore, this paper takes the distribution distance and customer satisfaction as the objective functions, establishes a bi-objective dynamic programming model, and proposes an improved SPEA2 (strength Pareto evolutionary algorithm 2). The improved algorithm introduces the local search strategy, on the basis of the original algorithm. It conducts a local search for the better non-dominated solutions obtained in each iteration. The new dominated solutions and non-dominated solutions are determined, and the crossover operator is improved, so that the local search ability is improved, on the basis of ensuring its global search ability. The numerical experiment results show that the improved algorithm achieves an excellent performance in three aspects: the Pareto front, generation distance, and spacing, and would have a high application value in UAV cargo delivery and other MOPs (multi-objective optimization problems). The average spacing value of the improved algorithm is more than 20% smaller than SPEA2 + SDE (strength Pareto evolution algorithm 2–shift-based density estimation), which is the second-best algorithm. In the comparison of the average generation distance value, this number reaches 30%.

Keywords

• UAV delivery
• multi-objective optimization
• strength Pareto
• bi-objective
• local search