Research On Algorithm Of Train Scheduling Problem In The Single-track Railway Network

The train scheduling problem on the single-track railway has always been very difficult in the research of railway transportation. Compared with the double-track and multi-track railway, the interaction between trains is more complex in the single-track railway, and more constrains need be considered. However, the single-track line has a substantial proportion in the rail network in our country. And it has an intricate connection between single-track line, double-track line and the multi-track line. So the qualities of scheduling plan on single-track lines have sigificant effect on the train scheuling of other multi-track sections, even the entire railway network. It has an important practical significance of improving the quality of scheduling plan and the technique of conflict detection and conflict resolution on single-track line.In this dissertation, we make some researches about the train scheduling algorithm based on single-track railway network. On the basis of correlative research at home and abroad, the single-track train scheduling model is introduced based on railway network. Based on the discrete event model proposed by Dorfman, we design a more efficient ETAS algorithm for solving train scheduling problem, which combine the simulation technology with optimization method. Based on this research, we further concern the model and algorithm about train scheduling problem with the assignment of track or platform in the station, and also discuss the tain depart adjustment problem. The contents of this dissertation are as follows:1. The ETAS method has been designed for solving the train scheduling problem, which adopts the combination of the simulation technology and the optimization.(1) The extended capacity check algorithm is designed to avoid the deadlock phenomenon.(2) The ETAS method for solving train scheduling problem is proposed based on the global conflict information in the remainder route of the train, which determine the macroscopic travel strategy of the train so as to improve the drawback of the TAS method.(3) Based on the different requirement for the solution quality and computational performance, three strategies are designed to expect and estimate all the conflict information in the remainder route of the train. (4) The acceleration of the train is adopted in the ETAS method to describe microscopic behavior of the train. Based on the local information of the train, such as the position and velocity, the expression of the train's acceleration can be decided.(5) Several important factors are analyzed to determine the update step of the discrete dynamic system. The event-step method proposed ensures that the ETAS method not only can describe the microscopic behavior of the train accurately, but also has efficient computational performance.2. We discuss the train scheduling model and algorithm when the track assignment is considered in the station. The 0-1 mixed integer programming model is constructed, which consider some constraints related to the station, such as track occupation, track capacity, etc. The SATA method (Scheduling Algorithm with Track Assignment) is designed to solving the developed model. The character of the SATA method is that, the scheduling plan obtained by the ETAS method is decomposed as a discrete event serial. Moreover, two track assignment strategies are adopted based on analyse of train information in the station.3. The train departure adjustment problem is studied in the paper. We showed that it is feasible and necessary of adjusting train departure to further impove the quality of train scheduling plan on the foundation of original departure time. The two-phase heuristic algorithm (TDAS method) has been designed to solve the problem. In the first phase, we propose a search strategy to obtain reasonable distribution of conflict point in the train diagram. Based on the detailed analysis of the conflict character between different trains, the criterions of reasonable conflict distribution are introduced. In the second phase, the departure adjustment strategy is designed to improve the quality of train scheduling plan, based on the delayed information of the train, which is reflected by the feasible scheduling plan obtained by the ETAS method.