Flight Route Optimization

Flyruter er en essentiel del af den flyveplan som indsendes til godkendelse hos flyve myndighederne før afgang. De består af en sekvens af navigationspunkter i et luftrum som flyet skal følge for at rejse fra en lufthavn til en anden. På grund af den store belastning af det europæiske luftrum bliver et stort antal restriktioner anvendt til at regulere trafikken og garantere sikre flyvninger. Restriktionerne betyder typisk at hvis man anvender specifikke luftrum og navigationspunkter, så skal andre luftrum og navigationspunkter enten undgås eller besøges. Stier bliver valgt ud fra omkostningskriterier. Prisen for at flyve afhænger, direkte, af brændstofforbrug og flyvetid, og, indirekte, af vægten på flyet og af vejret.
Klassiske algoritmer til at finde korteste vej såsom Dijkstra’s algoritme og A∗ bliver almindeligvis brugt i automatiseret ruteplanlægning. Restriktionerne og omkostningernes afhængighedsforhold invaliderer imidlertid de normale domineringskriterier anvendt i disse algoritmer, da den såkaldte FIFO-egenskab, som normalt antages i korteste vej problemer, ikke kan antages at holde. Endvidere kan omkostninger ikke beregnes før søgningen startet. Sammen med den enorme størrelse på luftrum, gør disse komplikationer at flyruter kan tage lang tid at beregne. En almindelig fremgangsmåde til at reducere beregningstiden er at dekomponere problemet til en sekvens af horisontale og vertikale optimeringer.
 Vi undersøger om det er muligt at gribe problemet an direkte i 3D. Det gør vi ved at implementere begge faser af dekomponeringen og sammenligner denne løsning med den direkte fremgangsmåde. Vi præsenterer en teknik til behandlingen af restriktionerne i korteste vej algoritmer. Vi studerer desuden ’dovne’ fremgangsmåder til at håndtere restriktionerne og brugen af heuristikker til at fjerne restriktioner baseret på geografiske overvejelser. Vi anvender den forventede vertikale profil for en flyrute til at udvikle heuristikker der reducerer størrelsen af søgningen. Vi udfører eksperimentelle undersøgelser på data fra den virkelige verden. Vi viser at FIFO-egenskaben kan antages at holde for omkostninger i forbindelse med vertikal optimering. Vi viser også at vores fremgangsmåde til håndtering af restriktionerne fungerer bedst sammen med en iterativ søgning, hvor kun restriktioner som er blevet overtrådt i tidligere iterationer bliver håndteret under søgningen. Vi konkluderer til sidst at den direkte 3D fremgangsmåde er praktisk anvendelig og leder til flyruter af bedre kvalitet end den dekomponerede fremgangsmåde.