Train timetabling by skip-stop planning in highly congested lines

•A real-world application combining train scheduling with adding/skipping stops while considering acc/dec times is studied.•A Lagrangian-based heuristic algorithm is extended from a previous work to deal with the additional features.•Real-world instances of the JingHu Line with up to 387 trains are tested showing the effectiveness of the proposed algorithm.

We study the problem of scheduling passenger trains in a highly congested railway double-track line with the aim of increasing the number of scheduled trains. A feasible timetable of the trains currently scheduled in the network is given. Additional trains should be scheduled to meet the increasing passenger demand. To achieve this goal, we are allowed to increase the dwelling time of some trains at some stations, to let them stop at some additional stations and even to skip a few stops. Thereby, we need to take explicitly into account the deceleration and acceleration times that are needed by the train when it stops at a station. This problem integrates the choice of the train schedule with the choice of the train stops, the latter being usually made in the Line Planning process. To solve this problem, we propose a heuristic algorithm, extended from a previous method to include the new features of the studied application, and show its performance on real-world instances of the Chinese high-speed JingHu corridor (between Beijing and Shanghai) involving up to 387 trains.