TY - JOUR
T1 - Integrated optimization on train scheduling and preventive maintenance time slots planning
AU - Luan, Xiaojie
AU - Miao, Jianrui
AU - Meng, Lingyun
AU - Corman, Francesco
AU - Lodewijks, Gabri
PY - 2017
Y1 - 2017
N2 - 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.
AB - 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.
KW - Cumulative flow variables
KW - Integrated optimization
KW - Lagrangian relaxation
KW - Preventive maintenance time slots (PMTSs) planning
KW - Train scheduling
UR - http://www.scopus.com/inward/record.url?scp=85019542417&partnerID=8YFLogxK
U2 - 10.1016/j.trc.2017.04.010
DO - 10.1016/j.trc.2017.04.010
M3 - Article
AN - SCOPUS:85019542417
VL - 80
SP - 329
EP - 359
JO - Transportation Research. Part C: Emerging Technologies
JF - Transportation Research. Part C: Emerging Technologies
SN - 0968-090X
ER -