A Heuristic Algorithm for Solving Crew Rostering Problem

Abstract:

Crew rostering is one of the most important scheduling problems for large airlines. In this study, a LP resolving algorithm in the B&B tree context and a heuristic for the IP solution of the crew rostering problem were proposed. The efficiency mainly comes from the special structure of the crew rostering problem. The computational experiments on the real-world problems showed that the time of the proposed resolving algorithm doesn't exceed 30% of that solves from scratch although the problem has largely changed, and the heuristic for the IP solution can rapidly get a sufficiently good scheme for all crew.

• Periodical: Applied Mechanics and Materials (Volumes 178-181)
• Pages: 2854-2858
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.178-181.2854
• Online since: May 2012
• Authors: Ming Yu Zhao, Zhen Yu Wang, Qiong Liu
• Keywords: Crew Rostering Optimization, Set Partition Problem, Subproblem Algorithm

References

[1] Cynthia Barnhart. Airline Scheduling: Accomplishments, Opportunities and Challenges. Lecture Notes in Computer Science, Vol. 5015, 2008.

[2] Cynthia Barnhart, Amy Cohn, Ellis Johnson, Diego Klabjan, et.al. Airline Crew Scheduling, in Randolph W. Hall (Eds.), Handbook of Transportation Science, Kluwer Scientific Publishers, Boston. 2003, pp.57-93.

DOI: 10.1007/0-306-48058-1_14

[3] Niklas Kohl, Stefane E. Karisch. Airline Crew Rostering: Problem Types, Modeling and Optimization. Annals of Operations Research, Vol. 127, No. 1-4, 2004, pp.223-257.

DOI: 10.1023/b:anor.0000019091.54417.ca

[4] Mingyu Zhao, Qiong Liu, Zhenyu Wang. Slacken Piercing Point Based Subproblem Algorithm for the LP Relaxation of Crew Rostering. International MultiConference of Engineers and Computer Scientists 2012.

[5] Ranga Anbil, Rajan Tanga, Ellis Johnson. A Global Approach to Crew Pairing Optimization. IBM Systems Journal 31, 1991, pp.71-78.

DOI: 10.1147/sj.311.0071