1 Introduction

Disasters are unpredictable and cause significant damage to infrastructure as well as human and economic losses. Although disasters are unavoidable, their adverse effects could be alleviated thanks to an effective and enhanced disaster management system. Disaster management is a strategic planning and procedure that is administered and applied to protect vital infrastructure from severe damage when man-made calamities and natural catastrophic disasters occur [1]. Such a management system is required to respond to a disaster in a timely manner, thereby reducing the post-disaster risk, the physical impact of the disaster, the number of fatalities, and the economic damage.

Türkiye lies on the highly seismically active Anatolian Plate, which has experienced massive earthquakes throughout history. Since 1900, there have been 20 earthquakes with a magnitude greater than 7, making Türkiye one of the most seismically active countries in the world. All these earthquakes have claimed the lives of people and caused major devastation, damaging telecommunications and energy infrastructures, which are vital services in the first hours of a rescue. Such breakdowns of the primary infrastructures disrupt the coordination between the organizations and institutions who are trying to cooperate in search and rescue operations and disrupt the control of the risk situation. During a disaster, most terrestrial base stations may collapse, rendering mobile phones unusable in the first hours and days of the disaster response. In most cases, some people are trapped in the affected areas and are unable to communicate by mobile phones to notify their locations due to the destruction of the mobile network infrastructure [2]. On the other hand, local communication based on social media is known to play an important role in locating people in restricted disaster areas [3, 4]. It is therefore essential that an efficient, temporary, and uninterrupted communication network is established as soon as possible to coordinate emergency response teams and locate isolated victims. Although many effective technological solutions are being developed to reduce the effect of the disaster, drones have recently demonstrated their ability to address the most challenging issues of an emergency event [5, 6]. Considering the golden rescue time, integrating drone technology into management applications can help emergency response teams make quicker decisions and more efficiently deploy resources, thereby reducing casualties. It can also provide initial situational awareness, enabling teams to take better action. Drones have also been used in search and rescue operations by providing communication networks. For example, during Hurricane Harvey in Texas, drones were used to assess damage, provide real-time information, and locate people in need of urgent assistance. AT&T company developed the flying COW and used it to provide emergency 4 G coverage to Puerto Rico in the aftermath of Hurricane Maria in 2018 [7]. Another search and rescue drone (SARDO) provided first responders with a victim location system capable of operating without the support of existing network infrastructure. A drone equipped with a cellular base station is sent over a specific area. The drone will then fly over the area and detect signals from the phones in the area. This allows the drone to locate the phone and send it back to the rescuers [8]. The Revector Detector Drone (RDD) is a drone with a mobile phone base station that allows rescue teams to know exactly where injured people are on a mountain, in a forest or even after an earthquake, as long as someone has an active mobile phone [9]. NASA’s Scalable Traffic Management for Emergency Response Operations (STEReO) project focuses on using drones to establish communications networks in disaster areas. These drones can act as temporary cellular towers, providing critical connectivity when ground-based infrastructure is damaged or destroyed [10]. The Japan UAS Industrial Development Association (JUIDA) dispatched the drones to the affected area to assist with recovery efforts. These drones provided real-time data and aerial imagery to first responders, enabling faster and more efficient search and rescue operations [11].

Driven by real-world applications, this study aims to develop a network planning framework to improve the efficiency of search and rescue operations through optimization. In disaster management, the timely and effective distribution of resources is essential to minimize the impact of emergencies. However, the deployment and coordination of drones present significant logistical and operational complexities, particularly from a network management perspective. This challenge can be framed as designing and managing a drone operations network, with base stations acting as key nodes for recharging, maintenance, and task coordination. The core issue is to strategically locate these base stations and optimize the allocation of drones to maximize coverage and efficiency while considering operational constraints such as limited energy capacity and communication range. In this study, it is assumed that DBSs are initially placed at recharging stations located at emergency assembly points during the pre-disaster phase. When a disaster is detected, they are first positioned to cover the area as shown in Fig. 1, and then make successive visits between locations to provide continuous coverage.

Fig. 1
figure 1

System model

Full size image

The primary aspect of interest is to determine how long a DBS should hover to adequately cover a location. The aim is to maximize the time spent at each location to provide optimal service. Consequently, the problem is to find the optimal hovering locations and hovering time at each location, as well as the sequence of visits between these locations, given the constraints of the drones’ battery capacity. Each DBS is equipped with a battery and moves to a central location for recharging at the end of each cycle. To ensure continuous communication, a battery constraint is incorporated into this problem.

Furthermore, disaster scenarios often involve unevenly distributed populations and resource needs, requiring equitable service provision across areas. This adds a layer of complexity, as traditional optimization objectives, such as maximizing total coverage, may inadvertently result in inequities. Balancing efficiency with fairness becomes essential to ensure that all affected areas receive adequate attention, regardless of their geographic or demographic characteristics. Fairness can be defined as spatial fairness or both spatial and temporal fairness in terms of resource allocation. The fairness measure based on resource allocation assumes that each client in a system is entitled to an equal share of the resource (server) [12]. Ensuring a balanced (fair) allocation is an important concern in allocation problems; therefore, various methods of incorporating fairness into allocation decisions have been discussed in several papers (see [13] and references therein).

In this study, DBSs are considered as resources that will serve disaster areas to ensure a ’fair’ distribution of services and fairness signifies balanced time allocation. To achieve a fair distribution of services, this study balances the hover times in a route through a proposed fairness-enhancing constraint. However, such a solution may leave some areas significantly underserved. From a disaster management perspective, covering (servicing) as many areas as possible is a top priority. To the best of our knowledge, this article is the first reported attempt to solve the balanced (fair) service allocation problem. The two objectives are to maximize the areas covered (spatial coverage) and to maximize the total hover time (temporal coverage). The hover time of a disaster area depends on the DBS locations, and it is desired to maximize the total hover time of the DBS locations while minimizing the travel time. The proposed framework focuses on equitable distribution of services to maximize coverage and resource effectiveness. By incorporating fairness and adaptability, this research contributes to the development of robust solutions that enhance the resilience and efficiency of disaster response systems.

