TOPSU - RDM a simulation platform for online railway delay management

ABSTRACT

Delays in a railway network is a common problem that railway companies face in their daily operations. When a train gets 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 and on the schedule. 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, and 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. 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 often too far away from practice, and the methods which are used in practice today, whose performance is almost impossible to measure.

REFERENCES

• 1: A. Berger, R. Hoffmann, U. Lorenz, and S. Stiffer. TOPSU--RDM -- A Web-Based Simulation for Railway Delay Management. http://wwwcs.uni-paderborn.de/cs/agmonien/PERSONAL/FLULO/PP/TOPSU_RDM1.html.
• 2: G. Chaslot, S. de Jong, J.-T. Saito, and J. Uiterwijk. Monte-Carlo Tree Search in Production Management Problems. In Proceedings of BNAIC 2006, (2006).
• 3: M. Gatto, B. Glaus, R. Jacob, L. Peeters, and P. Widmayer. Railway delay management: Exploring its algorithmic complexity. In Algorithm Theory - Proceedings SWAT 2004, volume 3111 of LNCS, pages 199--211. Springer, 2004.
• 4: M. Gatto, R. Jacob, L. Peeters, and A. Schöbel. The computational complexity of delay management. In D. Kratsch, editor, Graph-Theoretic Concepts in Computer Science: 31st International Workshop (WG 2005), volume 3787 of Lecture Notes in Computer Science, 2005.
• 5: C. R. Efficient selectivity and backup operators in monte-carlo tree search. In 5th International Conference on Computer and Games, 2006.
• 6: A. Schöbel. Integer programming approaches for solving the delay management problem. Lecture Notes in Computer Science, 2006. to appear.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

Keywords:
PSPACE, experimental algorithms, heuristics, online optimization, online railway delay management, simulation, stochastic scheduling, transportation, web-based simulation