Solving The Train Scheduling Problem Of A Single-Track Line

Provision of punctual and reliable services is a major goal in railway operations and management.Due to the complexities of railroad operations planning,innovative operation management strategies must be developed in order to optimize the existing capacity,improve profitability and the general level of rail service.Train scheduling is an important stage in railway operations planning and is used as the basis for railroad organization.In this thesis,the train scheduling problem of a single-track line is formulated as a variable-based cumulative flow model so as to minimize the total completion time of trains traversing the network.Through the reformulation of the physical network infrastructure capacity on a time-space network,the model enables the decomposition of the initial complex train scheduling problem into a series of multiple single-train optimization sub-problems.The physical network of the entire railway line is constructed in NEXTA-Rail Network Editor.A train scheduling package FastTrain,which combines a time-dependent shortest path algorithm and a priority rule-based algorithm within a Lagrangian relaxation framework is used to solve the proposed model.The model is applied in a case study on Kenya’s Mombasa-Nairobi Standard Gauge Railway.The construction of the physical network is first done for the current network consisting of 33 stations and then with 45 stations for the planned long-term network.The data for this line was obtained from the feasibility study reports.In the solution,a maximum of 10000 iterations was allowed after which the program terminates.FastTrain tends to converge to better solutions with increasing number of Lagrangian iterations and the optimality gap decreases with increasing computational time.The hardest problem comprised 36 trains and was solved in 43 min 18 s,with optimality gap of 16.1%,which is within acceptable time for a train scheduling problem.The impact of varying the traffic demand by increasing the number of scheduled trains as well as opening up the reserved passing stations on this network is discussed.The results obtained from this research can be used as a support tool to schedule trains on single-track railway networks as well as a planning tool to assess the implications of changes in traffic demand and railroad infrastructure.