Der Trassenkonflikt verständlich erklärt

Auf einem einzigen Gleis können sich zwei Züge nur im Bahnhof begegnen, und alle wollen im selben Zeitfenster los. Wer fährt zuerst, wer wartet? Diese Seite zeigt, was einfache Regeln kosten und was es kostet, die Wartezeit gerecht zu verteilen.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Eine Straße, auf der nur ein Auto Platz hat

Stellen Sie sich eine schmale Bergstraße vor, auf der nur ein Auto Platz hat. Alle paar Kilometer gibt es eine Ausweichbucht. Kommen sich zwei Wagen entgegen, muss einer in der nächsten Bucht warten. Auch Überholen geht nur dort.

Genauso funktioniert eine eingleisige Bahnstrecke. Zwischen zwei Bahnhöfen passt nur ein Zug. Nach jedem Zug muss der Abschnitt noch kurz frei bleiben, bevor der nächste einfahren darf. Begegnen und Überholen geht nur im Bahnhof.

Nun wollen innerhalb von zwei Stunden viele Züge von drei Bahnunternehmen losfahren. Die Unternehmen heißen A, B und C. Manche fahren in die eine Richtung, manche in die andere. Schnelle Züge brauchen für einen Abschnitt weniger Zeit als langsame.

Jeder Zug hat eine Wunschabfahrt und startet nie früher. Muss er warten, kommt er später an. Seine Verspätung ist die Zeit, die er länger braucht als bei freier Fahrt. Die Summe über alle Züge heißt Gesamtverspätung. In dieser Summe zählt jede Minute gleich, egal welcher Zug und welches Unternehmen.

Alles auf dieser Seite beschreibt ein vereinfachtes Rechenbild (Fachwort: Modell). Es hat eine erfundene Strecke mit fünf Abschnitten und sechs Bahnhöfen und sechs bis zehn Züge. Die Aussagen gelten für dieses Rechenbild, nicht für die Wirklichkeit.

Zwei einfache Regeln

Wer darf zuerst fahren? Zwei Regeln liegen nahe.

• Erstanmelder: Der Zug mit der frühesten Wunschabfahrt kommt zuerst dran. Wer sich zuerst gemeldet hat, spielt im Rechenbild keine Rolle.
• Vorrang: Ein Unternehmen wird bevorzugt. Zuerst werden alle seine Züge eingeplant, danach die übrigen nach Wunschabfahrt.

Beide Regeln planen Zug für Zug. Der erste Zug bekommt für seine ganze Fahrt die frühesten freien Zeiten. Der zweite nimmt, was dann noch frei ist, und so weiter. Verschoben wird danach nichts mehr.

Das ist einfach und nachvollziehbar, aber nicht unbedingt gut. Ein Zug, der früh eingeplant ist, kann spätere Züge lange aufhalten. Ein anderer Plan hätte allen zusammen vielleicht Zeit gespart. Das ist eine Vermutung. Gemessen wurde nur, wie weit die Regeln vom besten Plan entfernt liegen.

Was die Regeln kosten

Als Maßstab dient der beste mögliche Plan, das Optimum. Ein Rechenverfahren sucht ihn, indem es sehr viele Pläne systematisch vergleicht. Es meldet, wann es keinen besseren mehr gibt.

Gemessen wurde an zufällig gezogenen Fällen mit acht Zügen. Ein Fall legt fest, welche Züge in welche Richtung fahren, zu welchem Unternehmen sie gehören und wann sie losfahren wollen. Die Zahlen sind Mittelwerte über 20 Fälle. Sie nennen, um wie viel % die Gesamtverspätung eines Verfahrens über der des Optimums liegt.

• Erstanmelder: 58 % mehr.
• Vorrang für Unternehmen A: 81 % mehr.
• Verbesserte Reihenfolge (mehr dazu im nächsten Abschnitt): 16 % mehr.

Warum kostet Vorrang mehr? Vermutlich kommt ein Zug früh dran, der gar nicht früh fahren wollte. Er belegt Zeiten, die sonst früher eintreffende Züge anderer Unternehmen genutzt hätten.