The remainder of this paper is organized as follows. Section 2 presents a literature review on the use of DBSs under post-disaster conditions. Section 3 describes a mixed-integer linear programming formulation for the problem with two different objectives, in which hover time balancing constraints are considered. A case study is carried out to demonstrate the application of the developed model in Sect. 4. Finally, the concluding remarks are given in Sect. 5.

2 Literature Review

More recently, drones have been explored to help in emergency situations by delivering humanitarian aid [14,15,16,17,18,19,20] and post-disaster assessment [21,22,23,24,25]. Very few works have focused on the use of drones for emergency communication systems in post-disaster scenarios [5, 26,27,28]. This literature review has focused on some of the challenges to the effective use of DBSs following a disaster. These challenges are location allocation and routing optimization, energy efficiency and battery optimization, handover mechanism, and hover time optimization.

Location allocation of DBSs is one of the most challenging issues as it has a direct impact on communication quality and connectivity reliability. This challenge may include the placement of a single DBS or multiple DBSs over the stationary or mobile locations. Stationary placement involves positioning a set of DBSs at fixed locations over an area, while mobile placement involves changing their position over time. Some studies have focused on optimizing a single stationary DBS as a relay node to increase network capacity in a heterogeneous network including terrestrial base stations (TBS) [29] or as a communication helper unit to replace non-functional TBSs [30]. However, in a larger disaster area with a large number of victims that need to be served, multiple DBSs are required to provide efficient coverage. Multiple drone coverage has been considered in both the heterogeneous networks [31,32,33] and DBS-only networks [34,35,36,37,38]. On the other hand, since victims in disasters are randomly distributed over a very large area, DBSs can fly over the area due to their mobility and flexibility. Although studies have shown that DBS placement is a compelling problem and have developed many approaches to solving it, the movement of the DBSs over the area has not been considered. Optimal route planning for DBS placement is another important challenge in drone communication systems. It can help to moderate the movement of a limited number of DBSs and provide better coverage of the area. A single DBS route was designed to collect data [39] and provide communication to victims from a central DBS flying in discrete time slots [40, 41] in a heterogeneous network. In the DBS-only network study, multiple DBSs were placed and clustered to account for DBS movement [42]. By developing a clustering approach, an anchor DBS was selected as the cluster head in each cluster, and other cluster members were positioned according to the position of the cluster head. Hence, their positions were randomly initialized, and then they all searched for better solutions by changing their current positions using particle swarm optimization-based algorithms. In this study, the movement of DBSs was designed to find accurate and efficient positions with a location-aware mechanism. Unlike previous works, this paper assumes that each DBS has a route to visit the disaster areas. This is because the need to effectively manage the limited number of DBSs and provide continuous coverage of the disaster area requires the movement of DBSs.

The limited lifetime of a DBS is one of the main factors limiting its widespread use in communication networks. This challenge has not been well addressed in the relevant literature. Some works have considered a network of multiple DBSs hovering over a given location by considering the battery capacity only for the flight time of the DBSs [43]. Another work [44] considered an adaptive movement of DBSs to maintain connectivity with mobile users in a disaster area where some TBSs have failed. However, the battery level and flight time tracking were not considered. Due to their limited flight time, the DBSs were unable to provide continuous coverage of the disaster area, and their batteries had to be either replaced or recharged while in flight. Some works [45, 46] considered the return to the recharging station. In the study by [45], they restricted several DBS activities (covering, traveling, and recharging) to predefined time steps of 10 min each. They also assumed the same amount of battery consumption for traveling and covering and expressed the battery capacity of the DBS as the maximum number of time steps between recharges. Jin et al. [46] developed an integrated placement model for DBSs and a Capsule Airport (CA), which serves as a recharge and retrieval station for DBSs, to extend the limited coverage and endurance of DBSs for emergency communication in disaster scenarios. Another work [47] aimed to reduce the total energy consumption of the drone group while maintaining user service quality in rural areas. They provided an energy consumption model for information transmission and execution of the drone itself. Bozkaya et al. [48] also proposed energy efficient model for dynamic drone placement considering handover management. Since drones are battery-constrained, handover is frequently required. They proposed a handover scheme while predicting the energy-efficient drone trajectories. Several handover processes were defined to maintain connectivity between users and an associated drone whenever the drone needs to be replaced because of battery replenishment [49,50,51,52]. In our study, when a DBS returns to the charging station to recharge its battery, a handover process is performed between two neighbor cluster heads to ensure continuous communication.

Another important factor affecting the efficiency and fairness of such systems is the hover time of the DBSs providing communications for each disaster area. Hover time refers to the length of time a DBS can remain stable without moving. A longer hover time allows the DBS to cover a definite area for a longer time. Since the maximum flight time of a DBS is limited by its battery capacity, it would be beneficial to determine the hover time of DBSs from an optimization perspective. Muntaha et al. [53] investigated the effect of the hover time in a heterogeneous network with varying numbers of DBSs to improve the coverage of a TBS. Stationary DBSs and users were considered during the communication period. Unlike Muntaha et al. [53], our work faces a different problem, where the mobility of DBSs over the disaster area is considered in a DBS-only system. Furthermore, we investigate the balanced hover time for mobile DBSs in each cycle to ensure coverage reliability and fairness in each disaster area by introducing a linear programming model.

