Energy-Efficient Multi-Unmanned Aerial Vehicle Path Planning: A Comparative Study of Random, Greedy, and Clustering Strategies

The coordination of multiple autonomous agents serving spatially distributed tasks represents a fundamental problem in computational optimization and engineering systems [1]. Such problems arise in many applications, including robotic swarms for monitoring tasks [2], decentralized drone networks [3], and cooperative Unmanned Aerial Vehicle (UAV) operations in dynamic environments [4]. In these scenarios, agents must cooperatively plan routes that minimize operational cost while satisfying practical constraints, most notably limited onboard energy resources [5]. From a computational perspective, these problems are commonly formulated as variants of the Multiple Traveling Salesman Problem (mTSP) or the Vehicle Routing Problem (VRP). Both formulations are NP-hard and become increasingly difficult to solve optimally as the system scale grows [6], [7].

A representative instance of this problem arises in cooperative multi-UAV data-collection missions. In such missions, UAVs must visit spatially distributed sensing locations, referred to as Points-of-Interest (PoIs), while operating under strict energy and time constraints. The use of multiple UAVs enables parallel sensing operations and improved spatial coverage. However, it also introduces coordination challenges related to task allocation, route planning, and energy management.

Among these challenges, path planning plays a critical role because the trajectories followed by UAVs directly determine travel distance, energy consumption, and overall mission feasibility. For battery-powered UAVs, limited onboard energy capacity imposes strict constraints on operational endurance and safety margins. Energy consumption in UAV missions depends not only on travel distance but also on mission-phase energy demands associated with sensing, communication, hovering, and control subsystems. Consequently, routing strategies that optimize geometric distance alone may not necessarily minimize total mission energy.

Due to the computational complexity of multi-UAV routing problems, heuristic methods are widely adopted in practice. Existing heuristic approaches can generally be categorized into two paradigms. The first paradigm focuses on route-driven optimization, where UAV trajectories are constructed directly by minimizing distance-related metrics, such as Greedy nearest-neighbor routing or simplified Traveling Salesman Problem (TSP) heuristics [8]. These methods are computationally efficient and often produce short travel distances. However, they may lead to imbalanced workload allocation, particularly when the UAV fleet size exceeds the effective task density.

The second paradigm follows a cluster-first, route-second strategy [9]. In this approach, sensing tasks are first partitioned into spatial clusters using algorithms such as K-Means [10], [11], [12], and routes are subsequently constructed within each cluster. This paradigm improves spatial organization and workload balance across UAVs, making it particularly suitable for large-scale missions. However, clustering methods typically optimize cluster compactness rather than global routing efficiency. As a result, they may produce longer travel distances or higher energy consumption, especially when cluster boundaries are misaligned with the Base Station (BS) location or when the UAV density is high.

Despite extensive research on UAV path planning and energy-aware routing, two important research gaps remain. First, many studies implicitly assume that minimizing travel distance is equivalent to minimizing energy consumption. Several frameworks model propulsion energy as directly proportional to travel distance [13], or treat energy as a cumulated routing cost within heuristic and genetic optimization schemes [14]. Similarly, many recent path planning studies explicitly assume that reducing flight distance is the primary mechanism for improving energy efficiency [15], [16]. However, propulsion-aware analyses demonstrate that UAV energy consumption is inherently nonlinear and influenced by multiple flight dynamics factors [17]. This requires the simultaneous consideration of trajectory, velocity, and mission-phase energy components [18]. Empirical studies further demonstrate that minimum-distance trajectories may deviate from energy-optimal solutions by approximately 10–15% [19]. Therefore, the common assumption that distance minimization guarantees energy minimization requires further investigation under realistic mission-level energy models.

Second, although both cluster-based and route-driven heuristics have been widely studied, controlled comparisons under a unified energy-consumption framework remain limited. Cluster-based strategies typically focus on workload balancing and network lifetime [20], [21], whereas route-driven approaches emphasize geometric efficiency. Because these approaches are often evaluated under heterogeneous experimental assumptions, direct comparisons between them remain difficult.

Motivated by these limitations, this paper presents a comparative study of three representative routing strategies for energy-aware multi-UAV data-collection missions: Random assignment, Greedy nearest-neighbor routing (Greedy), and Greedy routing assisted by K-Means clustering (Greedy + K-Means). Rather than proposing a new algorithm, this study aims to systematically analyze the trade-offs among geometric efficiency, energy consumption, and workload distribution under controlled multi-UAV simulation conditions.

Accordingly, this study addresses the following research question: To what extent does explicit spatial task partitioning improve energy efficiency and workload balance compared with route-driven routing strategies in multi-UAV data-collection missions?

The main contributions of this work are threefold:

• A unified mission-level evaluation framework that integrates multi-UAV path planning and data collection under a modular, phase-based energy consumption model.

• A controlled comparative analysis of route-driven and cluster-driven heuristics across different spatial layouts and fleet sizes.

• A regime-aware engineering decision framework that translates statistical findings into practical routing-strategy selection guidelines.

By clarifying the strengths and limitations of commonly used heuristics, this study contributes to a more nuanced understanding of energy-efficient multi-UAV path planning and highlights the importance of evaluating routing strategies not only in terms of geometric efficiency but also in relation to mission-level energy behavior and workload balance.

