Research output

Online railway delay management: Hardness, simulation and computation

Research output: Contribution to journalArticleAcademicpeer-review

Standard

Online railway delay management : Hardness, simulation and computation. / Berger, A.; Hoffmann, R.; Lorenz, U.; Stiller, S.

In: Simulation - Transactions of the Society for Modeling and Simulation International, Vol. 87, No. 7, 07.2011, p. 616-629.

Research output: Contribution to journalArticleAcademicpeer-review

Harvard

APA

Vancouver

Author

Bibtex

@article{a2a4dd31721a43e28e9a3ca99654034d,
title = "Online railway delay management: Hardness, simulation and computation",
abstract = "Delays in a railway network are a common problem that railway companies face in their daily operations. When a train is delayed, it may either be beneficial to let a connecting train wait so that passengers in the delayed train do not miss their connection, or it may be beneficial to let the connecting train depart on time to avoid further delays. These decisions naturally depend on the global structure of the network, on the schedule, on the passenger routes and on the imposed delays. The railway delay management (RDM) problem (in a broad sense) is to decide which trains have to wait for connecting trains and which trains have to depart on time. The offline version (i.e. when all delays are known in advance) is already NP-hard for very special networks. In this paper we show that the online railway delay management (ORDM) problem is PSPACE-hard. This result justifies the need for a simulation approach to evaluate wait policies for ORDM. For this purpose we present TOPSU-RDM, a simulation platform for evaluating and comparing different heuristics for the ORDM problem with stochastic delays. Our novel approach is to separate the actual simulation and the program that implements the decision-making policy, thus enabling implementations of different heuristics to ''compete'' on the same instances and delay distributions. We also report on computational results indicating the worthiness of developing intelligent wait policies. For RDM and other logistic planning processes, it is our goal to bridge the gap between theoretical models, which are accessible to theoretical analysis, but are often too far away from practice, and the methods which are used in practice today, whose performance is almost impossible to measure.",
keywords = "online railway delay management, Web-based simulation, discrete event simulation, PSPACE, RELIABILITY",
author = "A. Berger and R. Hoffmann and U. Lorenz and S. Stiller",
year = "2011",
month = "7",
doi = "10.1177/0037549710373571",
language = "English",
volume = "87",
pages = "616--629",
journal = "Simulation-transactions of the Society for Modeling and Simulation International",
issn = "0037-5497",
publisher = "SAGE Publications Inc.",
number = "7",

}

RIS

TY - JOUR

T1 - Online railway delay management

T2 - Simulation-transactions of the Society for Modeling and Simulation International

AU - Berger, A.

AU - Hoffmann, R.

AU - Lorenz, U.

AU - Stiller, S.

PY - 2011/7

Y1 - 2011/7

N2 - Delays in a railway network are a common problem that railway companies face in their daily operations. When a train is delayed, it may either be beneficial to let a connecting train wait so that passengers in the delayed train do not miss their connection, or it may be beneficial to let the connecting train depart on time to avoid further delays. These decisions naturally depend on the global structure of the network, on the schedule, on the passenger routes and on the imposed delays. The railway delay management (RDM) problem (in a broad sense) is to decide which trains have to wait for connecting trains and which trains have to depart on time. The offline version (i.e. when all delays are known in advance) is already NP-hard for very special networks. In this paper we show that the online railway delay management (ORDM) problem is PSPACE-hard. This result justifies the need for a simulation approach to evaluate wait policies for ORDM. For this purpose we present TOPSU-RDM, a simulation platform for evaluating and comparing different heuristics for the ORDM problem with stochastic delays. Our novel approach is to separate the actual simulation and the program that implements the decision-making policy, thus enabling implementations of different heuristics to ''compete'' on the same instances and delay distributions. We also report on computational results indicating the worthiness of developing intelligent wait policies. For RDM and other logistic planning processes, it is our goal to bridge the gap between theoretical models, which are accessible to theoretical analysis, but are often too far away from practice, and the methods which are used in practice today, whose performance is almost impossible to measure.

AB - Delays in a railway network are a common problem that railway companies face in their daily operations. When a train is delayed, it may either be beneficial to let a connecting train wait so that passengers in the delayed train do not miss their connection, or it may be beneficial to let the connecting train depart on time to avoid further delays. These decisions naturally depend on the global structure of the network, on the schedule, on the passenger routes and on the imposed delays. The railway delay management (RDM) problem (in a broad sense) is to decide which trains have to wait for connecting trains and which trains have to depart on time. The offline version (i.e. when all delays are known in advance) is already NP-hard for very special networks. In this paper we show that the online railway delay management (ORDM) problem is PSPACE-hard. This result justifies the need for a simulation approach to evaluate wait policies for ORDM. For this purpose we present TOPSU-RDM, a simulation platform for evaluating and comparing different heuristics for the ORDM problem with stochastic delays. Our novel approach is to separate the actual simulation and the program that implements the decision-making policy, thus enabling implementations of different heuristics to ''compete'' on the same instances and delay distributions. We also report on computational results indicating the worthiness of developing intelligent wait policies. For RDM and other logistic planning processes, it is our goal to bridge the gap between theoretical models, which are accessible to theoretical analysis, but are often too far away from practice, and the methods which are used in practice today, whose performance is almost impossible to measure.

KW - online railway delay management

KW - Web-based simulation

KW - discrete event simulation

KW - PSPACE

KW - RELIABILITY

U2 - 10.1177/0037549710373571

DO - 10.1177/0037549710373571

M3 - Article

VL - 87

SP - 616

EP - 629

JO - Simulation-transactions of the Society for Modeling and Simulation International

JF - Simulation-transactions of the Society for Modeling and Simulation International

SN - 0037-5497

IS - 7

ER -