Incremental timetable generation in busy and complex railway stations: sliding-window algorithm with cancellation processing

This paper studies the problem of platforming trains faced by railway station infrastructure managers to generate a feasible conflict-free timetable. This platforming problem is to assign each train to an internal line inside the railway station and to find a path towards this line through the railway station network. Two kinds of movements are considered: commercial and technical movements. Strict reference arrival and departure times are only given for commercial movements by activity managers at a national level without any feasibility checking at the railway station level. On the other hand, a time deviation is permitted for technical movements. In this paper, we propose a sliding window algorithm using mathematical programming steps to solve the platforming problem. This hybrid algorithm consists of initialization, preprocessing, resolution, reinsertion and refinement. It takes into account train cancellation with suggestions for the modification of departure and arrival time of commercial movements in order to minimize the number of cancellations. The algorithm is tested based on real data related to a French railway station.