Crew Pairing verständlich erklärt

Ein Zug pendelt den ganzen Tag zwischen zwei Städten, aber niemand darf den ganzen Tag vorn sitzen. Wer löst wen wo ab, damit alle Regeln stimmen und das Ganze möglichst wenig kostet? Diese Seite zeigt, wie man das plant und was jede Regel kostet.

Zuletzt aktualisiert: 11. November 2026

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

Ein Zug, viele Besatzungen

Stellen Sie sich einen Zug vor, der von früh bis spät zwischen zwei Städten pendelt. Er hält unterwegs an mehreren Stationen. Das Stück von einem Halt zum nächsten heißt hier Teilstrecke. Jede Teilstrecke dauert gut eine Stunde und braucht eine Besatzung, die vorn im Führerstand fährt.

Niemand darf den ganzen Tag am Steuer sitzen, denn wer lange fährt, ermüdet. Regeln setzen Grenzen, und die Besatzungen lösen sich ab. An jeder Station darf getauscht werden.

Die Seite erklärt das an einem vereinfachten Rechenbild (Fachwort: Modell): einer erfundenen Strecke mit sieben Stationen, zwei Tagen und drei bis fünf Zügen. Eine solche Strecke samt Fahrplan heißt hier Netz. Darin gelten diese Regeln:

• Lenkzeit am Stück: Wer vorn fährt, lenkt den Zug. Sie darf höchstens viereinhalb Stunden am Stück dauern. Eine Lücke von einer halben Stunde unterbricht sie, ebenso das Mitfahren als Fahrgast.
• Lenkzeit je Dienst: höchstens acht Stunden. Ein Dienst ist ein Arbeitstag der Besatzung.
• Dienstspanne: Vom Beginn bis zum Ende eines Dienstes dürfen höchstens elf Stunden vergehen.
• Ruhezeit: Zwischen zwei Diensten liegen mindestens neun Stunden.
• Hotel: Wer die Ruhezeit nicht zu Hause verbringt, braucht ein Hotelzimmer. Das kostet extra.
• Mitfahren: Eine Besatzung darf als Fahrgast mitfahren, etwa um zum nächsten Einsatzort zu kommen. Sie fährt dann nicht vorn, wird aber bezahlt.

Von zuhause bis zuhause

Ein Dienst allein reicht nicht. Die Besatzungen wohnen an einer von zwei Heimatbasen, den beiden Enden der Strecke. Von dort startet eine Besatzung, arbeitet einen Dienst oder mehrere, ruht dazwischen und kehrt am Ende zur selben Heimatbasis zurück. Diese Folge von Diensten heißt Paarung. Die Planung nennt man auf Englisch Crew Pairing.

Gesucht sind Paarungen, die jede Teilstrecke besetzen und alle Regeln einhalten. Die Kosten aus Lohn und Hotel sollen klein sein.

Das ist schwerer, als es klingt. Jede Teilstrecke lässt viele Anschlüsse zu, und das über mehrere Tage. Wie bei einem Zahlenschloss vervielfacht jede weitere Stelle die Möglichkeiten. Alle Paarungen aufzuschreiben ist deshalb nicht sinnvoll.

Wie der Rechner plant

Der Rechner beginnt mit einem Notplan: Jede Teilstrecke bleibt unbesetzt. Das kostet in der Rechnung eine hohe Strafe, damit unbesetzte Teilstrecken nur im Notfall vorkommen.

Dann gibt der Rechner jeder Teilstrecke einen Verrechnungspreis. Er sagt, was es den Plan zurzeit kostet, diese Teilstrecke zu besetzen. Eine neue Paarung lohnt sich, wenn der Plan für ihre Teilstrecken zusammen mehr bezahlt, als sie selbst kostet.

Die lohnendsten Paarungen kommen in die Auswahl, und die Preise werden neu berechnet. Das wiederholt sich, bis keine Paarung mehr lohnt.

