Das ÖPNV-Liniennetz verständlich erklärt

Eine Stadt hat wenige Busse und viele Haltestellen. Welche Haltestellen soll jede Linie verbinden, damit möglichst viele Fahrgäste ohne Umsteigen ankommen? Wer dabei nur die beliebtesten Strecken bedient, lässt manche Fahrgäste zurück. Diese Seite zeigt, warum.

Zuletzt aktualisiert: 11. November 2026

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

Wohin fährt welche Linie?

Stellen Sie sich eine Kleinstadt mit vielen Bushaltestellen und nur wenigen Bussen vor. Deshalb gibt es nur wenige Linien, also feste Strecken, auf denen ein Bus hin und her fährt. Jede Linie darf nur begrenzt viele Haltestellen anfahren. Die Planerin entscheidet, welche Haltestellen jede Linie verbindet.

Die Fahrgäste wollen nicht überallhin. Viele fahren zwischen denselben wenigen Orten, etwa vom Wohngebiet zum Bahnhof. Eine gute Planerin legt die Linien dorthin, wo die meisten Fahrgäste hinwollen.

Für jede Verbindung zwischen zwei Haltestellen gibt es drei Möglichkeiten. Erstens: Beide Haltestellen liegen auf derselben Linie. Dann fährt man ohne Umstieg. Zweitens: Zwei Linien halten an einer gemeinsamen Haltestelle. Dort wechselt man einmal die Linie. Drittens: Es bräuchte mindestens zwei Umstiege. Oder eine der beiden Haltestellen liegt auf gar keiner Linie. In beiden Fällen heißt die Verbindung auf dieser Seite nicht erreichbar. Das ist eine Festlegung für den Vergleich: Im echten Leben käme man mit zwei Umstiegen oft noch an, hier zählt es als gescheitert.

Jeder Umstieg kostet Warten und Nerven. Darum zählt diese Seite vor allem die Fahrten ohne Umstieg.

Zwei Wege zum Netz

Der erste Weg ist das Sternnetz. Man nimmt die Haltestelle mit den meisten Fahrgästen als Zentrum. Von dort geht jede Linie wie eine Speiche am Fahrrad in eine andere Richtung. Wer von einer Linie zu einer anderen will, steigt im Zentrum um. Weil alle Linien sich dort treffen, braucht niemand mehr als einen Umstieg, solange beide Haltestellen auf irgendeiner Linie liegen. Der Nachteil: Wer von Speiche zu Speiche will, muss über das Zentrum, auch wenn beide Orte nebeneinander liegen.

Der zweite Weg ist das Nachfrage-Verfahren. Es sucht zuerst die Verbindung, die die meisten Fahrgäste wollen, und legt dort eine Linie hin. Dann hängt es nacheinander die Haltestellen an, die der Linie die meisten zusätzlichen Fahrgäste bringen, bis die Linie voll ist. Danach beginnt die nächste Linie bei der stärksten Verbindung, die noch fehlt und an das bisherige Netz anschließt. Warum dieser Zusatz nötig ist, zeigt der nächste Abschnitt.

Warum das kluge Verfahren zuerst scheiterte

Die erste Fassung des Nachfrage-Verfahrens war schlechter als das einfache Sternnetz. Ihr fehlte der Zusatz: Sie begann jede neue Linie bei der stärksten Verbindung, die noch fehlte, egal wo diese lag. So entstanden Linien, die sich nirgends berührten. Man kann sie sich als Inseln vorstellen. Von einer Insel zur anderen führt kein Weg, denn Umsteigen geht nur dort, wo zwei Linien dieselbe Haltestelle anfahren. Im Test blieb deshalb über die Hälfte der Fahrgäste unerreichbar. Beim Sternnetz blieb im selben Test niemand unerreichbar.

Die Entwickler beseitigten das mit einer Regel: Jede neue Linie muss das bestehende Netz an mindestens einer Haltestelle berühren. Das ist der Zusatz von oben. Dann gibt es keine Inseln mehr. Eine zweite Regel kam hinzu. Ohne sie baute das Verfahren immer wieder an denselben beliebten Haltestellen. In einem Testfall erreichte es nur elf von zwanzig Haltestellen. Seitdem zählen die Fahrgäste von Haltestellen, die noch auf keiner Linie liegen, bei der Auswahl stärker mit. Das ist der Bonus. Er hilft im Beispielnetz unten, aber nicht in jeder Stadt.

Was am Ende herauskommt

