# UAV Set Covering Problem for Emergency Network

Youngsoo Park, Ilkyeong Moon

► To cite this version:

Youngsoo Park, Ilkyeong Moon. UAV Set Covering Problem for Emergency Network. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2019, Austin, TX, United States. pp.84-90, 10.1007/978-3-030-29996-5_10. hal-02460476

HAL Id: hal-02460476

https://inria.hal.science/hal-02460476

Submitted on 30 Jan 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# UAV Set Covering Problem for Emergency Network*

Youngsoo Park<fnref n="1" /> and Ilkyeong Moon<fnref n="1" />,<fnref n="2" />[0000-0002-7072-1351]

**Abstract.** Recent technology allows UAVs to be implemented not only in fields of military, videography, or logistics but also in a social security area, especially for disaster management. UAVs can mount a router and provide a wireless network to the survivors in the network-shadowed area. In this paper, a set covering problem reflecting the characteristics of UAV is defined with a mathematical formulation. An extended formulation and branch-and-price algorithm are proposed for efficient computation. We demonstrated the capability of the proposed algorithm with a computational experiment.

**Keywords:** UAV · Disaster management · Set covering problem

## 1 Introduction

Over the last few years, there has been an increasing interest in unmanned aerial vehicles (UAVs) in the various fields including military, telecommunication, and aerial videography [1, 2]. Although it has been widely used for commercial or military purposes, this study suggests that UAVs can also be useful for disaster management. When a disaster occurs, activities to mitigate further damages, such as relief logistics, casualty transportation, and evacuation, are planned. Because of extremely varying situations in the demand (disaster) areas, it is crucial to establishing a plan with the scientific decision. Therefore, accurate data collection through contacting with survivors is needed to make these activities efficiently. However, large-scale disasters can cause survivors to be isolated or disconnected in disaster areas. In this case, the reconstruction of the temporary network by using the UAVs can accommodate the communication with the survivors and gathering the real-time data [3, 4]. By using UAVs of built-in network routers, rebuilding the network on shadow areas can be realized when the proper amounts of UAVs are distributed in the appropriate locations. If the

<footnote n="1">¹ Department of Industrial Engineering, Seoul National University,
Seoul 08826, Korea</footnote>

<footnote n="2">² Institute for Industrial Systems Innovation, Seoul National University,
Seoul 08826, Korea
ikmoon@snu.ac.kr</footnote>

<footnote>* This research was supported by the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT & Future Planning [Grant no. 2017R1A2B2007812].</footnote>
number of UAVs is sufficient, launching with a large number of UAVs simulta-
neously can reconnect the network easily. However, the decision maker with the
limited resource is obliged to make an optimal plan because the risk of either
under-or-over plan would result in the damage of human life. Therefore, the
following two questions can be raised naturally.

* What is the minimum number of UAVs to cover all areas?

* Where should each UAV be located?

By developing the mathematical model based on the set covering problem, the
minimum number of UAVs and their flight position to cover every survivor was
analyzed in this research.

The proposed UAV set covering problem (USCP) generalizes the classical set
covering problem by incorporating the flexible characteristic of UAVs which have
no restrictions on the position of facilities that can be located. As well as a disas-
ter situation, USCP can model various environments, including manufacturing
industry. In the smart factory, established by industry 4.0, individual resources
communicate with each other via wired or wireless network. Especially for the
wireless network, it is vital to cover every resource efficiently with minimal in-
vestment. As with the USCP, the location where the wireless network router can
be installed at this time is relatively free, making it impossible to choose over
given candidates of positions.

This study proposes a branch-and-price approach to overcome the intractabil-
ity caused by the quadratic constraint and solve USCP for efficient computation.
The overall structure of the study takes the form of 5 chapters, including this
introductory chapter. Section 2 is concerned with the description of USCP and
the standard formulation of the mathematical model. In Section 3, an extensive
formulation and a branch-and-price algorithm are presented for the problem. In
Section 4, computational experiments are conducted, and results are analyzed.
Section 5 summarizes the findings of the research.

## 2 Problem Definition and Mathematical Formulation