This section describes the computational framework used to evaluate energy-efficient multi-UAV data-collection strategies. The study adopted a simulation-based experimental methodology in which UAVs collected sensing data from spatially distributed PoIs. The proposed framework integrated a physically motivated energy consumption model with heuristic routing algorithms under controlled simulation conditions. All routing strategies were evaluated using identical system parameters, spatial layouts, and statistical protocols. This unified framework enabled the isolation of algorithmic effects from environmental variability and ensured fair and reproducible comparison. The objective was to systematically investigate how different routing paradigms influenced travel distance, energy consumption, and workload distribution in cooperative UAV missions.

A cooperative multi-UAV data-collection mission was considered within a 1000 $\times$ 1000 m rectangular area. A set of PoIs, denoted by $\mathcal{P}=\left\{p_1, p_2, \ldots, p_N\right\}$, was deployed within the mission area. Each PoI represented a sensing location that had to be visited exactly once by a single UAV. A fleet of homogeneous UAVs was denoted by $U=\{1,2, \ldots, U\}$. All UAVs were assumed to depart from a common Base Station (BS) and to return to the BS upon completing their assigned tasks.

Homogeneity in kinematic capabilities and energy parameters was assumed across all UAVs to ensure that performance differences among routing strategies arose solely from coordination mechanisms rather than from hardware-induced bias. Each UAV was assumed to operate at a fixed cruising altitude and to follow piecewise-linear trajectories between PoIs under constant-speed horizontal motion.

To investigate the influence of spatial task distribution, two PoI layout configurations were considered (Figure 1): (i) a grid PoI layout, representing structured sensing missions such as photogrammetry or systematic area coverage, and (ii) a random PoI layout, representing spatially heterogeneous sensing environments where sensing tasks are irregularly distributed.

In addition to the system configuration described above, basic safety and communication mechanisms were incorporated into the simulation environment. A reactive collision-handling mechanism was implemented to prevent unsafe inter-UAV proximity by adjusting UAV positions when a predefined safety threshold was exceeded. In the event of severe collisions, the affected UAV mission was terminated.

The energy consumption of each UAV was modeled based on the fundamental physical principle that energy equals the time integral of power [22]. To enable numerical simulation, the continuous-time energy formulation was discretized into uniform time slots of duration $\Delta t$. Let $P_i(t)$ denote the instantaneous power consumption associated with the mission phase $i$, and let $T$ denote the total mission duration. The energy consumed during the phase $i$ was computed according to Eq. (1):

where, $P_i^{(j)}$ denotes the power level during slot $j$, and $t_i{ }^{(j)} \leq \Delta t$ represents the effective duration of phase $i$ within that slot.

Following the modeling approach in [23], the total energy consumption of a UAV during a mission was defined as the aggregation of the six principal components, as expressed in Eq. (2):

where, each component corresponds to take-off, horizontal propulsion, hovering, sensing, data transmission, and landing energy, respectively. All energy components are expressed in Joules. At the beginning of the mission, each UAV was assumed to be equipped with an initial energy $E_u^{\text {init}}$. The mission was executed until the assigned tasks were completed or the remaining energy dropped below the safety threshold $E_u^{\text {th}}$.

Compared with simplified distance-based energy models, the proposed phase-based formulation explicitly captures mission-dependent energy expenditures such as sensing and communication, which are critical in datacollection scenarios. This formulation enables a more faithful evaluation of routing strategies at the mission level while retaining computational efficiency.

Although routing decisions were formulated primarily in terms of travel distance, the evaluation remained explicitly energy-aware. Distance minimization was the routing objective, and total mission-level energy consumption was the primary performance metric under the adopted phase-based model. This approach allows physically meaningful assessment of routing strategies without introducing excessive model complexity.

The take-off phase corresponds to the UAV's vertical ascent from the BS to the designated cruising altitude. The energy consumed by UAV $u$ during take-off is expressed in Eq. (3):

where, $P^{\text {to}}$ denotes the take-off power and $t^{\text {to}}$ represents the take-off duration. Assuming a constant take-off velocity $v^{\text {to}}$ and a fixed cruising altitude $h$, the take-off time is given by $t^{\text {to}}=h / v^{\text {to}}$. The global environmental and UAV system parameters adopted in this study are summarized in Table 1.

After reaching the cruising altitude $h$, the UAV moves horizontally towards a target location, which may correspond either to a PoI or to the BS during the return phase. Horizontal motion is assumed to occur at a constant horizontal velocity $v^{\text {prop}}$. The propulsion energy of UAV $u$ is expressed in Eq. (4):

where, $P^{\text {prop}}$ denotes the propulsion power during horizontal flight. The total horizontal flight time is defined as $t_u^{\text {prop}}=d_u^{\mathrm{hz}} / v^{\text {prop}}$, where $d_u^{\mathrm{hz}}$ represents the total horizontal travel distance of UAV $u$.

Hovering energy represents the power required to maintain a stationary position during periods in which the UAV is not performing translational motion. Such periods include sensing and data transmission operations. While sensing and transmission energies are accounted for separately, hovering energy represents the baseline power consumption during all non-motion intervals.

Let $t_u^{\text {hov}}(j)$ denote the total non-motion time of UAV $u$ in slot $j$. The hovering energy is therefore computed in Eq. (5):

