Train Schedule in Public Rail Transport

This thesis deals with train scheduling problems with an emphasis on public rail transport. In particular, we assume a periodic schedule and a fixed railroad track network, which is common for public rail transport. A train schedule consists of arrival and departure times for the lines at certain points of the traffic network, e.g. railroad stations. The minimization of operational cost for the realization of a schedule forms a central part of this thesis. We introduce a mixed integer linear programming model for this objective. A direct solution of instances of real-world size is not possible with today's hard- and software. With the help of a decomposition idea, we are able to find solutions of acceptable quality for those instances in a reasonable amount of time. Therefore, we split the instance into an optimization component and a feasibility component. Both subproblems are integrated into a branch-and-bound algorithm. With these methods, we can produce solutions of practically sufficient quality in a few minutes. We present computational results for networks of the Netherlands and Germany.Die vorliegende Arbeit befasst sich mit Fahrplanoptimierung unter Beruecksichtigung der Verhaeltnisse beim spurgefuehrten, oeffentlichen Personenverkehr. Insbesondere wird davon ausgegangen, dass der Fahrplan sich nach einer bestimmten Zeitperiode (z.B. eine Stunde) wiederholen soll. Ein Fahrplan besteht aus den Ankunfts- und Abfahrtzeiten der einzelnen Verkehrslinien an bestimmten Punkten im Verkehrsnetz, etwa den Bahnhoefen beim Eisenbahn-Fernverkehr. Im Mittelpunkt dieser Arbeit steht die Minimierung der durch einen Fahrplan entstehenden Betriebskosten fuer die Fahrzeuge. Hierzu wird ein Modell entwickelt, das auf einem gemischt-ganzzahligen linearen Programm basiert. Eine direkte Loesung von Instanzen fuer praktisch relevante Problemgroessen ist mit der zur Zeit zur Verfuegung stehenden Hard- und Software nicht moeglich. In der Arbeit wird ein Dekompositionsansatz vorgestellt, mit dem auch aus Praxissicht interessante Problemgroessen bearbeitet werden koennen. Hierzu wird das gemischt-ganzzahlige Programm in eine Optimierungs- und eine Zulaessigkeitskomponente zerlegt. Beide Teilprobleme werden in ein Branch-and-Bound-Verfahren integriert, das innerhalb weniger Minuten auch fuer die oben genannten Problemgroessen gute Ergebnisse liefert. Es werden Rechenergebnisse fuer Netzwerke aus den Niederlanden und aus Deutschland vorgestellt