Techniques for Inserting Additional Train Paths into Existing Cyclic Timetables

With the development of high-speed railway (HSR), cyclic timetable shows many advantages. However, the pure cyclic timetable is not suitable in China's HSR. Consequently, a hybrid timetable concept named "cyclic + non-cyclic" timetable is proposed, with a cyclic core timetable in which some trains are inserted as non-cyclic trains. Nowadays, the cyclic timetables have been well developed but the technique of inserting additional train paths is still a significant demand for research. The Adding Train Paths (ATP) problem firstly is an integration of timetable scheduling and rescheduling problem. Therefore it is considered involving many general constraints, such as flexible running time, dwell time and headways. Based on an event-activity graph, a general mixed integer program model for the ATP problem is formulated. In addition, several real-world constraints that concerning the acceleration and deceleration time, priority for overtaking, station capacity, allowed adjustments, periodic structure and frequency of services are incorporated into the general model. In order to get a new timetable that with low deviations to the initial services and high quality of the performance to the additional trains, objective functions of minimizing travel time, minimizing total adjustments, minimizing the makespan and maximizing the robustness of the new timetable are discussed in this thesis. More importantly, many additional trains may not be inserted because of a shortage of train-sets. So how to cover the entire trains with minimum train-sets must be also taken into account in this problem. The train-set circulation in the ATP problem is decomposed to two sub-problems. (i) For initial trains, the initial train-set route is assumed to be fixed; it is solved as a rescheduling problem of a tight constraint to keep the current circulation. (ii) For additional trains, it is a train-set planning problem to cover all the additional trains with minimal number of train-sets. In order to solve the problem in a reasonable time, we start from fixed train-set route, and then apply flexible train-set route that provides possible alternative turning activities to decrease the waiting time of a train-set in an overnight turn-around. Case studies based on Shanghai-Hangzhou HSR line in China investigate the proposed framework and associated techniques. Meanwhile, the performances of various settings are compared to analyse the affecting factors to this specific problem.