Sensing energy corresponds to the power consumed by onboard sensors (e.g., cameras or data-acquisition electronics) during data acquisition at Pols. Within the simulation framework, sensing is performed whenever the UAV is located within the predefined sensing radius of a PoI. Specifically, when the Euclidean distance between UAV $u$ and PoI $n$ is less than or equal to the sensing range $r^{\text {sens}}$, the sensing module is activated. Data acquisition is then performed during the available non-motion time within the time slot.

Let $t_u^{\text {rem},(j)} \leq \Delta t$ denote the remaining non-motion time of UAV $u$ in slot $j$. Given a sensing rate $\rho^{\text {sens}}$ (Mbps), the maximum amount of data that can be sensed in slot $j$ is computed in Eq. (6):

The actual sensed data volume is expressed in Eq. (7):

where, $D_n^{\text {rem,}(j)} \leq D_n^{\text {req}}$ denotes the remaining data at PoI $n$ in slot $j$. All data volumes are expressed in bits. The effective sensing time is then computed using Eq. (8):

The total sensing energy is therefore obtained in Eq. (9):

where, $P^{\text {sens}}$ denotes the sensing power.

After sensing, the collected data are transmitted from the UAV to the BS through an air-to-ground (A2G) wireless link. The A2G channel was modeled using an elevation-angle-dependent probabilistic line-of-sight (LoS) formulation combined with free-space path loss, excess non-LoS attenuation, and log-normal shadowing. This probabilistic abstraction follows widely adopted UAV communication models and is consistent with 3GPP-inspired aerial channel characterization principles [24], [25].

Let $P^{\mathrm{tx}}$ denote the transmission power. The total transmission energy consumed by UAV $u$ during the mission horizon is expressed in Eq. (10):

where, $t_u^{\mathrm{tx},(j)}$ denotes the transmission duration in slot $j$. The transmission duration is computed according to Eq. (11):

where, $D_u^{\operatorname{del},(j)}$ represents the successfully delivered data in slot $j$, and $\rho_u^{\operatorname{com},(j)}$ denotes the instantaneous communication data rate. The signal-to-interference-plus-noise ratio (SINR) is defined in Eq. (12):

where, $G^{\mathrm{tx}}$ and $G^{\mathrm{rx}}$ denote the linear antenna gains of the UAV and BS, respectively; $F_u^{(j)}$ is the small-scale fading power gain; $P L_u^{(j)}$ is the large-scale path loss, including shadowing, and excess NLoS loss expressed in decibels (dB); $P^{\text {noise }}$ is the total receiver noise power over the communication bandwidth; and $I_u^{(j)}$ is the aggregate interference power.

The achievable communication data rate is then obtained from the Shannon capacity formulation in Eq. (13):

where, $B_w$ denotes the communication bandwidth and $\beta \in(0,1]$ represents implementation efficiency.

The landing phase corresponds to the UAV's controlled descent from cruising altitude back to the BS. Assuming a constant landing velocity $v^{\text {land}}$, the landing duration is defined as $t^{\text {land}}=h / v^{\text {land}}$. The landing energy is therefore computed in Eq. (14):

where, $P^{\text {land}}$ denotes the landing power.

The routing problem considered in this study can be formulated as a cooperative multi-agent task allocation and path-planning problem. A set of autonomous agents must service spatially distributed tasks while minimizing operational cost under resource constraints. In the present study, the agents correspond to UAVs, and the tasks correspond to spatial PoIs that require data collection. Each UAV $u \in U$ is assigned an ordered route defined in Eq. (15):

where, $\mathbf{p}_{u, i} \in \mathcal{P}$, and $k_u=\left|\mathcal{P}_u\right|$ denotes the number of PoIs assigned to the UAV $u$. The value of $k_u$ may vary across UAVs, allowing unequal task allocation and enabling the analysis of workload balance among agents.

The primary optimization objective is to minimize the total traveled distance as expressed in Eqs. (16)-(18):

Subject to:

where, $d_u$ denotes the total travel distance of the route $R_u$, including both departure from and return to the BS. This formulation captures the essential characteristics of cooperative multi-agent routing while remaining specialized for energy-aware multi-UAV data-collection missions.

To evaluate the impact of different task allocation and routing mechanisms on energy consumption, three heuristic routing strategies were considered: Random assignment, Greedy nearest-neighbor routing, and clustering-assisted Greedy routing. For clarity, the three routing strategies are hereafter referred to as Random assignment, Greedy routing, and Greedy + K-Means clustering throughout the remainder of the paper. These strategies represent progressively increasing levels of spatial awareness and routing coordination. All strategies were implemented under identical system assumptions and energy models to ensure a fair and controlled comparison.

Random assignment was used as a baseline and does not explicitly optimize any cost function. In this approach, PoIs were randomly permuted and sequentially assigned to UAVs in a round-robin manner. The visiting order of PoIs for each UAV was therefore randomized, without regard to spatial proximity or travel costs.

Because it does not incorporate distance-aware decision-making, this strategy typically results in long travel distances and correspondingly high energy consumption. Consequently, it represents an uncoordinated routing approach with minimal computational overhead and serves as a lower-bound reference for performance comparison.

In Greedy routing, UAV routes were constructed using a global nearest-neighbor heuristic that explicitly accounts for spatial distance. At each assignment step, the pair consisting of a UAV and an unvisited PoI that yields the minimum incremental travel distance was selected. The incremental distance was measured as the Euclidean distance between the UAV's current position and the candidate PoI. Formally, the Greedy selection rule is expressed in Eq. (19):

