Addressing the industry challenges of post-earthquake drone search route planning—which relies on manual experience and suffers from low information collection efficiency—this study conducts specialized research on rapid route planning methods for post-earthquake drone rescue operations to enhance the scientific rigor and efficiency of information gathering. We propose a four-stage technical framework comprising “high-value POI screening—spatial clustering and zoning—rescue priority assessment—ant colony algorithm path optimization”. The key innovations include: (1) screening six categories of high-value POIs characterized by high population density and significant rescue value; (2) employing a two-layer MeanShift-K-means clustering algorithm to partition search and rescue areas and calculating the required number of drones based on dual “area–point” constraints; (3) building upon traditional rescue priority models to construct a multi-indicator rescue priority determination model that integrates both objective and subjective factors, introducing building rescue priority and the number of patrol UAVs as new indicators tailored to drone technology; (4) introducing the ant colony algorithm to optimize flight paths, mapping building rescue priority to pheromone concentration to achieve precise alignment between rescue priority and path planning. Using Fengnan District, Tangshan City as the study area, we selected 1,443 high-value POIs for experimentation. The results demonstrate that the proposed method significantly improves search efficiency and resource allocation for post-earthquake drone technology applications.
1. Post-Earthquake Search and Rescue Area Clustering
1.1 High-Value POI Screening
POIs serve as carriers for precise location descriptions of geographic entities, reflecting urban spatial activity vitality. Following the core principle of “prioritizing areas with high survival probability”, we focus on regions where people are densely gathered and building functions possess rescue value. Six categories of high-value POI types are selected as data sources for drone search tasks: education and culture services (e.g., middle schools, primary schools), medical and health services (e.g., general hospitals, emergency centers), commercial and residential buildings (e.g., office buildings, residential communities), accommodation services (e.g., hotels, inns), shopping services (e.g., supermarkets, shopping malls), and corporate enterprises (e.g., construction companies, pharmaceutical companies). Table 1 lists the detailed classification.
| Major Category | Middle Category | Subcategory Examples |
|---|---|---|
| Education & Culture Services | Schools | Middle schools, primary schools, kindergartens, adult education |
| Medical & Health Services | General hospitals, specialized hospitals, emergency centers | Grade-A tertiary hospitals, orthopedics hospitals, brain hospitals |
| Commercial & Residential | Business parks, buildings, residential areas | Office buildings, dormitories, apartment complexes |
| Accommodation Services | Hotels, inns | Star-rated hotels, budget inns, guesthouses |
| Shopping Services | Supermarkets, shopping malls, markets | Hypermarkets, department stores, furniture centers |
| Corporate Enterprises | Factories, companies | Construction firms, pharmaceutical companies, electronics manufacturers |
1.2 Search Area Partitioning Based on Two-Layer Clustering
To achieve the objectives of “reducing interference from low-density blank areas” and “matching partition size with drone swarm search capability”, we design a MeanShift-Kmeans dual-layer clustering algorithm. The process is carried out in two stages: first, MeanShift performs density-based preliminary clustering to eliminate blank area effects; second, Z-curve-optimized K-means performs secondary clustering to ensure partition size matches drone technology performance.
MeanShift Primary Density Clustering: MeanShift automatically identifies density peaks via kernel density estimation without requiring a preset number of clusters. This data-driven characteristic allows natural adaptation to different building distribution patterns, which is crucial for ensuring no building is missed during earthquake rescue.
Z-Curve Assisted K-means Secondary Clustering: Although primary clustering resolves blank area interference, the resulting clusters may exceed the single-mission capacity of a drone swarm. Therefore, we employ a K-means algorithm with cluster centers determined by Z-curve to ensure uniform spatial distribution. The number of clusters \(K\) is calculated as:
$$ K = \text{round}\left( \frac{S_{\text{total}}}{3 \cdot S_{\text{drone}}} \right) $$
where \(S_{\text{total}}\) is the convex hull area of a single primary cluster, and \(S_{\text{drone}}\) is the planned search area for a single drone swarm (set to 3 drones as the baseline). The drone swarm’s search area is given by:
$$ S_{\text{drone}} = L \times 2 \times \text{GSD} \times \frac{f}{d \cdot \tan(\text{FOV}/2)} $$
Here, \(L\) is the flight distance, GSD is ground sampling distance (should be less than 5 cm for searching an adult), \(f\) is focal length, \(d\) is pixel size, and FOV is camera field of view. With an industrial drone DJI Matrice 300 RTK operating at 17 m/s and 55-minute endurance, we compute:
$$ S_{\text{drone}} = 75900 \times 225 \approx 17.08 \, \text{km}^2 $$
Table 2 summarizes the relevant drone technology parameters used in this calculation.
| Parameter | Value |
|---|---|
| Maximum flight speed (P-mode) | 17 m/s |
| Maximum endurance | 55 min (3,300 s) |
| Camera model | DJI H20T (zoom) |
| Focal length | 60 mm |
| Pixel size | 1.43 μm |
| Field of view (FOV) | 84° |
| Ground sampling distance (GSD) | ≤ 5 cm |
1.3 UAV Quantity Calculation
After secondary clustering, the actual area of each partition may deviate from the theoretical value, requiring precise calculation of the number of drones needed. We propose a dual-constraint method based on “area constraint” and “point number constraint”:
$$ N = \max\left( \left\lceil \frac{S_{\text{zone}}}{S_{\text{drone}}} \right\rceil, \; \left\lceil \frac{P_{\text{zone}}}{P_{\text{max}}} \right\rceil \right) $$
where \(N\) is the number of drones required for a single secondary partition, \(S_{\text{zone}}\) is the total area of the partition, \(P_{\text{zone}}\) is the total number of POI points in the partition, and \(P_{\text{max}}\) is the maximum number of POIs a single drone can search per mission (set to 30). This ensures that rescue tasks match drone technology capabilities while meeting timeliness and data completeness requirements.
2. Rescue Priority Determination Model
2.1 Selection and Determination of Influencing Factors
Based on the well-established three-level evaluation model proposed by Cao et al. (2014), we adapt it to drone technology by replacing, adding, and optimizing indicators. The original model uses “assessment factors” (weight 0.4) and “objective factors” (weight 0.6). We make the following modifications:
- Replacement: Replace “secondary geological hazard risk level” with “terrain”, which directly affects drone flight efficiency and safety.
- Addition: Add “building rescue priority” (quantified by entropy weight method) and “number of inspection UAVs deployed” as new indicators.
- Calculation logic optimization: Change the basic statistical unit from administrative district to secondary cluster partition.
Ten core influencing factors are finally determined. Table 3 lists them with their weights and scoring criteria.
| Level-1 Indicator | Weight (W1) | Level-2 Indicator | Weight (W2) | Scoring Criteria (3–7 or 1–10) |
|---|---|---|---|---|
| Subjective Factors | 0.4 | Intensity (I) | 0.35 | VI=0, VII=1, VIII=2, IX=3, X=4, XI=5 |
| Deaths (D) | 0.20 | 3–7 (normalized) | ||
| Injuries (C) | 0.08 | 3–7 (normalized) | ||
| Number of Inspection UAVs (N) | 0.05 | 1–10 (actual count) | ||
| Building Rescue Priority (K) | 0.09 | 1–10 (weighted average of POI scores) | ||
| Objective Factors | 0.6 | Epicenter Location (L) | 0.05 | 10 if in partition, 0 otherwise |
| Population Density (PD) | 0.03 | 7 if above average, 3 if below | ||
| Distance from Epicenter (S) | 0.04 | 3–7 (normalized inverse) | ||
| Population Aggregation (PA) | 0.06 | 3–7 (normalized) | ||
| Terrain (T) | 0.05 | Plain=1, Hill=2, Mountain=3, Plateau=4 |
The building rescue priority \(K\) for each POI category is computed using the entropy weight method based on four sub-dimensions: population density, population vulnerability, social function urgency, and secondary disaster risk. Table 4 shows the entropy weights for these dimensions.
| Sub-dimension | Information Entropy e | Information Utility d | Weight (%) |
|---|---|---|---|
| Population Density | 0.831 | 0.169 | 21.49 |
| Population Vulnerability | 0.806 | 0.194 | 24.72 |
| Social Function Urgency | 0.747 | 0.253 | 32.30 |
| Secondary Disaster Risk | 0.831 | 0.169 | 21.49 |
The weighted sum yields the comprehensive rescue priority for each POI category, as shown in Table 5.
| POI Category | Score |
|---|---|
| Medical & Health Services | 8.71 |
| Education & Culture Services | 5.85 |
| Accommodation Services | 2.68 |
| Commercial & Residential | 4.31 |
| Corporate Enterprises | 2.46 |
| Shopping Services | 2.61 |
2.2 Model Construction
The rescue priority score for each partition \(i\) is calculated as:
$$ M_i = \sum_{j=1}^{n} (W_1 \times W_2 \times S_j) $$
where \(W_1\) is the level-1 indicator weight, \(W_2\) is the level-2 indicator weight, and \(S_j\) is the score of the \(j\)-th factor. A higher \(M_i\) indicates a higher rescue priority.
3. UAV Path Planning
3.1 Model Formulation
We formulate the path planning problem as a multi-traveling salesman problem (MTSP) with capacity constraints. The optimization objectives are two-fold:
(1) Minimize total flight distance:
$$ \min \sum_{i=1}^{n} \sum_{j=0}^{m} \sum_{k=1}^{m} d_{jk} y_{ijk} $$
(2) Maximize weighted priority coverage:
$$ \max \sum_{j=1}^{m} y_{ij} P_j $$
Subject to the following constraints:
- Endurance constraint: \(\sum_{j=1}^{m} \sum_{k=1}^{m} x_{ijk} \cdot d_{ijk} \leq L_i\), where \(L_i\) is the maximum flight range of drone \(i\).
- Closed path: \(\sum_{j=1}^{m} x_{i,\text{start},j} = \sum_{j=1}^{m} x_{i,j,\text{end}} = 1\).
- Full coverage without repetition: \(\sum_{i=1}^{n} y_{ij} = 1\) for all \(j\).
- Task load: \(\sum_{j=1}^{m} y_{ij} \leq M\), where \(M=30\) is the maximum POIs per drone.
- Load balancing: \(\left| \sum_{i=1}^{n} y_{ij} – \frac{m}{n} \right| \leq \text{round}(0.15 \times \frac{m}{n})\).
- Priority heuristic: The next target is selected as \(\arg\max (P_j \cdot \eta_{jk})\), where \(\eta_{jk}\) is the distance heuristic.
- Communication range: \(\max_{j \in \text{Path}_i} d_{0j} \leq R_{\text{comm}} = 15 \, \text{km}\).
- Time window: \(\sum_{j=1}^{m} \sum_{k=1}^{m} \frac{x_{ijk}d_{jk}}{v_i} + \sum_{j=1}^{m} y_{ij} \cdot t_j \leq T_{\text{max}} = 30 \, \text{min}\).
The search time \(t_j\) for each POI depends on its type and area. Table 6 shows the search time for each category, computed based on typical building footprint and drone scanning speed.
| POI Category | Typical Area (10,000 m²) | Search Time (s) |
|---|---|---|
| Medical & Health Services | 8 | 45 |
| Education & Culture Services | 5 | 38 |
| Accommodation Services | 1 | 6 |
| Commercial & Residential | 6 | 41 |
| Corporate Enterprises | 2 | 9 |
| Shopping Services | 4 | 36 |
The search time is calculated considering straight-line scanning and turning maneuvers:
$$ T_{\text{straight}} = \frac{L \cdot \text{ceil}\left( \frac{L}{W(1-O)} \right)}{V} $$
$$ T_{\text{turn}} = \frac{\pi R_{\text{min}}}{v} $$
$$ R_{\text{min}} = \frac{v^2}{g \cdot \tan(\theta)} $$
where \(L\) is building side length, \(W\) is camera swath width, \(O\) is overlap ratio, \(v\) is drone speed, \(g\) is gravity acceleration (9.8 m/s²), and \(\theta\) is maximum bank angle.
3.2 Model Solution Using Ant Colony Optimization
We select the Ant Colony Optimization (ACO) algorithm to solve the MTSP due to its adaptability to complex constraints and natural generation of closed-loop feasible paths. The key innovation is to map the building rescue priority \(K\) directly onto the pheromone concentration, so that high-priority POIs are visited earlier. The transition probability from node \(j\) to node \(k\) for drone \(i\) is:
$$ p_{jk}^i = \frac{[\tau_{jk}]^\alpha [\eta_{jk}]^\beta}{\sum_{l \in \text{allowed}} [\tau_{jl}]^\alpha [\eta_{jl}]^\beta} $$
where \(\tau_{jk}\) is the pheromone on edge \((j,k)\), initialized proportional to the product of priorities of \(j\) and \(k\), \(\eta_{jk} = 1/d_{jk}\) is the distance heuristic, \(\alpha=2\) (accentuating priority), and \(\beta=3\) (balancing distance). This formulation ensures that drone technology directly ties rescue value to path planning.
4. Scenario Validation
4.1 Parameter Setup
We assume a magnitude 7.5 earthquake at coordinates 117°E, 39°N. The study area is Fengnan District, Tangshan City (117°51’43″–118°25’28″E, 39°11’28″–39°39’28″N), which lies in the active North China seismic belt. We select the DJI Matrice 300 RTK as the experimental drone and the H20T zoom camera for data acquisition. Key parameters are listed in Table 2.
Data filtering yields 1,443 high-value POIs: 25 medical, 527 corporate, 247 shopping, 193 education, 379 commercial/residential, and 72 accommodation. The total convex hull area is 1,774.97 km². After MeanShift clustering, 6 primary partitions are obtained with total area reduced to 1,079.48 km². After K-means secondary clustering, 25 secondary partitions with total area 681.21 km² are generated, achieving a 61.6% reduction in blank area. The results are illustrated in the figure below, which shows the compact and efficient partition structure achieved by the proposed drone technology framework.
4.2 Rescue Priority Evaluation for Sample Partitions
We select the fifth primary cluster (Cluster5) and its four secondary partitions (5-0, 5-1, 5-2, 5-3) for detailed priority calculation. Table 7 lists the raw data for each factor.
| Factor | 5-0 | 5-1 | 5-2 | 5-3 |
|---|---|---|---|---|
| Intensity | 6.46 | 6.38 | 6.30 | 6.23 |
| Total population | 27,615 | 66,707 | 28,967 | 19,521 |
| Administrative level | Town | City | Town | Village |
After applying the scoring and normalization, the final priority scores are computed. Table 8 presents the results.
| Partition | 5-0 | 5-1 | 5-2 | 5-3 |
|---|---|---|---|---|
| Intensity score | 0 | 0 | 0 | 0 |
| Deaths score | 5.13 | 7.00 | 5.26 | 3.00 |
| Injuries score | 4.04 | 7.00 | 4.10 | 3.00 |
| Inspection UAV count | 1 | 2 | 4 | 2 |
| Building rescue priority | 3.54 | 3.65 | 3.45 | 4.48 |
| Epicenter location | 0 | 0 | 0 | 0 |
| Population density | 3.00 | 3.00 | 3.00 | 7.00 |
| Distance from epicenter | 3.00 | 4.22 | 5.52 | 7.00 |
| Population aggregation | 3.38 | 3.00 | 3.38 | 7.00 |
| Terrain (plain=1) | 1 | 1 | 1 | 1 |
| Final score \(M_i\) | 0.60 | 0.74 | 0.72 | 0.90 |
Partition 5-3 obtains the highest score due to its high population density, long distance from the epicenter, and high building rescue priority. This demonstrates that the model effectively distinguishes rescue priorities by integrating subjective and objective factors within the drone technology framework.
4.3 Drone Path Planning Results for a Representative Partition
We select partition “0-4” (one of the 25 secondary partitions) for detailed path planning. This partition contains 99 POI points, and according to the dual-constraint formula, 4 drones are required. Table 9 shows the four generated paths after ACO optimization.
| Parameter | Path 1 | Path 2 | Path 3 | Path 4 |
|---|---|---|---|---|
| Path length (km) | 14.97 | 21.97 | 22.82 | 12.86 |
| Max communication distance (km) | 4.02 | 4.01 | 3.49 | 3.74 |
| Medical POIs | 2 | 0 | 0 | 0 |
| Education POIs | 0 | 8 | 3 | 1 |
| Accommodation POIs | 3 | 0 | 0 | 2 |
| Commercial/Residential POIs | 1 | 6 | 3 | 6 |
| Corporate POIs | 18 | 9 | 13 | 16 |
| Shopping POIs | 2 | 2 | 4 | 1 |
| Flight time (min) | 10.85 | 15.92 | 16.54 | 9.32 |
| Search time (min) | 6.38 | 11.72 | 8.30 | 6.27 |
| Total time (min) | 17.23 | 27.64 | 24.84 | 15.59 |
| Number of POIs covered | 26 | 25 | 23 | 26 |
All paths satisfy the endurance constraint (max distance 22.82 km < 40 km), communication radius constraint (max 4.02 km < 15 km), time window constraint (max 27.64 min < 30 min), and load balancing constraint (POI counts differ by at most 3). High-priority POIs (medical and education) are visited early in the paths, demonstrating the effectiveness of mapping rescue priority to pheromone concentration in drone technology.
4.4 Comparison with Real Earthquake Case
We compare our method with the drone operations during the 2023 Jishishan earthquake in Gansu. In that case, 4 mapping drones flew 17 sorties to survey 32.05 km² in key towns. Our partition 0-4 has a similar area (32.19 km²) and uses the same number of drones (4), but only requires 4 sorties to cover all 99 POIs. Table 10 summarizes the comparison.
| Metric | Jishishan Case (original) | Jishishan (optimized with our method) | Partition 0-4 (our method) |
|---|---|---|---|
| Survey area (km²) | 32.05 | 22.84 | 32.19 |
| Number of drones deployed | 4 | 4 | 4 |
| Number of sorties | 17 | 2 | 4 |
| Number of POIs covered | N/A (manual selection) | 49 | 99 |
| Reduction in sorties vs. original | – | 15 (88%) | 13 (76%) |
The proposed drone technology framework not only reduces blank areas by 61.6% but also dramatically cuts flight sorties by 76–88%, proving its adaptability and efficiency across different regions and earthquake scenarios.
5. Conclusion
This study addresses the difficulty of post-earthquake information collection using drones by proposing a four-stage framework: high-value POI screening, MeanShift-Kmeans dual-layer clustering, multi-factor rescue priority assessment, and ant colony optimization for path planning. The key contributions of our drone technology approach include:
- Targeted data source: Screening six categories of high-value POIs provides a precise “target list” for drones, focusing on areas with highest survival probability.
- Efficient clustering: The dual-layer clustering reduces ineffective area by 61.6% in Fengnan District, from 1,775 km² to 681 km², while the “area–point” dual-constraint formula ensures a closed-loop match between partitions and drone swarm capacity.
- Priority integration: The new rescue priority model incorporates building rescue priority and inspection UAV count, directly linking the decision of “where to rescue” to “where to fly first”.
- Optimized routing: By mapping building priority onto pheromone concentrations in ACO, we achieve a direct binding of rescue value to path planning. In partition 0-4, 4 drones completed 99 POI searches in 4 sorties, reducing sorties by 76% compared to the similar-area real earthquake case in Jishishan.
Future work should incorporate real-time terrain monitoring data (e.g., landslides, dammed lakes) to further refine clustering and path avoidance strategies. Additionally, calibrating population and area assumptions for different cities, and exploring hybrid algorithms (e.g., ACO+GA) could enhance robustness. Overall, this research provides a scientific, efficient, and feasible method for post-earthquake rapid search route planning using drone technology, offering significant practical value for improving rescue efficiency and reducing casualties in low-altitude economy applications.