Optimization of demand-oriented train timetables under overtaking operations: A surrogate-dual-variable column generation for eliminating indivisibility

This paper aims to optimize demand-oriented train timetables under overtaking operations for a high-speed rail corridor. With the application of the constructed space-time network representation, the timetabling and skip-stopping decisions in response to passenger demand for heterogeneous train traffic are formulated into an integer linear programming model. Specifically, we carefully assign the hour-dependent origin-to-destination demand to the skip-stop-flexible timetable by using a group of tailored constraints that bind the origin station and destination station together. While solving the proposed model under the column-generation-based 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 coupled stations. To dynamically eliminate the indivisibility attached to the demand-oriented timetabling problem, we propose a novel approach to replace the two-station-dependent dual variable with its single-station-dependent surrogate counterpart. A branch-and-price-and-cut procedure is also conducted to achieve the corresponding integer solutions, where specific families of valid inequalities are selected to narrow the feasible solutions in the restricted master problem. Finally, numerical experiments are implemented to demonstrate the efficiency and effectiveness of the proposed method.