where, $\mathbf{x}_u=\left(x_u, y_u, h\right)$ denotes the current position of the UAV $u$, and $\mathbf{p}_n$ denotes the spatial coordinate of Pol $n$.

This selection process was repeated iteratively until all PoIs were assigned. To avoid degenerate solutions in which some UAVs remain idle, a minimum task assignment constraint was enforced. Specifically, when the number of PoIs exceeded the number of UAVs, each UAV was allocated at least one PoI.

Although the Greedy strategy does not explicitly minimize the global tour length, the stepwise minimization of incremental distance often produces relatively short overall travel distances. This behavior is particularly evident in environments with relatively uniform spatial distributions.

Greedy + K-Means clustering follows a two-stage routing framework. In the first stage, PoIs were partitioned into U clusters using the K-Means algorithm, where U represents the number of available UAVs. The clustering process minimizes the within-cluster sum of squared distances to generate spatially compact clusters. The clustering objective is defined in Eq. (20):

where, $\boldsymbol{\mu}_{\ell_n}$ denotes the centroid of the cluster assigned to PoI $\mathbf{p}_n$. In the second stage, each UAV was assigned to one cluster, and its route was constructed using a Greedy heuristic restricted to the PoIs within that cluster. By limiting routing decisions to a predefined subset of PoIs, spatial partitioning was enforced, and workload balance across UAVs was promoted.

Notably, Greedy + K-Means clustering does not directly optimize total travel distance or total energy consumption. Instead, cluster compactness is optimized during the first stage, while incremental intra-cluster travel distance is minimized during the second stage. Consequently, although this approach improves the structural organization of task allocation, global routing optimality may be reduced in certain spatial configurations.

Overall, Greedy + K-Means clustering follows a cluster-first, route-second paradigm in which spatial decomposition precedes route construction. This paradigm promotes scalability, modularity, and improved workload balance, making it suitable for large-scale sensing missions. However, since the clustering stage is agnostic to the BS location and to inter-cluster routing dependencies, the resulting routes may not achieve the globally minimal travel distance compared with purely route-driven heuristics.

Computational experiments were conducted using numerical simulations with a fixed number of PoIs (N = 100) and varying numbers of UAVs (U = 1–10). Two spatial deployment scenarios were evaluated: a grid-based layout representing structured sensing environments and a random layout representing spatially heterogeneous missions. For each fleet size and layout configuration, 20 independent episodes were executed. Distinct random seeds were generated for each episode to account for stochastic variability in Random assignment and K-Means initialization.

All routing strategies were evaluated under identical system parameters, UAV physical constants, communication settings, and a common phase-based energy model to ensure methodological consistency and a fair comparison. Within each episode, identical random-seed settings were applied across routing strategies to enable paired statistical analysis and isolate algorithmic effects.

Performance was evaluated using three primary measurable observables: (i) total travel distance, (ii) total energy consumption, and (iii) workload distribution across UAVs. These quantities were treated as experimentally observable outputs of a controlled computational system rather than abstract algorithmic indicators. Each reported value was the outcome of a statistically replicated, seed-controlled simulation run. The simulation environment was designed to emulate repeatable experimental conditions through fixed parameter configurations, deterministic execution, controlled seed policies, and replicated mission episodes.

The computational complexity of the evaluated routing strategies differs across paradigms. Random assignment requires a single permutation of PoIs and sequential allocation, resulting in linear complexity $\mathcal{O}(N)$. The Greedy routing strategy performs iterative pairwise distance evaluations across UAV-PoI combinations, yielding approximately $\mathcal{O}\left(U \cdot N^2\right)$ complexity in the worst case. The Greedy + K-Means clustering introduces an initial K -Means partitioning stage with complexity proportional to $\mathcal{O}(k \cdot N \cdot i)$, where $k=U$ is the number of clusters and $i$ is the number of clustering iterations, followed by intra-cluster greedy routing. Empirically, for the considered mission scale $(N=100, U \leq 10)$, all algorithms run within sub-second per-episode time on standard computing hardware, confirming computational tractability.

This section presents the comparative experimental results of the three routing strategies—Random assignment, Greedy routing, and Greedy + K-Means clustering—under both grid PoI layout and random PoI layout. All simulations were conducted using identical system parameters and the same phase-based energy consumption model to ensure methodological consistency and fair comparison. To improve clarity, the presentation emphasizes quantitative interpretation and structural comparison rather than repetitive description of visual trends.

The trajectory visualizations reveal distinct structural behaviors across the three routing strategies. Under both PoI layouts, Random assignment produces irregular and highly intersecting paths, as shown in Figure 2. The resulting trajectories exhibit substantial spatial overlap and frequent detours, reflecting the absence of distance-aware or spatially coordinated decision-making. As a result, the overall coverage pattern is inefficient.

In contrast, Greedy routing generates geometrically compact trajectories, as illustrated in Figure 3. Under the grid PoI layout, the resulting paths follow structured sweep-like patterns that align with the regular PoI arrangement. Under the random PoI layout, local compactness is preserved through incremental minimization of Euclidean distance, although global structural regularity becomes less evident. Because Greedy routing does not explicitly enforce workload balance, some UAVs may receive fewer assignments as fleet size increases, depending on the spatial configuration.

