Traditional fire patrol methods, relying on manual inspections or fixed surveillance cameras, often suffer from inefficiencies, limited coverage, and delayed response times. Firefighting drones, or fire drones, present a transformative potential for urban safety with their high efficiency, low operational cost, and exceptional mobility. To fully leverage fire drones in urban patrols, a core challenge is the development of a rational patrol network plan. Patrol frequency and duration are intrinsically linked to the spatial heterogeneity of fire risk across a city—higher-risk areas demand more vigilant and prolonged surveillance. These requirements, in turn, critically influence the strategic placement of drone launch sites and the design of patrol flight paths. This study investigates the integrated location-routing problem for an urban fire drone patrol network, explicitly incorporating dynamic patrol demands derived from fire risk assessments.
A stable and efficient fire drone patrol network model for urban environments is established. The core problem involves simultaneously determining which fire stations to activate as drone bases (location), designing patrol routes originating from these bases (routing), and scheduling the frequency of each route and the service time at each patrol point. This integrated approach, considering the mutual influence between facility location and vehicle routing, enhances solution feasibility and overall system quality.
1. Determining Patrol Demand Points via Fire Risk Assessment
Patrol requirements are not uniform across the city. To reflect this, a Geographic Information System (GIS)-based fire risk assessment is conducted first, translating spatial risk into quantifiable patrol demand inputs for the optimization model.
The assessment synthesizes multiple data sources related to ignition potential, environmental susceptibility, and potential consequences. Six key risk indicators are evaluated, as summarized in Table 1.
| Risk Indicator | Rationale |
|---|---|
| Population Density | High-density areas increase the likelihood of casualties and secondary incidents like stampedes during a fire evacuation. |
| Nighttime Light Intensity | Areas with intense nighttime lighting often correlate with high commercial activity, nightlife, and concentrated combustible materials, elevating fire exposure risk at night. |
| Fire Station Service Coverage | Areas within quick response reach of fire stations have higher rescue success rates; inaccessible areas face greater probability of fire spread and loss. |
| High-Risk Buildings | Structures like historical buildings, chemical plants, or large malls have high fire loads and potential for catastrophic casualties. |
| Building Height | High-rise buildings pose significant challenges for firefighting and require longer evacuation times. |
| Building Age | Older buildings often have lower fire resistance ratings, aging electrical wiring, and a higher likelihood of unauthorized modifications. |
Data for these indicators are gathered from multiple sources including Points of Interest (POI) databases, OpenStreetMap, population census grids, and official lists of high-risk fire units. Using GIS software, each indicator layer is classified into five risk levels. These layers are then weighted and overlaid using a natural breaks classification method to generate a composite fire risk map with five distinct zones (Level 1 being lowest risk, Level 5 highest).
This risk map is subsequently rasterized, with the cell size varying according to risk level to ensure finer surveillance in higher-risk areas: Level 5 (800m x 800m), Level 4 (1000m x 1000m), Level 3 (1200m x 1200m), Level 2 (1400m x 1400m), and Level 1 (1600m x 1600m). The centroid of each resulting grid cell is extracted to form the set of patrol demand points, \(I\), each with an associated fire risk level.
2. Fire Risk-Adaptive Drone Location-Routing Model
Given the set of patrol demand points \(I\) and a set of candidate launch sites at existing fire stations \(S\), the model aims to design patrol routes \(R\) for a homogeneous fleet of fire drones. The model is a Mixed-Integer Quadratically Constrained Programming (MIQCP) model, as the product of patrol frequency and service time introduces quadratic terms.
2.1 Assumptions and Notation
The model is based on the following key assumptions: 1) All fire drones are identical in specifications (speed, battery). 2) External weather impacts on flight energy consumption are negligible for planning purposes. 3) Fire risk levels and associated patrol demands are stable within the planning horizon. 4) The drone is considered to be in flight while performing its surveillance pattern within a grid cell; service time is thus part of the flight phase.
The main sets, variables, and parameters are defined below.
| Category | Symbol | Description |
|---|---|---|
| Sets | \(I\) | Set of patrol demand points, indexed by \(i\) or \(j\). |
| \(H \subset I\) | Set of high-risk demand points, indexed by \(h\). | |
| \(S\) | Set of candidate drone launch sites (fire stations), indexed by \(s\). | |
| \(R\) | Set of patrol routes, indexed by \(r\). | |
| Variables | \(x_{ijr} \in \{0,1\}\) | Equals 1 if route \(r\) travels from point \(i\) to point \(j\). |
| \(A_r \in \{0,1\}\) | Equals 1 if route \(r\) is activated. | |
| \(B_s \in \{0,1\}\) | Equals 1 if launch site \(s\) is activated. | |
| \(P^{max}\) | Maximum completion time among all routes (minutes). | |
| \(T_{ir}\) | Single-visit patrol time at demand point \(i\) on route \(r\) (minutes). | |
| \(F_r\) | Patrol frequency of route \(r\) (sorties/minute). | |
| \(P^{in}_{ir}, P^{out}_{ir}\) | Remaining flight time upon arrival/departure at point \(i\) on route \(r\). | |
| \(T_r\) | Total patrol time for route \(r\) (minutes). | |
| \(R^{ed}\) | Total patrol demand redundancy for high-risk points. | |
| Parameters | \(C^r, C^s, C^c\) | Fixed cost for a route, a launch site, and a charging event, respectively. |
| \(C^e\) | Energy cost per minute of flight ($/kW·min). | |
| \(\mu_i\) | Patrol demand for point \(i\) (time fraction). | |
| \(l_i, u_i\) | Min./max. single-visit patrol time at point \(i\) (minutes). | |
| \(q\) | Drone endurance/battery life (minutes). | |
| \(t_{ij}\) | Flight time from point \(i\) to \(j\) (minutes). | |
| \(\omega\) | Conversion factor from per-minute to weekly cost (\(\omega \approx 410\)). | |
| \(v, m\) | Drone speed (km/h) and mass (kg). | |
| \(g, \phi, \sigma\) | Gravity, powertrain efficiency, and lift-to-drag ratio. | |
| \(\alpha, \beta, \gamma\) | Weight coefficients for the multi-objective function. |
2.2 Model Formulation
The model has three objectives, combined into a single weighted objective function for minimization.
1) Minimize Total Weekly Cost: Includes fixed costs for routes and launch sites, charging/maintenance costs, and energy costs.
$$f_1 = \omega \left[ \sum_{r \in R} A_r C^r + \sum_{s \in S} B_s C^s + \sum_{r \in R} F_r C^c + \sum_{r \in R} F_r T_r \left( C^e + \frac{mgv}{370\phi\sigma} \right) \right]$$
The last term calculates energy cost per minute based on the power required for steady flight.
2) Minimize Maximum Patrol Completion Time: To free up drone resources quickly.
$$f_2 = P^{max}, \quad \text{where } P^{max} = \max_{r \in R} \{ T_r \}$$
3) Maximize Safety Coverage for High-Risk Areas: Expressed as minimizing the negative of the total patrol demand redundancy \(R^{ed}\) for high-risk points \(h \in H\). Redundancy is the excess patrol time provided beyond the minimum demand.
$$f_3 = -R^{ed}, \quad \text{where } R^{ed} = \sum_{h \in H} \left( \sum_{r \in R} T_{hr} F_r – \mu_h \right)$$
The combined objective function is:
$$\min f = \alpha f_1 + \beta f_2 + \gamma f_3$$
The model is subject to the following key constraints:
Drone Endurance & Path Flow:
$$P^{in}_{ir} \leq P^{out}_{ir} – T_{ir} + t_{ij} – (1 – x_{ijr})q, \quad \forall i,j \in I \cup S, i \neq j, r \in R$$
$$P^{out}_{sr} = q B_s, \quad \forall s \in S, r \in R$$
$$0 \leq P^{out}_{ir} \leq q, \quad \forall i \in I \cup S, r \in R$$
$$T_r \geq q – P^{out}_{sr}, \quad \forall s \in S, r \in R$$
$$\sum_{i \in S} \sum_{j \in I} x_{ijr} = A_r, \quad \sum_{i \in I} \sum_{j \in S} x_{ijr} = A_r, \quad \forall r \in R$$
$$\sum_{i \in I} x_{isr} = \sum_{j \in I} x_{sjr}, \quad \forall s \in S, r \in R$$
$$\sum_{j \in I \cup S} x_{ijr} = \sum_{j \in I \cup S} x_{jir}, \quad \forall i \in I, r \in R$$
These constraints manage battery state-of-charge, ensure routes start and end at the same active launch site, and maintain path continuity.
Patrol Demand Satisfaction:
$$\sum_{r \in R} T_{ir} F_r \geq \mu_i, \quad \forall i \in I$$
$$l_i \sum_{r \in R} \sum_{j} x_{ijr} \leq T_{ir} \leq u_i \sum_{r \in R} \sum_{j} x_{ijr}, \quad \forall i \in I, r \in R$$
Constraint (16) ensures the total patrol time at each point meets its demand. Constraints (17-18) bound the single-visit patrol time based on the point’s risk level and area.
Logical & Redundancy Constraints:
$$B_s \geq x_{isr}, \quad \forall i \in I, s \in S, r \in R$$
$$A_r \geq F_r / M, \quad \forall r \in R$$
$$A_r T_r \leq P^{max} \leq q, \quad \forall r \in R$$
$$R^{ed} \geq 0$$
Constraints (19-20) link activation variables. Constraint (21) defines the maximum completion time. Constraint (22) ensures redundancy is non-negative.
3. Solution Algorithm: Adaptive Large Neighborhood Search (ALNS)
The problem is decomposed. The main problem (determining \(B_s, A_r, x_{ijr}\)) is solved using an ALNS metaheuristic. A sub-problem (determining \(F_r, T_{ir}\) for a given route \(r\)) is solved exactly within the ALNS framework.
3.1 Solving the Sub-problem: For a given route \(r\) with points \(i \in I_r\), demands \(\mu_i\), and bounds \(l_i, u_i\):
- Check feasibility: If \(\sum t_{ij} + \sum l_i > q\), the route is infeasible.
- Generate an initial solution: Set initial frequency \(F_r^{init} = \max_i (\mu_i / u_i)\). Calculate initial \(T_{ir} = \mu_i / F_r^{init}\). If \(\sum T_{ir} + \sum t_{ij} \leq q\), this is optimal.
- If infeasible, fix points where \(T_{ir} < l_i\) to \(T_{ir} = l_i\), subtract their time from the usable battery budget \(t_{use}\), and remove them from the list.
- Recalculate for remaining points: \(F_r^{new} = \sum \mu_i / t_{use}\), \(T_{ir}^{new} = \mu_i / F_r^{new}\). If any \(T_{ir}^{new} < l_i\), return to step 3. Otherwise, the solution is optimal.
3.2 ALNS for the Main Problem:
- Initial Solution: A greedy heuristic activates the launch site with the most unserved demand points nearby and constructs routes by sequentially inserting the closest feasible demand point until battery limits are reached.
- Destroy Operators: Partially destroy the current solution. Operators include: Random Removal, Worst-Cost Removal, Route Removal, Launch Site Removal, and Geographic Cluster Removal.
- Repair Operators: Reinsert removed points into the partial solution. Operators include: Random Insertion, Greedy Insertion (minimizes cost increase), and Regret-2 Insertion.
- Adaptive Mechanism & Acceptance: Operator selection probabilities are updated based on their historical performance using a roulette-wheel principle. A simulated annealing criterion accepts worsening solutions early in the search to escape local optima. The algorithm iterates between destroy and repair until a maximum iteration count is reached.
4. Case Study: Central Tianjin, China
The model is applied to the six central districts of Tianjin (area: 195 km²). Fire risk assessment yielded 141 patrol demand points across five risk levels.
4.1 Parameter Setting & Algorithm Validation
Drone parameters are based on a commercial model (e.g., weight \(m=2\) kg, speed \(v=30\) km/h, endurance \(q=46\) min). Cost and algorithm parameters are set as in Table 3.
| Parameter | Value | Parameter | Value |
|---|---|---|---|
| \(\alpha, \beta, \gamma\) | 0.5, 0.3, 0.2 | \(C^r, C^s\) | $20,000, $50,000 |
| \(C^c, C^e\) | $15, $1.8/kW·min | ALNS Iterations | 5000 |
| \(\phi, \sigma\) | 0.5, 3 | SA Cooling Rate | 0.999 |
Small-scale tests (3-15 demand points) comparing ALNS to the exact solver Gurobi showed ALNS found solutions within 2% of optimality but was significantly faster (2.33s vs. 142.8s for the largest test). Further comparison with Genetic Algorithm (GA), Particle Swarm Optimization (PSO), and Ant Colony Optimization (ACO) on a 40-point problem confirmed ALNS’s superior solution quality and robustness.
4.2 Results and Sensitivity Analysis
Patrol demands \((\mu_i)\) and time bounds \((l_i, u_i)\) were set proportional to risk level. The ALNS algorithm converged stably around iteration 1100. The optimal solution activated 24 out of 45 candidate fire stations as drone launch sites and designed 63 distinct patrol routes, with a total weekly cost of approximately $4.30 million.
Sensitivity Analysis:
1) Impact of Drone Endurance (\(q\)): Increasing endurance from 46 to 85 minutes significantly reduced system scale and cost, as shown in Table 4.
| Endurance (min) | Activated Launch Sites | Number of Routes | Total Weekly Cost |
|---|---|---|---|
| 46 | 24 | 63 | $4.30M |
| 65 | 18 | 42 | $3.78M |
| 85 | 14 | 29 | $3.43M |
2) Impact of Patrol Demand (\(\mu_i\)): Higher patrol demands (e.g., increasing Level 5 demand from 0.3 to 0.5) led to a 64.5% cost increase. The number of launch sites and routes remained relatively stable, but the average patrol frequency \(F_r\) of routes increased by 123.8% to meet the heightened surveillance requirements.
3) Impact of Single-Visit Patrol Time Bounds (\(l_i, u_i\)): Increasing the required minimum patrol time per visit directly increased system complexity. Adding just 2 minutes to both \(l_i\) and \(u_i\) caused the number of activated launch sites to rise by 129.4% and routes by 93.3%, with cost increasing by 33.2%. Concurrently, the average patrol frequency decreased by 88.4%, as each visit consumed more of the drone’s battery budget.
5. Conclusion
This study developed an integrated location-routing model for an urban fire drone patrol network that explicitly incorporates spatially differentiated fire risk. The MIQCP model co-optimizes drone base location, patrol routing, frequency, and dwell time to minimize cost and completion time while maximizing surveillance in high-risk zones. The proposed ALNS algorithm effectively solves this complex problem, outperforming other common metaheuristics in solution quality.
The case study of central Tianjin demonstrates the model’s practicality, generating a specific patrol plan requiring 24 launch sites and 63 routes. Sensitivity analyses provide critical insights: enhancing fire drone endurance offers significant cost and infrastructure savings, while increased patrol demands or longer per-visit times substantially raise operational costs and network complexity. This model provides a scientifically grounded decision-support tool for fire departments planning the deployment of fire drone fleets, moving beyond traditional methods towards intelligent, risk-adaptive urban safety management.
Future work will address current limitations, such as incorporating detailed 3D urban obstacles (e.g., high-rise buildings) for precise path planning and modeling dynamic energy consumption due to wind and complex maneuvers, further enhancing the realism and applicability of the fire drone patrol network design.