Research on UAV Delivery Route Optimization Based on Improved Adaptive Genetic Algorithm

Zhe Bian

《Frontiers in Economics and Management》 2卷3期 (2021/03) Pp. 290-296

https://doi.org/10.6981/FEM.202103_2(3).0036

摘要

Based on the background of the rapid spread of COVID-19, in order to block the path of human-to-human transmission of the virus, the use of drones for ＂last mile＂ end delivery can effectively solve the problem of material supply during the epidemic isolation stage. This paper considers the range and load constraints of UAVs, establishes a distribution route optimization model with the shortest total delivery time as the goal, and designs a symbolic encoding method that conforms to the model to generate chromosomes according to the characteristics of taking first and then sending in the distribution process. The adaptive crossover and mutation probability is designed to improve the optimization ability of the genetic algorithm, and finally the simulation test is carried out. The results show that compared with the standard genetic algorithm, the improved adaptive genetic algorithm is more efficient, better quality, and has better solving ability in solving such problems.

關鍵字

Instant Delivery ； UAV ； Path Optimization ； Genetic Algorithm

參考文獻

D. Schermer: Integration of Drones in Last-Mile Delivery: The Vehicle Routing Problem with Drones (Operations Research Proceedings, Cham 2018), p.219-551.

David. Sacramento, David. Pisinger, Stefan. Ropke: An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones, Transportation Research Part C: Emerging Technologies, Vol.102(2019), p.289-315.

Mauro. Dell Amico, Roberto. Montemanni, Stefano. Novellani: Matheuristic algorithms for the parallel drone scheduling traveling salesman problem, Annals of Operations Research, Vol.289 (2020), p.1-16.

Wang Z, Sheu J B: Vehicle routing problem with drones, Transportation research part B: methodological, Vol.38(2019) No.2, p.350-364.

Mauro. Dell Amico, Roberto. Montemanni, Stefano. Novellani: Drone-assisted deliveries: new formulations for the flying sidekick traveling salesman problem, Optimization Letters, p.1-32.