Biobjective route planning for a fleet of UAVs: Exact and heuristic approaches

Creative Commons License

Biskin B., TEZCANER ÖZTÜRK D., TUNCER ŞAKAR C.

JOURNAL OF THE FACULTY OF ENGINEERING AND ARCHITECTURE OF GAZI UNIVERSITY, cilt.38, sa.4, ss.2167-2178, 2023 (SCI-Expanded) identifier identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 38 Sayı: 4
  • Basım Tarihi: 2023
  • Doi Numarası: 10.17341/gazimmfd.990791
  • Dergi Adı: JOURNAL OF THE FACULTY OF ENGINEERING AND ARCHITECTURE OF GAZI UNIVERSITY
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Art Source, Compendex, TR DİZİN (ULAKBİM)
  • Sayfa Sayıları: ss.2167-2178
  • Anahtar Kelimeler: Unmanned aerial vehicles, Route planning, Multiobjective optimization, Genetic algorithm
  • Gazi Üniversitesi Adresli: Hayır

Özet

Purpose: This study aims to develop time-efficient and computationally easy methods that find or approximate the nondominated frontier of the UAV route planning problem considered. Theory and Methods: A mixed integer linear programming model is developed that finds routes of the UAVs by optimizing the two objectives. Since the computational burden of the mathematical model increases significantly as the problem size increases, a genetic algorithm (GA_fIHA) that approximates the nondominated frontier is also established. Results: Three problem instances with varying numbers of UAVs and targets are designed, and their nondominated frontiers are generated and approximated using the epsilon-constraint method and GA_fIHA, respectively. GA_fIHA results in good approximations of the nondominated frontier with an average hypervolume indicator value of 97.38% for 15 different runs. Additionally, it runs in approximately 1.7% of the duration of the exact method. Conclusion: The proposed genetic algorithm GA_fIHA is time-efficient and approximates the nondominated frontier well. Its computational requirements do not increase substantially as the problem size increases. Considering its computational efficiency and approximation quality, GA_fIHA can be used in practical operations succesfully.