Evolutionary crew scheduling with adaptive chromosomes

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 Non-deterministic Polynomial-time (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.

• Record URL:
  https://doi.org/10.1016/j.trb.2013.08.003
• Record URL:
  http://www.sciencedirect.com/science/article/pii/S0191261513001392
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/01912615
• Supplemental Notes:
  • Abstract reprinted with permission from Elsevier.
• Authors:
  • Shen, Yindong
  • Peng, Kunkun
  • Chen, Kai
  • Li, Jingpeng
• Publication Date: 2013-10

Language

• English

Media Info

• Media Type: Print
• Features: Figures; References; Tables;
• Pagination: pp 174-185
• Serial:
  • Transportation Research Part B: Methodological
  • Volume: 56
  • Issue Number: 0
  • Publisher: Elsevier
  • ISSN: 0191-2615
  • Serial URL: http://www.sciencedirect.com/science/journal/01912615

Subject/Index Terms

• TRT Terms: Adaptive control; Genetic algorithms; Personnel management; Public transit; Scheduling; Shifts; Transit operators
• Subject Areas: Planning and Forecasting; Public Transportation; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 01497235
• Record Type: Publication
• Files: TRIS
• Created Date: Oct 21 2013 1:04PM