Route Planning for UAVs : A Column Generation Approach

We study an integer optimization problem that describes the route planning for UAVs (unmanned aerial vehicles). The aim in the route planning problem is to minimize the number of UAVs that monitors the locations in a region within specific visiting times. The challenge is to find travelling salesman routes that satisfy the criteria for how often the locations should be monitored. The main purpose of this work is to apply column generation to this route planning problem, based on three strategies. The interest in this approach is to evaluate how effective each strategy is to solve the problem and then conclude its advantages and disadvantages. The strategies that are being presented in this work, are exact column generation, heuristic column generation and ad hoc column generation. We present algorithms for each strategy and study its behavior on different problem instances. The implementations have been performed in the programming language Python with the use of the optimization solver Gurobi.