The objective of USCP is to cover every demand point with the minimum num-
ber of UAV with a fixed coverage and without a restrictions on the position. The
detailed assumptions of USCP are defined as follows: (1) Positions of demand
points are deterministic. (2) Coverage distance of UAV is identical. (3) There
are no restrictions on the position of UAV. (4) Each wireless network is unca-
pacitated and the network traffic is ignored. (5) Overlap interference between
UAVs and shadowing effect by buildings are ignored.

A mathematical model is developed based on the assumptions. Let $N$ denote the set of the demand points where the survivors are distributed. The following is the notations used in the standard formulation for USCP.

### Parameters
$a_i^x$ a position of demand point $i$ on x-coordinate. $\forall i \in N$

$a_i^y$ a position of demand point $i$ on y-coordinate. $\forall i \in N$

$R$ coverage radius of a UAV.

Decision variables

$$y_j = \begin{cases} 1, & \text{if UAV } j \text{ is used.} \\ 0, & \text{otherwise.} \end{cases} \qquad \forall j \in N$$

$$x_{ij} = \begin{cases} 1, & \text{if demand point } i \text{ is covered by UAV } j. \\ 0, & \text{otherwise.} \end{cases} \quad \forall i \in N, \forall j \in N$$

$$c_j^x \in \mathbb{R}, \quad \text{position of UAV } j \text{ on x-coordinate.} \quad \forall j \in N$$

$$c_j^y \in \mathbb{R}, \quad \text{position of UAV } j \text{ on y-coordinate.} \quad \forall j \in N$$

When the coverage range is given as a parameter, what we are interested in is the minimum number of UAVs and the position of each UAV in the x-y plane to cover all demand points. The relevant mathematical formulation based on mixed-integer programming is developed as follows:

$$\min \sum_{j=1}^{m} y_j \qquad (1)$$

$$\text{s.t.} \quad x_{ij} \le y_j, \qquad \forall i \in N, \forall j \in N \quad (2)$$

$$\sum_{j=1}^{m} x_{ij} \ge 1, \qquad \forall i \in N \qquad (3)$$

$$(a_i^x - c_j^x)^2 + (a_i^y - c_j^y)^2 \le R^2 + M(1 - x_{ij}), \quad \forall i \in N, \forall j \in N \quad (4)$$

$$x_{ij} \in \{0, 1\}, \qquad \forall i \in N, \forall j \in N \quad (5)$$

$$y_j \in \{0, 1\}, \qquad \forall j \in N \quad (6)$$

$$c_j^x, c_j^y \in \mathbb{R}, \qquad \forall j \in N \quad (7)$$

Objective function (1) minimizes the number of UAVs to cover all demand points. Constraint (2) indicates the linking constraint between a demand point and a UAV. That is, a UAV $j$ is required to cover a demand point $i$. Constraint (3) represents that each demand point $i$ should be covered by one UAV. Constraint (4) is the logical constraint to incorporate the network coverage of the UAV. When the demand point $i$ is covered by the UAV $j$, the location of the demand point $(a_i^x, a_i^y)$ is covered by a circle with a circumcenter placed on the point $(c_i^x, c_i^y)$. Constraints (5) and (6) mean that variables $x_{ij}$ and $y_j$ are binary variables. Constraint (7) means that $c_i^x$ and $c_i^y$ are the non-negative real variables. For distinction, the formulation will be renamed as Euclidean standard formulation (ES). ES contains the non-linear constraint as presented in Constraint (4). Accordingly, it is hard to obtain the optimal solution within a reasonable time, even for small-sized problems. Since the fast decision is vital in the response for disaster management, a branch-and-price approach for USCP is designed, which will be introduced in the next section.
## 3 Branch-and-Price Approach for USCP

Branch-and-price (B&P) approach is a well-known exact-algorithm for large-scale optimization problems. By incorporating the column generation technique into the branch-and-bound, it can significantly improve the bounds of the linear programming relaxation and resolve the symmetry of the solutions while branching. For detailed information of the B&P approach, one can refer [5].

### 3.1 Master problem

Denote by $\Omega$ is the set of the possible patterns to cover the demand points by one UAV. The patterns are defined with a given parameter $w_{ij}$ indicating the inclusion of each demand point for a pattern. The minimum number of UAVs can be determined by an integer program as follows:

$$ \min \sum_{j \in \Omega} y_j \qquad (8) $$

$$ \text{s.t.} \quad \sum_{j \in \Omega} w_{ij} y_j \geq 1 \quad \forall i \in N \qquad (9) $$