Greedy + K-Means clustering exhibits a more explicit spatial partitioning structure, as shown in Figure 4. PoIs are first grouped into clusters using K-Means, after which Greedy routing is applied within each cluster. This produces spatially coherent sub-missions for individual UAVs. Under the grid PoI layout, the clusters align well with the underlying spatial symmetry. Under the random PoI layout, compact regional assignments are still obtained, although some cluster boundaries are not optimally aligned with the BS location. This decomposition reduces inter-UAV spatial overlap but may introduce additional travel overhead at the cluster level.

Overall, the trajectory plots provide geometric intuition for the quantitative comparisons presented in the following subsections. In particular, they suggest a trade-off between local routing compactness, global routing efficiency, and workload regularity.

The total travel distance achieved by the three routing strategies across fleet sizes is presented in Figure 5. Under the grid PoI layout, Greedy routing generally achieves the shortest total travel distance for most fleet sizes. The regular spatial arrangement enables sweep-like trajectories that reduce detours and route overlap. Greedy + K-Means clustering remains competitive, but its performance is occasionally slightly inferior because cluster boundaries restrict global routing flexibility. As expected, Random assignment consistently produces the largest travel distance because no spatial awareness is incorporated.

Under the random PoI layout, performance becomes increasingly sensitive to fleet size because the PoIs are irregularly distributed. Although Greedy routing maintains locally compact movements, its global efficiency deteriorates as fleet size increases. In contrast, Greedy + K-Means clustering benefits from spatial partitioning, which limits cross-region traversal and reduces long-range route fragmentation.

As shown in Figure 5b, Greedy + K-Means clustering achieves consistent reductions in total travel distance for medium-to-large fleets (U $\geq$ 5) relative to Greedy routing. The relative reduction ranges from approximately 11.6–24.5%, with the largest improvement observed around U = 7. These reductions were computed relative to the Greedy baseline at each fleet size. Taken together, the results indicate that travel-distance performance is strongly context-dependent. Route-driven heuristics are more effective under structured spatial layouts, whereas cluster-based decomposition becomes increasingly advantageous in spatially heterogeneous environments.

The total energy consumption across routing strategies and fleet sizes is presented in Figure 6. Under the grid PoI layout, the differences in total energy consumption are relatively small for small fleet sizes. Although distance differences are already observable, the corresponding energy curves remain close. This indicates that non-propulsion mission phases contribute substantially to the total energy budget in this regime.

As fleet size increases, the energy curves diverge more clearly, and the relative ordering of the strategies increasingly follows the travel-distance trends observed in Figure 5. This pattern indicates that the routing structure exerts an increasingly strong influence on total energy consumption as fleet size grows.

Under the random PoI layout, the divergence in total energy consumption becomes more pronounced as fleet size increases. As shown in Figure 6b, Greedy + K-Means clustering reduces total energy consumption by approximately 4.6–10.5% relative to Greedy routing for U $\geq$ 5. The magnitude of this reduction is smaller than the corresponding reduction in travel distance because non-propulsion energy components (take-off/landing, hovering, sensing, and communication) moderate the proportional effect of route shortening on total mission energy.

These results indicate that Greedy + K-Means clustering provides measurable energy-efficiency gains in propulsion-dominated regimes. By contrast, when fixed mission phases account for a substantial share of total energy consumption, the differences among routing strategies remain comparatively modest.

Beyond aggregate mission-level metrics, workload distribution across UAVs provides important insight into coordination quality and operational fairness. Uneven workload allocation can lead to premature battery depletion in a subset of UAVs, thereby reducing overall mission robustness even when total distance or total energy remains acceptable. To examine workload balance, per-UAV travel distance and per-UAV energy consumption are presented in Figure 7, while the corresponding standard deviation trends across different fleet sizes are shown in Figure 8.

Under the grid PoI layout, clear differences are observed among the three routing strategies, as shown in Figure 7a. Random assignment exhibits the widest dispersion in both travel distance and energy consumption, indicating pronounced workload imbalance. Some UAVs travel significantly farther than others because the assignment process does not account for spatial structure. Greedy routing reduces this imbalance to some extent, since incremental distance minimization naturally promotes local compactness. However, the dispersion still increases with fleet size, indicating that route-driven optimization alone does not guarantee balanced task allocation. In contrast, Greedy + K-Means consistently produces the most compact boxplots and the lowest standard deviation values across fleet sizes. Because PoIs are explicitly partitioned into spatial clusters before routing, the resulting assignments are structurally segmented across UAVs. Each UAV, therefore, operates within a more coherent spatial region, thereby reducing overlap and limiting extreme task concentration. These results indicate that explicit spatial partitioning improves fairness and coordination stability under structured deployment.

Under the random PoI layout as shown in Figure 7b, similar trends are observed, although the differences between Greedy routing and Greedy + K-Means become less pronounced. Since the PoIs are already irregularly distributed, K-Means clustering does not always produce perfectly balanced spatial partitions relative to the BS location. Nevertheless, Greedy + K-Means still yields lower standard deviations in most configurations, indicating greater robustness to spatial uncertainty.

