Model and method of balanced partitioning and route optimization for multi-unmanned aerial vehicle task planning

This study addresses centralized mission planning for heterogeneous UAV fleets that perform a single sortie from a common depot to service spatially distributed tasks. The study develops a deterministic planning framework for asymmetric and weakly non-metric travel costs. The framework supports early feasibility control, workload balance, and route-quality improvement. The research materials consist of benchmark mission instances defined by task locations, dwell times, endurance limits, and precomputed directed cost matrices for each UAV. The methods include feasibility masking of task–vehicle assignments, workload balancing with an order-independent surrogate load, and weighted power partitioning with deterministic offset updates. They also include single-vehicle route optimization and exchange-based refinement under a composite objective of total fleet cost and makespan. The results show that the first stage provides a strong trade-off between balance and efficiency while preserving spatial coherence. The second stage yields consistent additional reductions in makespan and in the composite objective with modest computational overhead. Across the benchmarks, the framework maintains near-minimal total cost while markedly reducing the longest route relative to cost-greedy assignment. The study shows that localized route-level refinement improves solution quality without repeated low-level replanning. Early feasibility control is incorporated at the allocation stage. The scientific novelty consists in establishing that cost-matrix-aware workload allocation reduces route-cost imbalance before route sequencing under UAV-specific directed costs. The study also shows that route-level correction under the same cost representation further reduces makespan and the composite mission objective.