Highlights We study an integrated train timetabling and track maintenance scheduling problem. We present a new bi-objective microscopic optimization model for this problem. We propose an iterative algorithm to compute near-optimal solutions in a short time. The iterative algorithm outperforms previous methods and a commercial solver. We provide new best-known solutions to PSC instances.

    Abstract 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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

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


    Contributors:


    Publication date :

    2019-07-22


    Size :

    42 pages




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English






    Integrated Optimization Model on Maintenance Time Window and Train Timetabling

    Meng, Lingyun / Mu, Ce / Hong, Xin et al. | British Library Conference Proceedings | 2018


    Robust Train Timetabling

    Cacchiani, Valentina / Toth, Paolo | Springer Verlag | 2018