Optimization of drone routing for humanitarian applications.

Abstract

The present thesis aims to determine if drones could effectively replace \textit{in-situ} inspection for the collect of information in humanitarian crisis situations. This study focuses on the elaboration of optimization models and their application to route efficiently an Unmanned Aerial Vehicle for a given humanitarian mission. The four models developed were all implemented in a mixed-integer linear programming utility so the solutions for UAV routing could be compared with a land vehicle completing the same mission.

This report is divided in four main chapters. The first one introduces the drone technology environment and the humanitarian applications with these drones. A macro-environmental study is performed using a "PESTEL" analysis to better understand the reasons why drones would be useful in the humanitarian context. In the second chapter, a hypothetical mission based on a simplistic version of the transportation network of Haiti will be presented. This scenario will be used in the following chapters as a baseline case study. Chapter three concerns the elaboration of four different optimization models. The first three are a subset of node routing problems (Traveling Salesman Problem and Distance-constrained Vehicle Routing Problems), while the last one is closer to the arc routing category (Capacitated General Routing Problem).

The results obtained for of all these models show that a UAV is always faster than a single land vehicle operating in normal conditions for the test network. However, due to the very large network used as a basic example, the endurance limitations of existing UAVs appear to be a major issue for the real-world applications. Some existing UAV systems could fulfill the mission but they are likely still too expensive for humanitarian organizations. Fortunately, the models elaborated here can be applied to any network, and therefore the advantages of drones with a smaller autonomy can be verified, especially in jungle or mountain environments.