High Efficiency And High Precision Research On The Integration Of High-speed Railway Train Timetabling Problem

Up to 2020,the total mileage of high-speed railway(HSR)in operation worldwide has reached 52,000 kilometers,of which the operating mileage of HSR in China is 35,000 kilometers,accounting for 2/3 of the total operating mileage in the world.With the rapid development of HSR network,its high-speed,high-comfort,high-convenient,low-carbon and environmentally friendly operating characteristics have also brought huge increase in the number of passengers dispatched.Only in 2019,the national HSR passenger traffic volume reached 2.35 billion person-times.However,the continuous increase of passenger traffic has also brought new challenges to the operation and management of HSR.The Medium and Long-Term Railway Network Planning points out that at present,some cross-regional channels still have capacity shortages.Moreover,with the improvement of people's economic living standard,passengers have higher requirements for travel service level.The hierarchical optimization characteristics of traditional transportation organization methods have been difficult to adapt to the operation mode of HSR,and have become a key factor restricting the improvement of HSR service level.In response to this problem,based on the full reference of relevant domestic and foreign research experience,this paper proposes an integrated system for the compilation of HSR train timetabling problem,and studies specific theories and methods.The main research contents of this paper are as follows:(1)Sorted out the relevant contents of the station operation plan.It first introduces the operation of trains in the station,then describes the establishment process,unlocking process,approach search and approach conflicts of the station approach in detail,and points out the deficiencies of using the approach to describe the train operation in the station.On this basis,an approach plane-time three-dimensional discrete time-space network is proposed,which can well describe the whole process of train operation on the line and lay a foundation for the subsequent study of the passing ability of the train timetabling.(2)Use the approach plane-time three-dimensional discrete time-space network to transform the train timetabling problem into a network flow problem with resource constraints.Based on this,the HSR train timetabling and station operation integration model with the optimization goal of maximizing the number of trains and minimizing the total stop time are constructed,and an improved branch-and-price algorithm is designed to solve.Taking the actual Beijing-Shanghai HSR line as an example,it is verified that the model and algorithm proposed in this paper can effectively improve the passing capacity of the line on the basis of ensuring the quality of passenger service.(3)An integrated compilation model of HSR train timetabling and stop plan based on discrete time-space network is constructed,and the optimization problem of HSR train timetable under conditions of non-sequential and non-fixed stop station is studied from the perspective of meeting passenger service demand,train scheduling and station service demand.An improved branch-and-price algorithm is designed.When solving the pricing problem,the ASPFA algorithm based on A* algorithm and SPFA algorithm is proposed to solve the shortest path problem of the restricted dynamic weight network.Taking the actual Wuhan-Guangzhou HSR line as an example,it is verified that the proposed model and algorithm can effectively improve the quality of the train timetable and the travel efficiency of passengers.(4)In view of the problems of easy degradation,solving time-consuming of sub-problem,and difficulty in solving integers in the improved branch-and-price algorithm.The corresponding acceleration strategies are proposed from the pre-processing stage,restricted master problem stage,pricing problem stage,branching stage,and post-processing stage.And multiple sets of comparative experiments are designed to measure the acceleration effect of different strategy combinations.Taking the Beijing-Shanghai HSR as an example,it is verified that the proposed acceleration strategies can effectively improve the calculation efficiency of the algorithm while ensuring the calculation accuracy.