Mönchengladbach Hauptbahnhof, 8.31 Uhr. Stadt-Expreß 3209 fährt aus irgendwelchen Gründen mit 6 Minuten Verspätung ab und kommt entsprechend erst um 8.49 statt um 8.43 Uhr am Zielbahnhof Krefeld an. Regionalbahn 3811 aus Kleve wartet den Anschluß in Krefeld ab und fährt deshalb erst um 8.52 Uhr statt 8.48 Uhr nach Neuss weiter, wo sie um 9.07 statt 9.03 Uhr eintrifft. Dort wartet bereits die S-Bahn aus Hagen und Düsseldorf, die eigentlich um 9.06 Uhr hätte abfahren müssen; entsprechend um vier Minuten verspätet kommt sie um 9.26 Uhr in Mönchengladbach an.

Nun fahren auf allen drei Strecken die Züge im Stundentakt; deswegen wartet in Mönchengladbach bereits Stadt-Expreß 3211 (planmäßige Abfahrt 9.25 Uhr) auf Fahrgäste, die beispielsweise von Korschenbroich nach Viersen wollen, und verspätet sich um vier Minuten; diese Verspätung pflanzt sich wiederum in die nächste Runde fort, und so weiter. Dadurch kommt der Fahrplan den ganzen Tag nicht wieder in Ordnung.

Das Gesamtnetz der Deutschen Bahn enthält zahlreiche Umsteigeknoten. Gegenseitige Abhängigkeiten der geschilderten Art können also häufig auftreten und Verspätungen sich über das ganze Netz ausbreiten; die Summe aller Zeitverluste ist erheblich. Ohne Zweifel will man solche Instabilitäten des Fahrplans unbedingt vermeiden.

Wenn das Netz – wie in dem Beispiel – im wesentlichen nur aus einem Dreieck besteht, ist die Lösung nicht schwer: Man verkürze durch Ausbaumaßnahmen die Gesamtfahrzeit, so daß sich Reserven ergeben, oder verdichte den Takt auf geeigneten Teilstrecken. Wenn beispielsweise die S-Bahn alle 15 statt alle 30 Minuten fahren würde, wäre der Kreis aufgebrochen – bei minimal verlängerten Übergangszeiten.

In einem vielfach verknüpften Netz werden die gegenseitigen Abhängigkeiten jedoch sehr schnell unübersichtlich. Wie kann man gleichwohl kritische, von einer Verspätungskaskade gefährdete Rundwege ausfindig machen, so daß sich Abhilfemaßnahmen ergreifen lassen?

Allgemeiner geht es darum, den optimalen Fahrplan zu finden: Es sei ein Streckennetz mitsamt Fahrzeiten für jede Einzelstrecke, zu garantierenden Anschlüssen und Mindestumsteigezeiten vorgegeben. Wie setzt man die Abfahrtszeiten der Züge so, daß sie sich (zum Beispiel) im Stundentakt wiederholen und alle Anschlüsse erreicht werden? Wie lange braucht es, bis die Folgen einer Verspätung in diesem Netz abgeklungen sind? Wie wirkt es sich aus, wenn – beispielsweise durch Baumaßnahmen -die Umsteigezeiten in einem Bahnhof sich erhöhen? An welcher Stelle hat Geld, das man in die Verbesserung des Netzes investiert (durch Ausbau von Strecken oder Einsetzen weiterer Züge), die größte Wirkung?

Abstrakt gesprochen geht es darum, daß ein Prozeß (eine Zugfahrt ab Mönchengladbach) erst stattfinden kann, nachdem gewisse andere Prozesse (Anschlußfahrten nach Mönchengladbach) vollendet sind. Gleiches gilt für Maschinen in einem Produktionsbetrieb, die auf die Anlieferung von Vorprodukten anderer Maschinen warten müssen, oder die einzelnen Kleincomputer in einem Parallelrechner, die Zwischenergebnisse von anderen Prozessoren benötigen. Man spricht von dynamischen Systemen mit diskreten Ereignissen (discrete event dynamic systems, DEDS), denn in dieser Abstraktion ist nicht mehr von Interes-se, daß die Zeit kontinuierlich abläuft; es kommt nur noch auf Einzelereignisse an, die zu gewissen Zeitpunkten stattfinden.