$$ y_j \in \{0, 1\}, \quad \forall j \in \Omega \qquad (10) $$

Objective function (8) minimizes the number of UAVs required to cover all demand points. Constraint (9) is related to an assignment constraint to the demand points. The optimality under the current basis is determined by the pricing subproblem.

### 3.2 Pricing subproblem

We have defined $\pi_i$ as the dual price of constraint (9). By solving the pricing subproblem, one can identify whether there is a better assignment pattern of demand points for a UAV. To construct a pattern (column), the decision variable is binary to identify whether a demand point $i$ is covered by the generated column or not. Another decision variables $c^x$ and $c^y$ represent the position of UAV of the generated pattern. Additional columns for the master problem is generated by solving the following pricing problem:

$$ \min \quad 1 - \sum_{i=1}^{m} \pi_i w_i \qquad (11) $$

$$ \text{s.t.} \quad (a_i^x - c^x)^2 + (a_i^y - c^y)^2 \leq R^2 + M(1 - w_i), \quad \forall i \in N \qquad (12) $$

$$ w_i \in \{0, 1\}, \quad \forall i \in N \qquad (13) $$

$$ c^x, c^y \in \mathbb{R}, \qquad (14) $$
## 4 Computational Experiments

To compare the effectiveness of the proposed solution algorithms, computational experiments are performed. All optimization models were developed in FICO Xpress Mosel version 7.9. Experiments were performed with Intel® Core™ i5-6600 CPU @ 3.30GHz and 32 GB of RAM operated on Windows 10 64 bit OS. To be applied in the disaster management, each experiment was conducted with the run-time limit of 1800 seconds. Data set was made based on the benchmark data from OR-Library [6, 7]. For each size of demand points of 10, 20, and 50, 10 instances were created, and the demand points were distributed uniformly on the 100 x 100 Euclidean plane. Three coverage radiuses of 10, 20, and 30 were examined for each instance.

An analysis of algorithmic performance and sensitivity analysis are provided for the managerial insight in disaster management. Table 1 lists the computational results. The columns in this table are defined as follows. #Opt/#Feas: the number of solved/feasible-solution-provided problems within the time limits. Time: the average of the computation time to solve the problems. For the problems not solved within the time limit, we used 1800 seconds while calculating the average. GapL: the average of the gap between lower (LP) bound and the feasible solution. # of UAVs: the average of the objective value of the feasible solution. Gap: the average of the gap between # of UAVs of ES and B&P algorithm, calculated by {(# of UAVs of ES)-(# of UAVs of B&P)}/(# of UAVs).

<table><caption>**Table 1.** Computational results</caption><thead><tr><th rowspan="2">ND</th><th rowspan="2">Rd</th><th colspan="2">#Opt/#Feas</th><th colspan="2">Time(s)</th><th colspan="2">GapL(%)</th><th colspan="2"># of UAVs</th><th>Gap(%)</th></tr><tr><th>ES</th><th>B&P</th><th>ES</th><th>B&P</th><th>ES</th><th>B&P</th><th>ES</th><th>B&P</th><th>B&P</th></tr></thead><tbody><tr><td rowspan="3">10</td><td>10</td><td>1/9</td><td>10/10</td><td>1661.2</td><td>0.2</td><td>33.32</td><td>-</td><td>7.6</td><td>7.2</td><td>-4.43</td></tr><tr><td>20</td><td>9/9</td><td>10/10</td><td>388.8</td><td>1.1</td><td>4.00</td><td>-</td><td>4.6</td><td>4.0</td><td>-6.00</td></tr><tr><td>30</td><td>10/10</td><td>10/10</td><td>11.2</td><td>2.7</td><td>-</td><td>-</td><td>2.8</td><td>2.8</td><td>-</td></tr><tr><td rowspan="3">20</td><td>10</td><td>0/0</td><td>10/10</td><td>1800*</td><td>17.9</td><td>85.00</td><td>-</td><td>20.0</td><td>10.7</td><td>-46.50</td></tr><tr><td>20</td><td>0/9</td><td>10/10</td><td>1800*</td><td>91.9</td><td>46.00</td><td>-</td><td>6.9</td><td>5.5</td><td>-7.00</td></tr><tr><td>30</td><td>5/10</td><td>10/10</td><td>944.8</td><td>78.3</td><td>12.50</td><td>-</td><td>3.5</td><td>3.5</td><td>-</td></tr><tr><td rowspan="3">50</td><td>10</td><td>0/0</td><td>10/10</td><td>1800*</td><td>447.9</td><td>96.00</td><td>-</td><td>50.0</td><td>16.5</td><td>-67.00</td></tr><tr><td>20</td><td>0/0</td><td>5/10</td><td>1800*</td><td>1594.7</td><td>96.00</td><td>26.77</td><td>50.0</td><td>11.6</td><td>-85.56</td></tr><tr><td>30</td><td>0/2</td><td>1/10</td><td>1800*</td><td>1765.1</td><td>88.47</td><td>68.61</td><td>41.0</td><td>17.8</td><td>-75.64</td></tr></tbody></table>

