Â鶹APP

Route planning for unmanned aerial vehicles (UAVs) in reconnaissance missions, such as post-disaster search and rescue, wildfire monitoring, and precision agriculture, requires selecting targets and determining the order to visit them, subject to limited flight time and energy. Unlike classical routing problems with static profits, targets in these missions carry time-dependent information: the decaying survival probability of a disaster victim, crop imaging requiring a specific solar window, or a wildfire zone whose monitoring value rises as fire approaches. This time dependence introduces a critical speed trade-off between time and energy constraints.

 

We formulate this problem as an extension of the Orienteering Problem with Time Windows (OPTW) that incorporates time-dependent information functions and explicit energy constraints. We show that the resulting non-linear optimization problem can be reformulated as a mixed-integer second-order cone program (SOCP) which linearizes the energy function. For larger instances, we develop a metaheuristic in which each candidate tour is evaluated by solving a continuous SOCP for optimal speeds, embedded within iterated local search with tabu-based perturbation. We calibrate well-known Solomon and Gehring-Homberger benchmarks to the specifications of a real-world drone. Computational experiments investigate time-dependent information regimes, energy sensitivity, the value of loitering, and the gap between exact and heuristic solutions.

This is joint work with Melis Boran and Mustafa Tural.