Eine neue Art von Algebra

Die Mathematiker François Baccelli und Jean-Pierre Quadrat vom französischen Informatik-Forschungsinstitut INRIA, Guy Cohen von der École Nationale Supérieure des Mines de Paris sowie Geert Jan Olsder von der Technischen Hochschule Delft (Niederlande) haben für solche Systeme einen Formalismus entwickelt. Der besondere Reiz dieser sogenannten Max-Plus-Algebra besteht darin, daß sie durch einen einfachen Interpretations-Kunstgriff die unübersichtlichen DEDS in die Nähe der hausbackensten Probleme rückt, die der modernen Mathematik geläufig sind: lineare Gleichungssysteme. Die Theorie zu deren Lösung heißt lineare Algebra und ist wegen ihrer grundlegenden Bedeutung Standardstoff der ersten Semester in Mathematik. Es geht um Gleichungen der Form Man hat also über die unbekannten Zahlen bis Informationen indirekter Art: Wenn man jede Unbekannte mit einer (bekannten) Zahl – dem Koeffizienten beziehungsweise und so weiter – multipliziert und die Produkte aufsummiert, ist das Ergebnis . Aus n Gleichungen dieser Art (der Index i läuft von 1 bis n) sind die Unbekannten zu erschließen. Der äußerst erfolgreiche Grundgedanke der linearen Algebra ist, sich möglichst auf die unübersichtlich vielen Additionen und Multiplikationen nicht im einzelnen einzulassen. Statt dessen faßt man die zahlreichen Größen des Systems zu übergeordneten Gebilden zusammen: alle Unbekannten bis zu einem Vektor x, desgleichen die rechten Seiten bis zu b; aus den Koeffizienten bis wird eine Matrix A. Aus zahlreichen komplizierten Gleichungen wird so eine einfache: Ax=b. Zwischen A und x muß man sich, wie in der Algebra üblich, ein Multiplikationszeichen denken. Was die Multiplikation einer Matrix mit einem Vektor sein soll, versteht sich allerdings nicht von selbst, sondern muß geeignet vereinbart werden. Warum belegt man dann überhaupt diese neue Rechenoperation mit einem alten Namen? Weil sie mit der klassischen Multiplikation etliche Gemeinsamkeiten hat. Die meisten Rechenregeln gelten weiterhin, vor allem im Zusammenhang mit der – ebenfalls neu zu definierenden – Addition von Vektoren beziehungsweise Matrizen. Man kann also, was enorm hilfreich ist, mit den neuen Objekten umgehen wie mit den gewohnten Zahlen – bis zu einem gewissen Grade, denn nicht alle Rechenregeln bleiben gültig. Nach demselben Prinzip haben die Schöpfer der Max-Plus-Algebra eine neue Addition und eine neue Multiplikation definiert – anzuwenden allerdings auf ganz gewöhnliche Zahlen. Die neue Addition ist nichts weiter als die Bildung des Maximums, die neue Multiplikation dasselbe wie die konventionelle Addition. Zur Vermeidung von Verwirrungen verwendet man neue Rechenzeichen (siehe Kasten auf Seite 22). Beispielsweise ist und . Die neuen Rechenarten sind ohne Zweifel gewöhnungsbedürftig; aber rein formal sind die meisten der geläufigen Rechenregeln – Assoziativ-, Kommutativ- und Distributivgesetz – erfüllt. Es gibt neutrale Elemente für beide Operationen, wenn man  als Zahl gelten läßt; denn es gilt – beispielsweise – und . Es ist also möglich, widerspruchsfrei mit den neuen Rechenoperationen umzugehen. Aber wozu ist es nütze?

Anwendung

