Analyzing Train Time Table Graphs

Abstract

The project that this thesis grew out of stems from a cooperation with a subsidiary of the German railway company concerning time tables of trains. Each time table contains the train stations with their arrival and departure times. The abstract representation of the time table data is a directed time table graph: If for two train stations u and v there is at least one time table in which u and v are consecutive stops, then the directed edge (u,v) belongs to the time table graph. The starting point for this thesis is now the following question: For every edge e of a time table graph, decide whether e corresponds to a segment of the physical railroad network, or whether the trains that induce e are passing through one or more train stations without stopping there while traveling along e. This thesis deals with a structural approach for solving this edge classification problem, resulting in the formulation of the bundle recognition problem, a graph theoretic optimization problem. For three versions of the bundle recognition problem NP-completeness results using reductions from 3-Satisfiability or one of its variants can be obtained. In order to still obtain solutions for the underlying application problem, this thesis develops a heuristic for the bundle recognition problem and presents an extensive computational study.