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
A Column Generation Method for Minimization of Shift Costs at an Airport
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.
2019 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

This thesis addresses the problem with minimizing the cost of labor shifts for the workforce at an airport. The cost of idle time is specifically a difficulty for the employer. With idle time means time that it is not a break at the same time as there is no work task to be performed. This originates from big variations in the traffic flow which lead to the workload to be characterized by peaks and valleys. This situation has increased the demand among airport service companies for efficient staff schedules. Even small reductions of the idle time mean considerable savings for the employer. This thesis uses authentic data from an international airport in Europe. The method used to solve the task is an algorithm based on column generation. The mathematical model used has a high flexibility and handles breaks, multi-activity, such as boarding, and non-splittable tasks, in other words tasks that has to be performed by one employee in one shift. The subproblem is a binary integer program that generates feasible shifts following certain rules and is solved using a commercial solver. The results have shown possible improvements. In the best test scenario, the idle time is reduced to 4.7 percent of the total worktime. There is room for improvement of the model and the results. One possible improvement is to reduce the running time of the program which also could lead to improved results.

Abstract [sv]

Det här arbetet adresserar problemet med att minimera skiftkostnaderna för arbetskraften på flygplatser. Speciellt är det tom arbetstid som innebär kostnader för arbetsgivaren. Med tom arbetstid menas att det inte är rast samtidigt som ingen arbetsuppgift finns att utföra. Detta är en följd av stora variationer i trafikflödet vilket leder till att arbetsbördan utmärks av toppar och dalar. Av den anledningen är efterfrågan hög på effektiva scheman för de anställda hos de aktörer som sysslar med service på flygplatser. Även en liten minskning av tomtiden innebär betydande besparingar för arbetsgivaren. Arbetet bygger på autentiska data om arbetsuppgifter och personal vid en europeisk storflygplats. Metoden som används för att lösa uppgiften är en algoritm baserad på kolumngenerering i en matematisk modell med hög flexibilitet. Den hanterar raster, flera aktiviteter, som boarding, samt odelbara uppgifter, det vill säga uppgifter som måste utföras av en person under ett skift. Underproblemet är skrivet som ett binärt heltalsprogram och genererar tillåtna skift enligt ett antal regler och löses med ett kommersiellt lösningsprogram. Resultaten har visat på möjliga effektiviseringar. I det bästa testscenariot reduceras tomtiden till 4,7 procent av den totala arbetstiden. Det finns utrymme att förbättra modellen och resultaten, bland annat genom att förkorta tiden att köra programmet vilket också i sin tur kan förbättra resultaten.

Place, publisher, year, edition, pages
2019.
Series
TRITA-SCI-GRU ; 2019:005
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-241917OAI: oai:DiVA.org:kth-241917DiVA, id: diva2:1282822
External cooperation
Aviolinx
Subject / course
Systems Engineering
Educational program
Master of Science in Engineering - Vehicle Engineering
Supervisors
Examiners
Available from: 2019-01-26 Created: 2019-01-26 Last updated: 2019-01-26Bibliographically approved

Open Access in DiVA

fulltext(2128 kB)72 downloads
File information
File name FULLTEXT01.pdfFile size 2128 kBChecksum SHA-512
632edeb7cdffb344e09bc7577ffe4e042eb43ee2a9affeacb06167829c99be47de6e45bc58054d309a54d729e12a7c7209a58970fcfe05ae89d06143cac45029
Type fulltextMimetype application/pdf

By organisation
Optimization and Systems Theory
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 72 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: 274 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