Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Robust airline crew pairing optimization for short-haul flights
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.
2018 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Robust crew pairing optimering för flygbolag på kortdistansflyg (Swedish)
Abstract [en]

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. 

Abstract [sv]

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.

Place, publisher, year, edition, pages
2018.
Series
TRITA-SCI-GRU ; 2018:011
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-222340OAI: oai:DiVA.org:kth-222340DiVA, id: diva2:1180817
External cooperation
Aviolinx Software AB, Stockholm
Subject / course
Systems Engineering
Educational program
Master of Science - Aerospace Engineering
Supervisors
Examiners
Available from: 2018-02-06 Created: 2018-02-06 Last updated: 2018-02-06Bibliographically approved

Open Access in DiVA

fulltext(1519 kB)130 downloads
File information
File name FULLTEXT01.pdfFile size 1519 kBChecksum SHA-512
b53f1dc781ea1f86e50c97343be20ea89ce376b30906dc85ac49021a292646123a11c667a7f37acf51e4176ffe48e8d6f1d65baf9063be84683eaaeeebf53035
Type fulltextMimetype application/pdf

By organisation
Optimization and Systems Theory
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 130 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 1463 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf