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

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

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.