Warum die Reihenfolge allein nicht reicht

Eine bessere Reihenfolge der Züge hilft. Eine Suche probiert aus, einzelne Züge früher oder später einzuplanen, solange die Gesamtverspätung sinkt. So fällt der Aufschlag von 58 % auf 16 %. Die Suche kennt dafür alle Züge im Voraus. Eine Regel, die man vorab ankündigen könnte, ist es deshalb nicht.

Ganz zum Optimum kommt es nicht. Ein Bild dazu: Die Bergstraße hat zwei Stücke mit einer Ausweichbucht in der Mitte. Zwei Autos wollen bergauf, ein Lastwagen kommt von oben. Gilt „Lastwagen zuerst“, fährt er ohne Halt ins untere Stück. Dort steht er der Straße im Weg, und das zweite Auto muss unten warten. Besser ist es, wenn der Lastwagen in der Bucht in der Mitte wartet, bis beide Autos an ihm vorbei sind. Er verliert Zeit, das zweite Auto gewinnt mehr.

Eine Regel, die Zug für Zug plant, gibt dem früher eingeplanten Zug immer seinen frühesten Platz. Dass er für einen späteren wartet, plant sie nicht ein. Das Optimum kann es. In einem kleinen Beispiel war der beste Plan wirklich besser als jede Reihenfolge der Züge. Ob das den ganzen Rest von 16 % erklärt, zeigt die Messung nicht. Außerdem probiert die Suche nicht alle Reihenfolgen aus und kann eine bessere übersehen.

Und die Gerechtigkeit?

Bisher zählte nur die Summe. Ein Bahnunternehmen fragt aber: Wie lange warten meine Züge im Mittel? Bei Vorrang für A wartet A in der Messung im Mittel am wenigsten, B und C tragen die Last.

Die faire Lösung geht in zwei Schritten vor. Erst fragt sie: Bei welchem Plan wartet das am schlechtesten gestellte Unternehmen im Mittel seiner Züge am kürzesten? Dann sucht sie unter allen Plänen, die dieses Ergebnis halten, die kleinste Gesamtverspätung. In dieser Rechnung zählt also zuerst das schlechtestgestellte Unternehmen, erst danach wieder die Summe.

Die Fairness kostet im Mittel etwa 3 % mehr Gesamtverspätung als das Optimum. In 14 von 20 Fällen sind es unter 5 %. In den übrigen sechs Fällen lag der Aufschlag darüber. Bei der fairen Lösung liegen die Unternehmen in der mittleren Verspätung am nächsten beieinander. Zahlen dazu stehen im zweiten Teil.

Warum kostet das so wenig? Vermutlich gibt es mehrere Pläne mit fast gleicher Gesamtverspätung. Unter ihnen lässt sich einer wählen, der die Last gleichmäßiger verteilt.

Das Programm zum Ausprobieren

Zu dieser Seite gehört ein Programm zum Ausprobieren, die Demo. Der erste Knopf unten öffnet sie, der zweite führt zum Teil für Fachleute. Zum Verstehen brauchen Sie die Demo nicht. Dort wählen Sie Zugzahl und Pause zwischen den Zügen selbst und sehen in einem Fahrplanbild, welcher Zug wann wartet.

Häufige Missverständnisse

• „Gleiche Regel für alle heißt gleiche Wartezeit.“ Nein. Die Erstanmelder-Regel sortiert nur nach Wunschabfahrt. Sie sieht nicht, zu welchem Unternehmen ein Zug gehört, und kann nichts ausgleichen. In der Messung war der Abstand zwischen den Unternehmen bei ihr größer als bei der fairen Lösung.
• „58 % heißt: 58 % der Züge sind verspätet.“ Nein. Es heißt: 58 % mehr Gesamtverspätung als beim Optimum. Beispiel: Hat das Optimum 100 Minuten Gesamtverspätung, sind es bei Erstanmelder 158 Minuten.
• „Das Optimum ist ein Plan, den die Bahn einfach umsetzen könnte.“ Nein. Es kennt alle Züge und Wunschzeiten im Voraus und zählt jede Minute gleich. Es ist ein Maßstab, kein Vorschlag.

