Solving location and routing problem for UAVs

- A variant of LRP is introduced to optimize location and routing of UAV fleet.
- Problem is characterized by a prize collecting objective function.
- An ant colony optimization metaheuristic is developed to solve the problem.
- Most instances are found difficult to solve optimally using a commercial solver.
- Proposed metaheuristic can find close to the best known solution in a short time.

Unmanned Aerial Vehicles (UAVs) are used increasingly in military and civil operations. Efficiency in utilization of those vehicles is a great challenge for the practitioners. We address the problem of locating and routing of small UAVs at tactical level with a specific objective function. We formulate this problem as an integer linear program (ILP) with the aim of maximization of the total score collected from visited interest points by flight routes of UAVs. Those routes are originated from assigned base stations that are determined simultaneously along with the visit order of interest points for each route. We also develop a novel ant colony optimization metaheuristic approach which is specifically designed for the introduced combinatorial problem. We perform a computational experiment using a commercial ILP solver and implementation of the proposed heuristic. Most instances are found difficult to solve optimally while our metaheuristic can find the best known or close to the best known solution in a short time.