A differential evolution algorithm with dual populations for solving periodic railway timetable scheduling problem

Jing Hui Zhong, Meie Shen, Jun Zhang, Henry Shu Hung Chung, Yu Hui Shi, Yun Li

Research output: Contribution to journalArticle

51 Citations (Scopus)

Abstract

Railway timetable scheduling is a fundamental operational problem in the railway industry and has significant influence on the quality of service provided by the transport system. This paper explores the periodic railway timetable scheduling (PRTS) problem, with the objective to minimize the average waiting time of the transfer passengers. Unlike traditional PRTS models that only involve service lines with fixed cycles, this paper presents a more flexible model by allowing the cycle of service lines and the number of transfer passengers to vary with the time period. An enhanced differential evolution (DE) algorithm with dual populations, termed 'dual-population DE' (DP-DE), was developed to solve the PRTS problem, yielding high-quality solutions. In the DP-DE, two populations cooperate during the evolution; the first focuses on global search by adopting parameter settings and operators that help maintain population diversity, while the second one focuses on speeding up convergence by adopting parameter settings and operators that are good for local fine tuning. A novel bidirectional migration operator is proposed to share the search experience between the two populations. The proposed DP-DE has been applied to optimize the timetable of the Guangzhou Metro system in Mainland China and six artificial periodic railway systems. Two conventional deterministic algorithms and seven highly regarded evolutionary algorithms are used for comparison. The comparison results reveal that the performance of DP-PE is very promising.

Original languageEnglish
Article number6231680
Pages (from-to)512-527
Number of pages16
JournalIEEE Transactions on Evolutionary Computation
Volume17
Issue number4
DOIs
Publication statusPublished - 12 Aug 2013

Keywords

  • differential evolution (DE)
  • evolutionary algorithm
  • passenger waiting time
  • periodic railway timetable scheduling

Fingerprint Dive into the research topics of 'A differential evolution algorithm with dual populations for solving periodic railway timetable scheduling problem'. Together they form a unique fingerprint.

  • Cite this