## 3 Problem Description  
The tackled problem consists of determining exploration and refueling strategies to evaluate the accessibility of victims by road using a UAV. The evaluation of the known road network is addressed as an on-line UAV routing problem with flying range limitations, aimed at minimizing the evaluation time to determine the accessibility of all victim locations by road. The problem is described as a network \(G=(N,E)\), where \(N\) is the set of nodes referring to road-crossings, victim nodes, and the DMC. \(E\) is the set of functional edges that represent functional roads in the pre-disaster situation. \(\hat{G}_{t}=(\hat{N}_{t},\hat{E}_{t})\) represents the disrupted road network. \(\hat{E}_{t}\) refers to the set of functional edges and non-explored edges at time \(t\) of exploration. \(\hat{N}_{t}\) is the set of nodes associated with road-crossings, victim nodes, the DMC, and disrupted nodes. Now, let \(AG_{t}=(N_{t},A_{t})\) be the fully connected aerial network where \(A_{t}\) represents the set of edges connecting the set of nodes \(N_{t}\) in the aerial network at time \(t\). The number of nodes and edges of the aerial network grows as disruptions are detected. The location of the disruption on the road becomes a disrupted node connected to the aerial network. The routing problem involves both the disrupted network and the aerial network simultaneously (see Figure 4). \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Authors** & **(a)** & **(b)** & **(c)** & **(d)** & **Objective** \\ \hline
[5] & x & & & x & Measure impact of a disaster \\ \hline
[30] & x & x & & Maximize reliability of distribution routes \\ \hline
[20] & x & x & &
\begin{tabular}{c} (i) Maximize coverage \\ (ii) Maximize equity of relief supply \\ \end{tabular} \\ \hline
[21] & x & & x &
\begin{tabular}{c} (i) Minmax. tour length from depot to victims \\ (ii) Maximize coverage of victims \\ \end{tabular} \\ \hline
[22] & x & & x & Minimize social cost \\ \hline
[23] & x & & &
\begin{tabular}{c} (i) Minimize transport costs \\ (ii) Minimize fixed costs for depots and vehicles \\ (iii) Maximize coverage \\ \end{tabular} \\ \hline
[24] & & x & & Minimize operational costs \\ \hline
[25] & x & x & &
\begin{tabular}{c} (i) Minimize risk of a disaster \\ (ii) Minimize total shipping costs of relief supplies \\ \end{tabular} \\ \hline
[26] & x & & x &
\begin{tabular}{c} (i) Minimize distance traveled \\ (ii) Minimize cost of opening and operating a relief center \\ (iii) Minimax. tour length from depot to victims \\ (iv) Minimize total quantity of perished items \\ \end{tabular} \\ \hline
[27] & x & x &
\begin{tabular}{c} (i) Minimize expected total cost \\ (ii) Minimize cost variability \\ (iii) Minimize customer satisfaction \\ \end{tabular} \\ \hline
[29] & x & & x & Minimize weighted sum of shortest paths from depot to victims \\ \hline
[31] & x & x & Maximize equity of relief supply \\ \hline
[32] & x & x & Minimize expected total cost \\ \hline
[33] & x & & x & Maximize number of people evacuated \\ \hline
**This research** & x & x & Minimize time to assess road accessibility to victims \\ \hline \hline \end{tabular} (a) complete information; (b) on-line information; (c) stochastic information; (d) deterministic information  
\end{table} 
Table 1: Summary of the literature related to humanitarian operations and disrupted road networks. The problem of on-line routing with limited flying range involves the risk of having a route failure because the UAV runs out of fuel. We assume that the UAV selected to perform the exploration has a minimum flying range that allows it to go and return from the DMC to the farthest node of the network. We define the flying range in terms of distance. An example of a UAV used for exploration of small and medium instances is the Super Bat UAV with a flying range of 643 km and a maximum flying speed of 83 km/h [35]. For large instances, the U-Max UAV with a flying range of 1852 km and a maximum flying speed of 160 km/h is suitable [35].