Table 1 summarizes the literature on the use of DBS in disasters. Columns are self-explanatory. To the best of our knowledge, no previous work has performed an analysis similar to this work. Unlike previous studies, this paper addresses an optimization problem in several aspects: (i) DBS-located areas that are continuously visited by one DBS after another in an ordered sequence, and a cycle constrained by the limited battery, constitute the routes of the DBSs, (ii) the scheduling of the DBSs traveling, hovering, and recharging actions, (iii) the DBS-only communication network is provided by satellite links, (iv) the energy consumption calculation based on the DBSs movements, (v) the consideration and a unique formulation of additional DBSs to provide continuous coverage of the disaster area for sustainable operations. Accordingly, the contributions of this study could be highlighted as given below.

  • Development of a novel mathematical programming model using multiple drones and multiple recharges to provide the communication network for search and rescue operations.

  • Ensuring continuity and fairness by proposing problem-specific constraints in the proposed coverage model.

  • Conducting a case study of İzmir, Türkiye, considering different parameters.

    Table 1 Summary of related work
    Full size table

3 Problem Formulation

This section introduces the mixed integer linear programming (MILP) models. A directed graph G = (V, A). The set \(V = \{1, 2,\dots \, n\}\) of nodes is partitioned into a set of disaster areas N and a set of recharging stations C with the maximum number of DBSs available (\(D_{max}\)). There are no arcs between pairs of recharging stations exist, thus \(A = \{ (i,j): \;i, j \in V\) and \(\{i, j\} \cap N \ne \emptyset \}\) is the set of arcs characterized by two attributes, namely the travel time and the energy consumption. Each arc \((i,j)\in A\) has a travel time \(\varsigma _{ij}>0\) with a time limit denoting by T (seconds). \(\Pi _{init}\) denotes the initial time at the start of operations. The energy consumption rates per unit time for flight and hovering are captured by \(\alpha\) and \(\beta\), respectively. These parameters ensure that the model accurately reflects the energy dynamics of the DBSs, allowing feasible route planning and coverage optimization. Each DBS travels through its route r at a constant speed and hovers with limited battery capacity. A feasible DBS route starts and ends at the recharging station. The battery level of a DBS decreases as it leaves the recharging station. Therefore, the battery of a DBS reaches full charge level Q when the DBS visits the recharging station. Furthermore, TC denotes the charging time at recharging stations, which accounts for scheduling decisions for efficient energy replenishment. The disaster area is divided into hexagonal cells. Each cell represents an affected area with victims and is organized into clusters. DBSs are positioned to hover over the cluster centers and follow return paths to recharging stations to traverse the centers of these cells. To capture neighborhood relationships between disaster areas, \(a_{ij}\) is introduced as a binary parameter, taking the value 1 if area i is a neighbor of another area j and 0 otherwise. To guarantee a minimum level of service, the parameter \(\vartheta\) specifies the minimum desired percentage of coverage of the disaster-affected areas. The hexagonal tessellation provides a geometrically efficient structure that allows for a larger coverage area per DBS charge compared to a square tessellation, thereby increasing the overall operational effectiveness of the coverage network [54]. Finally, M is a very large number. The following is a brief definition of sets and indices, parameters and decision variables, followed by the mathematical formulations.


Sets and indices

N: Set of disaster areas, indexed by i, j, k, and u

C: Set of battery recharging stations, indexed by i

R: Set of potential routes, (\(\mid\text{R}\mid = \mid\text{N}\mid\)), indexed by r

V: Set of all nodes, i.e., V=\(N \cup C\)


Parameters

T: Maximum allowable cycle time for each route

\(D_{max}\): Maximum number of DBSs available

\(\vartheta\): Minimum desired percentage of coverage

TC: Charging time at the recharging stations

\(\alpha\): Unit energy consumption rate for flight

\(\beta\): Unit energy consumption rate for hovering

Q: Battery capacity of a DBS

\(\varsigma _{ij}\): Travel time required by a DBS through arc \((i,j)\in V \mid i\ne j\)

\(a_{ij} \in \{0,1\}\): Equals 1 if an area \(i \in N\) is a neighbor of another area\(j \in N\), and 0 otherwise

M: A very large number

\(\Pi _{init}\): Initial time.


Decision variables

\(x_j \in \{0,1\}\): Equals 1 if a DBS is allocated over area \(j \in N\), and 0 otherwise

\(l_{ji} \in \{0,1\}\): Equals 1 if a DBS is located over area \(j \in N\) assigns to a recharging station \(i \in C\) and 0 otherwise

\(z_{ij} \in \{0,1\}\): Equals 1 if an area \(i \in N\) is covered by a DBS allocated at the area \(j \in N\), and 0 otherwise

\(y_{ijr} \in \{0,1\}\): Equals 1 if arc \((i,j)\in V \mid i\ne j\) is traversed by a DBS along with the route \(r \in R\), and 0 otherwise

\(g _{jr} \in \{0,1\}\): Equals 1 if an area \(i \in V\) is traveled along with the route \(r \in R\), and 0 otherwise

\(s_r \in \{0,1\}\): Equals 1 if a route \(r \in R\) is active, and 0 otherwise

\(b_{ir} \in [ \,0, Q] \,\): Battery level of a DBS at area \(i \in V\) in route \(r \in R\)

\(\tau _{ir} \in [ \,0, T] \,\): Arrival time of a DBS at area \(i \in V\) in route \(r \in R\)

\(w_{jr} \in [ \,0, T] \,\): Hover time of a DBS at area \(j \in V\) in route \(r \in R\)

