Optimizing Demand-driven High-Speed Train Timetables By Using Column Generation Approach

As an important component of high-speed railway operations and management,train timetables determine the arrival,departure and passing times for each train at each station,and provide the basis for passengers to arrange travel activities.In practice,the train timetable design is influenced by many complicated constraints and different optimization goals.It has been recognized as an intractable problem in the public transportation field,and has long been much concerned by the relevant scholars.Traditionally,the train timetable and its closely related factors such as skip-stop patterns and operation zones are determined separately under a hierarchical decision-making framework.Though such hierarchical decision can effectively simplify this problem,the resulting solution is difficult to coordinate the different requirements of operators and passengers.Thus,it is necessary to propose a system-optimization-based approach to generate well-designed train timetables for satisfying their requirements.In this dissertation research,we consider the train timetabling problems with various operational constraints and heterogeneous passenger demand considerations,and formulate them as different integer linear programming models.Then the high-performance column-generation-based algorithms are designed to solve these problems.The main contents of the research are as follows.(1)The train timetabling problem with station-based passenger demand is studied.The hour-dependent demand entering and leaving stations is given,and the actual constraints such as train overtakings,skip-stop patterns and safe operational intervals are systematically considered.Further,a 0-1 integer programming model based on train space-time path variables is proposed.The column generation algorithm is adopted for the proposed model,in which an improved labeling algorithm is designed to solve the pricing subproblem with train skip-stop constraints.To obtain the expected integer solution,the column generation procedure is embedded in a branch-and-bound framework.Finally,the results of numerical experiments demonstrate that the proposed approach can obtain satisfactory train timetables.(2)The train timetabling model with hour-dependent OD demand is presented.For the hour-dependent OD demand under consideration,all the passengers during a period are able to successfully take the qualified trains.The timetabling and skip-stopping decisions in response to passenger demand for heterogeneous train traffic are formulated into an integer linear programming model.While solving the proposed model under the branch-and-price-and-cut framework,the biggest barrier is that the pricing subproblem cannot be successfully solved through the standard dynamic programming algorithm,because the dual price from the demand constraint is dependent upon two indivisible stations.Therefore,we propose a novel approach to replace the two-station-dependent dual variable with its single-station-dependent surrogate counterpart,and several numerical examples are conducted to show the efficiency of the proposed approach.(3)The optimization of train timetables under excess demand condition is performed.For the excess demand,the remaining passengers during the peak periods are considered.By introducing new passenger assignment variables,an excess-demand-driven train timetabling model is proposed by extending the above mathematical model with hour-dependent OD demand.The branch-and-price-and-cut algorithm is still used to solve the proposed model.The results from some numerical experiments show that the obtained train schedules are basically consistent with the spatial and temporal distribution of passenger demand.That is,there are more trains in peak hours and fewer in off-peak hours.(4)The train timetables with unfixed operation zones are optimized.Under the conditions of the unfixed train operational zones,the hour-dependent OD demand and the total number of trains are known a priori.We use heterogeneous space-time paths to illustrate running trajectories for trains in candidate zones and present passenger travel processes.Considering the two types of path variables,a mathematical model is established to simultaneously optimize the arrival and departure times,the skip-stop patterns and the operation zones.Finally,a column-generation-based two stage approach is proposed,in which the heuristic method is designed to speed up the solution process of pricing subproblem.Finally,the efficiency of the proposed approach is verified by different-size experiments.(5)The train timetabling problem with passenger transfer is studied.Considering the hour-dependent OD demand in a high-speed rail network,a multidimensional space-time network is constructed to illustrate train movements on different lines and represent travel processes of heterogeneous demand.Under this high-dimensional analysis framework,an optimization model with passenger transfer is proposed to minimize the total costs of passengers and trains.Finally,a column-generation-based heuristic method is presented,and then its effectiveness is demonstrated by numerical experiments.