Optimization of Drone Routing in Humanitarian Applications

The present thesis aims to determine if drones could effectively replace 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 macroenvironmental
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.