Woran Sie das im Alltag erkennen

• Mehrere Parteien teilen etwas, das immer nur einer nutzen kann, etwa das Bad am Morgen oder den Waschkeller. Jede Reihenfolge verteilt das Warten anders.
• Eine Regel „wer zuerst kommt“ wirkt gerecht. Sie sieht aber nur die Reihenfolge, nicht, wer schon mehrmals warten musste.

Wie ernst ist das Rechenbild zu nehmen?

Reserven, Preise und Rechtslage fehlen, und die Wunschabfahrten stehen fest. Die Zahlen zeigen Größenordnungen für diese erfundenen Fälle.

Was Sie mitnehmen:

• Fragen Sie bei jeder Vergaberegel, wonach sie sortiert und was sie dabei nicht sieht.
• Fragen Sie bei jedem Prozentwert, wovon er gerechnet ist.
• Prüfen Sie Gesamtzeit und Verteilung getrennt, denn die Summe sagt nicht, wer wartet.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Das Modell ist eine synthetische eingleisige Strecke; alle Zahlen gelten nur für sie.

• Strecke: 5 Abschnitte zwischen 6 Stationen, ein Gleis je Abschnitt (absoluter Blockabstand: nie zwei Züge gleichzeitig im Abschnitt, auch nicht in Gegenrichtung). Ein Zug belegt einen Abschnitt für seine Fahrzeit plus die Räumzeit \(c\) von 1 bis 3 min; erst danach darf ein anderer Zug einfahren, gleich welcher Richtung. In Stationen darf beliebig lange gewartet werden (unbegrenzt Ausweichgleise); dort begegnen und überholen sich Züge. Die Fahrzeit \(p_i\) je Abschnitt beträgt 6 min (Schnellzug) oder 10 min (langsamer Zug).
• Züge und Fälle: Drei Unternehmen A, B, C. Jeder Zug fährt die ganze Strecke in einer Richtung (beide Richtungen gleich wahrscheinlich) und hat eine Wunschabfahrt \(r_i\) am Start in den ersten 120 min; früher abfahren darf er nicht. A fährt mehr Schnellzüge (60 gegen 30 % bei B und C). Das Unternehmen jedes Zuges wird zufällig gezogen: Im Standardfall gehört ein Zug mit der Wahrscheinlichkeit einhalb zu A, drei Zehntel zu B und zwei Zehntel zu C. Die Zahl der Züge je Unternehmen schwankt deshalb von Fall zu Fall; bei 8 Zügen kommen im Mittel rund viereinhalb, zwei und anderthalb Züge für A, B und C heraus, und ein Unternehmen kann ganz ohne Zug bleiben (Rechnung dieser Seite aus den Rohergebnissen). Die Zugzahl beträgt 6, 8 oder 10 (Standard 8), die Räumzeit 1, 2 oder 3 min (Standard 2). Ein Fall ist eine mit einem deterministischen Zufallsgenerator gezogene Zugmenge; alle Zeiten sind ganzzahlig in Minuten.
• Verspätung: \(d_i\) = Ankunft am Ziel minus (Wunschabfahrt plus ungestörte Fahrzeit), also reine Wartezeit am Start und in Stationen. Die Gesamtverspätung ist \(\sum_i d_i\); jede Minute zählt für jedes Unternehmen gleich.
• Fairness: Mit der mittleren Verspätung \(a_o = \frac{1}{n_o}\sum_{i \in o} d_i\) des Unternehmens \(o\) (\(n_o\) Züge) ist die Spreizung die größte minus die kleinste Größe \(a_o\), gerechnet nur über Unternehmen mit mindestens einem Zug. Der Jain-Index ist \(J = (\sum_o a_o)^2 / (q \sum_o a_o^2)\) mit \(q\) Unternehmen; \(J = 1\) heißt, alle \(a_o\) sind gleich. Die Demo zeigt ihn neben der Spreizung; die Befunde unten verwenden nur die Spreizung, weil sie in Minuten gelesen werden kann.
• Verfahren: (a) Erstanmelder: Serienplanung, Züge nach Wunschabfahrt geordnet (nicht nach dem Zeitpunkt einer Anmeldung). (b) Vorrang: Serienplanung, erst alle Züge des bevorzugten Unternehmens, dann die übrigen nach Wunschabfahrt. (c) Reihenfolge verbessert: Lokalsuche über die Reihenfolge der Serienplanung. (d) Optimum: kleinste Gesamtverspätung, mit dem Löser CP-SAT (OR-Tools) berechnet. (e) Fair: erst die kleinste größte mittlere Verspätung, dann die kleinste Gesamtverspätung unter dieser Grenze.
• Messreihe: 9 Varianten mit je 20 Fällen mit festen Startwerten des Zufallsgenerators. Der Standardfall (8 Züge, Räumzeit 2 min, A mit Wahrscheinlichkeit einhalb, Vorrang für A) wird je einmal abgewandelt: 6 oder 10 Züge, Räumzeit 1 oder 3 min, Wahrscheinlichkeit für A drei Zehntel oder sieben Zehntel, Vorrang für B oder C. Die Verteilungen der Wunschabfahrten und die übrigen Annahmen bleiben gleich; alle fünf Verfahren rechnen auf denselben Zügen. Angegeben sind Mittelwerte über die Fälle, bei einem ± der Standardfehler des Mittels.

