Multi-Objective Emergency Path Planning Based on Improved Nondominant Sorting Genetic Algorithm

Y B. Yuan

doi:10.3390/sym17111818

2025-10-29

Y B. Yuan

Hang Xu *

Cuiyong Tang

DOI：10.3390/sym17111818

原文链接

原文求助

摘要

En 中文

Three-dimensional path planning in emergency logistics is a complex optimization problem, particularly challenging because it requires considering conflicting objectives such as flight time, energy consumption, and obstacle avoidance. Unlike most urban logistics research, this study examines emergency delivery path planning in mountainous environments during natural disasters. One of the most effective approaches to this problem is to employ multi-objective evolutionary algorithms. However, while multi-objective genetic algorithms can handle multiple conflicting objectives, they struggle when dealing with complex constraints. This paper proposes a multi-objective genetic optimization method, Adaptive Crossover-Mutation Multi-Objective Genetic Optimization (ACM-NSGA-II), based on the classic NSGA-II framework. Inspired by the principle of symmetry, this method dynamically adjusts the mutation and crossover rates based on population diversity to maintain a balanced exploration-exploitation trade-off. When population diversity is low, the mutation rate is increased to promote exploration of the solution space; when population diversity is high, the crossover rate is increased to promote better information exchange. The algorithm maintains symmetry by gradually adjusting the step size, balancing adaptability and stability. To address the obstacle avoidance problem, we introduced a dynamic path repair strategy that respects the symmetry of no-fly zone boundaries and terrain features, ensuring the safety and efficiency of Unmanned Aerial Vehicles. This algorithm jointly optimizes three objectives: safety cost, flight time, and energy consumption. The algorithm was tested in a mountainous environment model simulating a remote area. In experiments, ACM-NSGA-II was compared with several mainstream evolutionary algorithms. The Pareto set and hypervolume metrics of each method were recorded and statistically analyzed at a 5% significance level. The results show that ACM-NSGA-II outperforms the baseline algorithms in terms of diversity, convergence, and feasibility. Specifically, compared with the traditional NSGA-II, ACM-NSGA-II improved the average hypervolume metric by 53.39% and reduced the average flight time by 24.26%. ACM-NSGA-II also demonstrated significant advantages over other popular standard algorithms. Experimental results show that it can effectively solve the path planning challenge of emergency logistics Unmanned Aerial Vehicles in mountainous environments.

Keyword:

emergency delivery

adaptive crossover and mutation

multi-objective genetic algorithm

three-dimensional path planning

unmanned aerial vehicle

mountainous environments