Am Ende steht eine Untergrenze: Billiger kann kein Plan sein. Dafür rechnet der Rechner großzügiger als die Wirklichkeit: Er darf eine Paarung auch nur zu einem Teil einsetzen, als ließe sich eine Besatzung teilen. Wer mehr Spielraum hat, kommt nie teurer weg, denn er darf auch alles ganz lassen. Echte Besatzungen sind nicht teilbar, darum liegt der echte Plan im Mittel darüber. Er wählt unter den gefundenen Paarungen. Im Mittel liegt er 3 bis 5 % über der Untergrenze, gemessen an 20 erfundenen Netzen je Zugzahl.

Zum Vergleich plant ein gieriges Verfahren, das immer sofort den nächsten billigen Schritt nimmt: Es wählt die Paarung, die je neu besetzter Teilstrecke am billigsten ist. Danach streicht es Paarungen, deren Teilstrecken auch andere besetzen. Es liegt im Mittel 17 bis 20 % über der Untergrenze. Das Bild dazu: Wer zuerst das billigste Stück nimmt, bindet früh Besatzungen, die später bei anderen Teilstrecken fehlen. Das ist eine Deutung, gemessen wurde nur der Abstand.

Was jede Regel kostet

Der Aufschlag ist der Mehrpreis gegenüber dem Plan nach den Regeln oben, wenn jeweils eine Regel verändert wird. Die Prozentzahlen sind Mittelwerte über 20 erfundene Netze mit vier Zügen. Gemessen wurden die Aufschläge und die Zahl der Nächte, die Gründe nach „Warum“ sind Deutungen.

• Hotel: Verdoppelt man den Hotelpreis, wird der Plan 25 % teurer, bei vierfachem Preis 77 %. Warum so viel? Hotel macht 27 % der Kosten aus. Blieben alle Nächte gleich, wären es beim doppelten Preis gerade diese 27 % mehr. Der Plan weicht kaum aus: Die Zahl der Nächte sinkt im Mittel um weniger als eine je Netz.
• Lenkzeit am Stück: Nur noch drei statt viereinhalb Stunden. Der Plan wird 11 % teurer. Warum? Eine Besatzung schafft dann nur noch zwei Teilstrecken am Stück statt drei. Das erzwingt mehr Wechsel unterwegs, und jeder Wechsel muss zu den Anschlüssen passen.
• Ruhezeit: Dreizehn statt neun Stunden. Im Mittel bleibt dann eine Teilstrecke je Netz unbesetzt. Warum? Nach einem späten Dienstende reicht die Ruhezeit nicht mehr bis zum frühen Zug am nächsten Morgen. Die Strafe für diese Ausfälle macht den größten Teil des gemessenen Aufschlags aus. Darum sagt hier die Zahl der unbesetzten Teilstrecken mehr als die Kostenzahl.
• Mitfahren: verboten. Im Mittel bleiben gut zwei Teilstrecken je Netz unbesetzt, nur in 7 von 20 Netzen sind alle besetzt. Ohne Strafe steigen die Kosten um 9 %. Diese Zahl ist aber auf weniger besetzten Teilstrecken gerechnet und daher zu niedrig. Warum bleiben Teilstrecken offen? Ohne Mitfahren kann eine Besatzung nur dort arbeiten, wo sie schon ist.

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 stellen Sie die Regeln selbst ein.

Häufige Missverständnisse

• „Eine strengere Regel macht den Plan teurer.“ Nicht automatisch. In einem anderen, einfacheren Netz kehrte jede Besatzung abends ohnehin heim, und eine längere Ruhezeit änderte nichts. Eine Regel kostet nur dort, wo sie wirklich bindet.
• „Die Untergrenze ist der beste mögliche Plan.“ Nein. Sie ist nur ein Wert, unter den kein Plan fallen kann. Bei fünf Zügen traf der echte Plan sie in keinem von 20 Netzen. Der Abstand kommt von der Unteilbarkeit der Besatzungen und von der Auswahl unter den gefundenen Paarungen.

Woran Sie das im Alltag erkennen