Die Formeln

Modell. Zug \(i\) hat die Route \(j_1, \dots, j_S\) (die \(S = 5\) Abschnitte in Fahrtrichtung), die Fahrzeit \(p_i\) je Abschnitt und die Wunschabfahrt \(r_i\). Die Variable \(s_{ij}\) ist die Einfahrt in Abschnitt \(j\). Der Zug fährt nicht vor der Wunschabfahrt los und fährt erst in den nächsten Abschnitt, wenn er den vorigen durchfahren hat (Warten in der Station ist erlaubt; \(k\) zählt die Abschnitte der Route):

\[s_{i j_1} \ge r_i\]

\[s_{i j_{k+1}} \ge s_{i j_k} + p_i\]

Auf jedem Abschnitt \(j\) dürfen sich die Belegungsintervalle \([s_{ij},\, s_{ij} + p_i + c)\) aller Züge nicht überschneiden. Das gilt für beide Fahrtrichtungen gemeinsam.

Verspätung und Optimum. Der Klammerterm ist die früheste Ankunft bei ungestörter Fahrt:

\[d_i = s_{i j_S} + p_i - (r_i + S\,p_i)\]

Das Optimum minimiert die Gesamtverspätung über alle zulässigen Pläne:

\[\min \sum_i d_i\]

Fairness in zwei Stufen. Die erste Stufe minimiert die Obergrenze \(m\) der mittleren Verspätung, wobei \(m\) ganzzahlig ist und \(n_o\) die Zahl der Züge des Unternehmens \(o\):

\[\min m\]

\[m \cdot n_o \ge \sum_{i \in o} d_i\]

Mit dem Optimalwert \(m^*\) der ersten Stufe minimiert die zweite Stufe wieder \(\sum_i d_i\), nun unter der zusätzlichen Bedingung \(m \le m^*\).

Serienplanung. Für eine Reihenfolge der Züge nimmt jeder Zug auf jedem Abschnitt die früheste Lage, die kein bereits belegtes Intervall schneidet; Lücken vor bereits belegten Intervallen werden genutzt, sofern das ganze Intervall hineinpasst. Die Lokalsuche startet bei der Reihenfolge nach Wunschabfahrt, nimmt einzelne Züge heraus und fügt sie an anderer Stelle ein, solange die Gesamtverspätung sinkt (bei Gleichstand bleibt es, wie es ist). Sie prüft nicht alle Reihenfolgen.

