article

Duty-period-based network model for crew rescheduling in European airlines

Authors:

Rüdiger Nissen,

Knut HaaseAuthors Info & Claims

Journal of Scheduling, Volume 9, Issue 3

Pages 255 - 278

https://doi.org/10.1007/s10951-006-6780-1

Published: 01 June 2006 Publication History

Abstract

Airline rescheduling is a relatively new field in airline Operations Research but increasing amounts of traffic will make disturbances to the original schedule more frequent and more severe. Thus, the need to address the various problems arising from this situation with systematic, cost-efficient approaches is becoming more urgent. One such problem is crew rescheduling where after a disturbance in the crew schedule the aim is to determine new crew assignments that minimize the `impact' on the original schedule.

In this work we present a new duty-period-based formulation for the airline crew rescheduling problem that is tailored to the needs of European airlines. It uses a new type of resource constraints to efficiently cover the various labor regulations. A solution method based on branch-and-price is tested on various rescheduling scenarios, each with several distinct cases. Results show that the solution method is capable of providing solutions within the short period of time available to a rescheduler after a disturbance occurs.

References

[1]

Anbil, R., E. Gelman, B. Patty, and R. Tanga, "Recent advances in crew-pairing optimization at American Airlines", Interfaces, vol. 21, no. 1, pp. 62-74, 1991.

Digital Library

[2]

Bard, J.F., G. Yu, and M.F. Argüello, "Optimizing aircraft routings in response to grounding and delays", IIE Transactions, vol. 33, pp. 931-947, 2001.

[3]

Bixby, R.E., J.W. Gregory, I.J. Lustig, R.E. Marsten, and D.F. Shanno, "Very large scale linear programming: A case study in combining interior point and simplex methods", Operations Research, vol. 40, no. 5, pp. 885-897, 1992.

Digital Library

[4]

Campbell, K.W., R.B. Durfee, and G.S. Hines, "FedEx generates bid lines using simulated annealing", Interfaces, vol. 27, no. 2, pp. 1-16, 1997.

Digital Library

[5]

Clarke, M.D.D., "Irregular airline operations: A review of the state-of-the-practice in airline operations control centers", Journal of Air Transport Management, vol. 4, no. 2, pp. 67-76, 1998.

[6]

CPLEX Optimization Inc, Using the CPLEX callable library, CPLEX Optimization: Incline Village, Nevada, 2000.

[7]

Day, P.R., and D.M. Ryan, "Flight attendant rostering for short-haul airline operations", Operations Research, vol. 45, no. 5, pp. 649-661, 1997.

Digital Library

[8]

Desaulniers, G., J. Desrosiers, Y. Dumas, S. Marc, B. Rioux, M.M. Solomon, and F. Soumis, "Crew pairing at Air France", European Journal of Operational Research, vol. 97, pp. 220-244, 1997.

[9]

Gamache, M., F. Soumis, D. Villeneuve, J. Desrosiers, and É GÉlinas, "The preferential bidding system at Air Canada", Transportation Science, vol. 32, no. 3, pp. 246-255, 1998.

Digital Library

[10]

Gamache, M., F. Soumis, and G. Marquis (1999), "A column generation approach for large-scale aircrew rostering problems", Operations Research, vol. 47, no. 2, pp. 247-262, 1999.

[11]

Graves, G.W., R.D. McBride, I. Gershkoff, D. Anderson, and D. Mahidhara, "Flight crew scheduling", Management Science, vol. 39, no. 6, pp. 736-745, 1993.

Digital Library

[12]

Hoffman, K.L., and M. Padberg, "Solving airline crew scheduling problems by branch-and-cut", Management Science, vol. 39, no. 6, pp. 657-682, 1993.

[13]

Irrgang, M.E., "Airline irregular operations" in D. Jenkins, and C.P. Ray (eds.), Handbook of airline economics (1st edition), McGrawHill Aviation Week Group: New York, pp. 349-365, 1995.

[14]

Jarrah, A.I.Z., and J.T. Diamond, "The problem of generating crew bidlines", Interfaces, vol. 27, no. 4, pp. 49-64, 1997.

[15]

Klabjan, D., E.L., Johnson, G.L. Nemhauser, E. Gelman, and S. Ramaswamy, "Solving large airline crew scheduling problems: Random pairing generation and strong branching", Computational Optimization and Applications, vol. 20, pp. 73-91, 2001.

[16]

Lavoie, S., M. Minoux, and E. Odier, "A new approach for crew pairing problems by column generation with an application to air transportation", European Journal of Operational Research, vol. 35, pp. 45-58, 1988.

[17]

Lettovský, L., E.L. Johnson, and G.L. Nemhauser, "Airline crew recovery", Transportation Science, vol. 34, no. 4, pp. 337-348, 2000.

Digital Library

[18]

Medard C.P., and N. Sawhney, "Airline crew scheduling: From planning to operations", Carmen Systems AB, Güteborg, Sweden, Carmen Research and Technology Report CRTR-0406, 2004.

[19]

Nissen, R., Airline crew rescheduling, Shaker: Aachen, Germany, 2004.

[20]

Rosenberger, J.M., E.L. Johnson, and G.L. Nemhauser, "Rerouting aircraft for airline recovery", Transportation Science, vol. 37, no. 4, pp. 408-421, 2003.

Digital Library

[21]

Ryan, D.M., and B.A. Foster, "An integer programming approach to scheduling" in A. Wren, (ed.), Computer scheduling of public transport, Urban passenger vehicle and crew scheduling, North-Holland: Amsterdam, pp. 269-280, 1981.

[22]

Stojkovi¿ M., and M. Soumis, "The operational airline crew scheduling problem", Transportation Science, vol. 32, no. 3, pp. 232-245, 1998.

[23]

Vance, P.H., A. Atamtürk, C. Barnhart, E. Gelman, E.L. Johnson, A. Krishna, D. Mahidhara, G.L. Nemhauser, and R. Rebello, "A heuristic branch-and-price approach for the airline crew pairing problem", Auburn University, Working Paper, 1997.

[24]

Wedelin, D., "An algorithm for large scale 0-1 programming with application to airline crew scheduling", Annals of Operations Research, vol. 57, pp. 283-301, 1995.

[25]

Wei, G., G. Yu, and M. Song, "Optimization model and algorithm for crew management during airline irregular operations", Journal of Combinatorial Optimization, vol. 1, no. 3, pp. 305-321, 1997.

[26]

Yan, S., and C.-G. Lin, "Airline scheduling for the temporary closure of airports", Transportation Science, vol. 31, no. 1, pp. 72-82, 1997.

Digital Library

[27]

Yu, G., M. Argüello, G. Song, S.M. McCowan, and A. White, "A new era for crew recovery at Continental Airlines", Interfaces, vol. 33, no. 1, pp. 5-22, 2003.

Cited By

Becker TSchiffer MWalther G(2022)A General Branch-and-Cut Framework for Rotating Workforce SchedulingINFORMS Journal on Computing10.1287/ijoc.2021.114934:3(1548-1564)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1287/ijoc.2021.1149
Maher S(2016)Solving the Integrated Airline Recovery Problem Using Column-and-Row GenerationTransportation Science10.1287/trsc.2014.055250:1(216-239)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1287/trsc.2014.0552
Sinclair KCordeau JLaporte G(2016)A column generation post-optimization heuristic for the integrated aircraft and passenger recovery problemComputers and Operations Research10.1016/j.cor.2015.06.01465:C(42-52)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1016/j.cor.2015.06.014
Show More Cited By

Index Terms

Duty-period-based network model for crew rescheduling in European airlines

Recommendations

An integrated aircraft routing, crew scheduling and flight retiming model

In the integrated aircraft routing, crew scheduling and flight retiming problem, a minimum-cost set of aircraft routes and crew pairings must be constructed while choosing a departure time for each flight leg within a given time window. Linking ...
Airline Crew Scheduling Under Uncertainty

Airline crew scheduling algorithms widely used in practice assume no disruptions. Because disruptions often occur, the actual cost of the resulting crew schedules is often greater. We consider algorithms for finding crew schedules that perform well in ...
A computational study of Benders decomposition for the integrated aircraft routing and crew scheduling problem

The integrated aircraft routing and crew scheduling problem consists in determining a minimum-cost set of aircraft routes and crew pairings such that each flight leg is covered by one aircraft and one crew, and side constraints are satisfied. While some ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Scheduling

Journal of Scheduling Volume 9, Issue 3

June 2006

109 pages

ISSN:1094-6136

Issue’s Table of Contents

Copyright © Copyright © 2006 Springer Science + Business Media, LLC.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 June 2006

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Becker TSchiffer MWalther G(2022)A General Branch-and-Cut Framework for Rotating Workforce SchedulingINFORMS Journal on Computing10.1287/ijoc.2021.114934:3(1548-1564)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1287/ijoc.2021.1149
Maher S(2016)Solving the Integrated Airline Recovery Problem Using Column-and-Row GenerationTransportation Science10.1287/trsc.2014.055250:1(216-239)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1287/trsc.2014.0552
Sinclair KCordeau JLaporte G(2016)A column generation post-optimization heuristic for the integrated aircraft and passenger recovery problemComputers and Operations Research10.1016/j.cor.2015.06.01465:C(42-52)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1016/j.cor.2015.06.014
Zhang DHenry Lau HYu C(2015)A two stage heuristic algorithm for the integrated aircraft and crew schedule recovery problemsComputers and Industrial Engineering10.1016/j.cie.2015.05.03387:C(436-453)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1016/j.cie.2015.05.033
Potthoff DHuisman DDesaulniers G(2010)Column Generation with Dynamic Duty Selection for Railway Crew ReschedulingTransportation Science10.1287/trsc.1100.032244:4(493-505)Online publication date: 1-Nov-2010
https://dl.acm.org/doi/10.1287/trsc.1100.0322

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents