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

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.

• Chia-Hung Chen
• Shangyao Yan

• Coordinated flight scheduling
• multiple commodity network flow problem
• Lagrangian relaxation.

[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