Mathematik

"Ordnung ist das halbe Leben - auch im Zugverkehr"

Vortrag von Christina Büsing vom Institut für Mathematik an der Technischen Universität Berlin

Aufgrund der steigenden Bedeutung des Zugverkehrs als Handelsmittler wird versucht, das Rangieren so effizient wie möglich zu gestalten, also im Sinne der zeitlichen Dauer zu optimieren, da der Rangierprozess zeitlich gesehen bis zu 2/3 des Transportes ausmachen kann. Zur Klärung dieser Frage wurden mathematische Modelle verwendet, welche den Rangierprozess darstellen. Als Rangieren bezeichnet man die Neuanordnung bzw. -reihung von Güterwagen zu Güterzügen in einem dafür vorgesehenen Bahnhof mit entsprechenden Gleisen.

In Modellen des Rangierbahnhofes erhalten alle Wagen Nummern. Entsprechend dieser Nummern sollen die Wagen in die richtige Reihenfolge gebracht werden. Zum Zweck der Umsortierung werden bestimmte Wagen aus einem Gleis heraus- und in ein neues Gleis hineingerollt. Die Gesamtzahl der Wagen bezeichnet man mit der Variable n. Die Variable i bezeichnet die jeweilige Nummer eines Wagens. Das Gleis links außen bleibt für die Zielsortierung frei. n diesem Vortrag ging es um das Rangieren im Bahnhof, dazu werden 2 Schritte befolgt. Als erstes werden nun alle Wagen in die Anfangskonfiguration gebracht, um dann die Wagen aus dem Gleis zu ziehen und Wagen i auf das Gleis mit i-1 zu leiten. Dies wird mit verschiedenen Methoden gemacht:

Gruppensortierung

Die Wagen werden entsprechend der Reihenfolge ihrer Nummern auf die einzelnen Gleise aufgeteilt. Anschließend werden die Wagen sortiert, indem ein Wagen mit der Nummer i auf den Gleis gerollt wird, auf dem der Wagen mit der Nummer i minus 1 steht. Dabei beginnt man mit dem Wagen, der die zweitniedrigste Nummer trägt und fährt mit dem Wagen mit der nächsthöheren Nummer fort. Insgesamt werden n Sortierschritte benötigt.

Dreieckssortierung

Die Wagen werden in Form eines Dreiecks auf die Gleise gefahren, d. h. auf dem ersten Gleis steht ein Wagen, auf dem zweiten zwei etc. Die Wagen werden entsprechend sortiert. Es sind Wurzel (2n) - 1 Sortierschritte nötig. Die Dreieckssortierung ist bei längeren und komplizierteren Ordnungen üblich.

Geometrische Sortierung

Auf dem ersten Gleis wird ein Wagen mit einer ungeraden Zahl abgestellt, auf dem zweiten Gleis ein Wagen mit dem zweifachen einer ungeraden Zahl, auf dem dritten Gleis ein Wagen mit dem vierfachen einer ungeraden Zahl etc. Es werden ½ log2 (n) Sortierschritte benötigt.

Darstellung im mathematischen Modell

Die Rangiervorgänge können mit dem mathematischen Modell der Matrizen dargestellt werden. Jede Spalte entspricht einem Rangiergleis und jede Zeile einer Wagennummer. Falls sich an einem Gleis ein Wagen befindet, wird an der entsprechenden Schnittstelle eine 1 eingetragen, die übrigen Stellen werden mit Nullen aufgefüllt. Die Matrize zeigt auf einen Blick an, welches Rangiergleis, wann, von welchem Wagen befahren wird.

Man spricht auch von "Bitstrings", da die Einsträge nur aus 0 oder 1 bestehen und mithilfe der Binärdarstellung eindeutig zuzuordnen sind. Ein "Break" liegt vor, wenn sich ein Wagen im Zuge der Umstrukturierung auf mehreren Gleisen befindet und folglich im Modell auch auf mehreren Gleisen eingetragen ist. Auf Gleis 5 sind alle Wagen eingetragen, da sie am Ende dort geordnet stehen sollen.

Doch wann sind diese Matrixen zulässig?
Dazu müssen zwei Bedingungen gelten:

Dies tritt ein bei einer unbegrenzten Anzahl an Gleisen. Diese und andere schwierige Umstrukturierungsprozesse lassen sich lösen, indem man im Modell zwischen den Einsen keine zwei aufeinanderfolgenden Nullen zulässt. Man spricht dann von der "Round-Robin-Methode".

© Jana Kürten, Christoph Homölle, David Rehnert
Mit freundlicher Unterstützung von Christina Büsing, TU-Berlin.