Optimal routing problems for a ground vehicle and a carried energy constrained drone in search and rescue problems

In this work, the cooperation between a ground vehicle and a drone subjected to energy constraints is investigated. The ground vehicle is able to move along a road network and to carry the drone when needed while the drone is able to y in a straight line with the objective to reach one or more given targets in the minimum time. We focus on the possible application in search and rescue operations, where the drone can be an helpful tool in providing life-saving support in areas difficult to access quickly for ground rescue teams. The drone for example can assist ground teams in searching an injured person located in an area or can be equipped with automated defibrillators and bring it faster to the target location where first aid operations can be carried out. In order to increase the maximum distance that the drone can cover before complete depletion of its battery, we provide the drone the option to land back again on the ground vehicle, where it can recharge or swap its battery (a faster solution with respect to a direct recharge). Recharging takes place with a battery swap operation, a much faster solution with respect to having rechargeable batteries. We define three optimization problems, with assumptions growing in complexity. For each problem, both an exact mathematical model and a solving algorithm (exact for the first problem, heuristic for the other two) will be proposed. Instances with growing sizes are randomly generated and analyzed in order to evaluate the efficiency and reliability of all algorithms and models. Numerical results show that the heuristic for the third and especially the second problem have computational times more competitive compared to the proposed models.

In questo lavoro di tesi, è studiata la cooperazione tra un veicolo di terra e un drone soggetto a limiti energetici. Il veicolo terrestre è in grado di muoversi lungo una rete stradale e trasportare il drone quando necessario mentre il drone è in grado di volare in linea retta con lo scopo di raggiungere una o più destinazioni predefinite nel minor tempo possibile. Ci focalizziamo sulla possibile applicazione nelle operazioni di salvataggio, in cui il drone può essere uno strumento utile nel fornire supporto di pronto soccorso in aree di difficile accesso rapido per le squadre di soccorso a terra. Il drone può, ad esempio, assistere operazioni di ricerca in un' area o essere dotato di defibrillatori automatizzati, che sono quindi portati più velocemente a destinazione, dove le operazioni di pronto soccorso possono essere eseguite da esterni. Al fine di aumentare la distanza massima che il drone può coprire prima del completo esaurimento della sua batteria, forniamo al drone la possibilità di atterrare di nuovo sul veicolo, per ricaricarsi o per eseguire la sostituzione della batteria (soluzione molto più rapida rispetto alla ricarica). In questo ambito definiamo tre problemi di ottimizzazione, con assunzioni di complessità crescente. Per ogni problema, sono proposti sia un modello matematico esatto che un algoritmo di risoluzione (esatto per il primo problema, euristico per gli altri due). Le istanze con dimensioni crescenti sono generate casualmente e analizzate al fine di valutare l'efficienza e l'affidabilità di tutti gli algoritmi e modelli proposti. I risultati numerici mostrano che l'euristica per il terzo e in particolare il secondo problema hanno tempi di calcolo più competitivi rispetto ai modelli proposti.