Wie gut sind beide Wege? Das zeigt ein vereinfachtes Rechenbild (Fachwort: Modell). Es besteht aus erfundenen Städten mit zufällig verteilten Haltestellen und Fahrgastwünschen. Fahrzeiten und Fahrpläne kommen nicht vor, es zählt nur, welche Haltestellen eine Linie verbindet. Die Aussagen in diesem Teil beschreiben das Rechenbild, nicht die Wirklichkeit.

Nehmen wir als Beispiel eine Stadt mit zwanzig Haltestellen und vier Linien. Jede Linie darf höchstens sieben Haltestellen anfahren. In fünf solchen Beispielstädten fahren beim Sternnetz weniger als die Hälfte der Fahrgäste ohne Umstieg. Beim Nachfrage-Verfahren sind es etwa zwei Drittel. Alle übrigen kommen bei beiden Verfahren mit einem Umstieg ans Ziel. Ein plausibler Grund: Das Sternnetz teilt die Haltestellen nur nach ihrer Lage auf, nicht nach Fahrgastwünschen.

Wie nah am Besten?

Ein Ergebnis sagt erst etwas, wenn man es mit dem Besten vergleicht. Bei kleinen Städten probiert der Computer alle möglichen Netze durch, wie bei einem Zahlenschloss. Bei größeren Städten sind es zu viele. Dort liefert ein anderes Programm das beste Netz, das es in einer Frist von einigen Sekunden findet, und eine Obergrenze. Sie sagt: Mehr Fahrgäste ohne Umstieg kann kein Netz erreichen.

Ein Beispiel sind kleine Städte mit acht bis zehn Haltestellen und zwei oder drei Linien. Dort kennt man die Obergrenze: Sie ist die größte Zahl von Fahrgästen ohne Umstieg, die irgendein Netz erreichen kann. Im Mittel über jeweils hundert erfundene Städte fehlen dem Nachfrage-Verfahren dazu etwa ein bis sechs von hundert Fahrgästen. Dem Sternnetz fehlen zwölf bis vierunddreißig. Es liegt in allen drei Größen weiter zurück.

Häufige Missverständnisse

• „Das klügere Verfahren ist das bessere.“ Nicht immer. In einer Beispielstadt mit dreißig Haltestellen und sechs Linien lässt das Nachfrage-Verfahren trotz Bonus drei Haltestellen ohne Linie. Es bietet mehr Fahrten ohne Umstieg als das Sternnetz. Wer aber an diesen drei Haltestellen wohnt, kommt nirgends hin. Das Rechenbild wertet streng: Kommen Fahrgäste gar nicht an, ist das Netz schlechter, auch wenn andere bequemer fahren. Deshalb gilt hier das Sternnetz als besser.
• „Das Programm findet das beste Netz.“ Nur in kleinen Städten ist das beste Netz sicher bekannt. Bei zwanzig Haltestellen und vier Linien fand das Rechenprogramm in zehn Beispielstädten im Mittel etwa zweieinhalb von hundert Fahrgästen mehr ohne Umstieg als das Nachfrage-Verfahren. Dass sein Netz das beste ist, konnte es in dreißig Sekunden nie beweisen, denn die Obergrenze liegt noch höher. Man weiß nur: Das Nachfrage-Verfahren liegt im Mittel höchstens etwa sieben von hundert Fahrgästen unter dem Besten.
• „Ein bestes Netz lässt niemanden zurück.“ Bei neun Haltestellen und zwei Linien mit je vier Haltestellen bleibt selbst im besten Netz im Mittel etwa ein Viertel der Fahrgäste unerreichbar. Zwei solche Linien berühren sich entweder, dann decken sie höchstens sieben Haltestellen ab, denn vier plus vier abzüglich einer gemeinsamen sind sieben. Oder sie berühren sich nicht, dann kommt niemand von der einen zur anderen.

Woran Sie das im Alltag erkennen

• Sie wollen von einem Vorort zum Nachbarvorort. Es gibt keine Querlinie, also fahren Sie in die Mitte und steigen dort um. So sieht ein Sternnetz aus.
• In einem Stadtteil hält gar kein Bus, oder Sie bräuchten zwei Umstiege. Dort ist das Netz für Sie nicht vorhanden.

Wie ernst ist das Rechenbild zu nehmen?

Die Städte sind erfunden, und echte Wartezeiten beim Umsteigen sind nicht eingerechnet. Die Zahlen zeigen, wie die Verfahren zueinander stehen, nicht wie gut ein echtes Netz wäre.

Was Sie mitnehmen

