A computational study of Benders decomposition for the integrated aircraft routing and crew scheduling problem

A computational study of Benders decomposition for the integrated aircraft routing and crew scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor2006894
Country: United Kingdom
Volume: 32
Issue: 6
Start Page Number: 1451
End Page Number: 1476
Publication Date: Jun 2005
Journal: Computers and Operations Research
Authors: , ,
Keywords: personnel & manpower planning, scheduling, vehicle routing & scheduling, programming: mathematical
Abstract:

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 side constraints involve only crews or aircraft, linking constraints impose minimum connection times for crews that depend on aircraft connections. We propose an enhanced model incorporating robustness to handle these linking constraints and compare two Benders decomposition methods – one with the aircraft routing problem as the master problem and one with the crew pairing problem. We also study the impact of generating Pareto-optimal cuts on the speed of convergence of these methods. Computational experiments performed on test instances provided by two major airlines show that the proposed approach yields high-quality solutions in reasonable computing times.

Reviews

Required fields are marked *. Your email address will not be published.