Optimum. CP-SAT ist ein Löser der Constraint-Programmierung mit Intervallvariablen. Das Modell hat je Zug und Abschnitt ein Intervall der festen Länge \(p_i + c\) und je Abschnitt eine Nicht-Überlappungs-Bedingung. Der Löser läuft mit einem Zeitlimit (in der Messreihe dreißig Sekunden je Stufe; die faire Lösung hat zwei Stufen); ist das Optimum dann nicht bewiesen, ist das Ergebnis nur die beste gefundene Lösung.

Herleitungen Schritt für Schritt

Die folgenden Herleitungen sind Rechnungen dieser Seite, keine Messungen der Demo.

Warum jedes Verfahren mindestens so teuer ist wie das Optimum, und was daraus für die Fairness folgt.

• Schritt 1: Erstanmelder, Vorrang und verbesserte Reihenfolge liefern zulässige Pläne; die Demo prüft jeden mit einer unabhängigen Zulässigkeitsprüfung. Das Optimum minimiert über alle zulässigen Pläne, also ist ihre Gesamtverspätung mindestens so groß wie das Optimum. Bedingung: das Optimum ist bewiesen; sonst ist der Vergleichswert nur die beste gefundene Lösung.
• Schritt 2: Die faire Lösung minimiert \(\sum_i d_i\) über die Pläne mit \(m \le m^*\), eine Teilmenge aller zulässigen. Ihre Gesamtverspätung ist deshalb mindestens das Optimum; der Preis der Fairness ist nie negativ (beide Läufe bewiesen vorausgesetzt).
• Schritt 3: Weil \(m\) ganzzahlig ist, ist \(m^*\) die aufgerundete kleinstmögliche größte mittlere Verspätung. Die größte mittlere Verspätung der fairen Lösung ist höchstens \(m^*\) und damit weniger als eine Minute größer als die kleinstmögliche größte mittlere Verspätung.
• Schritt 4: Für die Spreizung gibt es keine solche Ordnung. Unter gleich guten Lösungen kann sie schwanken, und die Verfahren minimieren sie nicht unmittelbar.

Warum die Zug-für-Zug-Vergabe das Optimum verfehlen kann.

• Schritt 1: Die Serienplanung setzt jeden Zug auf jedem Abschnitt so früh wie möglich. Ein früher eingeplanter Zug wartet nie auf einen später eingeplanten. Für \(n\) Züge gibt es höchstens \(n!\) solche Pläne, einen je Reihenfolge; wohin ein Zug fällt, hängt dabei auch von den Lücken zwischen den schon belegten Intervallen ab.
• Schritt 2: Das Optimum darf dagegen einen Zug warten lassen, obwohl er in einem anderen Plan früher weiterfahren könnte, wenn ein anderer dadurch mehr gewinnt, als er verliert. Solche Pläne sind nicht immer unter den \(n!\) Serienplänen; der Beispielfall unten ist ein Fall, in dem keiner der Serienpläne das Optimum erreicht.
• Schritt 3: Für Ziele, die bei späterer Ankunft nie besser werden (die Gesamtverspätung, auch die mittlere Verspätung je Unternehmen), genügt es, Pläne zu betrachten, in denen jede Belegung so früh liegt, wie es eine festgehaltene Reihenfolge der Belegungen auf jedem Abschnitt erlaubt: Ein Plan mit Leerlauf lässt sich nach vorn schieben, ohne dass ein Zug später ankommt. Darauf stützt sich die Gegenprobe, die CP-SAT an kleinen Fällen mit der Aufzählung aller Reihenfolgen der Belegungen vergleicht (siehe Befunde).
• Folge: Die Messung trennt nicht, wie viel vom Rest zum Optimum aus der Zug-für-Zug-Struktur und wie viel aus der unvollständigen Lokalsuche stammt.