• Niemand darf lange am Stück arbeiten, und danach muss ein anderer übernehmen, etwa bei Fahrerwechseln auf einer langen Autofahrt.
• Jeder muss am Ende wieder am Ausgangspunkt sein, und wer unterwegs übernachtet, verursacht Extrakosten, etwa bei Fahrgemeinschaften zu einem Wochenendturnier.

Wie ernst ist das Rechenbild zu nehmen?

Die Strecke ist erfunden, und die Teilstrecken sind vorgegeben. Die Kosten stehen in Minuten Lohn, auch das Hotel ist so umgerechnet, nicht in Euro. Die Zahlen gelten für diese Netze und zeigen die Größenordnung.

Was Sie mitnehmen:

• Besatzungen planen heißt, Folgen von Diensten zu planen, nicht einzelne Tage.
• Fragen Sie bei einer Regel zuerst, ob sie bei Ihnen wirklich bindet, bevor Sie an ihr sparen.
• Fragen Sie bei jeder Kostenzahl, ob unbesetzte Teilstrecken schon eingerechnet sind.

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 ein synthetisches Netz mit festem Regelwerk; alle Zahlen gelten nur dafür.

• Netz: eine Strecke mit 7 Stationen, Planungshorizont 2 Tage. Jeder Zug pendelt zwischen zwei Stationen der Strecke und ist in Teilstrecken zwischen benachbarten Stationen zerlegt: 75 min je Teilstrecke, 4 min Halt zwischen den Teilstrecken einer Fahrt, mindestens 25 min Wende am Ende (mit zufälligem Zuschlag). Er beginnt den Tag dort, wo er abends stand. Abfahrts- und Wendezeiten schwanken zufällig. Jede Teilstrecke \(t\) braucht eine Besatzung. Bei 3, 4 und 5 Zügen sind im Mittel 47, 69 und 88 Teilstrecken unter den Standardregeln überdeckbar; gemessen wird nur auf diesen.
• Heimatbasen: zwei, an den beiden Endstationen der Strecke. Eine Variante der Messreihe nutzt nur eine.
• Dienst: eine Kette von Teilstrecken, jede gefahren (überdeckt die Teilstrecke, zählt als Lenkzeit) oder mitgefahren (überdeckt sie nicht, unterbricht die ununterbrochene Lenkzeit). Anschluss: gleiche Station; wer im selben Zug sitzen bleibt, braucht keine Umsteigezeit, zwischen verschiedenen Zügen sind mindestens 15 min nötig. Ein Dienst enthält mindestens eine gefahrene Teilstrecke. Standardgrenzen: Dienstspanne höchstens 11 h, Lenkzeit höchstens 8 h, ununterbrochene Lenkzeit höchstens 4,5 h (eine Lücke ab 30 min oder Mitfahren unterbricht sie). Bezahlt wird jeder Dienst mit mindestens 300 min (Garantie), sonst mit seiner Spanne.
• Paarung: bis zu 3 Dienste, dazwischen Ruhezeiten von mindestens 9 h und höchstens 30 h (die Regelvarianten der Messreihe ändern nur die Untergrenze). Die Ruhezeit verbringt die Besatzung dort, wo der Dienst endet und der nächste beginnt. Eine Paarung beginnt und endet an derselben Heimatbasis. Liegt eine Ruhezeit nicht an der Heimatbasis, kostet sie eine Hotelnacht (Preis 500). Lohn und Hotel stehen in Minutenäquivalenten.
• Strafe: Für jede Teilstrecke gibt es zusätzlich eine Strafspalte mit Kosten 5 000. Sie lässt die Teilstrecke unüberdeckt. Die Höhe der Strafe ist eine Setzung, kein Messwert; eine Empfindlichkeitsprüfung gibt es nicht.
• Verfahren: (a) Spaltengenerierung: Sie startet nur mit den Strafspalten. Dann folgt LP über die bekannten Paarungen, die Duale (Verrechnungspreise) gehen an das Pricing, die Suche nach neuen Paarungen; bis zu 30 mit negativen reduzierten Kosten je Heimatbasis und Runde werden aufgenommen, bis keine mehr kommt. Das Ergebnis ist die LP-Schranke. (b) Ganzzahlig: Auswahl unter allen erzeugten Paarungen (Mengenüberdeckung, Löser HiGHS). (c) Gierig: immer die Paarung mit den geringsten Kosten je neu überdeckter Teilstrecke, danach werden überflüssige gestrichen; derselbe Pool wie bei (b).
• Messreihe: 3, 4 und 5 Züge mit je 20 Netzen (feste Startwerte des Zufallsgenerators); dazu der Standard und 13 Regelvarianten auf 20 Netzen mit 4 Zügen. Angegeben sind Mittelwerte über die Netze, bei einem ± der Standardfehler des Mittels.

