Team oriented airline crew scheduling and rostering [Elektronische Ressource] : problem description, solution approaches, and decision support / vorgelegt von Markus P. Thiel

Markus P. Thiel

Sujets

• Handel

Informations

• Publié par: universitat_paderborn
• Publié le: 01 janvier 2005
• Nombre de lectures: 47
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

DOCTORAL THESIS


Team-oriented Airline Crew Scheduling and Rostering:
Problem Description, Solution Approaches,
and Decision Support


Submitted to the
Faculty of Business Administration and Economics
at the University of Paderborn, Germany

by
Markus P. Thiel
Diplom-Wirtschaftsinformatiker


Advisor Prof. Dr. rer. nat. Leena Suhl
Co-advisors Prof. Dr.-Ing. habil. Wilhelm Dangelmaier
Prof. Dr. rer. nat. Burkhard Monien
Prof. Dr. rer. pol. Natalia Kliewer

Paderborn, 2005







Team-oriented Airline Crew Scheduling and Rostering:
Problem Description, Solution Approaches, and Decision Support


Fakultät für Wirtschaftswissenschaften der Universität Paderborn
zur Erlangung des akademischen Grades
eines Doktors der Wirtschaftswissenschaften
doctor rerum politicarum (Dr. rer. pol.)

vorgelegte Dissertation von
Markus P. Thiel, Diplom-Wirtschaftsinformatiker

Paderborn, 2005


II










To my
loving parents






III
Acknowledgements

I am very grateful to the head of our laboratory, Prof. Dr. Leena Suhl, for guiding
my Ph.D. research during the last 3.5 years. Especially I would like to thank her
for the advice she gave me and the excellent support. Thank you for supervis-
ing and promoting this thesis also during tough times encountered.
In addition, I received valuable feedback of the commission members: Prof. Dr.-
Ing. habil. Wilhelm Dangelmaier, Prof. Dr. Burkhard Monien, and Prof. Dr. Na-
talia Kliewer. Thanks to all of you for your early and honest comments already
at early stages of my research work. I would also like to thank Prof. Dr. Taïeb
Mellouli from the University of Halle for his helpful support and stimulating con-
versations. As a former colleague he introduced me to the problem domain of
crew scheduling, and to real-life problems and data of our business partner.
My special appreciation goes to all my colleagues at the Decision Support &
Operations Research Laboratory at the University of Paderborn. Thank you for
the great cooperation, numerous fruitful discussions and the general support. I
am greatly indebted to my friend and office maid Dr. Yufeng Guo. We shared
uncountable discussions, also co-authored several publications and presenta-
tions during these years. Many thanks are directed to Dipl.-Wirt. Inform. Claus
Biederbick for the final proof-reading. Also Ms. Karin Heyen did an excellent job
on checking my English grammar. Special thanks also go to all the students and
friends who contributed their thoughts and ideas to certain aspects of this the-
sis. Thanks to Dipl.-Wirt. Inform. Sascha Keßels for his continuous assistance.
Particular thanks I would like to direct to the complete team of the International
Graduate School Dynamic Intelligent Systems – not only for offering this special
Ph.D. program, but also for an open hear whenever it was necessary. Thanks to
Prof. Dr. Wilhelm Schäfer, and PD Dr. Eckhard Steffen. I wish the IGS all the
best for the future and that many Ph.D. students will have the chance to face
the 3-years challenge over the next decades.
Furthermore, special thanks are also handed over to Dipl.-Kff. Stefanie Schmidt
and Dipl.-Wirt. Inform. Holger Bunzel for their support and hospitality during the
decisive months.
At the end, my most sincere thanks are addressed to my parents. Although my
father left before I finished this document, I thank both of you for believing in
me, supporting me, and reminding me of what is really important in life.

Paderborn, August 2005 Markus P. Thiel
IV
Abstract

Airline crew scheduling is a comparably well-studied field in Operations Re-
search, and most cost-relevant factors have been optimized to the greatest ex-
tent. As a result, usually second-class or casual attention is paid to the consid-
eration of the teams involved that form the mandatory flight personnel. It is well-
known that misunderstandings and disharmonies among the crew due to unfa-
miliar colleagues lead to a negative crew satisfaction which has a negative ef-
fect on the airline’s customers. More importantly, their occurrence is even
safety-critical with regard to the operating cockpit crew.
In this work a first interpretation of the Team-oriented Scheduling Problem
(ToSP) is presented. Irrespective of the assignment approach chosen (bidline
systems, personalized rostering or preferential bidding systems), current ap-
proaches do not account for frequently occurring changes within daily or day-
by-day team compositions. So crew members rarely know in advance the
strengths and weaknesses of their team-mates they are scheduled to work with.
Therefore, the realization of enhanced team stability should be highly appreci-
ated by the crew as well as by the airline itself. In this document a special em-
phasis is put on the personalized rostering in the so-called Team-oriented Ros-
tering Problem (ToRP).
Tailored to the requirements for the cockpit crew, namely captains and first offi-
cers, several mathematical programming-based optimization models are dis-
cussed. Based on a case study of a European tourist airline, a set of solution
approaches is presented. When the new approach is embedded into a decision
support system, the implied trade-off between additional operational cost and
the selected evaluation criteria for team orientation, e.g., the amount of team
changes, is examined along with further computational results.

Keywords: airline, cockpit crew, crew scheduling problem (CSP), crew pairing problem (CPP),
crew rostering problem (CRP), crew assignment problem (CAP), decision support
system (DSS), set partitioning problem (SPP), team orientation, team-oriented ros-
tering problem (ToRP), team-oriented scheduling problem (ToSP)

V
Content overview

Chapter 1 Introduction .......................................................................................1
Chapter 2 Airline Crew Scheduling....................................................................7
Chapter 3 Team-oriented Scheduling and Rostering.......................................39
Chapter 4 Model Formulations for Team-oriented Rostering...........................71
Chapter 5 Solution Approaches for Team-oriented Rostering .........................97
Chapter 6 Decision Support for Team-oriented Scheduling 128
Chapter 7 Conclusion ....................................................................................144

Bibliography....................................................................................................148
Glossary .........................................................................................................158

VI
Table of Contents

Chapter 1 Introduction .......................................................................................1
1.1 Motivation ...........................................................................................1
1.2 Goals of the Thesis and Demarcation ................................................4
1.3 Structure of the Thesis .......................................................................5

Chapter 2 Airline Crew Scheduling....................................................................7
2.1 Basics.................................................................................................7
2.1.1 Scheduling Processes.................................................................................. 7
2.1.2 Task Characteristics and Definitions ............................................................ 9
2.1.3 Assignment Approaches............................................................................. 13
2.1.4 Governmental Work Rules and Union Agreements ................................... 15
2.2 Model Formulations ..........................................................................16
2.2.1 The Crew Pairing Problem ......................................................................... 16
2.2.2 The Crew Assignment Problem.................................................................. 17
2.3 Solution Approaches ........................................................................19
2.3.1 Constructive Heuristics............................................................................... 19
2.3.2 Mathematical Programming 20
2.3.3 Network-based Models 23
2.3.4 Meta-Heuristics........................................................................................... 24
2.3.5 Further Approaches.................................................................................... 25
2.4 Partially Integrated Crew Scheduling................................................27
2.4.1 Aggregated Network Formulation for the Crew Pairing Chain Problem..... 28
2.4.2 Constructive Heuristics for the Rostering................................................... 30
2.5 Excursus: The Operational Crew Scheduling Prob