The standard deviation curves in Figure 8 further reveal the scalability characteristics of the routing strategies. As fleet size increases, workload imbalance rises rapidly under Random assignment and exhibits pronounced fluctuations under Greedy routing. In contrast, the Greedy + K-Means strategy exhibits a more gradual and structurally constrained increase in imbalance, particularly under the grid PoI layout. This behavior suggests that explicit spatial partitioning stabilizes task allocation and mitigates the instability that emerges in purely route-driven heuristics as fleet size expands. In contrast, Greedy + K-Means exhibits a more controlled increase in imbalance, particularly under the grid PoI layout. This indicates that explicit task partitioning becomes more beneficial as fleet size expands.

Overall, the workload analysis shows that minimizing total travel distance does not automatically ensure equitable workload distribution, motivating the need for rigorous statistical validation presented in the following subsection. Although route-driven heuristics can achieve competitive geometric efficiency, cluster-based decomposition offers a structural advantage in balancing workload across UAVs. From an engineering perspective, this trade-off is important for mission endurance, battery health management, and operational safety in multi-UAV deployments.

The validity of the analysis of variance (ANOVA) assumptions across fleet sizes was examined using the Shapiro–Wilk test for normality and Levene’s test for homogeneity of variances. The results of the Shapiro–Wilk test are summarized in Table 2. Partial violations of normality were observed for both total travel distance and energy consumption.

For travel distance, under the grid PoI layout, non-normality was detected in 5/10 configurations for Random assignment and 3/10 configurations for Greedy + K-Means. Under the random PoI layout, the corresponding counts were 3/10 and 2/10, respectively. For Greedy routing, zero variance in travel distance was observed across all fleet sizes, indicating deterministic outputs under fixed-layout conditions.

For energy consumption, violations of normality were more frequent. Under the grid PoI layout, non-normality was observed in 8/10 configurations for Random assignment, 6/10 for Greedy routing, and 4/10 for Greedy + K-Means. Under the random PoI layout, the corresponding counts were 1/10, 6/10, and 7/10, respectively.

The results of Levene’s test are summarized in Table 3. Systematic heteroscedasticity was observed across nearly all configurations. Equal variance was rejected in all 10 of 10 configurations for travel distance under both PoI layouts. For energy consumption, heteroscedasticity was observed in 9/10 configurations under the grid PoI layout and in 10/10 configurations under the random PoI layout. These findings indicate that the classical ANOVA assumptions of normality and homoscedasticity were not strictly satisfied across all cases.

Given the partial normality violations and the consistent heteroscedasticity observed in Table 2 and Table 3, the ANOVA results were interpreted primarily as indicators of variance decomposition rather than as the sole basis for inference. For deterministic outputs, such as Greedy routing under fixed layout conditions, the ANOVA decomposition reflects inter-algorithm differences rather than within-algorithm variability. To improve inferential robustness, paired Wilcoxon signed-rank tests with Holm correction were used for post hoc comparisons. Practical significance was quantified using Cliff’s delta ($\Delta$), and the proportion of explained variance was quantified using eta-squared ($\eta^2$). This combined framework ensures that the conclusions do not depend exclusively on parametric assumptions..

The ANOVA results for total travel distance are reported in Table 4. Under the grid PoI layout, $\eta^2$ ranges from 0.867 to 0.983, indicating that the routing strategy explains between 86.7% and 98.3% of the total variance in travel distance. Under the random PoI layout, $\eta^2$ ranges from 0.985 to 0.998, indicating that the routing strategy accounts for approximately 99% of the variance across all fleet sizes. These extremely large effect sizes demonstrate that travel distance is predominantly determined by routing structure rather than by stochastic variability.

The ANOVA results for total energy consumption are presented in Table 5. In this case, the effect sizes vary substantially across fleet sizes. Under the grid PoI layout, $\eta^2$ remains relatively small for small fleets, but increases substantially for U $\geq$ 7, reaching values above 0.67 and up to 0.907. This indicates that algorithmic influence becomes stronger as fleet size increases. Under the random PoI layout, $\eta^2$ becomes extremely large for U $\geq$ 5 ($\eta^2$ $\geq$ 0.924), indicating that the routing strategy almost completely determines the total energy-consumption performance in medium-to-large fleets.

Because identical environmental seeds were used across algorithms within each episode, paired post hoc comparisons were performed using the Wilcoxon signed-rank test with Holm correction. Practical significance was quantified using Cliff’s delta ($\Delta$). For conciseness, Table 6 and Table 7 report representative pairwise comparisons for U = 1, U = 5, and U = 10), which correspond to small-, medium-, and large-fleet regimes.

For total travel distance, the Wilcoxon results in Table 6 confirm that Random assignment is consistently inferior to the two structured routing strategies under both PoI layouts. In nearly all comparisons, the effect size reaches $\Delta$ = 1.00. For U = 1, Greedy routing and Greedy + K-Means produce identical travel distances ($\Delta$ = 1.00). For U $\geq$ 5, however, Greedy + K-Means significantly outperforms Greedy routing, with large effect sizes under both layouts ($\Delta$ $\geq$ 0.90 under the grid PoI layout and $\Delta$ = 1.00 under the random PoI layout). These results confirm that the benefit of clustering becomes more pronounced as fleet size increases.

For total energy consumption, the Wilcoxon results in Table 7 show a more nuanced pattern. Under the random PoI layout, no statistically significant differences are observed at U = 1 ($p$ = 0.269; $\Delta$ = -0.20), indicating nearly identical energy performance in the minimal-fleet regime. For U $\geq$ 5, however, all pairwise comparisons become highly significant under the random PoI layout, with extremely large practical differences ($\Delta$ = 1.00).

