Highlights Model and solve simultaneous passenger train routing and timetabling problem. Reformulate model containing a smaller number of safety usage interval constraints. Provide a train-based decomposition framework by relaxing fewer constraints. Present an efficient optimization method based on Lagrangian relaxation decomposition. Design a heuristic algorithm for generating feasible solution based on dual solution.

    Abstract This paper focuses on the simultaneous passenger train routing and timetabling problem on the rail network consisting of both unidirectional and bidirectional tracks using an efficient train-based Lagrangian relaxation decomposition. We first build an integer linear programming model with many 0–1 binary and non-negative integer decision variables, after then reformulate it as a train path-choice model for providing an easier train-based Lagrangian relaxation decomposition mechanism based on the construction of space-time discretized network extending from node-cell-based rail network. Moreover, through reformulating safety usage interval restrictions with a smaller number of constraints in this reformulated model, the train-based decomposition needs fewer Lagrangian multipliers to relax these constraints. On the basis of this decomposition, a solving framework including a heuristic algorithm is proposed to simultaneously optimize both the dual and feasible solutions. A set of numerical experiments demonstrate the proposed Lagrangian relaxation decomposition approach has better performances in terms of minimizing both train travel time and computational times.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Simultaneous passenger train routing and timetabling using an efficient train-based Lagrangian relaxation decomposition


    Contributors:


    Publication date :

    2016-10-18


    Size :

    31 pages




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English





    Multi-periodic train timetabling using a period-type-based Lagrangian relaxation decomposition

    Zhou, Wenliang / Tian, Junli / Xue, Lijuan et al. | Elsevier | 2017


    Passenger centric train timetabling problem

    Robenek, Tomáš | Online Contents | 2016


    Passenger centric train timetabling problem

    Robenek, Tomáš / Maknoon, Yousef / Azadeh, Shadi Sharif et al. | Elsevier | 2016


    Robust Train Timetabling

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