A new evolutionary optimization algorithm with hybrid guidance mechanism for truck-multi drone delivery system
[ X ]
Tarih
2024
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Pergamon-Elsevier Science Ltd
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
Synchronization of the Traveling Salesman Problem with Drone (TSP-D) is one of the most complex NP-hard combinatorial routing problems in the literature. The speeds, capacities and optimization constraints of the truck-drone pair are different from each other. These differences lead to the search space of TSP-D having a high geometric complexity and a large number of local solution traps. Being able to avoid local solution traps in the search space of TSP-D and accurately converge to the global optimal solution is the main challenge for evolutionary search algorithms. The way to overcome this challenge is to dynamically adapt exploitation and exploration behaviors during the search process and maintain these two in a balanced manner depending on the geometric structure of TSP-D's search space. To overcome this challenge, research consisting of three steps was conducted in this article: (i) three different guide selection methods, namely greedy, random and FDB-score based, were used to provide exploitation, exploration and balanced search capabilities, (ii) by hybridizing these three methods at different rates, guide selection strategies with different search capabilities were developed, (iii) by associating these hybrid guide selection strategies with different stages of the search process, the guidance mechanism was given a dynamic behavioral ability. Thus, the Fitness-Distance Balance-based evolutionary search algorithm (FDB-EA) was designed to achieve a sustainable exploitation-exploration balance in the search space of TSP-D and stably avoid local solution traps. To test the performance of the FDB-EA, the number of delivery points was set to 30, 50, 60, 80, and 100 and compared with twenty-seven powerful and current competing algorithms. According to the non-parametric Wilcoxon pairwise comparison results, FDB-EA outperformed all competing algorithms in all five different TSP-D problems. According to the results obtained from the stability analysis, the success rates and calculation times of FDB-EA, EA and AGDE algorithms were 88.00% (6308.79 sec), 58.40% (7377.43 sec) and 13.460% (34664.19 sec) respectively.
Açıklama
Anahtar Kelimeler
Fitness-Distance Balance-based Evolutionary Algorithm (FDB-EA), TSP-D problem, Guide selection method, Stability analysis, Routing optimization
Kaynak
Expert Systems With Applications
WoS Q Değeri
Q1
Scopus Q Değeri
Q1
Cilt
245
