An integrated train service plan optimization model with variable demand: A team-based scheduling approach with dual cost information in a layered network

A well designed train timetable should fully utilize the limited infrastructure and rolling stock resources to maximize operators’ profits and passenger travel demand satisfaction. Thus, an internally coherent scheduling process should consider the three main aspects: (1) dynamic choice behaviors of passengers so as to evaluate and calculate the impact of variable passenger demand to (2) underlying train service patterns and detailed timetables, which in turn are constrained by (3) infrastructure and rolling stock capacity. This paper aims to develop an integrated demand/service/resource optimization model for managing the above-mentioned three key decision elements with a special focus on passengers’ responses to time-dependent service interval times or frequencies. The model particularly takes into account service-sensitive passenger demand as internal variables so that one can accurately map passengers to train services through a representation of passenger carrying states throughout a team of trains. The added state dimension leads to a linear integer multi-commodity flow formulation in which three closely interrelated decision elements, namely passengers’ response to service interval times, train stopping pattern planning and timetabling for conflict detecting and resolving are jointly considered internally. By using a Lagrangian relaxation solution framework to recognize the dual costs of both passenger travel demand and limited resources of track and rolling stock, we transfer and decompose the formulation into a novel team-based train service search sub-problem for maximizing the profit of operators. The sub-problem is solvable efficiently by a forward dynamic programming algorithm across multiple trains of a team. Numerical experiments are conducted to examine the efficiency and effectiveness of the dual and primal solution search algorithms.