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

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.