The aim of this study is to develop a network structure that ensures uninterrupted mobile phone connectivity via DBSs under post-disaster conditions. Previous experiences, as stated in the Introduction, put forward the significance of such plans while managing search and rescue operations appropriately. In post-disaster conditions, such a plan must provide network coverage over as many areas as possible, and this coverage must last as long as possible. These requirements result in two different objectives, namely coverage and hover time maximization. Therefore, this study aims to develop two different MILPs according to these two objective functions and analyze them separately. Afterwards, the trade-offs between these two MILPs will be explored and illustrated through a Pareto analysis at the end of Sect. 4.1.

In the following, MILPs developed according to two different objectives are presented. The first model (see Sect. 3.1) formulates the coverage maximization problem based on the maximal coverage problem which is one of the well-known facility location problems [55]. Then, in conjunction with the maximal coverage formulation, the second model (see Sect. 3.2) formulates the hover time maximization problem.

3.1 Formulation of the Coverage Maximization Problem

This subsection first introduces the basic mathematical programming model for the coverage maximization problem. As mentioned above, the formulation of this problem variant is developed based on the maximum coverage problem. Model constraints can be grouped into five sets: assignment, routing, battery capacity, time tracking and balancing, and integrality constraints. All of these constraints are explained in detail in the following subsections.

3.1.1 Objective Function

$$\begin{aligned}&\text {max}\sum _{j=1}^{N}\sum _{i=1}^{N}z_{ij} \end{aligned}$$
(1)

The objective function (1) maximizes the number of disaster areas covered.

3.1.2 Assignment Constraints

Assignment constraints are proposed to establish the relationship between DBS-allocated locations and covered regions.

$$\begin{aligned}&z_{ij}\le x_j \quad \forall i,j\in N \end{aligned}$$
(2a)
$$\begin{aligned}&\sum _{j=1}^{N}z_{ij}\le 1 \quad \forall i\in N \end{aligned}$$
(2b)
$$\begin{aligned}&z_{jj} = x_j\quad \forall j\in N \end{aligned}$$
(2c)
$$\begin{aligned}&\sum _{j=1}^{N}x_j + \sum _{r=1}^{R}s_r\le D_{max} \end{aligned}$$
(2d)
$$\begin{aligned}&x_i\le 1- \left( a_{ij}x_{j}\right) \quad \forall i,j\in N \mid i\ne j \end{aligned}$$
(2e)
$$\begin{aligned}&z_{ij}\ge 1 - \mid V\mid *\left( 1 - a_{ij}x_{j}\right) \quad \forall i,j\in N \end{aligned}$$
(2f)
$$\begin{aligned}&z_{ij}\le \mid V\mid *\left( a_{ij}x_{j}\right) \quad \forall i,j\in N \end{aligned}$$
(2g)

The constraint sets (2a)–(2c) give the coverage relations. The constraint set (2d) limits the total number of DBSs in the system. The constraint sets (2e)–(2g) guarantee the hexagonal structure.

3.1.3 Routing Constraints

To provide accurate network connectivity across the disaster area and utilize the available DBSs as effectively as possible, it is necessary to move the DBSs along a route. In line with these objectives, the following routing constraints have been established to optimize the routes between charging stations and DBS-allocated locations.

$$\begin{aligned}&\sum _{i=1}^{V}\sum _{r=1}^{R}y_{ijr} = x_j \quad \forall j\in N \mid i\ne j \end{aligned}$$
(3a)
$$\begin{aligned}&\sum _{i=1}^{V}\sum _{r=1}^{R}y_{ijr} \le 1 \quad \forall j\in N \mid i\ne j \end{aligned}$$
(3b)
$$\begin{aligned}&\sum _{i=1}^{V}y_{ijr} - \sum _{i=1}^{V}y_{jir} = 0 \quad \forall r\in R,\quad \forall j\in V \mid i\ne j \end{aligned}$$
(3c)
$$\begin{aligned}&\sum _{i=1}^{C}l_{ji} \le x_j \quad \forall j\in N \end{aligned}$$
(3d)
$$\begin{aligned}&\sum _{k=1}^{N}y_{ikr} + \sum _{k=1, \mid k\ne j}^{V}y_{kjr} \le 1 + l_{ji} \forall i\in C,\quad \forall r\in R,\quad \forall j\in N \end{aligned}$$
(3e)
$$\begin{aligned}&\sum _{r=1}^{R}y_{ijr} \le l_{ji} \forall i\in C, \forall j\in N \end{aligned}$$
(3f)
$$\begin{aligned}&\sum _{r=1}^{R}y_{jir} \le l_{ji} \forall i\in C, \forall j\in N \end{aligned}$$
(3g)
$$\begin{aligned}&\sum _{r=1}^{R} g _{jr} \le x_j \forall j\in N \end{aligned}$$
(3h)
$$\begin{aligned}&\sum _{j=1}^{C} g _{jr} \le 1 \forall r\in R \end{aligned}$$
(3i)
$$\begin{aligned}&s_r + \left( \mid V\mid *\left( 1 - g _{jr}\right) \right) \ge 1\quad \forall j\in N,\quad \forall r\in R \end{aligned}$$
(3j)
$$\begin{aligned}&s_r - \left( \mid V\mid *\sum _{j=1}^{N} g _{jr}\right) \le 0 \quad \forall r\in R \end{aligned}$$
(3k)
$$\begin{aligned}&s_r\ge s_{r+1} \quad \forall r\in R\setminus \{R\} \end{aligned}$$
(3l)

