Identification And Releasing Method Of High-speed Railway Capacity Bottleneck

With the rapid development of railway construction in China,the scale of the railway network has been further expanded and the railway network structure has been further improved.Since high-speed railway(HSR)has become one of the most popular transportation means,HSR passenger demands keep increase and tend to be more individual and diversified.As the railway passenger demand grows each year,some of the railway lines in China need to operate more and more trains with limited infrastructure capacity to satisfy the passenger travel demand.However,the capacity utilization of HSR network is uneven,affected by the complex train operation mode,diversified passenger demand and limited infrastructure.For some HSRs,the capacity utilization of some sections approaches saturation level while the capacity utilization of some sections is relatively low.Some busy sections with high-capacity utilization are likely to be the capacity bottleneck of railway network,due to the difficulty of adding additional passenger train operation lines in these sections.Thus,the growing passenger demands are hard to be satisfied,limited by the capacity bottleneck.Since the framework of China’s high-speed railway network is basically formed and it is impossible to expand new lines on a large scale,improving the capacity utilization of the current HSR network seems to be particularly important.Therefore,it is necessary to analyze the influencing factors of HSR capacity utilization,identify the bottleneck of HSR capacity and propose bottleneck releasing methods.It is of great significance to promote the capacity utilization of HSR,as well as meet the increasing diversified passenger demand.The thesis first systemically reviews the literature on capacity utilization,capacity bottleneck identification and capacity optimization,as well as analyzes the shortcomings of the previous works.Considering the conditions and operating characteristics of the railway lines in China,this thesis conduct research on the identification and releasing methods of HSR capacity bottleneck.Specifically,the concept of capacity bottleneck is presented,and the affecting factors of capacity bottleneck are identified by means of the mathematical statistics based on the real-record train operation data.Then,two integer linear programming(ILP)models,capacity bottleneck verification model and capacity bottleneck identification model are established.Based on these models,the capacity utilization of HSR network is evaluated,and the capacity bottlenecks of HSR network are identified.Furthermore,capacity bottleneck releasing models and algorithms are proposed from two aspects.On one hand,releasing strategies related to train adjustment are applied to eliminate the capacity bottleneck.On the other hand,both trains adjustment and passenger travel demand are considered in the bottleneck releasing model.On the whole,this paper develops ILP models and efficient decomposition algorithms for the above capacity bottleneck problems,which are aimed to simultaneously improve the railway infrastructure capacity utilization rate and transport service quality.More specifically,this thesis has completed the following tasks:(1)Statistics analysis of capacity bottleneck influencing factors based on real-record data.Firstly,the thesis qualitatively expounds the influence mechanism of some factors on the capacity bottleneck,including timetable structure(such as train stop plans,train overtaking and train speed),operation of cross-line trains,temporal-spatial distribution characteristics of passenger flow,the matching degree between transport capacity and passenger flow.Subsequently,based on the real-record data of train operation and passenger flow,the thesis performs a qualitative analysis on the influencing effectiveness of the above factors on capacity utilization.The key factors leading to the capacity bottleneck,are identified,such as train stop plan,train speed,and the operation of cross-line trains(2)To address the problem of capacity bottleneck identification,the thesis develops a capacity bottleneck identification model by constructing a saturated timetable.Specifically,the number of train lines that can be added in a given train timetable is taken as the standard to measure the capacity bottleneck,and the capacity bottleneck is defined as the section in which fewer additional train lines can be added.Based on the UIC406 timetable saturation theory and a given timetable,the ILP model is established to get a saturation timetable,by minimizing the total train operation cost in the saturation timetable.Note that the origin train lines in the given timetable should be remained while the alternative train lines that can be added to the given timetable are prepared.The constraints related to timetable and train operation should be considered in the model.In addition,a dual decomposition method,that is Lagrangian Relaxation(LR),is adopted to dualize the departing and arrival interval constraints,such that the original ILP model is decomposed into a set of train-specific sub-problems.For each train-specific sub-problem in an iterative primal and dual optimization framework,an enhanced version of the labeling method is developed to find the time-dependent least cost train path across the space-time network over multiple periods.Thus,the dual solution to LR problem is obtained.Then,LR-motivated heuristic methods are also developed to obtain good upper bound solutions.Based on the UIC 406 timetable compression method,the capacity consumption of railway infrastructure can be measured by compressing the timetable.Regarding the UIC 406 timetable compression method as a framework,an ILP model is proposed to compress the real-record timetable for minimizing the train occupation time of all the trains involved during the time window in a section,concerning train orders,overtaking and crossing on the given timetable.The timetable compression model can be applied to verify the effectiveness of the bottleneck identification model.Finally,the real-world instances from the Chinese HSR network show that the capacity bottleneck identification model and algorithm proposed in this paper are feasible,which can efficiently calculate the number of new train lines in the road network and identify the capacity bottleneck of the road network.The bottlenecks of road network capacity are the sections from Hengyang East to Changsha south,from Bengbu South to Jinan west,and from Hangzhou East to Shanghai Hongqiao.(3)Research on the capacity releasing methods based on the trains adjustment.Firstly,the thesis analyzes the effects of capacity bottleneck influencing factors,such as train departure time,dwelling scheme,train speed difference,and cross-line trains.Based on the factors leading to capacity bottleneck,this thesis puts forward the capacity bottleneck elimination strategies,such as resetting the train departure time window,flexibly setting the train stop time,reducing the running time difference between trains running the sections and reasonably arranging the on-line time and off-line time of cross-line trains.Secondly,considering the constraints of train operation in the above bottleneck removal strategies,a ILP model for capacity bottleneck releasing is estimated,relying on the discrete temporal-spatial networks,to minimize the operating costs of all trains lines in the timetable.In order to solve large-scale practical problems efficiently,the alternating direction multiplier method(ADMM)is designed to relax the train interval constraint.The quadratic penalty term in the objective function is linearized according to the characteristics of model’s and0-1 variable so that the original model is decomposed into a series of sub-problem of a single train.The solution framework is designed based on the rolling solution mechanism.The trains are sorted according to the descending order of train resource cost,and the shortest-path algorithm based on the label method is applied to solve the single train sub-problem one by one.When the solution of ADMM is not feasible,a heuristic algorithm is used to convert the unfeasible solution into a feasible solution.In order to evaluate the efficiency of the ADMM,the standard LR is designed to make a comparison,and an example is designed based on the Beijing-Guangzhou HSR.After employing the capacity bottleneck releasing model,the results indicate that the average number of trains running on the Beijing-Guangzhou line increases by 7 and the average number of trains running on the section from Hengyang East to Changsha South increases by 6,and the line capacity utilization has been greatly improved.Meanwhile,compared to the LR,the ADMM proposed in this section has a higher convergence speed.The ADMM method can effectively improve the quality of feasible solutions and optimal gaps.(4)Research on collaborative optimization related to passenger travel demand and capacity bottleneck releasing.Based on the proposed capacity bottleneck releasing method,passenger demand is further considered,and the thesis conduct research on collaborative optimization between capacity bottleneck releasing and passenger travel is studied.The discrete temporal-spatial network is expanded into a time-space-state three-dimensional network by introducing the passenger transport state.According to the spatial-temporal characteristics of passengers and the existing train operation plan in the bottleneck section,flexible alternative set of service train for passengers can be set according to specific rules.In order to release capacity bottleneck and satisfy passenger travel demands simultaneously,an ILP model is constructed by considering constraints such as passenger traveling constraints and timetable feasibility constraints,to minimize railway transportation costs.Furthermore,an ADMM-based dual decomposition mechanism is developed to dualize the passenger service constraint and track capacity constraint,such that the original ILP model is decomposed into a line planning sub-problem and a set of train-specific sub-problems.After linearizing the quadratic penalty terms in ADMM,each of the sub-problem contains the information of LR prices.Trains are sorted according to the descending order of LR prices,and the shortest-path algorithm based on the label method is applied to solve the single train sub-problem one by one.When the solution obtained by ADMM is infeasible,a heuristic algorithm is used to convert it into a feasible solution.Meanwhile,a standard LR is designed as a comparison to verify the efficiency of the ADMM.Finally,real-world instances from the Beijing-Shanghai HSR are conducted to demonstrate the efficiency of the proposed collaborative optimization model.The results show that the capacity bottleneck of the Beijing-Guangzhou high-speed railway can be effectively eliminated using the collaborative optimization model.All the passengers can depart/arrive at the origin/destination station within the specified time window,and the passenger requirements are satisfied.The average number of trains that can be laid in the capacity bottleneck section increases and the capacity bottlenecks are released efficiently.Specially,the average number of trains running on the Beijing-Guangzhou lines increases by 6.The number of train lines in the section from Hengyang East station to Changsha South station increases by 4,indicating the capacity utilization has been greatly improved and the capacity bottleneck has been released.The average load rate of the rescheduled trains is about 10% higher than the original load rate of trains,and the train capacity has been dramatically improved.Compared to the LR,ADMM has satisfactory performance in the solution quality and solving efficiency.