Under the grid PoI layout, the pattern is less uniform. At U = 5, Random assignment does not consistently exhibit inferior energy performance, as indicated by small or negligible effect sizes. Nevertheless, Greedy + K-Means significantly outperforms Greedy routing, with $\Delta$ = 1.00. These findings indicate that the relationship between travel-distance reduction and energy savings is not strictly linear in small fleets. However, in medium- to large-sized fleets, clustering-assisted routing yields robust and statistically significant improvements in overall energy performance.

The experimental and statistical results reveal a structured relationship between routing strategy, geometric efficiency, and mission-level energy behavior. Rather than identifying a universally superior algorithm, the findings indicate that routing performance depends strongly on the operational regime defined by fleet size and the spatial structure of the sensing environment.

In this study, the term regime refers to an operating condition in which a particular structural component dominates the variance of system performance. To formalize this interpretation, total mission energy can be decomposed into routing-dependent and routing-independent components, as expressed in Eq. (21):

where, $E^{\text {prop}}(d)$ denotes propulsion energy as a function of travel distance $d$, and $E^{\text {fixed}}$ represents a routingindependent mission phase, such as take-off, landing, sensing, communication, and hovering. A propulsiondominated regime arises when $\left(E^{\text {prop}} / E^{\text {total}}\right) \rightarrow 1$, such that routing-induced distance variations significantly influence total energy consumption. Conversely, a phase-dominated regime occurs when $\left(E^{\text {fixed}} / E^{\text {total}}\right) \rightarrow 1$, where routing-induced geometric differences have limited influence on total mission energy.

In addition, a geometric-dominant regime is defined as a condition in which the routing strategy explains the majority of variance in travel distance, as reflected by large effect sizes ($\eta^2 \approx 1$). These regime definitions provide a structural framework for interpreting the algorithmic performance pattern observed in Section 3.

For total travel distance, the ANOVA results indicate extremely large effect sizes across all fleet sizes and PoI layouts ($\eta^2$ ranging from 0.867 to 0.998). These values demonstrate that the routing strategy explains nearly all observed variance in geometric performance. Particularly under the random PoI layout, $\eta^2$ approach unity, indicating that algorithmic structure overwhelmingly dominates stochastic variability.

This observation aligns with theoretical expectations from combinatorial optimization. In NP-hard routing problems such as the multi-UAV routing task considered here, structural heuristics largely determine solution quality once environmental randomness is controlled. Because identical environmental seeds were used across algorithms, the observed variance reflects intrinsic algorithmic behavior rather than sampling noise.

The Greedy strategy minimizes incremental Euclidean distance at each routing step. Under grid PoI layouts, this local decision rule naturally generates sweep-like trajectories that approximate near-optimal tours. However, the approach remains inherently myopic: global route optimality is not enforced, and workload balance emerges only incidentally.

In contrast, Greedy + K-Means introduces explicit spatial decomposition prior to route construction. From a computational perspective, clustering reduces the effective problem dimensionality by partitioning the global routing problem into U smaller subproblems. This cluster-first, route-second paradigm sacrifices some global flexibility in exchange for structural regularization. The statistical results demonstrate that this structural regularization becomes increasingly beneficial as fleet size grows. Thus, algorithmic dominance gradually shifts from purely route-driven heuristics to partition-aware heuristics as fleet sizes increase.

An important contribution of this study is distinguishing between geometric optimization and mission-level energy optimization. Although propulsion energy constitutes a major component of the energy model, the statistical results show that algorithmic influence on total energy consumption varies across operational regimes.

For small fleet sizes (e.g., U = 1–3 under the grid PoI layout), the effect sizes on energy consumption are small or statistically insignificant. This indicates a phase-dominated regime in which fixed mission components—such as take-off, landing, sensing, and communication—account for a substantial portion of the total energy expenditure. Under these conditions, improvements in travel distance have a limited influence on total energy.

In contrast, for medium-to-large fleets (U $\geq$ 5), particularly under random PoI layout, $\eta^2$ exceeds 0.9. This reflects a transition to a propulsion-dominated regime in which horizontal travel distance becomes the primary determinant of total energy consumption. In such regimes, the routing structure directly amplifies energy differences among algorithms.The experimental results confirm this transition. Under the random PoI layout, clustering-assisted routing reduces total travel distance by approximately 11.6–24.5% relative to Greedy routing, as shown in Figure 5b. This geometric advantage translates into measurable energy reductions of approximately 4.6–10.5%, as observed in Figure 6b. The smaller proportional reduction in energy reflects the moderating influence of fixed mission-phase energy components. These findings highlight an important methodological implication: evaluating routing strategies solely through geometric metrics may lead to incomplete conclusions regarding mission-level energy efficiency.

The workload distribution analysis reveals that clustering contributes primarily through structural regularization rather than purely geometric improvement. While Greedy routing can achieve a competitive total distance, it does not enforce fairness in task allocation across UAVs. As fleet size increases, workload dispersion becomes increasingly unstable.

Clustering introduces an implicit fairness mechanism by spatially partitioning the sensing region into separate operational subregions. The statistical reduction in workload variance observed in Section 3.4 confirms that spatial decomposition stabilizes task allocation.