The constraint set (3a) constitutes an arc in a route only for DBS-allocated areas, while the constraint set (3b) assigns each arc to at most one route. The flow balance constraints are represented by the constraint set (3c). The constraint set (3d) links the DBS locations to the recharging stations, while the constraint set (3e) ensures that a DBS location must be assigned to a recharging station if there is a route connecting them. Constraint sets (3f) and (3g) ensure that a route starts at a recharging station and ends at the same station. Constraint sets (3h) and (3i) link a DBS location and a recharging station to a route. Constraint sets (3j) and (3k) ensure that a route is active if and only if it contains a DBS allocated area, while the constraint set (3l) ensures that the active routes are in an ordered sequence.

3.1.4 Battery Capacity Constraints

As mentioned above, DBSs have a limited battery capacity and need to be recharged before the battery runs out. Accordingly, the battery level of the DBSs needs to be tracked as they provide network connectivity over the disaster area and move from one area to another along their routes. The following sets of constraints, representing the battery consumption formulations, have been developed to adequately track the endurance limit of the DBSs.

$$\begin{aligned}&b_{jr} = Q - \alpha \varsigma _{ij}y_{ijr} - \beta w_{ir} + Q\left( 1 - y_{ijr}\right) \quad \forall j\in V , \forall i\in C, \forall r\in R \mid i\ne j \end{aligned}$$
(4a)
$$\begin{aligned}&b_{jr} = b_{ir} - \alpha \varsigma _{ij}y_{ijr} - \beta w_{ir} + Q\left( 1 - y_{ijr}\right) \quad \forall j\in V , \forall i\in N , \forall r\in R \mid i\ne j \end{aligned}$$
(4b)
$$\begin{aligned}&b_{jr} + Q\left( 1 - g _{jr}\right) \ge 0.2*Q \quad \forall j\in C , \forall r\in R \end{aligned}$$
(4c)
$$\begin{aligned}&b_{ir} \le Q* g _{ir} \quad \forall i\in V , \forall r\in R \end{aligned}$$
(4d)
$$\begin{aligned}&b_{ir} \le Q*s_{r} \quad \forall i\in V , \forall r\in R \end{aligned}$$
(4e)

The constraint sets (4a)–(4c) track the battery of the DBSs and ensure that the remaining battery level of a DBS is sufficient to proceed to its next destination. Constraint sets (4d) and (4e) provide tracking of the battery level of a DBS for its route if and only if that route is active.

3.1.5 Time Tracking and Balancing Constraints

A Drone Base Station (DBS) has a limited flight time due to its battery capacity, which varies between hovering and flying. To manage this, flight time and time spent at the charging stations are tracked. This tracking ensures synchronized movement of the DBS, balancing hover and flight times. As a result, fair coverage is achieved across areas, with further analysis in Sect. 4.3.

$$\begin{aligned}&\Pi _{init} + \varsigma _{ij}y_{ijr} + w_{ir} - \tau _{jr} - T\left( 1 - y_{ijr}\right) = 0 \quad \forall j\in V , \forall i\in C, \forall r\in R \mid i\ne j \end{aligned}$$
(5a)
$$\begin{aligned}&\tau _{ir} + \varsigma _{ij}y_{ijr} + w_{ir} - \tau _{jr} - T\left( 1 - y_{ijr}\right) = 0 \quad \forall j\in V , \forall i\in N, \forall r\in R \mid i\ne j \end{aligned}$$
(5b)
$$\begin{aligned}&w_{jr} \le T* g _{jr} \quad \forall j\in V , \forall r\in R \end{aligned}$$
(5c)
$$\begin{aligned}&\tau _{ir} \le T* g _{ir} \quad \forall i\in V , \forall r\in R \end{aligned}$$
(5d)
$$\begin{aligned}&w_{jr} = 0 \quad \forall j\in C , \forall r\in R \end{aligned}$$
(5e)
$$\begin{aligned}&\varsigma _{ki}y_{kir} + w_{ir} - \varsigma _{ij}y_{ijr} - w_{jr} + T\left( 2 - y_{ijr} - y_{kir}\right) = 0 \quad \forall j\in N , \forall i, k\in V, \nonumber \\&\forall r\in R \mid \left( i\ne j \right) , \left( i\ne k \right) , \left( j\ne k \right) \end{aligned}$$
(5f)
$$\begin{aligned}&\varsigma _{ki}y_{kir} + w_{ir} - \varsigma _{ij}y_{ijr} - w_{jr} + T\left( 2 - y_{ijr} - y_{kir}\right) - \left( T - \tau _{jr}\right) = 0 \quad \forall j\in C , \forall i, k\in V, \nonumber \\&\forall r\in R \mid \left( i\ne j \right) , \left( i\ne k \right) , \left( j\ne k \right) \end{aligned}$$
(5g)
$$\begin{aligned}&\varsigma _{ki}y_{kir} + w_{ir} - \varsigma _{ij}y_{ijr} - w_{jr} + T\left( 2 - y_{ijr} - y_{kir}\right) \ge 0 \quad \forall i\in N , \forall j, k\in C, \nonumber \\&\forall r\in R \mid \left( j = k \right) \end{aligned}$$
(5h)
$$\begin{aligned}&M*\left( y_{kir}\right) + \left( \varsigma _{ij} - TC\right) *y_{ijr} \ge 0 \quad \forall i\in N , \forall j, k\in C , \forall r\in R \mid \left( j = k \right) \end{aligned}$$
(5i)
$$\begin{aligned}&w_{ir} + T\left( 1 - y_{kir}\right) \ge \varsigma _{uj}y_{ujr} \quad \forall i,u\in N , \forall j, k\in C , \forall r\in R \mid \left( j = k \right) \end{aligned}$$
(5j)

