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

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.