Multi-objective route planning of an unmanned air vehicle in continuous terrain: An exact and an approximation algorithm

DAŞDEMİR E., Köksalan M., TEZCANER ÖZTÜRK D.

European Journal of Operational Research, vol.322, no.3, pp.960-977, 2025 (SCI-Expanded) identifier

  • Publication Type: Article / Article
  • Volume: 322 Issue: 3
  • Publication Date: 2025
  • Doi Number: 10.1016/j.ejor.2024.11.015
  • Journal Name: European Journal of Operational Research
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, International Bibliography of Social Sciences, ABI/INFORM, Applied Science & Technology Source, Business Source Elite, Business Source Premier, Compendex, Computer & Applied Sciences, EconLit, INSPEC, Public Affairs Index, zbMATH, Civil Engineering Abstracts
  • Page Numbers: pp.960-977
  • Keywords: Continuous Terrain, Multiple Objective Programming, Route Planning, Unmanned Aerial Vehicles
  • Middle East Technical University Affiliated: Yes

Abstract

Unmanned Aerial Vehicles (UAVs) are widely used for military and civilian purposes. Effective route planning is an important component of their successful missions. In this study, we address the route planning problem of a UAV tasked with collecting information from various target locations in a protected terrain. We consider multiple targets, three objectives, and time-dependent information availability. Modeling the movement of UAVs in a continuous terrain in the presence of multiple objectives is complex. Conflicting objectives typically lead to a continuum of efficient trajectory options between two targets. We formulate the routing problem as a mixed-integer programming (MIP) model that captures the movement in the continuous terrain. We demonstrate the superiority of the continuous terrain formulation over the simplified discretized terrain formulation. We also develop an approximation algorithm that reduces the computational requirements of the MIP model substantially while ensuring a desired level of precision.