• Fragen Sie bei jedem Netz auch, wer gar nicht ankommt, nicht nur, wie bequem es für die meisten ist.
• Ein Netz braucht Haltestellen, an denen sich Linien treffen. Ohne sie gibt es nur Inseln.
• Ein einfaches Verfahren kann ein kluges schlagen, wenn das kluge etwas Wichtiges übersieht. Fragen Sie, was ein Verfahren übersieht.

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser, die Demo. Sie erreichen es über den ersten Knopf unten. Zum Verstehen brauchen Sie es nicht. Der zweite Knopf führt zum zweiten Teil für Fachleute.

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. Er beschreibt ein Rechenmodell der Linienplanung (Line Planning) für den öffentlichen Nahverkehr: Aus einer festen Zahl von Linien ist ein Netz zu wählen, das möglichst viel Fahrgastnachfrage ohne Umstieg verbindet. Es ist ein bewusst vereinfachtes Teilproblem des Transit Network Design (TNDP), das in der Literatur als NP-schwer, nicht konvex und mehrzielig beschrieben wird. Fahrzeiten, Takte, Umstiegszeiten, Fahrzeugkapazitäten und ein echtes Straßennetz fehlen. Anders als in der klassischen Linienplanung (Auswahl aus einem Linienpool auf einem Verkehrsnetz, mit Häufigkeiten) sind die Linien hier beliebige Haltestellenmengen, und die Geometrie geht nicht in die Bewertung ein. Die Aufgabe ähnelt daher einem Überdeckungsproblem mit Umstiegsbedingung.

• Daten: \(n\) Haltestellen mit zufälligen Koordinaten in einem Quadrat und eine symmetrische, ganzzahlige Nachfrage \(w_{ij} = w_{ji}\) (aggregierte Tagesnachfrage beider Richtungen) mit \(w_{ii} = 0\). Erzeugt wird zuerst ein Basiswert: Mittel zweier Zufallszahlen zwischen 1 und 10, dadurch symmetrisch. Die Zeilen und Spalten von \(h\) zufällig gewählten Pendlerzentren werden mit \(1 + 6c\) multipliziert (ein Paar aus zwei Zentren erhält den Faktor \((1 + 6c)^2\)), wobei \(c \in [0, 1]\) die Pendler-Konzentration ist (0 = gleichverteilt, 1 = stark auf wenige Zentren konzentriert). Danach wird auf ganze Zahlen gerundet. Regler: 6 bis 40 Haltestellen, 2 bis 8 Linien, 3 bis 12 Haltestellen je Linie, \(c\) von 0 bis 1, 1 bis 4 Pendlerzentren. Voreinstellung: 20 Haltestellen, 4 Linien, höchstens 7 Haltestellen je Linie, \(c = 0{,}5\), 2 Pendlerzentren.
• Entscheidung: Für jede Linie \(l = 1, \dots, k\) eine Menge \(S_l\) von höchstens \(L\) Haltestellen. Die Reihenfolge längs der Linie hat auf die Bewertung keinen Einfluss und dient nur der Karte.
• Bewertung für jedes Paar \(\{i, j\}\) mit \(w_{ij} > 0\): direkt, wenn eine Linie beide Haltestellen enthält; mit einem Umstieg, wenn nicht direkt, aber zwei Linien \(a, b\) mit \(i \in S_a\), \(j \in S_b\) eine gemeinsame Haltestelle haben; sonst nicht erreichbar. Gemessen wird in Anteilen an \(W = \sum_{i<j} w_{ij}\): \(D\) (direkt), \(E\) (genau ein Umstieg, ohne die direkten Paare) und \(U\) (nicht erreichbar), mit \(D + E + U = 100\,\%\). \(U\) enthält zwei Fälle: Paare, die nur mit zwei oder mehr Umstiegen verbunden wären, und Paare mit einer Haltestelle, die auf keiner Linie liegt.
• Zielgröße (Auswahlregel): lexikografisch erst \(U\) minimieren, bei Gleichstand \(D\) maximieren. Eine Umrechnung in Euro gibt es bewusst nicht. Dass weniger Umstiege kürzere Reisezeiten und mehr Zufriedenheit bringen, ist eine Annahme der Demo und im Modell nicht gemessen, denn Reisezeiten kommen darin nicht vor.

Zwei Konstruktionsverfahren Schritt für Schritt

