Evolutionary crew scheduling with adaptive chromosomes

Yindong Shen, Kunkun Peng, Kai Chen and Jingpeng Li

Transportation Research Part B: Methodological, 2013, vol. 56, issue C, 174-185

Abstract: This paper presents an adaptive evolutionary approach incorporating a hybrid genetic algorithm (GA) for public transport crew scheduling problems, which are well-known to be NP-hard. To ensure the search efficiency, a suitable chromosome representation has to be determined first. Unlike a canonical GA for crew scheduling where the chromosome length is fixed, the chromosome length in the proposed approach may vary adaptively during the iterative process, and its initial value is elaborately designated as the lower bound of the number of shifts to be used in an unachievable optimal solution. Next, the hybrid GA with such a short chromosome length is employed to find a feasible schedule. During the GA process, the adaptation on chromosome lengths is achieved by genetic operations of crossover and mutation with removal and replenishment strategies aided by a simple greedy algorithm. If a feasible schedule cannot be found when the GA’s termination condition is met, the GA will restart with one more gene added. The above process is repeated until a feasible solution is found. Computational experiments based on 11 real-world crew scheduling problems in China show that, compared to a fuzzy GA known to be well performed for crew scheduling, better solutions are found for all the testing problems. Moreover, the algorithm works fast, has achieved results close to the lower bounds obtained by a standard linear programming solver in terms of the number of shifts, and has much potential for future developments.

Keywords: Crew scheduling; Metaheuristic; Genetic algorithm; Adaptive chromosome; Public transit (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261513001392
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:56:y:2013:i:c:p:174-185

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2013.08.003

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().