Bättre ordning på flygplansrutter
Ett enda flygbolag kan ha tusentals plan som lyfter och landar världen runt dagligen. Eftersom varje minut är dyrbar och säkerheten av största vikt gäller det att hålla ordning på dem. En färsk doktorsavhandling från Chalmers kommer med en ny lösning på problemet.
Mattias Grönkvist, som skrivit avhandlingen, beskriver svårigheten konkret:
– Om tio plan nyss har landat på en flygplats, måste man ha ett schema som bestämmer i vilken ordning planen ska lyfta – och vart de ska. Det är många villkor som styr. Till exempel får inte alla flygplanstyper landa på alla flygplatser och planen måste ha tillräckligt stor bränsletank för resan. Allt ska göras så effektivt och kostnadsbesparande som möjligt, med tillräcklig säkerhet.
Problemet brukar kallas Tail Assignment – problemet, namngett efter planens så kallade tail-nummer. Det gäller alltså att bestämma vilken sekvens av flighter – rutter – varje individuellt flygplan ska flyga. Rutterna måste konstrueras på ett sådant sätt att alla flygplan kan ges tillräckligt med underhåll, och så att en mängd regler uppfylls. Ibland vill man dessutom att de skapade rutterna ska vara optimala på något sätt, till exempel så att de påverkas minimalt vid förseningar.
För någorlunda stora flygbolag är Tail Assignment-problemet mycket komplicerat. Från exempelvis ett bolags huvudflygplats finns ett enormt stort antal möjliga rutter att välja mellan. Som hjälp används datorprogram som hanterar de många förutsättningarna. Till grund för programmen ligger matematiska modeller.
Ett syfte med Mattias Grönkvists arbete var att komma ifrån ett par av nackdelarna med de vanligaste modellerna som används av flygbolag idag:
” ofta hanteras inte alla nödvändiga regler, vilket gör de resulterande rutterna svåra att använda i praktiken utan extra manuella ingrepp
” de flesta modeller kan bara optimera med avseende på ett visst förutbestämt kriterium
” ofta kan de traditionella modellerna bara användas för en viss typ av planeringsscenarier.
Mattias Grönkvist har kombinerat två sätt att lösa detta, med dels en strikt matematisk metod, dels en datavetenskaplig metod som har med villkorsprogrammering att göra. Idén har funnits tidigare men kan nu genomföras praktiskt, bland annat tack vare den extrema ökningen av datorers kapacitet under senare år.
– Min lösning är mer generellt användbar än de tidigare, och är tänkt att kunna användas för en större del av planeringsprocessen. Jag tror att denna typ av kombinerade metoder kommer att utvecklas och bli allt vanligare framöver, säger Mattias Grönkvist.
Hans metod har redan kommit till användning i en kommersiell produkt som används av två flygbolag. Arbetet gjordes som en del i ett projekt tillsammans med Carmen Systems AB, där Mattias Grönkvist arbetar. Carmen Systems AB utvecklar och säljer program för lösning av olika logistik- och planeringsproblem. Inom flygindustrin har företaget tidigare mest arbetat med personalscheman.
Avhandlingen heter “The Tail Assignment Problem” och försvarades den 13 september 2005.
Kontaktinformation
För mer information kontakta:
Mattias Grönkvist, Carmen Systems AB
031-720 81 58
mattias.gronkvist@carmensystems.com
