Crew pairing optimization by a genetic algorithm with unexpressed genes |
| |
Authors: | Email author" target="_blank">Taejin?ParkEmail author Kwang?Ryel?Ryu |
| |
Affiliation: | (1) Department of Computer Engineering, Pusan National University, San 30, Jangjeon-Dong, Guemjeong-Ku, Busan, 609-735, Korea |
| |
Abstract: | We propose a genetic algorithm to solve the pairing optimization problem for subway crew scheduling. Our genetic algorithm
employs new crossover and mutation operators specially designed to work with the chromosomes of set-oriented representation.
To enhance the efficiency of the search with the newly designed genetic operators, we let a chromosome consist of an expressed
part and an unexpressed part. While the genes in both parts evolve, only the genes in the expressed part are used when an
individual is evaluated. The purpose of the unexpressed part is to preserve information susceptible to be lost by the application
of genetic operators, and thus to maintain the diversity of the search. Experiments with real-world data have shown that our
genetic algorithm outperforms other local search methods such as simulated annealing and tabu search.
Received: June 2005/Accepted: December 2005 |
| |
Keywords: | Genetic algorithm Unexpressed genes Crew paring optimization Maximal covering problem |
本文献已被 SpringerLink 等数据库收录! |
|