Applying Lagrangian Relaxation-Based Algorithm for the Airline Coordinated Flight Scheduling Problems

Authors: Chia-Hung Chen, Shangyao Yan

Abstract:

The solution algorithm, based on Lagrangian relaxation, a sub-gradient method and a heuristic to find the upper bound of the solution, is proposed to solve the coordinated fleet routing and flight scheduling problems. Numerical tests are performed to evaluate the proposed algorithm using real operating data from two Taiwan airlines. The test results indicate that the solution algorithm is a significant improvement over those obtained with CPLEX, consequently they could be useful for allied airlines to solve coordinated fleet routing and flight scheduling problems.

Keywords: Coordinated flight scheduling, multiple commodity network flow problem, Lagrangian relaxation.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1076108

References:

[1] Etschmaier M, Mathaisel D (1984) Aircraft Scheduling: The State of the Art. AGIFORS XXIV 181-209
[2] Yan S and Tseng C H (2002) A Passenger Demand Based Model for Airline Flight Scheduling and Fleet Routing. Computers and Operations Research 29: 1559-1581
[3] Barnhart C, Kniker T, and Lohatepanont M (2002) Itinerary-Based Airline Fleet Assignment. Transportation Science 36(2): 199-217
[4] Lohatepanont M and Barnhart C (2004) Airline Schedule Planning: Integrated Models and Algorithms for Schedule Design and Fleet Assignment. Transportation Science 38(1): 19-32
[5] Yan S, Tang C H and Lee M C (2007) A Flight Scheduling Model for Taiwan Airlines under Market Competitions. OMEGA - International Journal of Management Science 35: 61-74
[6] Yan S, Chen S C and Chen C H (2006) Fleet Routing and Timetable Setting with Multiple Timeliness Air Cargo-s Demand. Transportation Research 42E(5): 409-430
[7] Yan S and Chen C H (2007) Coordinated Scheduling Models for Allied Airlines. Transportation Research 15C: 246-264
[8] Yan S and Chen C H (2008) Optimal Flight Scheduling Models for Cargo Airlines under Alliances. Journal of Scheduling 11(3): 175-186
[9] Garey M R and Johnson D S (1979) Computers and intractability: A Guide to the Theory of NP-Completeness, W.H. Freemean & Company, San Francisco
[10] Lee B C (1986) Routing Problem with Service Choices, Flight Transportation Laboratory Report R86-4, MIT, Cambridge, Massachusetts
[11] Teodorovic D (1988) Airline Operation Research. Gordon and Breach Science, New York
[12] Ball M O, Magnanti T L, Monma C L and Nemhauser G L (1995) Network Routing. Handbooks in Operations Research and Management Science
[13] Fisher M L (1981) The Lagrangian Relaxation Method for Solving Integer Programming Problems. Management Science 27: 1-18
[14] Yan S and Young H F (1996) A Decision Support Framework for Multi-Fleet Routing and Multi-Stop Flight Scheduling. Transportation Research 30A: 379-398
[15] Camerini P K, Fratta L and Maffioli F (1975) On Improving Relaxation Methods by Modified Gradient Techniques. Mathematical Programming Study 3: 6-25
[16] Barnhart C, Johnson E D, Nemhauser G L, Savelsbergh M W P and Vance P H (1998) Branch and Price Column Generation for Solving Hugh Integer Programs. Operations Research 46: 316-329