Scalable UAV Routing for Disaster Response: Spatial Decomposition of the Team Orienteering Problem via Particle Swarm Optimization, and Prediction of Resource Requirements from Instance Statistics
Author
Larsen, Mads Lindeborg
Term
4. semester
Education
Publication year
2026
Submitted on
2026-08-07
Abstract
Unmanned aerial vehicles (UAVs), or drones, are increasingly used to maintain situational awareness during disasters such as forest fires. However, operators lack tools that connect how drone routes are planned with how many resources are actually needed to achieve a given level of awareness. This thesis addresses both sides of that challenge. First, it focuses on the routing problem itself. The large‑scale routing task is modeled as a Team Orienteering Problem (TOP), where multiple drones must visit the most valuable locations within limited time. To make this problem computationally manageable, the search area is divided into smaller zones (spatial decomposition). A heuristic method, Particle Swarm Optimization (PSO), selects the zone boundaries, and each zone is then solved optimally as a single‑vehicle Orienteering Problem using a MILP solver (a mathematical optimization model). When tested against exact solutions on 593 problem instances, this approach achieves an average optimality gap of only 4.88%, while being about 27 times faster than the exact solver. Second, the thesis develops a way to predict how good a solution the routing algorithm will produce, without actually running the optimization software. A Random Forest model (a machine learning method) is trained on features that describe the search area: its geometry, how scores are distributed, and how reachable different locations are. Using these inputs, the model predicts the total score that the routing algorithm would obtain for a given number of UAVs and a given time budget. On held‑out spatial layouts (areas not used for training), the model reaches an R2 of 0.938 and a mean absolute percentage error (MAPE) of 3.50%. The results show that the achievable score is driven mainly by the number of UAVs and the available time, while the detailed structure of the area only refines the outcome. Taken together, these contributions allow operators to quickly compare different resource allocation options for a new search area, without having to run extensive and time‑consuming optimization procedures.
Ubemandede droner (UAV’er) bruges i stigende grad til at skabe overblik under katastrofer som skovbrande. Men operatører mangler værktøjer, der kobler den måde, dronerne rutes på, med hvor mange ressourcer der egentlig skal til for at opnå et bestemt niveau af situationsfornemmelse. Denne afhandling tager fat på begge dele. Først behandles selve ruteplanlægningsproblemet. Det store planlægningsproblem modelleres som et Team Orienteering Problem (TOP), hvor flere droner skal besøge de mest værdifulde punkter inden for en begrænset tid. For at gøre problemet håndterbart deles området op i mindre zoner (rumlig dekomposition). En heuristisk metode, Particle Swarm Optimization (PSO), bruges til at vælge zonegrænserne, og hver zone løses derefter optimalt som et enkelt-vehicle Orienteering Problem ved hjælp af en MILP-solver (en matematisk optimeringsmodel). Sammenlignet med en nøjagtig (eksakt) løsning på 593 testtilfælde giver denne fremgangsmåde i gennemsnit kun 4,88 % afvigelse fra det optimale resultat, men er cirka 27 gange hurtigere. Dernæst bygges en model, der kan forudsige, hvor god en løsning rutealgoritmen vil finde, uden at man behøver at køre selve optimeringssoftwaren. En Random Forest-model (en maskinlæringsmetode) trænes på geometriske karakteristika ved søgeområdet, hvordan scores er fordelt, og hvor let forskellige punkter kan nås. Baseret på disse oplysninger kan modellen forudsige den samlede score, som rutealgoritmen vil opnå for et givet antal droner og en bestemt tidsramme. På nye, ikke‑trænede områdelayouts opnår modellen en forklaringsgrad (R2) på 0,938 og en gennemsnitlig procentvis fejl (MAPE) på 3,50 %. Resultaterne viser, at den opnåelige score primært bestemmes af, hvor mange UAV’er der bruges, og hvor meget tid de har til rådighed, mens områdets egen struktur kun finjusterer resultatet. Samlet set giver disse bidrag operatører mulighed for hurtigt at sammenligne forskellige forslag til ressourcefordeling for et nyt søgeområde, uden at de først skal gennemføre omfattende og tidskrævende optimeringskørsler.
[This abstract has been rewritten with the help of AI based on the project's original abstract]
Keywords