A Workload-Balance Crossover Operation in a Genetic Algorithm solving an Airline Crew Rostering Problem
Article Sidebar
Published:
Jun 30, 2012
Keywords:
crew rostering genetic algorithm heurictic
Main Article Content
Abstract
The airline crew rostering problem is complex and very difficult to find the answer in a suitable time because the requirements are complicated and the size of the crew and flight are very large. This paper proposes the Genetic Algorithm to find a crew rostering solution for the case study of Thai Airways. The objective is to balance the workload and perdiem for each crew member. A non-binary encoding is used in the chromosome. The mutation and crossover are modified to accommodate the objective of the problem. The algorithm is tested with data from Thai Airways and the efficiency of the algorithm and the analysis of the result are discussed.
Article Details
How to Cite
อ้นสวน ก. ., อินทิยศ บ. ., & จีนอนันต์ ช. . (2012). A Workload-Balance Crossover Operation in a Genetic Algorithm solving an Airline Crew Rostering Problem. Journal of Engineering, RMUTT, 1, 1–10. Retrieved from https://ph01.tci-thaijo.org/index.php/jermutt/article/view/242124
Section
Research Articles
The manuscript, information, content, picture and so forth which were published on Journal of Engineering, RMUTT has been a copyright of this journal only. There is not allow anyone or any organize to duplicate all content or some document for unethical publication.
References
[1] D. Levine, 1996 "Application of a Hybrid Genetic Algorithm to Airline CrewScheduling,"Computers and Operations Research. 23, 6 (June): 547-558.
[2] K. Kotecha, G. Sanghani, N. Gambhava, 2004"'Genetic Algorithm for Airline Crew Scheduling Problem Using Cost-Based Uniform Crossover,"Applied Computing. 3285: 84-91.
[3] N. Souai, J. Teghem, 2009 "Genetic algorithm based approach for the integrated airline crew-pairing and rostering problem," European Journal of Operational Research.199,3 (December):674-683.
[4] H.T. Ozdemir, Chilukuri K.Mohan, 2001 "Flight graph based genetic algorithm for crew scheduling inairlines," Information Sciences.133,3-4(April):165-173.
[5] ZHANG Yinghui, RAO Yunbo, ZHOU Mingtian,2007"'GASA Hybrid Algorithm Applied in Airline Crew Rostering System," Tsinghua Science and Technology. 12, 1 (November):255-259.
[6] W. EL Moudani, Marc de Coligny and Felix MoraCamino, 2001 "A Bi-Criterion Approach for
the Airline Crew Rostering Problem," Computer Science. 1993:486-500.
[7] Alberto Caprara, Paolo Toth, Daniele Vigo, Matteo Fischetti, 1998 "Modeling and Solving the Crew Rostering Problem,"' Operations Research. 46,6 (November-December): 820-830.
[8] Yufeng Guo, Taieb Mellouli, Leena Suhl, Markus P. Thiel, 2006 "A partially integrated airline crew scheduling approach with time-dependent crew capacities and multiple home bases," European Journal of Operational Research. 171, 3: 1169-1181.
[9] B. Maebhout and Vanhoucke, 2010 "A Hybrid Scatter Search Heuristic for Personalized Crew Rosteringin the Airline Industry," European Journal of Operational Research. 206, 1: 155-167.
[10] D. M. Ryan, 1992 "The Solution of Massive Generalized Set Partitioning Problems in Aircrew Rostering," The Journal of the Operational Research Society. 43, 5(May): 459-467.
[11] Michel Gamache, Francois Soumis, Gerald Marquis,Jacques Desrosiers, 1999 "A Column Generation Approach for Large-Scale Aircrew Rostering Problems," Operations Research. 47, 2 (March-April): 247-263.
[12] P. Lucic and D. Teodorovic, 2007 "Metaheuristics approach to the aircrew rosteringproblem," Annals of Operations Research. 155, 1 (November):311-338.
[13] Paul R. Day and David M. Ryan, 1997 "Flight Attendant Rostering for Short-Haul Airline Operations,'"Operations Research.45,5(September-October): 649-661.
[14] M. Stojkovic, F. Soumis, J. Desrosiers, 1998 "The Operational Airline Crew Scheduling Problem," Transportation Science.32,3 (August):232-245.
[15] Paola Cappanera and Giorgio Gallo, 2004 "A Multicommodity Flow Approach to the Crew Rostering Problem," Operations Research. 52, 4 (July-August): 583-596.
[16] Michael J. Brusco and Larry W. Jacobs, 1993" A Simulated Annealing Approach to the Solution of Flexible LabourScheduling Problems,'"The Journal of the Operational Research Society. 44, 12 (December): 1191-1200.
[17] Tanet Kato, Chawalit Jeenanunta, 2010 "Crew Rostering Problem: Case of ThaiDomesticLowCostAirline," The 10t International Conference on Industrial Management, Beijing, Sep. 16-18,2010:480-485.
[18] Chawalit Jeenanunta, Boonyarit Intiyot, Wariya Puttapatimok, 2010 "A Multi-commodity Flow Approach to the Crew Rostering Problem,," The 2nd International Conference on Logistics and Transport,Queenstown,NewZealand,Dec.16-18,2010:735-742.
[19] V. Limlawan, B. Kasemsontitum, C. Jeenanunta 201 1"AirlineCrew Rostering ProblemUsingParticle SwarmOptimization,"The 2011 IE EE International Conferenceon Qualityand Reliability,Bangkok,Thailand, Sep. 14-17, 2011:501-505.
[20] Chawalit Jeenanunta, Boontariga Kasemsontitum,Tawinan Noichawee, 2011 "A Multi commodity Flow Approach for the Aircraft Routing and Maintenance Problem," The 2011 IEEE International Conference on Quality and Reliability,Bangkok, Thailand, Sep. 14-17, 2011:150-155.
[2] K. Kotecha, G. Sanghani, N. Gambhava, 2004"'Genetic Algorithm for Airline Crew Scheduling Problem Using Cost-Based Uniform Crossover,"Applied Computing. 3285: 84-91.
[3] N. Souai, J. Teghem, 2009 "Genetic algorithm based approach for the integrated airline crew-pairing and rostering problem," European Journal of Operational Research.199,3 (December):674-683.
[4] H.T. Ozdemir, Chilukuri K.Mohan, 2001 "Flight graph based genetic algorithm for crew scheduling inairlines," Information Sciences.133,3-4(April):165-173.
[5] ZHANG Yinghui, RAO Yunbo, ZHOU Mingtian,2007"'GASA Hybrid Algorithm Applied in Airline Crew Rostering System," Tsinghua Science and Technology. 12, 1 (November):255-259.
[6] W. EL Moudani, Marc de Coligny and Felix MoraCamino, 2001 "A Bi-Criterion Approach for
the Airline Crew Rostering Problem," Computer Science. 1993:486-500.
[7] Alberto Caprara, Paolo Toth, Daniele Vigo, Matteo Fischetti, 1998 "Modeling and Solving the Crew Rostering Problem,"' Operations Research. 46,6 (November-December): 820-830.
[8] Yufeng Guo, Taieb Mellouli, Leena Suhl, Markus P. Thiel, 2006 "A partially integrated airline crew scheduling approach with time-dependent crew capacities and multiple home bases," European Journal of Operational Research. 171, 3: 1169-1181.
[9] B. Maebhout and Vanhoucke, 2010 "A Hybrid Scatter Search Heuristic for Personalized Crew Rosteringin the Airline Industry," European Journal of Operational Research. 206, 1: 155-167.
[10] D. M. Ryan, 1992 "The Solution of Massive Generalized Set Partitioning Problems in Aircrew Rostering," The Journal of the Operational Research Society. 43, 5(May): 459-467.
[11] Michel Gamache, Francois Soumis, Gerald Marquis,Jacques Desrosiers, 1999 "A Column Generation Approach for Large-Scale Aircrew Rostering Problems," Operations Research. 47, 2 (March-April): 247-263.
[12] P. Lucic and D. Teodorovic, 2007 "Metaheuristics approach to the aircrew rosteringproblem," Annals of Operations Research. 155, 1 (November):311-338.
[13] Paul R. Day and David M. Ryan, 1997 "Flight Attendant Rostering for Short-Haul Airline Operations,'"Operations Research.45,5(September-October): 649-661.
[14] M. Stojkovic, F. Soumis, J. Desrosiers, 1998 "The Operational Airline Crew Scheduling Problem," Transportation Science.32,3 (August):232-245.
[15] Paola Cappanera and Giorgio Gallo, 2004 "A Multicommodity Flow Approach to the Crew Rostering Problem," Operations Research. 52, 4 (July-August): 583-596.
[16] Michael J. Brusco and Larry W. Jacobs, 1993" A Simulated Annealing Approach to the Solution of Flexible LabourScheduling Problems,'"The Journal of the Operational Research Society. 44, 12 (December): 1191-1200.
[17] Tanet Kato, Chawalit Jeenanunta, 2010 "Crew Rostering Problem: Case of ThaiDomesticLowCostAirline," The 10t International Conference on Industrial Management, Beijing, Sep. 16-18,2010:480-485.
[18] Chawalit Jeenanunta, Boonyarit Intiyot, Wariya Puttapatimok, 2010 "A Multi-commodity Flow Approach to the Crew Rostering Problem,," The 2nd International Conference on Logistics and Transport,Queenstown,NewZealand,Dec.16-18,2010:735-742.
[19] V. Limlawan, B. Kasemsontitum, C. Jeenanunta 201 1"AirlineCrew Rostering ProblemUsingParticle SwarmOptimization,"The 2011 IE EE International Conferenceon Qualityand Reliability,Bangkok,Thailand, Sep. 14-17, 2011:501-505.
[20] Chawalit Jeenanunta, Boontariga Kasemsontitum,Tawinan Noichawee, 2011 "A Multi commodity Flow Approach for the Aircraft Routing and Maintenance Problem," The 2011 IEEE International Conference on Quality and Reliability,Bangkok, Thailand, Sep. 14-17, 2011:150-155.