Constraint sets (5a)–(5e) are time tracking constraints that ensure that the maximum allowed cycle time for each route is not exceeded. The time balance constraint sets (5f)–(5h) guarantee continuous and temporal fair coverage by coordinating the movements of the DBS. These constraints are introduced to ensure fairness in the distribution of service levels in areas. The model seeks to maximize hovering time while minimizing travel distances, thereby optimizing routing efficiency. To achieve fairness, the constraints balance hovering times by accounting for the travel times required for drones to reach each area. This ensures coordinated drone movements, guarantees continuous coverage during the handover process, and promotes equitable service distribution across all areas. The constraint sets (5i) and (5j) guarantee only one additional DBS for each active route at the recharge station.

3.1.6 Integrality Constraints

$$\begin{aligned}&x_j \in \{0,1\} \quad \forall j\in N \end{aligned}$$
(6a)
$$\begin{aligned}&l_{ji} \in \{0,1\} \quad \forall i\in C , \forall j\in N \end{aligned}$$
(6b)
$$\begin{aligned}&z_{ij} \in \{0,1\} \quad \forall i,j\in N \end{aligned}$$
(6c)
$$\begin{aligned}&y_{ijr} \in \{0,1\} \quad \forall i,j\in V , \forall r\in R \end{aligned}$$
(6d)
$$\begin{aligned}&g _{jr} \in \{0,1\} \quad \forall j\in V , \forall r\in R \end{aligned}$$
(6e)
$$\begin{aligned}&s_r \in \{0,1\} \quad \forall r\in R \end{aligned}$$
(6f)
$$\begin{aligned}&b_{ir} \ge 0 \quad \forall i\in V ,\forall r\in R \end{aligned}$$
(6g)
$$\begin{aligned}&\tau _{ir} \ge 0 \quad \forall i\in V ,\forall r\in R \end{aligned}$$
(6h)
$$\begin{aligned}&w_{jr} \ge 0 \quad \forall i\in V ,\forall r\in R \end{aligned}$$
(6i)

The constraint sets (6a) and (6i) are integrality definitions of the decision variables.

3.2 Formulation of the Hover Time Maximization Problem

The hover time maximization problem is a reformulation of the coverage maximization problem. In this problem variant, the objective function (1) of the coverage maximization problem is replaced by another objective function (7). It should also be noted that the objective function (1) of the coverage maximization problem is reformulated and added to the hover time maximization problem as a constraint set (8). Thus, the resulting mathematical programming model below is the basic mathematical programming model of the hover time maximization problem.

$$\begin{aligned}&\text {max}\sum _{j=1}^{N}\sum _{r=1}^{R}w_{jr}\end{aligned}$$
(7)
$$\begin{aligned}&\text {Subject to} \nonumber \\&\sum _{i=1}^{N}\sum _{j=1}^{N}z_{ij} \ge \vartheta *\mid V\mid \nonumber \\&\text {Constraints (2a--6i)} \end{aligned}$$
(8)

The objective function (7) maximizes the hover time for each covered disaster area, as the problem considers ensuring continuous network communication. The constraint set (8) ensures that the coverage threshold is met. Constraint sets (2a)–(6i) are the same as above.

4 Computational Study

This section presents detailed analyses of the computational experiments conducted in this study. First, we describe the case study and datasets. Second, we present the experimental results of the MILP models on the instances that were generated based on the case study. Third, we analyze the effect of fairness on the service level. Finally, we analyze the number of drones required by varying the parameters of the problem. All computations are performed on an Intel Core (TM) i5-13600 CPU at 3.50 GHz, 32 gigabytes of RAM, and WINDOWS 64-bit operating system. The MIP models are implemented in Python and are solved using GUROBI 10.0.0.

4.1 Case Study

We present an original dataset for the Bayrakli district of Izmir, Türkiye. One of the main reasons for choosing Bayrakli as a case study is that it was the area most affected by the 2020 Izmir earthquake. Due to the geographical structure of the area, being an old settlement area and irregular urbanization, the impact of such a disaster was devastating. The dataset that we consider particularly covers the eastern part of İzmir, which consists of 34 gathering points with approximately 315,000 people. In addition, three candidate locations of recharging stations are represented among the gathering points, which were randomly chosen from densely populated areas. The main reason for using the small dataset is to evaluate the performance of the models and to analyze the impact of fairness (Refer to Sect. 4.3). The data set consists of GIS data from Izmir Metropolitan Municipality, where the Bayrakli district is considered as a potential disaster area. The refined data includes the number of mobile phone users in the district based on data from GSM operators. According to the Information Technologies and Communications Authority’s annual report [56] the number of mobile users is almost as large as the total population of the city. Since we could not directly access the data on the number of telephone users by district, it may be assumed that the total population of the district gives the number of mobile phone users. The area is divided into 40 hexagonal nodes including recharging stations as recharging stations to deploy the drones for coverage. Figure 2 shows the locations of the disaster areas (hexagons) and the recharging stations for the drones (red points) on the map of Izmir. We analyze the models in terms of the overall performance of each objective function and demonstrate the applicability of the proposed models in a disaster area.

Fig. 2
figure 2

Location of the study area

Full size image

We conduct experiments with one recharging station and ten DBSs. Energy consumption rates for flight and hovering are calculated based on the study by [57]. The total battery energy is calculated based on an equation in [58]. It is set to 107,712 Joules. The length of recharging is set to 5 min [59]. The flight altitude of the drones is set to 100 m, as described in [43]. The optimal solutions and CPU times for the problem are given in Table 2. In the table, “GAP” indicates the optimality gap when the optimal solution cannot be found within the two-hour time limit.

Table 2 MaxCover and MaxHover results for the case study
Full size table