• Sternnetz (Vergleichsverfahren): (1) Das Zentrum ist die Haltestelle mit der größten Nachfragesumme \(\sum_j w_{ij}\). (2) Die übrigen \(n - 1\) Haltestellen werden nach dem Polarwinkel um das Zentrum sortiert und in \(k\) Sektoren mit annähernd gleich vielen Haltestellen geteilt. (3) Je Sektor entsteht eine Linie aus dem Zentrum und den dem Zentrum nächsten Haltestellen des Sektors, höchstens \(L - 1\) davon. Die Nachfrage geht nur über die Wahl des Zentrums ein.
• Nachfrage-Verfahren (Konstruktionsheuristik): Für jede der \(k\) Linien nacheinander: (1) Startpaar ist unter den Paaren, die noch keine Linie gemeinsam hat, das mit der größten Nachfrage. (2) Anbindungsregel: Ab der zweiten Linie darf nur ein Paar starten, von dem mindestens eine Haltestelle schon im Netz liegt. (3) Wachstumsbonus: Liegt genau eine seiner Haltestellen im Netz, wird die Nachfrage des Paares mit 2,5 multipliziert. (4) Erweiterung: Solange die Linie weniger als \(L\) Haltestellen hat, kommt die Haltestelle \(c\) hinzu, deren Gewinn \(\sum_{s \in \text{Linie}} w_{cs}\) am größten ist; liegt \(c\) noch auf keiner Linie, wird der Gewinn ebenfalls mit 2,5 multipliziert. Sie wird an das Ende der Linie gesetzt, dem sie näher liegt. (5) Eine Linie endet, wenn sie \(L\) Haltestellen hat oder keine Haltestelle mehr hinzukommen kann. Findet sich für die nächste Linie kein zulässiges Startpaar mehr, endet das Verfahren, und die restlichen Linien bleiben leer. Der Wert 2,5 ist gesetzt; eine Empfindlichkeitsrechnung dazu gibt es nicht. Der Gewinn zählt nur direkte Nachfrage, Umstiege kommen nur über die Anbindungsregel vor.
• Folgerung für das Sternnetz (Rechnung dieser Seite): Alle Linien enthalten das Zentrum, daher braucht jedes Paar von Haltestellen, die auf irgendeiner Linie liegen, höchstens einen Umstieg. Nicht erreichbar bleiben nur Paare mit einer Haltestelle ohne Linie. Das tritt auf, wenn ein Sektor mehr als \(L - 1\) Haltestellen enthält, also bei \(\lceil (n-1)/k \rceil > L - 1\). Diese Bedingung wurde an einem Raster von Reglerwerten nachgeprüft, nicht allgemein bewiesen.

Die Formeln

Beide exakten Verfahren rechnen dieselbe Aufgabe mit derselben Auswahlregel. Sie beruhen auf einer Dominanz: Fügt man einer Linie eine Haltestelle hinzu, wachsen nur Mengen, und weder \(D\) noch \(D + E\) sinken. Es genügen daher Linien mit genau \(m = \min(L, n)\) Haltestellen.

Aufzählung. Kandidaten sind alle \(\binom{n}{m}\) Teilmengen mit \(m\) Haltestellen. Ein Netz ist eine Auswahl von \(k\) verschiedenen Kandidaten, es gibt \(\binom{\binom{n}{m}}{k}\) Netze. Für \(n = 10\), \(k = 3\), \(m = 5\) sind es 2 635 500. Die Aufzählung läuft bis höchstens 3 Millionen Netze.

CP-SAT-Modell. Die Binärvariable \(x_{l,s} = 1\) bedeutet, dass Haltestelle \(s\) auf Linie \(l\) liegt, mit \(\sum_s x_{l,s} = m\). Für jedes Paar \(p = (i, j)\) mit Nachfrage \(w_p\) gilt: \(u_{l,p} \le x_{l,i}\), \(u_{l,p} \le x_{l,j}\) und \(d_p \le \sum_l u_{l,p}\) (direkt). (Das ist die Fassung mit kompakten Variablen und fester Linienlänge; das Grundmodell der Messreihe verwendet stattdessen eine Variable je Paar und Linienpaar und \(\sum_s x_{l,s} \le m\).) Für die Erreichbarkeit mit höchstens einem Umstieg gilt \(r_p \le \sum_a v_{a,p}\) mit \(v_{a,p} \le x_{a,i}\) und \(v_{a,p} \le N_{a,j}\), wobei \(N_{a,j}\) bedeutet: \(j\) liegt auf Linie \(a\) oder auf einer Linie, die \(a\) an einer Haltestelle schneidet. Außerdem \(d_p \le r_p\). Weil maximiert wird, genügen diese einseitigen Bedingungen.

