A genetic algorithm for heterogeneous high-speed railway timetabling with dense traffic: The train-sequence matrix encoding scheme. (September 2022)

• Record Type: Journal Article
• Authors: Yao, Zhiyuan; Nie, Lei; He, Zhenhuan
• Is Part Of: Journal of rail transport planning & management. Volume 23(2022)
• Publication Date: 2022-09
• Subjects: Train timetabling -- Genetic algorithm -- Local search -- Train ordering -- Train overtaking; Railroads -- Periodicals; Railroads -- Planning -- Periodicals; Railroads -- Management -- Periodicals; Railroads; Railroads -- Management; Railroads -- Planning; Periodicals; 385.068
• DOI: 10.1016/j.jrtpm.2022.100334
• Languages: English
• ISSNs: 2210-9706

Abstract

Abstract: Recently, the continued growth of passenger demand for high-speed railways and expectations for varied types of train services have posed a great need for designing a railway timetable suitable for dense and heterogeneous train traffic, where train overtaking is necessary for proper capacity utilization. This study develops an efficient genetic algorithm that considers train orders in all sections to better depict train overtaking and impose specific operational rules essential in this context. Train-sequence matrix is chosen as the chromosome encoding, based on which the "exchange + regeneration" matrix crossover operator is innovatively designed that considers the heterogeneity among trains and improves the feasibility of the crossover, which previous one-sequence crossover operators cannot realize. An overtaking-oriented local search heuristic is inserted in the algorithm to facilitate the local improvement. To guarantee the feasibility of the final solution, a conflict resolution procedure with conflict impact area identification is introduced. Tests of the algorithm on several small- and medium-sized cases reveal that it can reach relatively good solutions within a short time. Finally, the algorithm is tested on Beijing-Shanghai high-speed railway corridor in China and presents good performance both in efficiency and quality. Highlights: A train timetabling model that considers train overtaking rules and heterogeneous train traffic is developed. The suitable form of genetic algorithm in heterogeneous train timetabling problem is analyzed. An efficient genetic algorithm based on train-sequence matrix encoding is designed.