Es soll ein Taktfahrplan mit vorgegebenen Umsteigeverbindungen erstellt werden. Die Abfahrtszeiten sind also die Unbekannten des Systems; dagegen ist bekannt, wie lange ein Zug von einem Knotenbahnhof zum anderen braucht. (Bahnhöfe, an denen man nicht umsteigen kann, bleiben unberücksichtigt.) Ein Zug darf abfahren, sobald alle seine Anschlußzüge eingetroffen sind; deren Ankunftszeit ist gleich der Abfahrtszeit im vorherigen Umsteige-Knotenbahnhof plus der Fahrzeit hierher. (Die zum Umsteigen benötigte Zeit wird in die Fahrzeit mit eingerechnet.) Formal ausgedrückt: Die Abfahrtszeit des i-ten Zuges ist gleich dem Maximum aus den Ankunftszeiten aller Anschlußzüge; die Ankunftszeit des j-ten Anschlußzuges ist gleich seiner (unbekannten) Abfahrtszeit plus seiner Fahrzeit . Demnach gilt, wenn m Anschlußzüge zu berücksichtigen sind, , oder, in der Max-Plus-Algebra ausgedrückt: Das sieht formal genauso aus wie die eingangs vorgestellte lineare Gleichung. In der Tat läßt sich das Problem des Taktfahrplans in ein lineares Gleichungssystem umformen – wenn man Addition und Multiplikation im Sinne der Max-Plus-Algebra versteht. Dazu sind noch einige technische Kunstgriffe erforderlich: Es ist zweckmäßig, einen Zug mit vielen Zwischenstationen in Gedanken in lauter einzelne Züge zu zerlegen, die jeweils nur von einem Knotenpunkt zum nächsten fahren. Die Bedingung, daß ein Zug angekommen sein muß, bevor er abfahren kann, ist formal einer Umsteigebedingung äquivalent. An manchen Endstationen machen Züge kehrt und fahren dieselbe Strecke wieder zurück; auch das läßt sich als Umsteigebedingung ausdrücken. Schließlich muß beispielsweise in dem eingangs geschilderten Dreiecksverkehr aus den Zügen A, B und C Zug C nicht Anschluß an den Zug A selbst haben (denn der ist längst weg), sondern an dessen Taktnachfolger. Auf der linken Seite der obigen Gleichung steht deshalb am Ende nicht , sondern , in Max-Plus-Algebra , wobei die noch unbekannte Taktzeit ist. Die Forderung, daß der ganze Fahrplan sich nach der Taktzeit genau wiederholen soll, läuft auf ein spezielles Max-Plus-Gleichungssystem hinaus: . Dabei ist A die Matrix aus den Fahrzeiten , ergänzt durch (das Null-Element der Max-Plus-Addition), wenn Zug i nicht auf Zug j warten muß, weil er beispielsweise in einem anderen Bahnhof abfährt. Außerdem erfordert die Kurzschreibweise, strenggenommen, die Übertragung der Max-Plus-Algebra auf Vektoren und Matrizen. In der klassischen linearen Algebra sind Gleichungssysteme des Typs unter dem Namen Eigenwertprobleme geläufig; heißt dann Eigenwert und x Eigenvektor von A. Sie treten in den verschiedensten Zusammenhängen auf. Beispielsweise kann man das Verhalten mancher mechanischer Systeme oder Rückkopplungsschleifen (Spektrum der Wissenschaft, April 1991, Seite 138) durch Matrizen beschreiben; deren Eigenwerte sind dann die Frequenzen, mit denen das System bevorzugt zu schwingen pflegt. Dementsprechend gibt es eine wohlausgebaute Theorie zur Lösung von Eigenwertproblemen. Die gilt es auf die Max-Plus-Algebra zu übertragen. Man gewinnt zunächst die Aussage, daß es stets einen Eigenwert gibt – vorausgesetzt, das Netz enthält keine losen Enden (Bahnhöfe, an denen stets ein Zug bereitsteht) und zerfällt nicht in unverknüpfte Teilnetze. Dieser Eigenwert ist die kürzestmögliche Taktzeit des Systems; er ist gleich der Zeit für den (nach Minuten) längsten Rundweg im Netz, den sogenannten kritischen Rundweg, geteilt durch die Anzahl seiner Stationen. Nun möchte man aber auch noch den Eigenvektor x berechnen; denn der enthält die taktgerechten Abfahrtszeiten. In der klassischen linearen Algebra müßte man dazu nur ein spezielles lineares Gleichungssystem lösen. Aber das geht in der Max-Plus-Algebra nicht so einfach; denn da kann man im allgemei-nen nicht subtrahieren: Die Gleichung hat genau eine Lösung, nämlich 7, hat unendlich viele, nämlich alle Zahlen, die kleiner oder gleich 7 sind, und die Gleichung hat gar keine. Glücklicherweise gibt es in der linearen Algebra auch Verfahren zur Lösung linearer Gleichungssysteme, die ohne Subtraktion auskommen. Statt einen Schritt rückwärts geht man gewissermaßen unendlich viele Schritte vorwärts – und kommt zum gleichen Ziel, denn die abstrakte Welt, in der sich das alles abspielt, ist rund. Formal ausgedrückt: Man berechnet über die geometrische Reihe oder physikalisch: Man läßt das System sich einschwingen, wobei sich der (dominierende) Eigenvektor von selbst ergibt. Dieses Verfahren liefert auch in der Max-Plus-Algebra die Lösung, und zwar schon nach endlich vielen Schritten. Der niederländische Mathematiker Hans Braker hat in seiner Dissertation ("Algorithms and Applications in Timed Discrete Event Systems", Delft 1993) all diese Verfahren auf das Intercity-Netz seines Landes angewandt (Bild). Ausgangspunkt seiner Untersuchung waren die im Kursbuch veröffentlichten Fahrplanzeiten, die er nur geringfügig idealisieren mußte. Die Ergebnisse enthalten alles, was ein Fahrplan-Ersteller wissen möchte: Der Eigenwert des Systems (die kürzestmögliche Taktzeit) beträgt Minuten. Das niederländische Bahnnetz hat einen Halbstundentakt, wird also bereits knapp an der Grenze des technisch Möglichen betrieben. Die Stabilitätsreserve des Netzes liegt bei Minuten; um so viel dürfen die Umsteigezeiten anwachsen, bevor der Halbstundentakt zusammenbricht. Aus der Rechnung ergibt sich auch der kritische Rundweg; auf diesem Rundkurs ist also die Zeit am knappsten. Ausbaumaßnahmen oder Taktverdichtungen wären demnach zweckmäßig dort vorzusehen. Weitere Fragen kann der von Braker ausgearbeitete Algorithmus nach Bedarf beantworten – etwa, auf welche Züge sich eine bestimmte Zugverspätung auswirkt, nach wieviel Takten ihr Effekt abgeklungen ist und was es für die Gesamtpünktlichkeit einbringt, wenn man einen Zug vor Ankunft eines verspäteten Anschlußzuges auf die Reise schickt und damit Zeitverluste für einen Teil der Reisenden in Kauf nimmt. Die Deutsche Bahn knüpft übrigens ihr Netz gar nicht erst so eng, daß Verspätungskaskaden auftreten können. Das eingangs angeführte Beispiel ist fiktiv, was die S-Bahn angeht. Die fährt nämlich planmäßig erst um 9.14 Uhr in Neuss ab, und wer den Zug um 9.25 Uhr in Mönchengladbach erreichen will, muß sich 20 Minuten eher auf den Weg machen. Allgemein gilt, daß man das Netz einfach loser (und die Fahrplan-Erstellung einfacher) machen kann, indem man an sich sinnvolle Anschlüsse überhaupt nicht vorsieht.


Aus: Spektrum der Wissenschaft 11 / 1995, Seite 20
© Spektrum der Wissenschaft Verlagsgesellschaft mbH