[en] This article presents a fuzzy-logic controlled genetic algorithm designed for the solution of the crew-scheduling problem in the rail-freight industry. This problem refers to the assignment of train drivers to a number of train trips in accordance with complex industrial and governmental regulations. In practice, it is a challenging task due to the massive quantity of train trips, large geographical span and significant number of restrictions. While genetic algorithms are capable of handling large data sets, they are prone to stalled evolution and premature convergence on a local optimum, thereby obstructing further search. In order to tackle these problems, the proposed genetic algorithm contains an embedded fuzzy-logic controller that adjusts the mutation and crossover probabilities in accordance with the genetic algorithm's performance. The computational results demonstrate a 10% reduction in the cost of the schedule generated by this hybrid technique when compared with a genetic algorithm with fixed crossover and mutation rates.
Disciplines :
Production, distribution & supply chain management Computer science
Author, co-author :
Khmeleva, E.; Sheffield Hallam University > Sheffield Business School
Hopgood, Adrian ; University of Portsmouth & University of Liege - ULiège > HEC Liège : UER > UER Opérations
Tipi, L.; Sheffield Hallam University > Sheffield Business School
Shahidan, M.; Sheffield Hallam University > Sheffield Business School
Language :
English
Title :
Fuzzy-Logic Controlled Genetic Algorithm for the Rail-Freight Crew-Scheduling Problem
Barnhart C, Hatay L, Johnson EL (1995) Deadhead selection for the long-haul crew pairing problem. Oper Res. doi:10.1287/opre.43.3.491
Drexl M, Prescott-Gagnon E (2010) Labelling algorithms for the elementary shortest path problem with resource constraints considering EU drivers’ rules. Log Res. doi:10.1007/s12159-010-0022-9
Kwan RSK (2004) Bus and train driver scheduling. Handbook of scheduling: algorithms, models, and performance analysis. Chapman and Hall/CRC, Boca Raton
Klabjan D, Johnson EL, Nemhauser GL, Gelman E, Ramaswamy S (2001) Solving large airline crew scheduling problems: random pairing generation and strong branching. Comput Optim Appl. doi:10.1023/A:1011223523191
Duck V, Wesselmann F, Suhl L (2011) Implementing a branch and price and cut method for the airline crew pairing optimization problem. Pub Transp. doi:10.1007/s12469-011-0038-9
Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: Column generation for solving huge integer programs. Oper Res. doi:10.1287/opre.46.3.316
Derigs U, Malcherek D, Schafer S (2010) Supporting strategic crew management at passenger railway—model, method and system. Pub Trans. doi:10.1007/s12469-010-0034-5
dos Santos AG, Mateus GR (2009) General hybrid column generation algorithm for crew scheduling problems using genetic algorithm. Evol Comp. doi:10.1109/CEC.2009.4983159
Zeren B, Özkol I (2012) An improved genetic algorithm for crew pairing optimization. J Intell Learn Syst Appl 4:70–80. doi: 10.4236/jilsa.2012.41007
Souai N, Teghem J (2009) Genetic algorithm based approach for the integrated airline crew-pairing and rostering problem. Eur J Oper Res. doi:10.1016/j.ejor.2007.10.065
Park T, Ryu K (2006) Crew pairing optimization by a genetic algorithm with unexpressed genes. J Intell Manuf. doi:10.1007/s10845-005-0011-z
Kornilakis H, Stamatopoulos P (2002) Crew pairing optimization with genetic algorithms. Methods Appl Artif Intell. doi:10.1007/3-540-46014-4_11
Kwan RSK, Wren A, Kwan ASK (2000) Hybrid genetic algorithms for scheduling bus and train drivers. Evol Comput. doi:10.1109/CEC.2000.870308
Costa L, Santo IE, Oliveira P (2014) An adaptive constraint handling technique for evolutionary algorithms. Optimization. doi:10.1080/02331934.2011.590486
Chu PC, Beasley JE (1998) Constraint handling in genetic algorithms: The set partitioning problem. J Heuristics. doi:10.1080/02331934.2011.590486
Rocha M, Neves J (1999) Preventing premature convergence to local optima in genetic algorithms via random offspring generation. In: Imam I, Kodratoff Y, El-Dessouki A, Ali M (eds) Multiple approaches to intelligent systems, IEA/AIE 1999. Lecture notes in computer science, vol 1611. Springer, Berlin, Heidelberg. doi:10.1007/978-3-540-48765-4_16
Herrera F, Lozano M (1996) Adaptation of genetic algorithm parameters based on fuzzy logic controllers. Genetic Algorithms and Soft Computing. Physica-Verlag, Heidelberg, Germany, pp. 95–125
Varnamkhasti MJ, Lee LS, Bakar MRA, Leong WJ (2012) A genetic algorithm with fuzzy crossover operator and probability. Adv Oper Res. doi:10.1155/2012/956498
Srinivas M, Patnaik LM (1994) Adaptive probabilities of crossover and mutation in genetic algorithms. Syst Man Cyber. doi:10.1109/21.286385
Kwan RSK, Kwan ASK, Wren A (2001) Evolutionary driver scheduling with relief chains. Evolut Comput. doi:10.1162/10636560152642869
Wang PY, Wang GS, Song YH (1996) Fuzzy logic controlled genetic algorithms. In: Proceedings of the fifth IEEE international conference on fuzzy systems. doi:10.1109/FUZZY.1996.552310 DOI: 10.1109/FUZZY.1996.552310
Herrera F, Lozano M (2003) Fuzzy adaptive genetic algorithms: design, taxonomy, and future directions. Soft Comput. doi:10.1007/s00500-002-0238-y
Sumer E, Turker M (2013) An adaptive fuzzy-genetic algorithm approach for building detection using high-resolution satellite images. Comput Environ Urban Syst. doi:10.1016/j.compenvurbsys.2013.01.004
McClintock S, Lunney T, Hashim A (1997) A fuzzy logic controlled genetic algorithm environment. In: IEEE international conference on systems, man, and cybernetics. Computational cybernetics and simulation. doi: 10.1109/ICSMC.1997.635189
Hongbo L, Zhanguo X, Abraham A (2005) Hybrid fuzzy-genetic algorithm approach for crew grouping. In: Proceedings of the 5th international conference on intelligent systems design and applications, ISDA ’05. doi: 10.1109/ISDA.2005.51
Yang J, Zhang R, Sun Q, Zhang H (2015) Optimal wind turbines micrositing in onshore wind farms using fuzzy genetic algorithm. Math Probl Eng. doi:10.1155/2015/324203
Homayouni S, And Tang S (2015) A fuzzy genetic algorithm for scheduling of handling/storage equipment in automated container terminals. Int J Eng Technol. doi:10.7763/IJET.2015.V7.844
Lau HCW, Nakandala D, Zhao L (2015) Development of a hybrid fuzzy genetic algorithm model for solving transportation scheduling problem. J Inf Syst Technol Manag. doi:10.4301/S1807-17752015000300001
Zhu KQ, Liu Z (2004) Population diversity in permutation-based genetic algorithm. In: Boulicaut JF, Esposito F, Giannotti F, Pedreschi D (eds) Machine learning: ECML 2004. Lecture notes in computer science, vol 3201. Springer, Berlin, Heidelberg. doi: 10.1007/978-3-540-30115-8_49
Ozdemir HT, Mohan CK (2001) Flight graph based genetic algorithm for crew scheduling in airlines. Inf Sci. doi:10.1016/S0020-0255(01)00083-4
Razali NM, Geraghty J (2011) Genetic Algorithm Performance with Different Selection Strategies in Solving TSP, World Congress on Engineering, vol II WCE 2011, ISBN: 978-988-19251-4-5
Yuhui S, Eberhart R, Yaobin C (1997) Implementation of evolutionary fuzzy systems. IEEE Trans Fuzzy Syst. doi:10.1109/91.755393
Khmeleva E, Hopgood AA, Tipi L, Shahidan M (2014) Rail-freight crew scheduling with a genetic algorithm. In: Bramer M, Petridis M (eds) Research and development in intelligent systems XXXI. Springer, Cham. doi:10.1007/978-3-319-12069-0_16 DOI: 10.1007/978-3-319-12069-0_16
Gopalakrishnan B, Johnson EL (2005) Airline crew scheduling: state-of-the-art. Ann Oper Res. doi:10.1007/s10479-005-3975-3 DOI: 10.1007/s10479-005-3975-3