Warum Prozentwerte und Minuten verschieden laufen. Der Abstand ist je Fall das Verhältnis der Gesamtverspätung des Verfahrens zu der des Optimums minus eins, in Prozent, und wird dann über die Fälle gemittelt. Das Optimum selbst wächst mit der Zugzahl und der Räumzeit. Aus den Rohergebnissen der Messreihe nachgerechnet: Die Mehrverspätung der Erstanmelder-Regel in Minuten wächst mit der Räumzeit, während ihr Prozentwert bei 2 und 3 min gleich bleibt, weil das Optimum mitwächst. Ebenso kostet die faire Lösung bei 6 und 8 Zügen in Minuten ungefähr gleich viel (gut drei Minuten je Fall; Mittel der Fall-Prozente und Prozent der Mittel weichen etwas voneinander ab); der höhere Prozentwert bei 6 Zügen kommt vom kleineren Optimum.

Durchgerechnet: ein kleiner Fall von Hand

Konstruierter Fall, Rechnung dieser Seite, keine Messung der Demo. Die Strecke hat zwei Abschnitte (Stationen 0, 1, 2), die Räumzeit beträgt 2 min. Die schnellen Züge A und B fahren aufwärts (6 min je Abschnitt), der langsame Zug C fährt abwärts (10 min je Abschnitt); alle drei wollen in Minute 0 abfahren. Ein schneller Zug belegt einen Abschnitt acht Minuten, ein langsamer zwölf. Ungestört fahren A und B zwölf Minuten, C zwanzig. Die Unternehmen spielen hier keine Rolle.

• Zug für Zug: Von den sechs Reihenfolgen der drei Züge sind C, A, B und C, B, A am besten, mit Gesamtverspätung achtundzwanzig. In der Reihenfolge C, A, B fährt C ungestört. A wartet 6 min, weil Abschnitt 1 bis Minute zwölf durch C belegt ist. B kann in Abschnitt 0 erst nach C einfahren (zwischen A und C ist die Lücke zu kurz) und wartet zweiundzwanzig Minuten. Die vier übrigen Reihenfolgen ergeben dreißig oder vierunddreißig.
• Besserer Plan: C fährt Abschnitt 1 zuerst (ab Minute 0) und wartet dann in Station 1 bis Minute sechzehn, bis A und B Abschnitt 0 durchfahren haben. A fährt Abschnitt 0 ab Minute 0 und Abschnitt 1 ab Minute zwölf, B Abschnitt 0 ab Minute 8 und Abschnitt 1 ab Minute zwanzig. Die Verspätungen sind 6 für A, vierzehn für B und 6 für C; die Summe ist sechsundzwanzig. Von Hand lässt sich nachprüfen, dass sich auf keinem Abschnitt zwei Belegungen überschneiden.
• Lehre: C wartet 6 min, obwohl er in der Reihenfolge C, A, B früher durch Abschnitt 0 käme. B gewinnt dadurch acht Minuten, der Gewinn insgesamt beträgt zwei Minuten. Dass es unter sechsundzwanzig nicht geht, ergibt eine Aufzählung aller Reihenfolgen der sechs Belegungen mit einem eigenen Programm außerhalb der Demo; die Handrechnung zeigt nur die Zulässigkeit.

Befunde

Jede Zeile gilt für 20 Fälle je Variante mit Mittelwert und Standardfehler nach dem ±. Der Abstand zum Optimum ist je Fall die Gesamtverspätung des Verfahrens im Verhältnis zu der des Optimums (Basis = Optimum) und wird über die Fälle gemittelt, nur über Fälle mit bewiesenem Optimum und bewiesener fairer Lösung. Der Standardfall hat 8 Züge, 2 min Räumzeit und Vorrang für A.