From a systems-engineering perspective, improved workload balance enhances mission robustness, promotes more uniform battery depletion across UAVs, and reduces the risk of premature mission termination due to individual UAV exhaustion. Consequently, the benefits of clustering extend beyond geometric efficiency to broader operational sustainability.

An additional structural phenomenon emerges in grid PoI layouts at larger fleet sizes (U $\geq$ 7). As discussed in Section 3.4, Greedy routing tends to generate increasingly uneven workload distribution in spatially regular environments. This effect can be interpreted as a spatial saturation inherent to deterministic nearest-neighbor allocation. Early routing decisions tend to exhaust nearby PoIs, leaving subsequent UAVs with smaller spatial regions. As a result, some UAVs perform minimal traversal while others continue to service larger areas. Although the total mission distance may decrease, the internal workload distribution becomes increasingly imbalanced. Figure 9 illustrated this phenomenon for U = 7–8 under the grid PoI layout.

Importantly, this behavior does not indicate algorithmic failure. Rather, it reflects the structural interaction between deterministic routing rules and regular spatial topology. These observations reinforce the need to evaluate routing strategies using both efficiency and fairness metrics.

The combined experimental and statistical evidence indicates that no single routing paradigm universally dominates across all operational regimes. Instead, algorithmic performance depends on fleet size, spatial structure, and the relative dominance of propulsion versus fixed-phase energy components. The regime-dependent dominance patterns identified in this study are summarized in Table 8. The table synthesizes geometric efficiency, energy sensitivity, and workload stability considerations into a practical framework for routing strategy selection.

Under small-fleet, structured environments, Greedy routing remains effective due to its ability to exploit geometric regularity. In these regimes, spatial partitioning provides limited additional benefit. Conversely, in medium-to-large fleets—particularly under irregular PoI distributions—Greedy + K-Means becomes increasingly advantageous. The large $\eta^2$ values observed in these regimes confirm that routing structure strongly influences both geometric and energy performance.

Moreover, clustering improves workload balance, which is essential for large-scale missions where operational robustness and fairness are critical. These findings suggest that routing strategy selection should be mission-aware rather than universally prescriptive.

Although fixed energy parameters were adopted to ensure controlled comparison across routing strategies, the regime-based dominance patterns observed in this study are structurally robust. Since total energy can be decomposed into propulsion-dependent and phase-dependent components, moderate variations in propulsion or hovering power primarily scale absolute energy values rather than altering the relative ordering of routing strategies in propulsion-dominated regimes.

In phase-dominated regimes (small fleet sizes), energy differences are inherently small because fixed mission phases dominate the energy budget. Under such conditions, parameter variations may reduce statistical significance but do not reverse the underlying structural trends.

Therefore, although absolute energy magnitudes depend on platform-specific parameters, the regime-based interpretation and relative performance patterns remain stable under moderate variations.

Beyond algorithm comparison, this study highlights the methodological importance of integrating:

• Phase-based mission energy modeling,

• Repeated-episode statistical validation,

• Effect size interpretation ($\eta^2$, Cliff’s $\Delta$), and

• Holm correction for family-wise error control.

The extremely large $\eta^2$ values for travel distance confirm that routing strategy is the dominant determinant of geometric mission efficiency. In contrast, the heterogeneous $\eta^2$ values for energy consumption demonstrate the necessity of multi-phase energy modeling when evaluating UAV routing strategies. By combining deterministic routing analysis with inferential statistics, this study advances heuristic comparison from descriptive evaluation toward statistically grounded structural insight.

This study presented a systematic computational evaluation of three routing paradigms for energy-aware multi-UAV data-collection missions: Random assignment, Greedy nearest-neighbor routing, and clustering-assisted Greedy routing (Greedy + K-Means). The evaluation employed a mission-level energy model integrating propulsion energy with fixed mission-phase components, including take-off, landing, sensing, communication, and hovering.

The results demonstrate that routing structure exerts a dominant influence on geometric mission efficiency. Across fleet sizes and spatial layouts, the routing strategy explains most of the variance in total travel distance, as confirmed by extremely large effect sizes in the statistical analysis. However, the influence of routing strategies on total energy consumption is regime-dependent. When propulsion energy constitutes a large fraction of the total mission energy, improvements in routing structure translate directly into measurable energy savings. Conversely, when fixed mission phases dominate the energy budget, the relative performance differences between routing strategies become less pronounced. These findings further indicate that minimizing total travel distance does not necessarily guarantee balanced workload distribution across UAVs.

Overall, the results indicate that routing strategy selection should be context-dependent rather than universally prescriptive. Greedy routing performs well in small fleets or spatially structured deployments, where geometric sweep efficiency dominates mission performance. In contrast, Greedy + K-Means provides greater robustness and scalability in larger fleets or spatially heterogeneous environments by introducing spatial task partitioning.

Beyond the algorithmic comparison, this study highlights the importance of integrating mission-level energy modeling, workload balance analysis, and statistical effect-size evaluation when assessing multi-UAV routing strategies. Such an integrated evaluation framework enables a more realistic understanding of how routing decisions interact with physical energy constraints and fleet-level coordination dynamics.

Future work may extend this framework to dynamic sensing environments, stochastic energy consumption models, and adaptive routing strategies for real-time multi-UAV coordination. These findings provide practical guidance for selecting routing strategies in energy-constrained multi-UAV sensing missions, emphasizing that effective coordination depends not only on geometric efficiency but also on workload balance and mission-phase energy characteristics.