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.