Frage	Befund
Was kostet das Erstanmelder-Prinzip? (8 Züge)	58 ± 8 % mehr Gesamtverspätung als das Optimum.
Und Vorrang für ein Unternehmen? (8 Züge)	Für A 81 ± 10 %, für B 68 ± 8 %, für C 73 ± 8 %.
Wie viel schließt eine verbesserte Reihenfolge?	16 ± 5 % statt 58 % (8 Züge); bei 6 Zügen 12 ± 4 %, bei 10 Zügen 24 ± 4 %.
Was kostet Fairness?	3,3 ± 1,0 % über dem Optimum (8 Züge), in 14 von 20 Fällen unter 5 %; bei 6 Zügen 8,0 ± 3,8 %, bei 10 Zügen 4,2 ± 0,9 %.
Wie ungleich verteilt Vorrang die Verspätung? (8 Züge)	Spreizung der mittleren Verspätung zwischen den Unternehmen: 41,6 min bei Vorrang für A, 5,7 min bei der fairen Lösung, 14,4 min bei Erstanmelder, 12,6 min im Optimum.
Wirkt die Zugzahl? (6 / 8 / 10 Züge)	Optimum der Gesamtverspätung im Mittel 47,5 / 93,5 / 151,4 min; Erstanmelder über dem Optimum 52 / 58 / 66 %.
Und die Räumzeit? (1 / 2 / 3 min, 8 Züge)	Optimum 75,6 / 93,5 / 113,1 min; Erstanmelder über dem Optimum 69 / 58 / 58 %.
Wie lange rechnet CP-SAT?	Median der Summe beider Läufe (Optimum und fair) 0,1 s bei 6, 0,3 s bei 8 und 7,8 s bei 10 Zügen; bei 10 Zügen ist das Optimum in nur 16 von 20 Fällen bewiesen. Die Zeiten gelten für den Rechner der Messung.

Was die Messung zeigt und wo die Grenzen liegen

Was sie belegt:

• Die Rangfolge in jedem Fall mit bewiesenem Optimum: Das Optimum liegt nicht über der verbesserten Reihenfolge, diese nicht über Erstanmelder; das Optimum liegt auch nicht über Vorrang und nicht über der fairen Lösung. Jeder Plan der Messreihe wurde unabhängig auf Zulässigkeit geprüft.
• Die Größenordnung: In jeder der 9 Varianten kosten Erstanmelder und Vorrang im Mittel mehr als die Hälfte der Gesamtverspätung des Optimums zusätzlich (aus den Rohergebnissen nachgerechnet). Die faire Lösung liegt in jeder Variante im Mittel unter einem Zehntel über dem Optimum, und Vorrang spreizt die Unternehmen in jeder Variante im Mittel mehr als vierfach so weit wie die faire Lösung (ebenfalls nachgerechnet).
• Der Löser: CP-SAT wurde an kleinen Fällen mit vier Zügen und zwei Abschnitten gegen die Aufzählung aller Reihenfolgen der Belegungen geprüft; Gesamtverspätung und kleinstmögliche größte mittlere Verspätung stimmen überein. Für die faire Lösung wurde geprüft, dass sie die Min-Max-Grenze hält und nicht unter dem Optimum liegt. An kleinen Fällen mit fünf Zügen und drei Abschnitten war das Optimum in mindestens einem Fall strikt besser als jede Reihenfolge der Züge.

Was sie nicht belegt:

