An efficient train scheduling algorithm on a single-track railway system

Xiaoming Xu (), Keping Li, Lixing Yang () and Ziyou Gao
Additional contact information
Xiaoming Xu: Hefei University of Technology
Keping Li: Beijing Jiaotong University
Lixing Yang: Beijing Jiaotong University
Ziyou Gao: Beijing Jiaotong University

Journal of Scheduling, 2019, vol. 22, issue 1, No 6, 85-105

Abstract: Abstract Since scheduling trains on a single-track railway line is an NP-hard problem, this paper proposes an efficient heuristic algorithm based on a train movement simulation method to search for the near-optimal train timetables within the acceptable computational time. Specifically, the time–space statuses of trains in the railway system are firstly divided into three categories, including dwelling at a station, waiting at a station and traveling on a segment. A check algorithm is particularly proposed to guarantee the feasibility of transition among different statuses in which each status transition is defined as a discrete event. Several detailed operation rules are also developed to clarify the scheduling procedure in some special cases. We then design an iterative discrete event simulation-based train scheduling method, namely, train status transition approach (TSTA), in which the status transition check algorithm and operation rules are incorporated. Finally, we implement some extensive experiments by using randomly generated data set to show the effectiveness and efficiency of the proposed TSTA.

Keywords: Train scheduling; Single-track railway; Train status transition; Discrete event model (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-018-0558-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jsched:v:22:y:2019:i:1:d:10.1007_s10951-018-0558-0

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-018-0558-0

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().