Zielfunktion. Maximiert wird \((W + 1) \sum_p w_p r_p + \sum_p w_p d_p\) mit \(W = \sum_p w_p\). Wegen \(\sum_p w_p d_p \le W\) und ganzzahliger Nachfrage entspricht das der Auswahlregel: erst die erreichbare, dann die direkte Nachfrage. Alternativ rechnet das Modell in zwei Stufen: Erst wird \(\sum_p w_p r_p\) maximiert, dann bei festgehaltenem Wert \(\sum_p w_p d_p\). So ist die Schranke der zweiten Stufe in Prozentpunkten der direkten Nachfrage lesbar. Weitere, einzeln abschaltbare Bausteine: eine lexikografische Ordnung der Haltestellen-Bitmasken der \(k\) austauschbaren Linien (Symmetriebrechung), Schnittbedingungen je Linie (höchstens \(m - 1\) Paare je Haltestelle und \(m(m-1)/2\) Paare je Linie), die kompakten Variablen \(N_{a,j}\) und eine Startlösung aus den Heuristiken.

Durchgerechnetes Beispiel: warum sich Linien berühren müssen

Rechnung dieser Seite, keine Messung der Demo. Sechs Haltestellen A bis F, jedes der fünfzehn Paare hat die Nachfrage 1, also ist \(W\) die Zahl der Paare. Die Tabelle zählt Paare, nicht Anteile.

Netz (\(k = 2\))	\(D\)	\(E\)	\(U\)
Getrennte Linien, \(L = 3\): \(\{A,B,C\}\), \(\{D,E,F\}\)	6	0	9
Eine gemeinsame Haltestelle, \(L = 3\): \(\{A,B,C\}\), \(\{C,D,E\}\) (Haltestelle F ohne Linie)	6	4	5
Zwei gemeinsame Haltestellen, \(L = 4\): \(\{A,B,C,D\}\), \(\{C,D,E,F\}\)	11	4	0

Ohne gemeinsame Haltestelle gibt es keinen Umstieg (\(E = 0\)). Zwei Linien mit je \(m\) Haltestellen decken, wenn sie sich an mindestens einer Haltestelle berühren, höchstens \(2m - 1\) Haltestellen ab. Sollen bei \(k = 2\) alle \(n\) Haltestellen paarweise mit höchstens einem Umstieg verbunden sein, muss also \(n \le 2m - 1\) gelten. Für \(n = 9\) und \(m = 4\) ist \(9 > 7\): Selbst das beste Netz lässt dort Nachfrage unerreichbar, im Mittel 24,5 ± 0,2 % (siehe Befunde). Die Anbindungsregel des Nachfrage-Verfahrens übersetzt die erste Einsicht in eine Konstruktionsregel.

Befunde

Alle Werte stammen aus den Messreihen der Demo auf erfundenen Netzen. „Punkte“ sind Prozentpunkte der Gesamtnachfrage. Wo eine Spanne steht, ist es der kleinste und größte Wert über die genannten Netze, kein Mittel. Wo „±“ steht, ist es das Mittel mit Standardfehler über die genannten Zufallsnetze.

Frage	Befund
Wie unterscheiden sich die Verfahren im Beispielnetz? (20 Haltestellen, 4 Linien, höchstens 7 je Linie, fünf Testnetze mit Zufallszahlen 1 bis 5, Pendler-Konzentration sechs Zehntel, 2 Pendlerzentren)	Ohne Umstieg: Sternnetz 44,9-48,1 %, Nachfrage-Verfahren 66,6-68,9 %. Bei beiden liegen alle 20 Haltestellen auf einer Linie, und 0,0 % sind nicht erreichbar. Der Vorsprung des Nachfrage-Verfahrens beträgt je Netz 18,5 bis 22,9 Punkte (je Netz nachgerechnet).
Was ging bei der Entwicklung schief?	Die erste Fassung des Nachfrage-Verfahrens ohne Anbindungsregel ließ 53-61 % der Nachfrage unerreichbar, das Sternnetz im selben Test 0 % (Angabe aus der Dokumentation der Demo; die Fassung ist nicht mehr im Code, die Netze sind nicht angegeben). Nach der Anbindungsregel allein konzentrierte sich die Konstruktion auf wenige Haltestellen, in einem Testfall deckte sie 11 von 20 ab. Der Wachstumsbonus behebt das im Beispielnetz (alle 20 Haltestellen auf einer Linie), nicht in jeder Einstellung: Im Beispielszenario der nächsten Zeile bleiben trotz Bonus drei Haltestellen ohne Linie.
Wann zeigt die Hauptansicht das Sternnetz? (Beispielszenario „Mehrere Zentren“: 30 Haltestellen, 6 Linien, höchstens 7 je Linie, 3 Pendlerzentren, Pendler-Konzentration sechs Zehntel, Zufallszahl 8)	Nachfrage-Verfahren: 27 von 30 Haltestellen auf einer Linie, 13,0 % nicht erreichbar, 57,5 % ohne Umstieg. Sternnetz: alle 30 Haltestellen, 0 % nicht erreichbar, 34,5 % ohne Umstieg. Die Auswahlregel nimmt das Sternnetz. Die 13,0 % entfallen vollständig auf die drei Haltestellen ohne Linie (Nachrechnung dieser Seite).