1800*: No problem is finished within the time limits.

As shown in Table 1, ES was not capable of providing optimal solutions even for the smallest problems. Long computation time and high GapL of ES were caused by both factors of weak LP bound and scarce feasible solution. ES could not provide feasible solutions for 49 of 90 problems and it led to the high average
of the number of UAVs required to cover the demand points. Especially for the problems with the 50 demand points, $Gap_L$ were higher than 88% and showed the intractability of ES. B&P algorithm solved 76 of 90 problems and provided a feasible solution for every problems. Thus, for 7 of 9 classes of problems showed 0 for $Gap_L$. For every data set used for the computational experiment, $Gap$ was always the same or less than zero, which meant that B&P algorithm makes a better plan to use fewer UAVs to cover the area.

Certainly, there was a tendency that the smaller the radius of the coverage be, the more UAVs were required. For the same coverage with the different number of demand points, the number of UAVs grew with the number of demand points, too. However, under the fixed-size area, the growth rate was less than 1. In other words, 7.2 UAVs with coverage radius 10 were required to cover 10 demand points, but only 10.7 UAVs were required to cover 20 demand points. In extreme cases, there is an upper bound of the number of UAVs, which will cover the whole area without any network-shadow area.

## 5 Conclusions

We introduced a UAV set covering problem with fixed coverage and without restrictions of positions for planning an emergency wireless network in disaster areas efficiently. Due to the intractability of quadratic constraints, proposed ES could not provide an optimal solution by a commercial solver within a practical time. An extended formulation of ES was proposed to implement B&P algorithm for USCP, which provided a better LP-bound and removed the symmetry of the solution. The computational experiment showed that B&P algorithm can provide an optimal solution for small-sized problems within reasonable time limits. Sensitivity analysis was conducted to show the tendency between the number of demand points, radius, and the number of UAVs required.

## Acknowledgements

This research was supported by the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT & Future Planning [Grant no. 2017R1A2B2007812].

## References

1. Kim, D., Lee, K., Moon, I.: Stochastic facility location model for drones considering uncertain flight distance. Ann. Oper. Res. (2018). doi:10.1007/s10479-018-3114-6

2. Kim, S., Moon, I.: Traveling Salesman Problem With a Drone Station. IEEE Trans. Syst. Man, Cybern. Syst. 49, 4252 (2019). doi:10.1109/TSMC.2018.2867496

3. Aida, S., Shindo, Y., Utiyama, M.: Rescue Activity for the Great East Japan Earthquake Based on a Website that Extracts Rescue Requests from the Net. In: Proceedings of the Workshop on Language Processing and Crisis Information 2013. pp. 1925 (2013).
4. Heinzelman, J., Waters, C.: Crowdsourcing crisis information in disaster-affected Haiti. US Institute of Peace Washington, DC (2010).

5. Vanderbeck, F., Wolsey, L.A.: Reformulation and decomposition of integer programs. In: 50 Years of Integer Programming 1958-2008. pp. 431502. Springer (2010).

6. Beasley, J.E.: OR-Library: Distributing Test Problems by Electronic Mail. J. Oper. Res. Soc. 41, 10691072 (1990). doi:10.1057/jors.1990.166 https://doi.org/10.1057/jors.1990.166

7. Osman, I.H., Christofides, N.: Capacitated clustering problems by hybrid simulated annealing and tabu search. Int. Trans. Oper. Res. 1, 317336 (1994). doi:10.1016/0969-6016(94)90032-9