Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - A set packing inspired method for real-time junction train routing
AU - Lusby, Richard M.
AU - Larsen, Jesper
AU - Ehrgott, Matthias
AU - Ryan, David M.
PY - 2013/3/1
Y1 - 2013/3/1
N2 - Efficiently coordinating the often large number of interdependent, timetabled train movements on a railway junction, while satisfying a number of operational requirements, is one of the most important problems faced by a railway company. The most critical variant of the problem arises on a daily basis at major railway junctions where disruptions to rail traffic make the planned schedule/routing infeasible and rolling stock planners are forced to re-schedule/re-route trains in order to recover feasibility. The dynamic nature of the problem means that good solutions must be obtained quickly. In this paper we describe a set packing inspired formulation of this problem and develop a branch-and-price based solution approach. A real life test instance arising in Germany and supplied by the major German railway company, Deutsche Bahn, indicates the efficiency of the proposed approach by confirming that practical problems can be solved to within a few percent of optimality in reasonable time.
AB - Efficiently coordinating the often large number of interdependent, timetabled train movements on a railway junction, while satisfying a number of operational requirements, is one of the most important problems faced by a railway company. The most critical variant of the problem arises on a daily basis at major railway junctions where disruptions to rail traffic make the planned schedule/routing infeasible and rolling stock planners are forced to re-schedule/re-route trains in order to recover feasibility. The dynamic nature of the problem means that good solutions must be obtained quickly. In this paper we describe a set packing inspired formulation of this problem and develop a branch-and-price based solution approach. A real life test instance arising in Germany and supplied by the major German railway company, Deutsche Bahn, indicates the efficiency of the proposed approach by confirming that practical problems can be solved to within a few percent of optimality in reasonable time.
KW - Train routing
KW - Disruption management
KW - Duality
KW - Optimization
U2 - 10.1016/j.cor.2011.12.004
DO - 10.1016/j.cor.2011.12.004
M3 - Journal article
VL - 40
SP - 713
EP - 724
JO - Computers and Operations Research
JF - Computers and Operations Research
SN - 0305-0548
IS - 3
ER -