A Differential Evolution Algorithm With Dual Populations for Solving Periodic Railway Timetable Scheduling Problem
- 3 July 2012
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Evolutionary Computation
- Vol. 17 (4) , 512-527
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.Keywords
This publication has 31 references indexed in Scilit:
- Mathematical Solutions for Solving Periodic Railway TransportationMathematical Problems in Engineering, 2009
- A branch and bound algorithm for scheduling trains in a railway networkEuropean Journal of Operational Research, 2007
- Completely Derandomized Self-Adaptation in Evolution StrategiesEvolutionary Computation, 2001
- Adaptive coupling of differential evolution and multiquadrics approximation for the tuning of the optimization processIEEE Transactions on Magnetics, 2000
- System design by constraint adaptation and differential evolutionIEEE Transactions on Evolutionary Computation, 1999
- Periodic network optimization with different arc frequenciesDiscrete Applied Mathematics, 1996
- A genetic algorithm approach to periodic railway synchronizationComputers & Operations Research, 1996
- A Mathematical Model for Periodic Scheduling ProblemsSIAM Journal on Discrete Mathematics, 1989
- Schedule synchronization for public transit networksOR Spectrum, 1989
- A railway scheduling problemMathematical Methods of Operations Research, 1986