Table 2 provides a comparative analysis of the performance metrics of two objective functions, MaxCover and MaxHover, within the context of the case study. In the solution of MaxCover, the drones choose to cover 34 of the 40 areas and reach approximately 270,000 users with a total hover time of 30 min. Coverage of the 34 disaster areas is found in 1312.17 s, 9 DBSs are used, including three additional DBSs. As the hover time was short, the total energy consumption was mainly influenced by the travel time. On the other side, MaxHover ensures that the balanced hover times on a route where multiple visits occur as well as the longest hover time when a single area visit occurs with a total hover time of 157 min using 8 DBSs. A visual representation of results from a drone routing and coverage optimization case study is demonstrated in Fig. 3. In the figure, the solid and dotted lines (green, black, and blue) represent the flight paths of the drones for three distinct routes (Route-1, Route-2, and Route-3). The numbers adjacent to the drone locations indicate the hover times (e.g., 62, 60, 13), representing the durations that the drones spend servicing each respective location. Coverage areas, indicated by circles, show the areas serviced by each drone while hovering at their assigned locations. For example, the drone servicing the location with a hover time of 62 ensures coverage for adjacent hexagonal cells, without requiring direct flight over each one. This representation highlights the efficient utilization of drones to optimize coverage while adhering to hover time constraints at each service location.

Fig. 3
figure 3

Visualization of the solution for the case problem (Color figure online)

Full size image

However, the number of areas covered is lower than the solution of the first objective while it satisfies the given coverage threshold. This model also reduces the travel time which indicates a more efficient route optimization. On the other hand, if these areas were to be visited as it is in the coverage maximization problem, the total energy consumed would be 221,800 joules. However, MaxHover requires a longer computation time, with a slight deviation from the optimal solution due to the 4.61% GAP. Overall, MaxCover is characterized by lower energy consumption, longer travel time, and an optimal solution, however, this objective function did not ensure fairness in the distribution of hover time between areas visited. On the other hand, MaxHover, despite requiring more computational times and consuming more energy, achieves a higher hovering time and shorter travel time, suggesting it may be better suited for applications where fairness is the primary concern. This comparison highlights the trade-offs between optimizing for coverage and hover time, and how each objective affects the overall system performance.

In addition, since we study the two competing objectives of maximizing the disaster areas covered and maximizing the hover time at each visited area, an analysis of the interaction between these two objectives is of particular interest. Figure 4 shows the interaction between spatial coverage and temporal coverage. Initially, covering more areas yields significant gains in both objectives, as resources are used efficiently. However, beyond a certain point, the marginal increase in spatial coverage leads to a sharper reduction in temporal coverage, reflecting the trade-off between covering more nodes and maintaining sufficient hover time. The steep decline at higher spatial coverage shows that spreading resources too thin reduces temporal coverage, highlighting the need to balance these objectives for an effective and fair solution.

Fig. 4
figure 4

Interaction between two objectives

Full size image

4.2 Experimental Analysis

There is no standard set of benchmark instances in the literature for the DBSARP as this is a new area of research in the literature. A performance analysis is carried out on a generated set of test instances in the range of 20–60 areas based on the case study. The main characteristics of the test instances are presented in Table 3, where instanceno, V, N, C and \(D_{max}\) denote the number of instances, the total number of nodes, the number of disaster areas, the number of charging stations and the maximum number of DBSs in the system, respectively. The models have some parameters to be set according to the problem size. The maximum number of DBSs available in the system is set to 6 DBSs for problems with up to 30 areas and is increased by the number of areas in terms of instance size. Coverage threshold is set to 80% of the disaster areas. The parameters are determined after some preliminary experiments on the test instances.

The experimental analysis concerns the performance evaluation of the MILPs on the test bed of instances in terms of solution time. We analyze the models in terms of the overall performance of each objective function and demonstrate the applicability of the proposed models to serve a larger disaster area. A simple fix-and-optimize (FAO) algorithm is then proposed to tackle the large-size instances. The FAO is a MIP-based improvement heuristic that is developed separately by [60] and [61]. It decomposes the original problem into smaller sub-problems in which some of the decision variables are fixed in value while the rest are optimized. FAO iterates between the fix and optimization phases until an optimal solution is found. In the fix phase of the algorithm, the values of variables \(x_j\) are fixed to the value obtained in the initial solution. Since the decision variables \(z_{ij}\) take its value directly from the decision variables \(x_j\), they are also fixed. In the optimization phase of the algorithm, the MILP model optimizes a subset of the remaining ‘free’ variables. In each iteration, most of the binary assignment variables are set to their fixed values. The results are presented in Table 4 for the models performed by two objective functions and FAO, respectively. The columns of the tables are self-explanatory.

Table 3 Main characteristics of the test instances
Full size table
Table 4 Experimental analysis for the models
Full size table

As can be seen from Table 4, the MILPs can solve the instance with up to 25 areas to optimal for all objectives in less than one minute. The models solve the instances with up to 40 areas to optimal within two hours, while no feasible solution was found by the coverage and hover time maximization models for the instance 7, and only by the hover time maximization model for the instance 6 within two hours. All models also return an "out of memory" for the instance 8. These results demonstrate the limits of the ability of the MILP models to generate solutions. However, real-life problems are on a larger scale. As can be seen from Table 4, for MaxCover, FAO has faster solution times. The algorithm is also able to obtain the best values for the instances 7 and 8. For the instance 6, the FAO improved the solution in a shorter time. For the instances 6 and 7, for which the MaxHover is not able to obtain optimal solutions, the FAO algorithm found feasible solutions in faster solution times. For the instance 8, MaxHover returns an “out of memory” error while the FAO solves these instances within an hour.

We can conclude that the developed MILP models can produce optimal or near optimal solutions for small and medium-size problem instances. On the other hand, when the problem sizes get larger the MILPs lack of providing optimum or feasible solutions in reasonable time limits due to memory limitations. Thus, FAO algorithm can overcome this shortage of the MILPs.

4.3 Impact of Fairness

