Minimizing the Longest Tour Time Among a Fleet of UAVs for Disaster Area Surveillance

In this paper, we study the employment of multiple Unmanned Aerial Vehicles (UAVs) to monitor Points of Interests (PoIs) in a disaster area, e. g. , collapsed buildings after an earthquake, where the UAVs can take photos and videos for the people trapped at PoIs, because such valuable information is imperative to make rescue decisions. Unlike most existing studies that ignored the monitoring time of PoIs and simply minimized the longest flying distance among the UAVs, we observe that it takes time to monitor the PoIs. Then, it is possible that the flying distance of a UAV in its flying tour may not be too long, the tour however contains many densely-located PoIs. Therefore, it will take a very long time for the UAV to monitor the PoIs in its tour. In this paper, we first formulate a problem of finding flying tours for K given UAVs to collaboratively monitor PoIs in a disaster area, such that the maximum spent time of the K UAVs among their tours is minimized, where the spent time of a UAV in its tour consists of the flying time and the PoI monitoring time. We then propose a novel 513 -approximation algorithm for the problem, improving the best approximation ratio 6 so far for the problem of minimizing the longest flying distance among the UAVs. In addition, we extend the proposed algorithm to the case that each UAV may not be able to monitor all PoIs assigned to it, due to its limited maximum flying time (e. g. , 30 minutes), and the UAV must return to its depot to replace its battery. We finally evaluate the performance of the proposed algorithms via simulation environments, and experimental results show that the proposed algorithms are very promising. Especially, the maximum spent times of the K UAVs in their tours by the proposed algorithms are up to 30 percent shorter than those by existing algorithms. In addition, the empirical approximation ratios of the proposed algorithms are no more than 2. 4, which are much smaller than their theoretical approximation ratios that are at least 513.