Abstract
We address the problem of simultaneously scheduling trains and planning preventive
maintenance time slots (PMTSs) on a general railway network. Based on network cumulative
flow variables, a novel integrated mixed-integer linear programming (MILP) model is
proposed to simultaneously optimize train routes, orders and passing times at each
station, as well as work-time of preventive maintenance tasks (PMTSs). In order to
provide an easy decomposition mechanism, the limited capacity of complex tracks is
modelled as side constraints and a PMTS is modelled as a virtual train. A Lagrangian
relaxation solution framework is proposed, in which the difficult track capacity
constraints are relaxed, to decompose the original complex integrated train scheduling
and PMTSs planning problem into a sequence of single train-based sub-problems. For each
sub-problem, a standard label correcting algorithm is employed 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. Numerical experiments are
conducted on a small artificial network and a real-world network adapted from a Chinese
railway network, to evaluate the effectiveness and computational efficiency of the
integrated optimization model and the proposed Lagrangian relaxation solution framework.
The benefits of simultaneously scheduling trains and planning PMTSs are demonstrated,
compared with a commonly-used sequential scheduling method.
Keywords
Integrated optimization,
Train scheduling,
Preventive maintenance time slots (PMTSs) planning,
Cumulative flow variables,
Lagrangian relaxation
Highlights
• Simultaneously schedule trains and plan preventive maintenance time slots (PMTSs).
•
Build an integrated optimization model through describing PMTSs as virtual trains.
•
Propose a Lagrangian relaxation solution framework to solve the proposed model.
•
At least 25% improvement in solution quality can be achieved in our experiments.
原文传递： https://doi.org/10.1016/j.trc.2017.04.010
