Using Differential Evolution Method to Solve Crew Rostering Problem

Budi Santosa, Andiek Sunarto, Arief Rahman

.

DOI: 10.4236/am.2010.14042                

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.

Keywords

Differential Evolution, Crew Scheduling, Pairing, Rostering

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	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.
[2]	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.
[3]	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.
[4]	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.
[5]	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.
[6]	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.
[7]	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.
[8]	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.
[9]	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.
[10]	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.
[11]	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.
[12]	D. Levine, “Application of a Hybrid Genetic Algorithm to Airline Crew Scheduling,” Computer Operations Research, Vol. 23, No. 6, 1996, pp. 547-558.
[13]	J. E. Beasly and B. Cao, “A Tree Search Algorithm for the Crew Scheduling Problem,” European Journal of Operational Research, Vol. 94, No. 3, 1996, pp. 517-526.
[14]	Z. Yinghui, R. Yunbao and Z. Mingtian, “GASA Hy- Brid Algorithm Applied in Airline Crew Rostering System,” Tsinghua Science and Thechnology, Vol. 12, No. S1, 2007, pp. 225-259.
[15]	R. Storn and K. Price, “Differential Evolution: A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces,” Technical Report TR-95-012, International Computer Science Institute, 1995.
[16]	V. P. Kennet, M. S. Rainer and A. L. Jouni, “Differential Evolution: A Practical Approach to Global Optimization,” Springer-Verlag, Berlin Heidelberg, 2005.
[17]	M. F. Tasgetiren, Q. K. Pan, Y. C. Liang and P. N. Suganthan, “A Discrete Differential Evolution Algorithm for the Total Earliness and Tardiness Penalties with a Common Due Date on Single Machine,” Proceedings of the 2007 IEEE Symposium on Computational Intelligence in Scheduling, 2007, pp. 271-278.
[18]	L. Jian, P. Chen and Z. M. Liu, “Solving Traveling Salesman Problems by Genetic Differential Evolution with Local Search,” Workshop on Power Electronics and Intelligent Transportation System, 2008
[19]	M. G. H. Omran and A. Salman, “Constrained Optimiza- tion Using CODEQ,” Chaos, Solitons and Fractals, Vol. 42, No. 2, 2009, pp. 662-668.
[20]	R. L. Fox, “Optimization Methods for Engineering Design,” Addison-Wesley, Reading, Massachusetts, 1971.
[21]	J. H. Cassis and L. A. Schmit, “On Implementation of the Extended Interior Penalty Function,” International Journal for Numerical Methods in Engineering, Vol. 10, No. 1, 1976, pp. 3-23.
[22]	Z. Labiba, “Aplikasi metode column generation dalam penyelesaian penugasan kru maskapai penerbangan: studi kasus di PT. Merpati Nusantara Airlines,” Tesis magister teknik, Jurusan Teknik Industri ITS, Surabaya, (in Bahasa Indonesia), 2006.
[23]	A. Rusdiansyah, Y. D. Mirenani and Z. Labiba, “Pemodelan dan penyelesaian permasalahan penjadwalan pilot dengan metode eksak dekomposisi,” Jurnal Teknik Industri, Vol. 9, No. 2, Desember 2007, pp. 112-124.