Abstand zum Optimum durch vollständige Aufzählung. Je Zeile 100 Zufallsnetze (Zufallszahlen 1 bis 100, Pendler-Konzentration 0,5, 2 Pendlerzentren). Die Spalte „Optimum“ ist das Optimum der direkten Nachfrage allein, also eine obere Schranke für jedes Verfahren. Der Abstand ist diese Schranke minus der erreichten direkten Nachfrage.

Instanz (Haltestellen, Linien, höchstens je Linie)	Optimum ohne Umstieg	Sternnetz (Abstand)	Nachfrage-Verfahren (Abstand)
8, 3, 5 (27 720 Netze)	97,5 ± 0,0 %	63,2 ± 0,4 % (34,3 ± 0,4 Punkte)	91,6 ± 0,1 % (5,9 ± 0,1 Punkte)
9, 2, 4 (7 875 Netze)	59,8 ± 0,3 %	47,9 ± 1,0 % (11,9 ± 1,0 Punkte)	58,9 ± 0,3 % (0,8 ± 0,1 Punkte)
10, 3, 5 (2 635 500 Netze)	84,3 ± 0,2 %	59,8 ± 0,3 % (24,5 ± 0,2 Punkte)	82,0 ± 0,3 % (2,3 ± 0,2 Punkte)

Das Nachfrage-Verfahren hat in 100, 97 und 100 von 100 Netzen mehr direkte Nachfrage als das Sternnetz. Kein Verfahren schlägt das Optimum nach der Auswahlregel (jeweils 100 von 100 Netzen). Das Nachfrage-Verfahren trifft es in 0, 4 und 0 von 100 Netzen. Bei der direkten Nachfrage ist der Abstand klein (0,8 bis 5,9 Punkte). Nach der Auswahlregel gilt das nicht überall: In der Zeile 9, 2, 4 lässt das Optimum 24,5 ± 0,2 % der Nachfrage unerreichbar, das Nachfrage-Verfahren im Mittel gut ein Drittel (Messdatei der Demo, in der Dokumentation nicht genannt; nach Nachrechnung dieser Seite mit mehr unerreichbarer Nachfrage als das Optimum in fast allen der 100 Netze). In der Zeile 10, 3, 5 bleibt es in 2 von 100 Netzen nicht ohne unerreichbare Nachfrage. Die 24,5 ± 0,2 Punkte beim Sternnetz in dieser Zeile sind eine andere Größe als die 24,5 % im Optimum der Zeile 9, 2, 4.

CP-SAT für größere Netze. Auf 60 kleinen Netzen (7 bis 10 Haltestellen, 2 bis 3 Linien) beweist CP-SAT das Optimum in 60 von 60 Fällen und findet in 60 von 60 dasselbe Optimum wie die Aufzählung (Rechenzeit im Mittel 0,21 ± 0,04 s bei CP-SAT gegen 0,50 ± 0,13 s bei der Aufzählung; im Median ist die Aufzählung etwa viermal schneller, Nachrechnung dieser Seite aus der Messdatei: Sie ist auf den kleinsten Netzen schneller, auf den größten langsamer). Die Skalierung zeigt die folgende Tabelle: je Zeile 10 Zufallsnetze, Zeitlimit 30 s, 8 Arbeiter, Pendler-Konzentration 0,5, 2 Pendlerzentren. Die letzte Spalte ist die Schranke von CP-SAT für die direkte Nachfrage bei kleinster nicht erreichbarer Nachfrage minus der direkten Nachfrage des Nachfrage-Verfahrens.

