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

Document Type

Article

Publication Date

1-1-2016

Publication Title

Transportation Research Part B: Methodological

Volume

94

First page number:

409

Last page number:

439

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. © 2016 Elsevier Ltd

Keywords

Decomposition; Lagrangian relaxation; Routing; Timetabling; Train

Language

English

Find It

UNLV article access

Search your library

Share

COinS