Die Formeln

Master (Mengenüberdeckung). \(P\) sei die Menge der zulässigen Paarungen \(p\) mit Kosten \(c_p\). Der Wert \(a_{tp} \in \{0, 1\}\) sagt, ob \(p\) die Teilstrecke \(t\) fährt, und \(x_p \in \{0, 1\}\) wählt \(p\) aus:

\[\min \sum_p c_p x_p\]

unter der Bedingung, dass jede Teilstrecke \(t\) überdeckt ist:

\[\sum_p a_{tp} x_p \ge 1\]

\(P\) ist riesig und wird nicht aufgezählt. Mehrfach überdeckte Teilstrecken entsprechen Mitfahren.

Spaltengenerierung. Man löst das LP über eine Teilmenge \(P' \subseteq P\) und erhält Duale \(\pi_t \ge 0\), die Verrechnungspreise der Teilstrecken. Die reduzierten Kosten einer Paarung sind

\[\bar c_p = c_p - \sum_t a_{tp}\pi_t\]

Gibt es ein \(p\) mit \(\bar c_p < 0\), kommt es zu \(P'\) hinzu. Gibt es keins, ist das LP-Optimum über \(P'\) das über \(P\) und damit die Schranke (Begründung unten).

Kosten einer Paarung. Mit Dienstbeginn \(s\), Dienstende \(e\), Garantie \(G = 300\) und Hotelpreis \(H\):

\[c_p = \sum_{\text{Dienste}} \max(G, e - s) + H \cdot (\text{Nächte auswärts})\]

Pricing als Ressourcen-Kürzester-Weg. Das Pricing sucht je Heimatbasis die Paarung mit den kleinsten reduzierten Kosten. Knoten sind Teilstrecken, jeweils als gefahren oder als mitgefahren, Kanten sind Anschlüsse im Dienst und Ruhezeiten zwischen Diensten. Ein Label fasst den Stand eines Teilwegs zusammen: \((\bar c, s, d, u)\) mit den reduzierten Kosten bis hier, dem Dienstbeginn \(s\), der Lenkzeit \(d \le d_{\max}\) und der ununterbrochenen Lenkzeit \(u \le u_{\max}\); dazu kommt die Spanne \(e - s \le \sigma_{\max}\), und ein Merkbit hält fest, ob der Dienst schon eine gefahrene Teilstrecke enthält. Dominanz streicht Teilwege, die nie besser enden können als ein anderer: Verglichen werden nur Labels an derselben Teilstrecke im selben Dienst der Paarung. Dort dominiert \((\bar c, s, d, u)\) das Label \((\bar c', s', d', u')\), wenn \(\bar c \le \bar c'\), \(s \ge s'\), \(d \le d'\) und \(u \le u'\) gilt und das erste Label eine gefahrene Teilstrecke enthält, sobald das zweite eine enthält.

Herleitungen Schritt für Schritt

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

Warum die LP-Schranke eine Untergrenze ist.

• Schritt 1: Jede ganzzahlige Auswahl erfüllt auch die LP-Bedingungen, denn \(x_p \in \{0, 1\}\) ist ein Sonderfall von \(x_p \ge 0\). Das LP minimiert über eine größere Menge, sein Optimum über alle \(P\) ist also höchstens so groß wie das beste ganzzahlige.
• Schritt 2: Das LP über \(P'\) hat weniger Spalten und liegt deshalb mindestens so hoch wie das über \(P\). Findet das Pricing eine Paarung mit \(\bar c_p < 0\), kann es noch sinken.
• Schritt 3: Findet das Pricing keine, gilt \(\sum_t a_{tp}\pi_t \le c_p\) für alle \(p \in P\). Die Duale sind dann auch im Dual-LP über ganz \(P\) zulässig. Ihr Zielwert \(\sum_t \pi_t\) ist das LP-Optimum über \(P'\) und nach schwacher Dualität (jeder zulässige Dualwert liegt höchstens beim Minimum) eine Untergrenze für das LP über \(P\), also für jede ganzzahlige Lösung.
• Bedingung: Das Pricing muss exakt sein. Es wurde auf kleinen Fällen gegen eine Vollaufzählung aller Paarungen geprüft. Die Strafspalten liegen von Anfang an im LP und gehören zu \(P'\).

Warum das Pricing ein Kürzester-Weg-Problem mit Ressourcen ist.

• Schritt 1: Ordnet man die Teilstrecken nach Abfahrt, laufen alle Anschlüsse in der Zeit vorwärts. Eine Paarung ist dann ein Weg in einem kreisfreien Graphen, der zu jeder Teilstrecke zwei Knoten hat, einen für gefahren und einen für mitgefahren.
• Schritt 2: Die reduzierten Kosten sind fast additiv: \(-\pi_t\) je gefahrene Teilstrecke, \(H\) auf jeder Ruhekante, die nicht an der Heimatbasis liegt, und beim Dienstende \(\max(G, e - s)\). Der letzte Term hängt vom Dienstbeginn ab. Deshalb wird \(s\) zur Ressource.
• Schritt 3: Auch die Zulässigkeit hängt an Ressourcen. Eine gefahrene Teilstrecke der Dauer \(\ell\) erhöht \(d\) um \(\ell\) und \(u\) um \(\ell\); liegt davor eine Lücke ab 30 min, beginnt \(u\) neu bei \(\ell\). Eine mitgefahrene Teilstrecke setzt \(u\) auf 0 und lässt \(d\) unverändert.
• Schritt 4: Gelten für zwei Labels an derselben Teilstrecke im selben Dienst der Paarung \(\bar c \le \bar c'\), \(s \ge s'\), \(d \le d'\) und \(u \le u'\), und enthält das erste eine gefahrene Teilstrecke, sobald das zweite eine enthält, ist jede Fortsetzung des zweiten Labels auch für das erste zulässig: Die Ressourcen sind kleiner, die Spanne ist kürzer. Sie ist auch nicht teurer, weil \(\bar c\) kleiner ist und \(\max(G, e - s)\) mit größerem \(s\) nicht wächst. Das zweite Label kann gestrichen werden, ohne das Optimum zu verlieren. Das Merkbit ist nötig: Ohne gefahrene Teilstrecke wäre eine Fortsetzung, die nur mitfährt und den Dienst beendet, für das erste Label unzulässig, für das zweite nicht.

Was die Regelwerte in Teilstrecken bedeuten. Nur ganze Teilstrecken zählen als Lenkzeit, und jede dauert 75 min.

• Ununterbrochen 4,5 h: Drei Teilstrecken am Stück bleiben unter der Grenze, vier überschreiten sie. Bei 3 h sind es zwei Teilstrecken am Stück, drei überschreiten die Grenze.
• Lenkzeit je Dienst: Bei 8 h sind höchstens sechs gefahrene Teilstrecken möglich, bei 7 h fünf, bei 6 h vier. Die Verschärfung von 8 auf 7 h nimmt also nur den sechsten Lenkabschnitt aus dem Dienst.
• Garantie 300 min: Drei aufeinanderfolgende Teilstrecken eines Zuges mit zwei Halten dauern knapp vier Stunden und werden pauschal bezahlt. Ab vier Teilstrecken übersteigt die Spanne die Garantie.
• Einordnung: Dazu passt, dass 8 auf 7 h nur +1,0 % kostet, 8 auf 6 h +3,6 % und 4,5 auf 3 h ununterbrochen +11,4 %. Die ersten beiden liegen im Bereich der Lücke der ganzzahligen Auswahl; die Ursache zeigt die Messung nicht.

Durchgerechnet: Paarung und Hotelaufschlag

Eine Paarung von Hand. Konstruierter Fall, Rechnung dieser Seite. Eine Besatzung fährt von einer Heimatbasis aus drei aufeinanderfolgende Teilstrecken eines Zuges bis zu einer Station mitten auf der Strecke. Der Dienst dauert knapp vier Stunden und wird mit der Garantie \(G\) bezahlt. Sie ruht dort mindestens 9 h, das kostet \(H\). Am nächsten Morgen fährt sie in einem zweiten Dienst, wieder knapp unter der Garantie, zur Heimatbasis zurück. Die Paarung kostet \(2G + H\), bei den Standardwerten also elfhundert Minutenäquivalente. Sie lohnt sich im Master, wenn die Verrechnungspreise der sechs gefahrenen Teilstrecken zusammen diese Summe übersteigen, wenn also \(\bar c_p < 0\) gilt.

Der Hotelaufschlag (Rechnung dieser Seite):

• Schritt 1: Der Hotelanteil der Standardkosten beträgt 27 %. Steigt der Hotelpreis auf das \(k\)-Fache und blieben Paarungen und Nächte gleich, wüchsen die Kosten um \((k-1)\) mal den Hotelanteil des Standardplans: für \(k = 2\) um 27 %, für \(k = 4\) um rund vier Fünftel.
• Schritt 2: Der alte Plan ist auch beim neuen Preis noch zulässig. Der exakte Optimalwert steigt daher höchstens um diesen Betrag. Die gemessenen Mittel +25,4 % und +77,0 % liegen knapp darunter. In einzelnen Netzen überschreitet die ganzzahlige Auswahl die Grenze, weil sie nicht das exakte Optimum liefert.
• Schritt 3: Die Umplanung spart also nur einen kleinen Teil: Die mittlere Zahl der Nächte je Netz sinkt um weniger als eine Nacht. Beides ist aus den Rohergebnissen nachgerechnet.

Wie viel der Strafe in den Aufschlägen steckt. Rechnung dieser Seite aus den Rohergebnissen der Messreihe: Jede unüberdeckte Teilstrecke kostet 5 000, die mittleren Standardkosten liegen bei 4 Zügen bei gut zwölftausend Minutenäquivalenten. Bei der Ruhezeit von 11 h bleiben im Mittel 0,4 Teilstrecken unüberdeckt (Aufschlag +15,8 %), bei 13 h sind es 1,0 (Aufschlag +38,6 %). Mittlere Strafe durch mittlere Standardkosten ergäbe nahezu den ganzen Aufschlag. Teilt man dagegen in jedem Netz und mittelt die Anteile, entfallen rund drei Viertel auf die Strafe; der Unterschied deutet auf überdurchschnittlich teure Netze unter denen mit unüberdeckten Teilstrecken (geschlossen, nicht geprüft). Der Rest bleibt einstellig und ist nur bedingt vergleichbar, weil der strengere Plan weniger Teilstrecken überdeckt.

Befunde

Jede Zeile gilt für 20 Netze und zeigt Mittelwerte mit Standardfehler nach dem ±. Aufschläge sind die Kosten der ganzzahligen Auswahl einschließlich Strafe, relativ zu den Standardregeln auf demselben Netz; Lücken beziehen sich auf die LP-Schranke desselben Netzes. Die Zeilen zu den Regeln gelten für 4 Züge.

Frage	Befund
Wie groß sind Netz und Standardplan? (4 Züge)	Im Mittel 69 Teilstrecken, 13,1 Paarungen mit 6,8 Übernachtungen. 73 % der Kosten sind Lohn, 27 % Hotel.
Wie nah liegt die ganzzahlige Lösung an der Schranke? (3 / 4 / 5 Züge)	5,2 / 4,1 / 3,4 % über der LP-Schranke; die größte Lücke je Zugzahl ist 15,5 / 12,7 / 8,2 %. Die ganzzahlige Lösung ist gleich der Schranke in nur 6 / 2 / 0 von 20 Netzen. Der Abstand besteht aus Ganzzahligkeitslücke und Paarungswahl; die Aufteilung ist nicht gemessen.
Was verschenkt das gierige Vorgehen? (3 / 4 / 5 Züge)	17,3 ± 2,1 / 19,1 ± 1,9 / 20,3 ± 1,5 % über der LP-Schranke; in jedem der 60 Netze mindestens 1,7 %.
Was kostet das Hotel?	Hotelpreis ×2: +25,4 ± 1,6 %, ×4: +77,0 ± 4,5 %; in allen 20 Netzen teurer.
Was kostet die Lenkzeit?	Ununterbrochen höchstens 3 statt 4,5 h: +11,4 ± 1,7 %. Lenkzeit je Dienst 7 h: +1,0 %, 6 h: +3,6 %. Garantie 360 statt 300: +2,0 %. In diesen Zeilen bleibt keine Teilstrecke unüberdeckt; die drei letzten Werte sind klein gegen die Lücke der ganzzahligen Auswahl.
Was kostet die Ruhezeit? (mit Strafe)	11 h: +15,8 ± 6,2 %, 13 h: +38,6 ± 12,0 %. Dabei bleiben im Mittel 0,4 bzw. 1,0 Teilstrecken unüberdeckt.
Was bringt das Mitfahren?	Ohne Mitfahren bleiben 2,4 Teilstrecken unüberdeckt, nur in 7 von 20 Netzen sind alle überdeckt. Mit Strafe verdoppeln sich die Kosten ungefähr (Rechnung aus den Rohergebnissen). Die Kosten ohne Strafe steigen um 9,3 %, gerechnet auf weniger überdeckten Teilstrecken; diese Zahl unterschätzt den Aufschlag.
Wie wichtig sind Übernachtung, zweite Heimatbasis und Dienstspanne? (unüberdeckte Teilstrecken von im Mittel 69)	Mit höchstens 1 Dienst je Paarung bleiben 27,6 Teilstrecken unüberdeckt, mit nur einer Heimatbasis 45,9, bei einer Dienstspanne von 9 h 4,8. Zwei Dienste je Paarung kosten mit Strafe +11,1 ± 7,0 %.
Wie lange rechnet die Spaltengenerierung? (3 / 4 / 5 Züge)	Median 0,5 / 1,7 / 3,5 s, davon das Pricing 64 / 73 / 76 % der Zeit; im Mittel 74 / 86 / 106 Iterationen.

Was die Messung zeigt und wo die Grenzen liegen

Was sie belegt:

• Die Reihenfolge LP-Schranke, ganzzahlige Lösung, gierige Lösung in jedem der 60 Netze der Größenreihe; die ganzzahlige Auswahl war dort unter den erzeugten Paarungen bewiesen optimal.
• Die Aufschläge für Hotel und für die ununterbrochene Lenkzeit. Hier bleibt in allen Netzen jede Teilstrecke überdeckt, der Aufschlag ist reiner Kostenunterschied, und die Regel ist in allen 20 Netzen teurer. Die kleinen Aufschläge für die Lenkzeit je Dienst und für die Garantie liegen dagegen im Bereich der Lücke der ganzzahligen Auswahl und sind nicht belegt.
• Das Pricing: Es wurde auf kleinen Fällen gegen eine Vollaufzählung aller Paarungen geprüft.

Was sie nicht belegt:

• Aufschläge mit Strafe: Bei Ruhezeit, Mitfahren, Dienstzahl, Dienstspanne und Heimatbasen hängt die Kostenzahl an der Strafe von 5 000 je Teilstrecke, deren Höhe nicht auf Empfindlichkeit geprüft ist. Ohne Strafe gerechnet ist der Vergleich verzerrt, weil der strengere Plan weniger Teilstrecken überdeckt: Bei Dienstzahl, Dienstspanne und Heimatbasen sieht er dann im Mittel sogar billiger aus, bei Ruhezeit und Mitfahren bleibt er im Mittel teurer, wird aber unterschätzt. Die Zahl der unüberdeckten Teilstrecken ist hier die verlässlichere Größe.
• Die ganzzahlige Lösung ist nicht das Optimum: Sie wählt nur unter den erzeugten Paarungen. Auf einem einzelnen Netz kann eine strengere Regel daher knapp billiger ausfallen. Das geschieht (aus den Rohergebnissen nachgerechnet): Bei der Lenkzeit von 7 h war der Plan in 6 von 20 Netzen billiger als der Standardplan, bei der Garantie von 360 min in 2, im exakten Optimum wäre das unmöglich. Ein Branch-and-Price fehlt.
• Absolute Preise: Das Netz ist synthetisch, die Kosten stehen ohne Tarifwerte in Minutenäquivalenten; die Preise der Regeln sind Größenordnungen.
• Abhängigkeit vom Netz: In einem ersten Netz mit Linien nur zwischen Basis und Außenstation war jeder Dienst ein Hin und Zurück, und eine Ruhezeit von 13 statt 9 h kostete +0,0 %. Erst der Umbau auf das jetzige Netz machte die Regeln wirksam; die Befunde gelten nur für diese Bauart.
• Gemeinsame Teilstreckenmenge: Gemessen wird auf den Teilstrecken, die unter den Standardregeln überdeckbar sind; andere (etwa am ersten Morgen, wo noch keine Besatzung angereist sein kann) fehlen im Netz.
• Was fehlt: Fahrzeugumlauf, Einteilung auf Personen mit Gerechtigkeit zwischen ihnen, Wochenruhe, Krankheitsreserve; Mitfahren ist kostenfrei und ohne Platzgrenze. Das gierige Vorgehen nutzt den Paarungspool der Spaltengenerierung; ein Vergleich mit Handplanung fehlt. Rechenzeiten hängen vom Rechner ab.

Erweiterungen und Verweise

Verwandte Demos dieser Website:

• Dasselbe Verfahren an anderen Aufgaben: Die column-generation-demo zeigt die Spaltengenerierung am Zuschnitt (Pricing: Rucksack). Die mcf-column-generation-demo nutzt einen gewöhnlichen kürzesten Weg als Pricing; hier kommen Ressourcen und das Regelwerk dazu.
• Ausbau zur ganzzahligen Lösung: Die branch-and-price-demo verbindet Verzweigung und Spaltengenerierung am Zuschnitt. Hier ist das nicht umgesetzt; die Verzweigungsregel müsste zum Regelwerk passen.
• Vorgänger in der Reihe: Der Taktfahrplan wählt die Abfahrtsminuten der Linien. Die Teilstrecken hier stammen nicht aus ihm, sondern aus einem eigenen Generator.

Quellen

• Gilmore, Gomory (1961): A linear programming approach to the cutting-stock problem. Operations Research 9 (frühe Anwendung der Spaltengenerierung).
• Desrosiers, Lübbecke (2005): A primer in column generation. In: Desaulniers, Desrosiers, Solomon (Hrsg.): Column Generation. Springer.
• Irnich, Desaulniers (2005): Shortest path problems with resource constraints. In: Column Generation, Springer (Pricing mit Ressourcen und Dominanz).
• Barnhart, Johnson, Nemhauser, Savelsbergh, Vance (1998): Branch-and-price: column generation for solving huge integer programs. Operations Research 46.
• Quelltext, Messreihe und Tests der Demo: github.com/sebastian-hanisch/crew-pairing-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen; die Angaben stammen aus dem Gedächtnis und sind nicht geprüft. Die Befundtabelle gibt die Messreihe der Demo wieder; Herleitungen, konstruierter Fall, Umrechnung in Teilstrecken sowie Hotel- und Strafrechnung sind Rechnungen dieser Seite.