Studies in Computational Intelligence
              Volume              1732009
Computational Intelligence in Integrated Airline SchedulingAuthors:

• Tobias Grosche
• …show all 1hide
  

ISBN: 978-3-540-89886-3 (Print) 978-3-540-89887-0  (Online)

Series: Studies in Computational Intelligence, Vol. 173

Grosche, Tobias

2009, XX, 250 p. 129 illus.


ISBN 978-3-540-89887-0

  Immediately available per PDF-download (no DRM, watermarked)

About this book

• Presents applications of Computational Intelligence in Integrated Airline Scheduling
  

An airline schedule represents the central planning element of each airline. In general, the objective of airline schedule optimization is to find the airline schedule that maximizes operating profit. This planning task is not only the most important but also the most complex task an airline is confronted with. Until now, this task is performed by dividing the overall planning problem into smaller and less complex subproblems that are solved separately in a sequence. However, this procedure is only of minor capability to deal with interdependencies between the subproblems, resulting in less profitable schedules than those being possible with an approach solving the airline schedule optimization problem in one step. In this work, two planning approaches for integrated airline scheduling are presented. One approach follows the traditional sequential approach: existing models from literature for individual subproblems are implemented and enhanced in an overall iterative routine allowing to construct airline schedules from scratch. The other planning appraoch represents a truly simultaneous airline scheduling: using metaheuristics, airline schedules are processed and optimized at once without a separation into different optimization steps for its subproblems.

Contents
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Airline Scheduling Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.1 Airline Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.2 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Flight Schedule Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1 Problem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.2 Solution Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 Aircraft Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.1 Problem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.2 Solution Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.4 Crew Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.1 Problem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.2 Solution Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.5 Integrated Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.5.1 Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.5.2 Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.6 Summary, Conclusion, and Future Challenges . . . . . . . . . . . . . 42
2.6.1 Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.6.2 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.6.3 Future Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3 Foundations of Metaheuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.2 Metaheuristic Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
VIII Contents
3.3 Design Elements of Metaheuristics . . . . . . . . . . . . . . . . . . . . . . . 49
3.3.1 Solution Representation and Variation Operators . . . . 50
3.3.2 Fitness Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.3.3 Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.3.4 Search Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.4 Selected Metaheuristic Optimization Techniques . . . . . . . . . . . 53
3.4.1 Local Search: Threshold Accepting . . . . . . . . . . . . . . . . 53
3.4.2 Recombination-Based Search: Genetic Algorithms . . . 54
3.5 Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4 Integrated Airline Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.1.2 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.1.3 Data. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.2 Schedule Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.2.1 Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.2.2 Market Size Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.2.3 Itinerary Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.2.4 Itinerary Market Share Estimation . . . . . . . . . . . . . . . . 84
4.2.5 Passenger Allocation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.2.6 Profit Estimation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.2.7 Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.3 Sequential Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
4.3.1 Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
4.3.2 Solution Steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.3.3 Solution Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
4.3.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
4.3.5 Summary and Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 126
4.4 Simultaneous Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
4.4.1 Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
4.4.2 Conceptual Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
4.4.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
4.4.4 Summary and Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 155
4.5 Evaluation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
4.5.1 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
4.5.2 Experimental Verification . . . . . . . . . . . . . . . . . . . . . . . . 161
4.5.3 Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
4.6 Summary, Conclusion, Limitations, and Future Work . . . . . . 167
4.6.1 Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
4.6.2 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
4.6.3 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
4.6.4 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
Contents IX
5 Summary, Conclusions, and Future Work . . . . . . . . . . . . . . . . 173
5.1 Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
5.2 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
5.3 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
A Aircraft Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
B Experimental Setups. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
B.1 Scenario A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
B.2 Scenario B. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
B.3 Scenario C. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
B.4 Scenario D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
B.5 Scenario E. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
C Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
C.1 Calibration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
C.1.1 Sequential Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
C.1.2 Simultaneous Approach . . . . . . . . . . . . . . . . . . . . . . . . . . 190
C.2 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
C.2.1 Sequential Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
C.2.2 Simultaneous Approach . . . . . . . . . . . . . . . . . . . . . . . . . . 211
C.3 Evaluation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249