Simultaneous passenger train routing and timetabling using an efficient train-based Lagrangian relaxation decomposition
Transportation Research Part B: Methodological
First page number:
Last page number:
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. © 2016 Elsevier Ltd
Decomposition; Lagrangian relaxation; Routing; Timetabling; Train
Simultaneous passenger train routing and timetabling using an efficient train-based Lagrangian relaxation decomposition.
Transportation Research Part B: Methodological, 94