Instanz (Haltestellen, Linien, höchstens je Linie)	bewiesen	Lücke zur Schranke (Punkte)	CP-SAT ohne Umstieg	Nachfrage-Verfahren ohne Umstieg	Nachfrage-Verfahren: Schranke minus Wert (Punkte)
10, 3, 5	10 von 10	0,0 ± 0,0	83,9 ± 0,5 %	81,2 ± 1,2 %	2,7 ± 0,9
12, 3, 6	10 von 10	0,0 ± 0,0	83,3 ± 0,2 %	80,2 ± 0,4 %	3,1 ± 0,3
12, 4, 5	0 von 10	4,0 ± 0,2	79,9 ± 0,3 %	76,0 ± 0,5 %	7,9 ± 0,3
14, 4, 6	0 von 10	4,2 ± 0,2	83,0 ± 0,4 %	76,7 ± 0,4 %	10,4 ± 0,2
16, 4, 6	0 von 10	5,1 ± 0,1	72,5 ± 0,4 %	70,4 ± 0,5 %	7,2 ± 0,2
20, 4, 7	0 von 10	4,7 ± 0,1	67,2 ± 0,3 %	64,8 ± 0,4 %	7,1 ± 0,2

Mit 3 Linien beweist CP-SAT bis 12 Haltestellen, mit 4 Linien ab 12 Haltestellen in keinem der 10 Netze. Dort ist das Nachfrage-Verfahren im Mittel je Zeile um 2,1 bis 6,2 Punkte schlechter als der CP-SAT-Fund. Modellbausteine: Auf 8 Netzen mit 10 bis 12 Haltestellen und 3 Linien (je ein Lauf, Zeitlimit 30 s) beweist das Grundmodell 7 davon (Summe der Rechenzeiten über alle 8 Netze 136 s, ein nicht bewiesenes Netz zählt mit dem Zeitlimit), das Modell mit allen Verbesserungen alle 8 in 23 s (Median 16,3 s gegen 1,0 s). Lässt man einzelne Bausteine weg, steigt die Summe ohne Symmetriebrechung auf 47 s, ohne Schnittbedingungen auf 47 s und ohne kompakte Erreichbarkeitsvariablen auf 40 s. Für die Startlösung, die Stufenbildung (zwei Stufen statt einer gewichteten Summe) und die feste Linienlänge zeigt diese Reihe keinen eindeutigen Zeitgewinn: ohne Startlösung 19 s, ohne feste Linienlänge 16 s, ohne Stufenbildung 29 s gegenüber 23 s mit allen Bausteinen, bei einem Lauf je Netz.

Grenzen und was die Messung zeigt

• Was sie belegt: den Vergleich beider Verfahren und ihren Abstand zum Optimum der vereinfachten Aufgabe auf erfundenen Netzen, als Mittel über 100 (Aufzählung) bzw. 10 (CP-SAT) Zufallsnetze je Zeile und mit den genannten Einstellungen. Die Beispielnetz-Werte sind Spannen über nur fünf Netze.
• Was sie nicht belegt: Aussagen über echte Netze. Es gibt keine Fahrzeiten, Takte, Wartezeiten beim Umsteigen, Fahrzeugkapazitäten, mehrstufigen Umstiege und kein Straßennetz. Entfernungen gehen nur in die Konstruktion der Heuristiken ein, nicht in die Bewertung. Ein Vergleich mit dem Mandl-Benchmark fehlt, weil dessen Zielgröße (mittlere Reisezeit auf einem Straßennetz) hier nicht vorkommt.
• Zwei Bezugsgrößen: In der Aufzählungstabelle ist das Optimum das der direkten Nachfrage allein. In der CP-SAT-Tabelle ist es die Schranke bei kleinster nicht erreichbarer Nachfrage. Die Abstände beider Tabellen sind deshalb nicht untereinander vergleichbar. Auch ein negativer Abstand ist möglich: In der Zeile 9, 2, 4 liegt das Nachfrage-Verfahren in der direkten Nachfrage im Mittel knapp über dem Optimum nach der Auswahlregel (um weniger als einen Punkt, rund zwei Standardfehler), weil dieses zuerst die unerreichbare Nachfrage minimiert. Je Netz ist das gemischt: nach Nachrechnung dieser Seite liegt es in etwas mehr als der Hälfte der Netze darüber, in gut einem Drittel darunter, in einigen gleich. Ein sicherer Effekt ist das nicht.
• Vergleichsbasis: Beide Verfahren sind einfach, ein stärkeres Verfahren (Lokalsuche, Linienpool mit Spaltenerzeugung) und ein Vergleich mit einer Heuristik aus der Literatur fehlen. Der Abstand zur Schranke hängt daher an diesen beiden Verfahren. Eine Schranke gibt es auch für die unerreichbare Nachfrage: In allen Zeilen der CP-SAT-Tabelle ist die erste Stufe (kleinste unerreichbare Nachfrage) in allen 10 Netzen bewiesen, offen bleibt nur die zweite (Messdatei, nicht in der Dokumentation).
• Optimalität: Bewiesen ist das Optimum nur in der Aufzählung bis etwa 10 Haltestellen und bei CP-SAT auf den kleinen Netzen und in den Zeilen mit „10 von 10“. Für 20 Haltestellen und 4 Linien (die Voreinstellung) beweist CP-SAT im Zeitlimit nichts. „Höchstens unter dem Optimum“ ist eine Obergrenze des Abstands, der wirkliche Abstand kann kleiner sein. Die Zeiten stammen von einem Entwicklungsrechner (8 Arbeiter, Zeitlimit 30 s, fester Zufallsstartwert des Lösers) und schwanken zwischen Läufen; bei den Modellbausteinen gilt nur ein Lauf je Netz.
• Heuristiken: Beide haben keine Gütegarantie. Das Sternnetz ist bewusst eine einfache Vergleichsbasis, und das Nachfrage-Verfahren ist eine Konstruktionsregel, kein Optimierer. Ob es mit anderen Regeln besser wäre, wurde nicht untersucht.
• Unerreichbare Nachfrage: \(U\) mischt Paare mit zwei oder mehr Umstiegen und Paare mit einer Haltestelle ohne Linie. Eine Stichprobe über 300 zufällige Reglerkombinationen (6 bis 40 Haltestellen, 2 bis 8 Linien, 3 bis 12 Haltestellen je Linie) fand Paare mit zwei oder mehr Umstiegen beim Nachfrage-Verfahren in 49 Fällen, im Extremfall mit 52 % der Nachfrage, beim Sternnetz nie. Die Zufallszahlen dieser Stichprobe sind nicht angegeben, sie ist hier nicht nachgerechnet. Eigene Stichproben mit anderen Zufallszahlen fanden solche Fälle in vergleichbarer Größenordnung, den Höchstwert von 52 % der Nachfrage aber nicht (Nachrechnung eines Prüfers, nicht der Demo).
• Kennzahl „mit einem Umstieg“: Sie ist exklusiv (ohne die direkten Paare). Eine Haltestelle ohne Linie macht alle ihre Paare unerreichbar, auch wenn das Netz sonst zusammenhängt.

