Abstract
Train dispatching is critical for the punctuality and
reliability of rail operations, especially for a complex rail network.
This paper develops an innovative integer programming model for the
problem of train dispatching on an N-track network by means of
simultaneously rerouting and rescheduling trains. Based on a time–space
network modeling framework, we first adapt a commonly used big-M method
to represent complex “if-then” conditions for train safety headways in a
multi-track context. The track occupancy consideration on typical single
and double tracks is then reformulated using a vector of cumulative flow
variables. This new reformulation technique can provide an efficient
decomposition mechanism through modeling track capacities as side constraints
which are further dualized through a proposed Lagrangian relaxation solution
framework. We further decompose the original complex rerouting and rescheduling
problem into a sequence of single train optimization subproblems. For each
subproblem, a standard label correcting algorithm is embedded for finding the
time dependent least cost path on a time–space network. The resulting dual
solutions can be transformed to feasible solutions through priority rules.
We present a set of numerical experiments to demonstrate the system-wide
performance benefits of simultaneous train rerouting and rescheduling,
compared to commonly-used sequential train rerouting and rescheduling approaches.
Keywords
Train dispatching, Rail network, Cumulative flow variable,
Lagrangian relaxation
Highlights
• Optimize N-track train schedules through simultaneous rerouting and rescheduling.
• Introduce a cumulative flow variables-based representation to capture various
practical constraints.
• Propose a Lagrangian relaxation solution framework with an efficient shortest path
algorithm.
• Simultaneous rerouting and rescheduling models provide a reduction of consecutive
delays compared to sequential approaches.
原文传递： https:/www.sciencedirect.com/science/article/abs/pii/S0191261514000782
