Microscopic optimization model and algorithm for integrating train timetabling and track maintenance task scheduling

This paper addresses the problem of improving the integration between passenger timetabling and track maintenance scheduling. We propose a microscopic optimization model and an iterative algorithm for solving this problem efficiently. Block sections are considered as the basic microscopic elements for train movements in a railway network. A mixed-integer linear programming formulation is proposed for the integrated optimization problem in which train timing, sequencing and routing are the timetabling variables, while timing and sequencing of maintenance tasks are the track maintenance variables. The objective function is to minimize the total train travel time and the maintenance tardiness cost. The constraints proposed in this work address the practical specifications of the INFORMS RAS 2016 Problem Solving Competition (2016 PSC). In this context, the main decision variables are the entrance and exit times of the trains on each block section plus the start and end times of each maintenance task. Since the integrated optimization problem is strongly NP-hard, an iterative algorithm is proposed to compute near-optimal solutions in a short computation time. The algorithm is based on a decomposition of the overall problem into sub-problems related to train scheduling and/or routing with or without track maintenance task scheduling. The connecting information between the two sub-problems concerns the selected train routes plus the start and end times of the maintenance tasks. Computational experiments are performed on a set of realistic railway instances, which were introduced during the 2016 PSC. The iterative algorithm outperforms a standard MILP solver and the first-place team of this competition in terms of both solution quality and time to deliver the new best-known solutions. The scalability of the iterative algorithm is investigated when increasing the number of trains and track maintenance tasks.