Research On Discrete Event-based Models And Algorithms For Train Scheduling Problem

Train scheduling operations are implemented according to train timetables, which is the core part of railway traffic and also the only way to complete transportation tasks. The quality of a train timetable determines the efficiency of the entire railway system. However, because there are lots of constraints in the system, such as limited capacity, influence among trains. Train scheduling problem, especially for trains on single-track railway, is a difficult work for both practitioners and related researchers. Theoretically, train scheduling problem has proved to be an NP-hard problem. Therefore, the research for train scheduling problem in this paper may not only be helpful for solving some practical problems, but also, to some extend, deepen the theories in the field of operations research. On the basis of the previous work, this paper applies the train movement simulation approach and optimization technology to solving train scheduling problems with different considerations. For different problems, enlightened by Dorfman and Medanic (2004), we discretize train movements on railway line and design corresponding conflict-resolving algorithms and train travel rules, based on which we develop different train scheduling. Specifically, we present the following several researches.1. We propose the concept of balanced train timetable with the least delay-ratio, i.e., the ratio between total train delay time and total train free-run time. A rigorous optimization model is proposed under the consideration of feasible speed constraint for finding the optimal velocity for each train. To obtain an approximately optimal scheduling strategy, a combination of the improved train travel strategy by Dorfman and Medanic (2004) and genetic algorithm, called GA-ITAS method, is in particular proposed to effectively solve the proposed model. The results indicate that compared with the ITAS, the GA-ITAS greatly, respectively, reduces the total delay time by 28.89% and 48.82% in the cases of heterogeneous and homogeneous trains.2. Considering an incident on a track of a double-track railway corridor, we formulate an optimization model to find near-optimal rescheduled timetables with the least total delay, where the crossovers are taken into account. A novel discrete event model is formulated where train position state transitions are characterized as a series of discrete events, based on which several well-developed capacity check algorithms and an efficient train rescheduling strategy (ETRS) are proposed. The experiments demonstrate that the ETRS can reschedule a larger number of trains on a subway line within a relative short computational time (at millisecond level) and suggest that the practical duration of departure intervals should not be smaller than the sum of the maximal section trip time and dwelling time, to ensure that only one train is allowed to run on any section for all the time.3. To further improve the utilization rate of railway tracks and reduce train delays, we present a novel integrated train dynamically routing and timetabling approach on the basis of discrete event model and an improved switchable policy. The aforementioned improved switchable policy, which is rooted in the approaches (Original-SP) by Mu and Dessouky (2013), is designed with the analysis of possible delays caused by different path choices. The case studies indicate that in comparison to No-SP and Original-SP approaches, respectively, the Improved-SP approach can reduce the total delay of trains up to 44.44% and 73.53% within a short computational time. An important conclusion can also be drawn that the total delay produced by Improved-SP approach is less than that generated by No-SP approach in all of the tested experiments, especially for those experiments with larger speed differences.4. We construct a cooperation optimization model, which is typically a Mixed-Integer Programming (MIP) model to simultaneously assign locomotives and schedule trains in single-track railway system with the consideration of minimizing total train delay time. To solve the considered problem, we develop a high-efficient cooperation optimization approach which includes the train movement simulation method and a well-designed locomotive assignment algorithm. We conduct extensive case studies to demonstrate the effectiveness of the proposed cooperation optimization approach. The results show that in most of the cases, the proposed approach is prior to CPLEX. In the best case, the cooperation approach increases the solution quality by as high as 14.15%. Since the proposed approach takes only several milliseconds while CPLEX uses 3 hours to solve the same problem, we conclude that the cooperation approach is better to be used in on-line applications.5. Lastly, we further develop a discrete event model-based simulation approach for train traffic flow on a single-track railway line, where speed limits, slopes and acceleration/deceleration, etc., are taken into consideration. Typically, we design a novel n-step-look-ahead forecasting algorithm to generate the train speed sequence with minimum train travel time. Simulation results demonstrate the effectiveness of the proposed simulation approach. Moreover, we find that line clear time and energy consumption have the same change trend as the dwelling time increases, while have different change patterns with the increase of time headway.