Demand-Driven Timetabling for a Metro Corridor Using a Short-Turning Acceleration Strategy

The efficient management of metro lines is a major concern for public transport operators. Traditionally, metro lines are operated through regular timetables, that is, timetables where trains have a constant headway between all stations. In this paper, we propose a demand-driven metro timetabling strategy and elaborate exact solution methods for the case of a two-directional metro corridor. In doing so, we avoid imposing any predetermined structure to the timetable, and instead control the trains individually to best match passenger demand. We consider that trains may short turn, that is, trains that are not required to serve the line from terminal to terminal, but instead may reverse direction before reaching the terminal. We present a mixed integer linear programming formulation for the demand-driven timetabling problem of a two-directional metro corridor with short turning. Furthermore, we develop an efficient exact algorithm using cut generation for an alternative formulation with an exponential number of constraints, and derive two classes of valid inequalities. We evaluate the proposed formulation and algorithm considering seven possible cut generation strategies on a number of test instances from artificially generated lines and on two test beds derived from real-world lines. Through the computational experiments, we demonstrate the effectiveness of the developed algorithm and the added value of the proposed strategy in terms of passengers' waiting time.