Models and algorithms for ground staff scheduling on airports [Elektronische Ressource] / von Jörg Herbers

Sujets

• Handel

Informations

• Publié par: rheinisch-westfalischen_technischen_hochschule_-rwth-_aachen
• Publié le: 01 janvier 2005
• Nombre de lectures: 23
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Models and Algorithms for
Ground Staff Scheduling on Airports
Von der Fakultat¨ fur¨ Mathematik, Informatik und Naturwissenschaften der
Rheinisch Westfalischen¨ Technischen Hochschule Aachen
zur Erlangung des akademischen Grades eines Doktors der
genehmigte Dissertation
von
Diplom Informatiker Jor¨ g Herbers
aus
Haselunne¨
Berichter: Universitatsprofessor¨ Dr. Drs. h.c. Hans Jur¨ gen Zimmermann
Universit¨ Dr. rer. nat. Juraj Hromkovicˇ
Universitatsprofessor¨ Dr. rer. nat. Peter Rossmanith
Tag der mundlichen¨ Prufung:¨ 14. Marz¨ 2005
¨Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online verfugbar.Abstract
The planning of airport ground staff gives rise to a number of challenging optimisation problems.
Ground handling workloads are naturally represented as work tasks, e.g. for baggage unload
ing or passenger check in. These workloads must be covered by appropriate employees. Staff
scheduling is usually carried out in several stages: In demand planning, workloads are aggregated
and analysed, in shift planning, appropriate shift duties are generated, and rostering consists in
generating lines of duty for the workers. These phases are strongly interrelated, and different
optimisation problems have to be solved at each stage.
Workforce scheduling models have traditionally built upon aggregate labour requirements given
in discrete time periods. However, the literature does not describe any models or algorithms for the
generation of appropriate workload representations. Additionally, it will not always be sufficient
to cover coarse grained abstractions of workloads. If information on flights as well as passenger
and load figures are sufficiently exact, we will rather be interested in directly covering individual
work tasks. Furthermore, shift scheduling and rostering approaches have regularly taken special
assumptions or investigated simplified problems, limiting their practical applicability.
In this work, we tackle optimisation problems at different planning stages. We show how in the
presence of movable tasks, we can obtain a suitable demand curve representation of workloads,
using a levelling procedure which combines aspects from vehicle routing and resource levelling.
Furthermore, we devise two algorithms for task level shift planning which relates to vehicle rout
ing and shift scheduling models. The first method is an improvement procedure, building upon
the results of a construction phase and dealing with a complex shift planning setting. The second
algorithm focuses on a subclass of task level shift planning and is able to solve many problems
to proven optimality. Finally, we design an algorithm for complex cyclic rostering on the basis
of aggregate workloads. The approach builds upon a novel model for representing flexible breaks
and solves the shift scheduling and rostering stage simultaneously.
Models and algorithms proposed in this thesis are more integrated and tackle more complex
settings than previous approaches. We employ modern constraint programming and integer pro
gramming solution techniques, including column generation and branch and price. For the novel
optimisation problems treated in this work, we provide complexity results. All algorithms are
evaluated on complex large scale test cases from the practice of airlines, airports and ground han
dling companies.Zusammenfassung
Die Planung von Bodenpersonal an Flughafen¨ beinhaltet eine Reihe anspruchsvoller Optimie
rungsprobleme. Das Arbeitsaufkommen fur¨ Abfertigungsdienste wird typischerweise in Form
von Arbeitsauftragen¨ dargestellt, z.B. fur¨ die Gepack¨ entladung oder fur¨ Check in Dienste. Dieses
Arbeitspensum muss durch geeignete Mitarbeiter abgedeckt werden. Die Planung wird ublicher ¨
weise stufig durchgefuhrt:¨ In der Bedarfsplanung wird das Arbeitsaufkommen aggregiert und
analysiert, in der Schichtplanung werden geeignete Schichtdienste generiert, und in der Dienst
planung werden Dienstplane¨ fur¨ die Mitarbeiter erstellt. Die einzelnen Phasen sind dabei eng
verzahnt, und auf jeder Stufe mussen¨ verschiedene Optimierungsprobleme gelost¨ werden.
Personalplanungsmodelle bauen traditionell auf aggregierten Bedarfszahlen auf, die in diskre
ten Zeitschritten angegeben werden. Fur¨ die tatsachliche¨ Generierung einer solchen Bedarfskur-
venreprasentation¨ sind in der Literatur allerdings keine Modelle oder Algorithmen beschrieben
worden. Daruber¨ hinaus ist eine Planung auf Basis grober Bedarfszahlen nicht immer ausreichend.
Wenn hinreichend genaue Informationen uber¨ abzufertigende Fluge¨ und Passagier /Gepackzahlen¨
zur Verfugung¨ stehen, ist man vielmehr daran interessiert, die einzelnen Arbeitsauftrage¨ zu ver-
planen. Schicht und Dienstplanungsansatze¨ in der Literatur gehen zudem durchgehend von spe
ziellen Annahmen aus oder behandeln vereinfachte Probleme, was ihre praktische Anwendbarkeit
einschrankt.¨
In dieser Arbeit werden Optimierungsprobleme fur¨ verschiedene Planungsschritte gelost.¨ Es
wird gezeigt, wie eine geeignete Bedarfskurvendarstellung unter Berucksichtigung¨ verschiebli
cher Auftrage¨ generiert werden kann, indem Elemente des Vehicle Routing und des Resource
Levelling kombiniert werden. Daruber¨ hinaus werden zwei Algorithmen fur¨ die auftragsbasier-
te Schichtplanung entwickelt, die auf Modellen des Vehicle Routing und des Shift Scheduling
aufbauen. Die erste Methode ist ein Verbesserungsverfahren, das auf den Ergebnissen einer Kon
struktionsheuristik basiert und ein komplexes Schichtplanungsproblem behandelt. Der zweite Al
gorithmus bezieht sich auf eine Teilproblemklasse und lost¨ viele praktische Probleminstanzen
beweisbar optimal. Schließlich wird ein Algorithmus fur¨ die Erstellung komplexer Schichtrader¨
auf Basis einer aggregierten Bedarfsdarstellung konzipiert. Der Ansatz baut auf einem Modell zur
impliziten Darstellung flexibler Pausen auf und lost¨ das Shift Scheduling und Dienstplanungs
problem simultan.
Die Modelle und Algorithmen in dieser Arbeit sind stark¨ er integriert und berucksichtigen¨ kom
plexere Nebenbedingungen als fruhere¨ Beitrage.¨ Moderne Techniken des Constraint Program
ming und der ganzzahligen Programmierung (einschließlich Spaltengenerierungs und Branch
and Price Ans atzen)¨ werden eingesetzt. Fur¨ die vorgestellten neuartigen Optimierungsprobleme
werden Komplexitatsuntersuchungen¨ durchgefuhrt.¨ Alle Algorithmen werden auf großen, kom
plexen Testfallen¨ aus der Praxis von Fluglinien, Flughafen¨ und Bodenverkehrsgesellschaften eva
luiert.Acknowledgements
This work has been carried out at the airport division of INFORM Institut fur¨ Operations Research
und Management GmbH. Many people have contributed to this thesis in one way or the other.
First, I would like to thank my doctoral advisors. Prof. Dr. Drs. h.c. Hans Jur¨ gen Zimmermann
initially made this work possible, and I am very grateful for his valuable support and feedback.
Prof. Dr. Juraj Hromkovicˇ was so kind to act as referee even if this entailed an additional burden
with his new position at ETH Zurich.¨ I would like to express my gratitude for his support and
comments on earlier drafts of this work. Thanks also to Prof. Dr. Peter Rossmanith for acting as
an additional co referee.
Special thanks go to Adrian Weiler for leading me to this challenging field of research and for
his interest in my work, and to Thomas Schmidt and Uschi Schulte Sasse for their encourage
ment. I am particularly indebted to Werner Siemes who leads the planning development group at
INFORM’s airport division. Without his support, this work would not have been possible.
Torsten Fahle provided me with numerous comments and suggestions, and I am very grateful
for the fruitful discussions. His extensive proof reading down to the smallest indices has consid
erably contributed to the quality of this thesis. Special thanks also to Ulrich Dorndorf and Tuomo
Takkula for discussions, suggestions and comments on earlier versions of this work. Christian,
Daniel, Melanie and Wolfgang deserve my gratitude for further corrections and suggestions.
Christof, Dimitra, Julia, Simone and Tom were not only colleagues, but have become real
friends, and their support has meant a lot to me. Thanks also to Andrea, Alex, Bernd, Frank,
Holger, Melanie, Michael, Olli, Sunil, Clementine and Fich for the pleasant working environment,
the motivating atmosphere and the guidance with the optimisation problems and the planning
system. Christian was an inspiring partner for lunchtime discussions during my short return to
student life.
The staff at Dash Optimization was very ambitious in providing me with suggestions for tuning
the cyclic roster algorithm.
My sincere gratitude goes to my parents who made this possible, for supporting and encourag
ing me during the years. Special thanks also to my brothers Jens and Ulf for their support.
Last but not least, special thanks to Katrin for her patience, love and encouragement throughout
all ups and downs of my work.Contents
1. Introduction 1
1.1. Airport Ground Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2. Planning Processes an