• Unterschiede zwischen Varianten: Dass der Erstanmelder-Abstand mit der Zugzahl wächst (52 / 58 / 66 %), mit der Räumzeit schwankt (69 / 58 / 58 %) oder dass Vorrang für A teurer ist als für B oder C, liegt im Bereich der Standardfehler bei 20 Fällen. Sicher ist nur, dass das Optimum selbst mit Zugzahl und Räumzeit wächst. Warum A teurer ausfällt, ist nicht gemessen; eine ungeprüfte Vermutung ist der höhere Schnellzuganteil von A.
• Obergrenze statt Untergrenze: Die Lücke der Erstanmelder-Regel ist die Lücke einer bestimmten Regel (Sortierung nach Wunschabfahrt). Die verbesserte Reihenfolge nutzt die Kenntnis aller Züge im Voraus und ist keine ankündbare Regel. Sie ist eine Obergrenze für die Kosten der besten Reihenfolge, keine Untergrenze für die Kosten von Regeln: Eine bessere Reihenfolge als die gefundene kann existieren. Der Rest von 16 % ist nicht auf Suche und Zug-für-Zug-Struktur aufgeteilt.
• Preis der Fairness: Der Mittelwert von 3,3 % verdeckt Ausreißer. Aus den Rohergebnissen nachgerechnet, liegt der Aufschlag in einem Fall mit 6 Zügen bei mehr als der Hälfte des Optimums, und im Standardfall liegen die sechs Fälle über 5 % zwischen gut 5 % und knapp einem Siebtel. Bei 6 Zügen sind es im Mittel 8,0 % bei kleinem Nenner. Der Mittelwert sagt wenig über den einzelnen Fall.
• Auswahl durch den Beweis: Abstände zum Optimum stehen nur für Fälle mit bewiesenem Optimum. Bei 10 Zügen fehlen 4 von 20 Fällen; sind es gerade die schwierigen, sind die Abstände dort verzerrt (nicht geprüft).
• Spreizung hängt vom Löser ab: CP-SAT gibt unter gleich guten Lösungen eine zurück (der Löser sucht mit mehreren parallelen Suchprozessen); die Gesamtverspätung des Optimums ist eindeutig, die Spreizung dieser einen Lösung nicht. Für die faire Lösung ist das vermutlich ähnlich (nicht geprüft). Die Spreizungen sind daher Messwerte dieses Laufs.
• Rechenzeit: Die Zeiten hängen vom Rechner ab.
• Modellgrenzen: Die Regeln vergeben die Trasse Zug für Zug und ganz. Jeder Zug fährt die ganze Strecke in einer Richtung, Wunschabfahrten sind fest, Ausweichgleise unbegrenzt, jede Verspätungsminute zählt für alle Unternehmen gleich. Fahrzeitreserven, Trassenpreise und Rechtslage fehlen, ebenso Teilstrecken und Halte, Mehrgleisstrecken, Störungen und Fahrzeugumläufe. Fairness ist nur das Min-Max der mittleren Verspätung je Unternehmen; andere Maße wie der Anteil verspäteter Züge oder die längste Verspätung wären ein Ausbau.
• Erstanmelder heißt hier: Sortierung nach Wunschabfahrt, nicht nach dem Zeitpunkt der Anmeldung. Wie reale Trassenanmeldungen geordnet werden, bildet das Modell nicht ab (Anmerkung dieser Seite).

Erweiterungen und Verweise

Verwandte Demos dieser Website:

• Dieselbe Struktur an anderen Aufgaben: Der Trassenkonflikt ist strukturell ein Job-Shop mit Routen: Jeder Zug ist ein Auftrag, der die Abschnitte als Maschinen in einer eigenen, festen Reihenfolge durchläuft. Die job-shop-demo behandelt den Job-Shop mit dem Ziel Gesamtdurchlaufzeit und Prioritätsregeln; hier stehen die Räumzeit nach jedem Abschnitt und die Fairness zwischen den Unternehmen im Mittelpunkt.
• Vorgänger und Nachbarn in der Reihe: Im Taktfahrplan stand die Mindest-Zugfolge nur als Vorgriff. Die Fahrzeitreserve verteilt die Reserven, die hier fehlen.

Quellen

• Giffler, Thompson (1960): Algorithms for solving production-scheduling problems. Operations Research 8(4), 487-503 (aktive Pläne im Job-Shop).
• Pinedo: Scheduling: Theory, Algorithms, and Systems. Springer (Lehrbuch, mehrere Auflagen).
• Jain, Chiu, Hawe (1984): A quantitative measure of fairness and discrimination for resource allocation in shared computer systems. DEC Technical Report 301 (Jain-Index).
• Bertsimas, Farias, Trichakis (2011): The price of fairness. Operations Research 59(1), 17-31.
• Löser CP-SAT: Google OR-Tools, Dokumentation unter developers.google.com/optimization.
• Quelltext, Messreihe und Tests der Demo: github.com/sebastian-hanisch/trassenkonflikt-demo.

Die genannten Arbeiten wurden für diese Seite nicht per Suche nachgeschlagen; die Angaben stammen aus dem Gedächtnis (Hefte und Seiten eingeschlossen) und sind nicht geprüft. Die Befundtabelle gibt die Messreihe der Demo wieder; Herleitungen, der Beispielfall und die Nachrechnungen aus den Rohergebnissen sind Rechnungen dieser Seite.