A review of principles and methods to decompose large-scale railway scheduling problems
Florin Leutwiler, Francesco Corman
Abstract
Providing punctual, reliable and performant services to customers is one main goal of railway network operators. The railway scheduling problem is to determine, ahead of time (timetabling), a plan describing the timing of the operations in a railway network, or updating such plan during operations (rescheduling). By optimization and automation, it is possible to operate more trains on the network, closer to the infrastructure capacity. Especially when the scale and complexity of the scheduling problem is increasing, for large-scale networks and multiple interconnected problems, this is of great value for network operators. When planning or adjusting railway operations becomes increasingly complex, modern scheduling algorithms can bring significant performance and economic benefits. In this survey we review approaches in the state of the art for the problems of railway scheduling. We show how the many different approaches of decomposition proposed in the literature of railway scheduling can be categorized into two general principles. We study different solution methods and identify a list of open topics for dealing with large-scale problems for future research. • Comprehensive review of decomposition in railway scheduling of large-scale instances. • Identified key commonalities and differences in the decomposition approaches. • Discussed motivation, insights, strength and weaknesses for different decompositions. • Suggested appropriate industry applications of academic methods. • Identified multiple avenues for future research.