Robust crew pairing optimering för flygbolag på kortdistansflyg

Crew costs are the second highest costs for airlines therefore they represent a key factor for an airline survival and crew scheduling is one of the hardest combinatorial problem. The scheduling process is broken down into crew pairing and crew rostering and, in this thesis, a robust solution is described in detail for the former one. The purpose of the thesis is to present an efficient and robust crew pairing optimization tool which minimizes the pairings costs and reduces unnecessary overcovers. The model framework is based on a new concept which involves four stages. During the first stage all roundtrip combinations are generated then in the second stage the roundtrips generated are optimized and the optimal solution is used in the third stage to generate all pairing combinations. And the last one, the fourth stage, optimizes the pairings obtained from the third stage. An augmented set covering problem is used to for the problem formulation where the unknown variables can take just integer values. A mixed integer programming solver from Google OR has been used to solve the optimization problem. In the last chapter numerical results are presented which show the efficiency of using this model framework. Besättningskostnader är den näst största kostnadsposten för ett flygbolag. De spelar därmed en nyckelroll i ett flygbolags överlevnad. Schemaläggning för besättning är ett mycket svårt kombinatoriskt problem. Schemaläggningsprocessen är indelad i två delmoment: crew pairing och crew rostering. I detta arbete presenteras en robust lösning på det tidigare problemet. Syftet med rapporten är att presentera ett effektivt och robust optimeringsvektyg för att minimera kostnaderna för pairingar och minska ickenödvändig övertäckning. Ramverket för modellen är baserat på ett nytt koncept vilket involverar fyra steg. I första steget skapas pairingar som rundresor, dvs. de slutar så snart en flight i pairingen når flygplatsen som pairingen började på. I det andra steget löses ett optimeringsproblem för attt hitta den optimala kombinationen av dessa rundresor, därefter genereras pairingar på nytt i det tredje steget. I detta steg genereras pairingar baserade på lösningen i det förra steget. Slutligen i det fjärde steget erhålles en optimal lösning baserat på en optimeringsmodell som använder sig av pairingar från det tredje steget, Optimeringsproblemet är formulerat som ett utvidgat övertäckningsproblem där variablerna enbart kan anta heltalsvärden, och en heltalslösare från Google OR tools används för att lösa detta problem. I det sista kapitlet presenteras numeriska resultat från modellen