As outlined in Sect. 3, this section provides an analysis of fair coverage. The main implication of our study is to implement a fair solution. In public safety implementations, achieving a fair solution is essential to increase the effectiveness of safety measures and to promote equitable distribution of resources. This section analyzes the effect of fairness on hover time by balancing it (minimizing the differences) in the areas visited on a route. Table 5 shows the results for a small instance, considering a recharging station and one DBS. In the table, “Visits”, “Cov. areas”, ’Hover time’ and ’Remaining energy’ represent the order of visits on the corresponding route, the number of areas covered by the visited area, the length of time spent in the visited area, and the energy remaining when a DBS arrives at an area, for both cases: the problem with balancing and the problem without balancing. However, as expected, the number of areas covered is the same in both cases, considering that equity leads to an increase in the total number of areas visited. In other words, it does not mean that the people in the area are only reached when the drone is constantly moving. The results reveal that the balancing problem gives a solution where the service reaches the people in the visited areas since there is a positive visit time for each visited area. Another observation from these experiments is that the impact of considering fairness on the hover time is less for the total area covered, the total energy consumed, and the total hovering time. It should be noted here that the results represent only one possible way of analyzing the equity issue, since we consider equity as the duration of each visited area. As fairness is a very important issue in disaster management, this study aims to ensure a fair distribution of hover time to the affected area.

Table 5 Comparison of visits with and without balancing
Full size table

4.4 Analysis on the Number of Drones

In disaster situations, where limited resources must be allocated among the entities, the notion of fairness is crucial. Efficient use ensures that these limited resources are directed to where they are most needed, maximizing their impact. Efficient resource allocation helps ensure that the greatest number of people receive aid and that critical areas are addressed first. We expect our findings to be valuable for decision-makers in promoting equity in public service delivery and the efficient use of available resources.

Therefore, this section provides an analysis of another crucial strategic extension of our problem, where the goal is to determine solutions with the minimum number of drones required to achieve a certain percentage of coverage. Identifying the optimal number of resources is vital for creating an efficient system to prepare for a potential earthquake, while avoiding overspending on the fleet. The inclusion of drones in the necessary fleet enhances the relevance of this extension for practitioners, given that drones are a relatively new technology and may not yet be widely available.

A practical approach to address this extension is to revise the mathematical formulation presented in Sect. 3.1. Specifically, the objective function should be modified to minimize the number of DBSs, and a constraint should be added to ensure a certain percentage of coverage is met. Essentially, the problem of minimizing the number of DBSs can be seen as a reformulation of the problem of maximizing coverage. The objective function (1) from the coverage maximization problem is replaced with an objective function focused on minimizing the number of DBSs, relaxing the constraint set (2d). Subsequently, the objective function (1) from the coverage maximization problem is incorporated as a constraint.

Table 6 shows different scenarios based on the number of recharging stations and the percentage of coverage required. Table 6 summarizes the values of the objective function (total number of drones used), the number of areas covered, and the computation times. The first two columns of table 6 indicate the number of recharging stations (c) and the percentage of coverage (\(\vartheta\)), respectively. Further analysis of the solutions shows that increasing the number of recharging stations generally reduces the number of drones needed for lower coverage percentages (70% and 80%). The CPU time is generally lower with more recharging stations for lower coverage percentages, indicating increased efficiency. As the percentage of coverage increases, the number of drones required increases by an average of 53.6% for each scenario. Higher coverage percentages typically result in more areas being covered. Overall, more recharging stations can lead to more efficient coverage with fewer drones and less CPU time for lower coverage targets, but higher coverage targets significantly increase resource requirements.

Table 6 Results of drone usage with varying parameters
Full size table

5 Conclusion

This study introduced an optimization problem for a communication system enabled by DBSs to provide reliable connectivity under disaster conditions. New MILP formulations with different objectives for the problem have been developed. Optimal DBS allocation consists of determining the hovering locations of the DBSs over the disaster area and keeping them hovering as long as possible to provide fair coverage. Optimal routes for DBSs consist of determining the visit order of these locations and recharging stations. The main aim of the problem is to maximize the total spatial-temporal coverage in all areas while ensuring that the coverage is provided within the given battery limit. The problem was first modeled as a coverage maximization problem, and then its derivation as a hovering time maximization problem was presented. During the Izmir earthquake, the impact of mobile phone signals on search and rescue operations was observed. For this reason, a case study was prepared based on the situation after the earthquake (location of settlements and assembly areas) in the Bayrakli district of Izmir, Türkiye. Different scenarios are generated in terms of charging station locations and coverage rates. Computational experiments were performed on a small dataset to evaluate the performance of the models, to analyze the impact of fairness concerns in the constraints, and to investigate the results under different parametric settings.

The following practical implications have been derived from extensive computational analysis: (i) the balanced hover time model improves fairness and efficiency by ensuring longer and more balanced hover times at each area, which can enhance data collection and user support in disaster areas. (ii) focusing on travel time due to short hover times, the total energy consumption is primarily impacted by travel, suggesting the need for efficient routing to minimize energy usage. The theoretical implications are as follows: (i) the comparison between coverage maximization and hover time maximization highlights the need to balance different objectives, influencing decision-making in disaster response strategies. (ii) ensuring fairness in hover time distribution between areas presents a complex optimization challenge, suggesting avenues for future research on equitable resource allocation. (iii) the solution’s requirement for longer computation time indicates the need for more efficient algorithms to solve such complex problems.

In future research, different objective functions considering fairness can be a promising area to investigate further. Another interesting area of future research may be to consider the uncertainties in the system, such as weather conditions. Finally, more solution approaches could be studied in the future, to solve the large datasets, such as metaheuristics and matheuristics.