Erweiterungen und Verweise

Nicht umgesetzt sind Taktfrequenzen und Fahrpläne (ein eigenes periodisches Planungsproblem), ein echtes Straßennetz, Fahrzeugkapazität und Umlaufplanung, eine Gewichtung mehrerer Ziele (Fahrgastzeit gegen Betreiberkosten) und ein metaheuristischer Ansatz wie ein genetischer Algorithmus. Verwandte Seiten:

• Abfahrtsminuten bei gegebenen Linien: Die Seite zum Taktfahrplan wählt, in welcher Minute jede Linie startet, und misst die Wartezeit der Umsteiger.
• Rufbus oder Linienbus: Die Seite Rufbus gegen Linienbus vergleicht beide Betriebsformen bei gleicher Qualität.
• Takt im Betrieb: Die Seite zum Bus-Bunching fragt, wie ein gleichmäßiger Takt auf einer Ringlinie im Betrieb auseinanderläuft.

Quellen

• Bussieck, M. R., Kreuzer, P., Zimmermann, U. T. (1997): Optimal lines for railway systems. European Journal of Operational Research (Direktreisenden-Modell, das die Zahl der Fahrgäste ohne Umstieg maximiert, dieselbe Zielgröße wie hier).
• Claessens, M. T., van Dijk, N. M., Zwaneveld, P. J. (1998): Cost optimal allocation of rail passenger lines. European Journal of Operational Research (Kostenminimierung statt Direktreisende).
• Borndörfer, R., Grötschel, M., Pfetsch, M. E. (2007): A column-generation approach to line planning in public transport. Transportation Science 41 (Linienplanung mit frei wählenden Fahrgästen).
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/transit-demo.

Die Dokumentation der Demo nennt keine Literatur. Bussieck et al. und Claessens et al. sind mit Zeitschrift und Zielgröße über Bibliografieeinträge bestätigt, die Inhalte nicht im Original geprüft. Borndörfer et al. steht aus dem Gedächtnis hier (nicht nachgeschlagen). Ein Vorlesungsskript von Borndörfer, Liebchen und Pfetsch (TU Berlin, 2006/07), das die Seite „ÖPNV und Fernverkehr optimieren“ nennt, war nicht auffindbar und ist deshalb nicht aufgeführt. Das Durchrechnen des Beispiels und die Folgerung für das Sternnetz sind Rechnungen dieser Seite und keine Messungen.