Using Differential Evolution Method to Solve Crew Rostering Problem
- 1
- 2
- 3
Abstract
Airline crew rostering is the assignment problem of crew members to planned rotations/pairings for certain month. Airline companies have the monthly task of constructing personalized monthly schedules (roster) for crew members. This problem became more complex and difficult while the aspirations/criterias to assess the quality of roster grew and the constraints increased excessively. This paper proposed the differential evolution (DE) method to solve the airline rostering problem. Different from the common DE, this paper presented random swap as mutation operator. The DE algorithm is proven to be able to find the near optimal solution accurately for the optimization problem. Through numerical experiments with some real datasets, DE showed more competitive results than two other methods, column generation and MOSI (the one used by the Airline). DE produced good results for small and medium datasets, but it still showed reasonable results for large dataset. For large crew rostering problem, we proposed decomposition procedure to solve it in more efficient manner using DE.
- R. Anbil, J. J. Forrest and W. R. Pulleyblanck, “Column Generation and the Airline Crew Pairing Problem,” Documentation Mathematica Extra, Journal der Deutschen Mathematiker Vereinigung Volume ICM, III, 1998, pp. 677-686.
- C. Barnhart, E. L. Johnson, G. L. Nemhauser, M. W. P. Savelsbergh and P. H. Vance, “Branch and Price: Column Generation for Solving Huge Integer Programs,” Operation Research, Vol. 46, No. 3, 1998, pp. 316-329.
- I. Gershkoff, G. W. Graves, R. D. Mc Bridge, D. Anderson and D. Mahidhara, “Flight Crew Scheduling,” Management Science, Vol. 39, No. 6, 1993, pp. 736-745.
- K. L. Hoffman and M. Padberg, “Solving Airline Crew Scheduling Problems by Branch and Cut,” Management Science, Vol. 39, No. 6, 1993, pp. 657-682.
- N. Souai, and J. Thegem, “Genetic Algorithm Based Ap- Proach for the Integrated Airline Crew-Pairing and Rostering Problem,” European Journal of Operational Research, Vol. 199, No. 3, 2009, pp. 674-683.
- N. Kohl, “Application of OR and CP Techniques in a Real World Crew Scheduling System,” In Proceedings of CP-AI-OR’00: 2nd International Workshop on Integra- tion of AI and OR Techniques in Constraint Program- ming for Combinatorial Optimization Problems, Pader- born, Germany, 8-10 March 2000, pp. 105-108.
- N. Kohl and S. E. Karisch, “Integrating Operations Re- search and Constraint Programming Techniques in Crew Scheduling,” In Proceedings of the 40th Annual AGIFORS Symposium, Istanbul, Turkey, 20-25 August 2000.
- S. C. K. Chu, “Generating, scheduling, and Rostering of Shift Crew-Duties: Applications at the Hongkong International Airport,” European Journal of Operational Research, Vol. 177, No. 3, 2007, pp. 1764-1778.
- C. P. Medard and N. Sawhney, “Airline Crew Scheduling from Planning to Operation,” European Journal of Operational Research, Vol. 183, No. 3, 2005, pp. 1013-1027.
- P. H. Vance, C. Barnhart, E. L. Johnson and G. L. Nemhauser, “Airline Crew Scheduling: A New Formulation and Decomposition Algorithm,” Operation research, Vol. 45. No. 2, 1997, pp. 188-200.
- P. Lu?i?, and D. Teodorovi?, “Simulated Annealing for the Multi-Objective Aircrew Rostering Problem,” Transportation Research Part A, Vol. 33, No. 1, 1999, pp. 19- 45.
- D. Levine, “Application of a Hybrid Genetic Algorithm to Airline Crew Scheduling,” Computer Operations Research, Vol. 23, No. 6, 1996, pp. 547-558.