Personenverkehr

ÖPNV und Fernverkehr optimieren

Haltestellen, Gleise und Straßen stehen meist bereits fest, aber welche Linien sollen darauf verkehren, damit möglichst viele Fahrgäste ohne Umstieg ankommen? Das ist die Frage des Liniennetz-Designs im öffentlichen Personenverkehr und im Fernverkehr: ein eigenständiges Optimierungsproblem mit einer anderen Zielgröße als die Fracht-Tourenplanung: Servicequalität statt Kosten je Tour. Drei weitere Demos auf dieser Seite fragen nach dem Betrieb auf dem Netz: ab wann ein Rufbus gegen einen Linienbus lohnt, welcher Preis zu welchem Ziel gehört und wie lange ein gleichmäßiger Takt hält.

Zu meiner Erfahrung aus über acht Jahren bei einem großen internationalen Logistikunternehmen gehören vor allem Fracht- und Intralogistikprobleme (mehr unter Projekte & Erfahrung); diese Seite zeigt dieselbe Methodik (Konstruktionsheuristik, Bewertung, Vergleich) auf das ÖPNV-/Fernverkehrsfeld angewendet, methodische Vielseitigkeit statt jahrelange Nahverkehrs-Facherfahrung. Ich nutze selbst viel Bus und Bahn und kenne Umsteigezeiten, Anschlüsse und Verspätungen aus dem Alltag. Das hat meine Fragen an diese Demo geprägt, ersetzt aber keine Betriebserfahrung.

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.

Zuletzt aktualisiert:

Verständlich erklärt

Zum Nachlesen: erst einfach, dann fachlich

BUS-BUNCHING

Bus-Bunching verständlich erklärt

Warum Busse im Pulk kommen und was das Halten an Haltestellen bringt und kostet: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.

RUFBUS ODER LINIENBUS

Rufbus oder Linienbus verständlich erklärt

Wo der Rufbus gegen den Linienbus kippt und warum die Antwort am Qualitätsmaß hängt: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.

TARIFPLANUNG

Tarifplanung verständlich erklärt

Warum ein Zonentarif je nach Ziel andere Preise verlangt und was das falsche Ziel kostet: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.

Zwei Ebenen

Das Netz steht, das Liniennetz ist die Wahl

EBENE 1 — NETZ

Wo gibt es Haltestellen und Strecken?

Die physische Infrastruktur (Gleise, Straßen, Haltestellen) ist meist über Jahre gewachsen und wird hier als gegeben angenommen, nicht mitoptimiert.

EBENE 2 — LINIEN

Welche Linien fahren darauf?

Aus dem Netz wird eine überschaubare Zahl an Linien gebildet, die zusammen die Fahrgastnachfrage bedienen sollen, mit möglichst wenigen Umstiegen. Das ist die Entscheidung, um die es hier geht.

Verwandt, aber eine andere Ebene: Auf der Themenseite Netzwerkdesign optimieren geht es um Frachtnetze, bei denen zusätzlich die Verbindungen selbst (nicht nur die Linien darauf) zur Debatte stehen. Mehr zu den Verfahren dahinter, in der Reihe Konzepte: Ein reines Verbindungsnetz ohne Linien ist der Fall der Spannbaum-Linie, Kürzeste Wege zwischen Haltestellen die Kürzeste-Wege-Linie.

Kerngedanke

Direktverbindung oder Umsteigen?

Ein einfaches Sternnetz (alle Linien laufen über eine zentrale Haltestelle) ist schnell geplant und garantiert, dass jede Haltestelle erreichbar ist. Es verschenkt aber Direktverbindungen dort, wo viele Fahrgäste tatsächlich hinwollen. Eine nachfrage-optimierte Liniengenerierung baut Linien gezielt entlang starker Nachfrage-Korridore, mit dem Risiko, dass neue Linien nicht mehr zusammenhängend ans bestehende Netz anschließen, wenn diese Kopplung nicht ausdrücklich geprüft wird.

Fachliteratur

Wo die Demo in der Linienplanungs-Literatur steht

Die Aufgabe, aus einem gegebenen Netz Linien auszuwählen, heißt in der Operations-Research-Literatur Linienplanung (Line Planning); unter dem Namen Transit Network Design erscheinen dazu meist Metaheuristiken. Seit Ende der 1990er Jahre gibt es ganzzahlige Modelle: Das Direktreisenden-Modell von Bussieck, Kreuzer und Zimmermann (1997) maximiert die Zahl der Fahrgäste, die ohne Umstieg ankommen, also dieselbe Größe wie die Kennzahl dieser Demo. Claessens, van Dijk und Zwaneveld (1998) minimieren stattdessen die Kosten, und Schöbel und Scholl sowie Borndörfer, Grötschel und Pfetsch (2005) lassen die Fahrgäste ihre Wege im Netz frei wählen.

Diese Modelle sind schwer: Schon die Frage, ob bei vorgegebenen Frequenzschranken je Kante überhaupt ein zulässiger Linienplan existiert, ist NP-vollständig (Bussieck 1997), das Direktreisenden-Modell damit NP-schwer. Gelöst wurden sie mit Vorverarbeitung, gültigen Ungleichungen (Branch-and-Cut) und Spaltengenerierung.

Die Hauptansicht der Liniennetz-Demo ist keiner dieser exakten Ansätze. Sie nimmt eine feste Linienzahl und Linienlänge an und vergleicht zwei Konstruktionsverfahren miteinander. Daneben steht ein Tab mit dem Optimum derselben vereinfachten Aufgabe (keine Fahrzeiten, Takte oder Umstiegszeiten): Bis 10 Haltestellen werden alle Netze aufgezählt, bis 20 Haltestellen und 4 Linien rechnet ein CP-SAT-Modell (OR-Tools) mit Zeitlimit und Schranke. Auf den kleinen Instanzen liegt die nachfrage-optimierte Heuristik 0,8 bis 5,9 Prozentpunkte unter dem Optimum der Nachfrage ohne Umstieg, das Sternnetz 11,9 bis 34,3. Bei 20 Haltestellen und 4 Linien beweist CP-SAT im Zeitlimit kein Optimum; die Heuristik liegt dort höchstens 7,1 ± 0,2 Punkte darunter. Die Aussagen gelten für diese Modellannahmen und die erzeugten Zufallsnetze. Quelle der Einordnung: die Vorlesungsskripte „Ganzzahlige Optimierung im Öffentlichen Verkehr“ (Borndörfer, Liebchen, Pfetsch; TU Berlin und Zuse-Institut Berlin, Wintersemester 2006/07).

Nebenbedingungen

Was Liniennetz-Design in der Praxis komplex macht

N01 — NACHFRAGE

Woher wollen die Fahrgäste wohin?

Zwischen jedem Haltestellenpaar besteht eine eigene Nachfrage, oft ungleich verteilt und auf wenige Pendlerrouten konzentriert.

N02 — UMSTIEGE

Direkt, ein Umstieg oder unerreichbar?

Jeder zusätzliche Umstieg kostet Zeit und schreckt Fahrgäste ab; die entscheidende Kennzahl ist der Anteil der Nachfrage, der ohne oder mit höchstens einem Umstieg ankommt.

N03 — ZUSAMMENHANG

Bleibt das Netz verbunden?

Eine neue Linie, die nicht an das bestehende Netz anschließt, hilft niemandem. Diese Kopplung muss die Konstruktion aktiv sicherstellen, nicht nur hoffen.

Vorgehen

Wie ich Liniennetz-Design angehe

SCHRITT 1

Nachfrage und Netz abbilden

Haltestellen, Strecken und die Fahrgastnachfrage zwischen jedem Haltestellenpaar werden zu einem Modell zusammengeführt.

SCHRITT 2

Linien konstruieren, Zusammenhang prüfen

Eine Konstruktionsheuristik bildet Linien entlang der Nachfrage, mit einer expliziten Prüfung, dass jede neue Linie ans Netz anschließt.

SCHRITT 3

Servicequalität messen und vergleichen

Der Anteil direkt bzw. mit einem Umstieg erreichbarer Nachfrage wird gegen eine einfache Baseline (Sternnetz) gemessen und die Bewertungslogik an handkonstruierten Fällen und Zufallsinstanzen geprüft.

Umgesetzt in Scala oder Python, auf Wunsch als eigener Webservice mit API für Ihre Systeme (mehr unter Leistungen).

Weitere Fragen

Nicht nur das Liniennetz: drei Fragen aus dem Betrieb

BETRIEBSFORM — RUFBUS

Ab wann lohnt ein Rufbus?

Ein Linienbus fährt, ob jemand einsteigt oder nicht; ein Rufbus (Dial-a-Ride) fährt nur, wenn jemand ihn ruft. Bei gleicher mittlerer Wartezeit kippt es im 10 × 10-km-Gebiet bei rund 44 Anfragen pro Stunde; fordert man stattdessen eine mittlere Gesamtreisezeit von höchstens 30 Minuten, ist der Rufbus im gemessenen Bereich überall billiger. Der Kipppunkt gehört also zum gewählten Qualitätsmaß, nicht zu den beiden Betriebsformen. Kosten sind Fahrzeugstunden je Fahrgast; der Rufbus ist optimistisch modelliert (keine Leerfahrten-Neupositionierung, keine Fahrerpausen). Der Rufbus ist ein Pickup-and-Delivery-Problem, wie es auch der Patiententransport im Krankenhaus ist (mehr auf Tourenplanung optimieren).

TARIF — ZIELKONFLIKT

Welcher Preis ist der richtige?

Ein Zonentarif mit Einzel- und Monatskarte hat drei verschiedene Preise, je nachdem, ob man den Erlös, den Gewinn oder die Zahl der Fahrgäste maximiert. Auf 40 synthetischen Netzen bringt der Erlös-optimale Tarif 108,8 ± 0,2 % des heutigen Erlöses, verliert aber 22,5 Prozentpunkte der Fahrten. Der optimale Preis hängt an der Preisempfindlichkeit, einer Annahme, die sich nicht messen lässt: Bei 25 % niedrigerer Preisempfindlichkeit steigt das Preisniveau des Erlösmaximums um 25,0 %, bei 25 % höherer sinkt es um 14,4 %.

TAKT IM BETRIEB — BUS-BUNCHING

Wie lange hält ein gleichmäßiger Takt?

Auf einer Ringlinie ist ein gleichmäßiger Takt instabil: Kommt ein Bus später, warten an der nächsten Haltestelle mehr Fahrgäste, der Halt dauert länger, und der Bus dahinter holt auf. Bei 24 Haltestellen und 8 Bussen warten die Fahrgäste ohne Regelung im Mittel 14,6 ± 1,0 min statt 3,75 min; Halten an den Haltestellen senkt das auf 4,1 und 3,9 min und kostet 10 und 17 % Umlaufzeit. Bei sehr vielen oder voll besetzten Bussen schadet das Halten.

Die Zahlen gelten für die jeweiligen Modellannahmen (synthetische Netze, Logit-Wahl mit gesetzten Parametern, Ringlinie mit unabhängiger Fahrzeitstörung, je Messreihe 30 Zufalls-Seeds, beim Tarif 40 Netze) und zeigen Mechanismen, keine Prognose für ein reales Netz.

Gleiches Modell

Sechs ÖPNV-Fragen, die anderswo schon stehen

TAKT — ABFAHRTSMINUTEN

Linien stehen, Abfahrtsminuten fehlen noch

Das Liniennetz dieser Seite kommt ohne Taktfrequenz und Fahrplan aus. Welche Minute ein Fahrzeug an welcher Haltestelle abfährt, wählt der Taktfahrplan mit periodischen Bedingungen modulo T; die Verbindungsauskunft RAPTOR rechnet dagegen auf einem gegebenen Fahrplan. Beide stehen unter Schienenverkehr optimieren, RAPTOR auch in der Reihe Kürzeste Wege.

UMLAUF — ZUORDNUNG

Welches Fahrzeug fährt welche Fahrten?

Mit einem Depot ist der Fahrzeugumlauf ein Zuordnungs- bzw. Min-Cost-Flow-Problem und damit dieselbe Mathematik wie in den Reihen Matching und Netzwerkfluss; erst mit mehreren Depots, Fahrzeugtypen und Wartungsgrenzen wird er eigenständig.

DIENSTPLAN — SPALTENGENERIERUNG

Besatzungen und Schichten

Das Besatzungs-Pairing mit Lenk- und Ruhezeiten hat dieselbe Master-Struktur wie die Zuschnittoptimierung, nur die Preisfrage und das Regelwerk sind andere; es steht unter Schienenverkehr optimieren. Die Einsatzplanung nach Schichten und die freien Tage im Wochenmuster stehen unter Schichtplanung optimieren.

HALTESTELLEN — STANDORTWAHL

Wo eine Haltestelle hingehört

Die Demo nimmt die Haltestellen als gegeben. Wo wie viele Haltestellen liegen sollen, ist strukturell eine Standortwahl: Anlagen öffnen und Nachfrage zuordnen, nur dass jeder zusätzliche Halt hier auch den Fahrgästen an Bord Zeit kostet. Die Verfahren dazu stehen in der Reihe Standortplanung.

NETZAUSFALL — ROBUSTHEIT

Was passiert, wenn eine Haltestelle ausfällt?

Fällt ein Knoten aus, zerfällt ein Netz je nach Struktur schnell oder langsam. Die Robustheits-Demo vergleicht auf Graphen allgemein zufälligen Ausfall mit gezieltem Angriff und sucht die Perkolationsschwelle; das Liniennetz dieser Seite verwendet sie nicht. Ausprobieren: Robustheit (mehr in der Reihe Graphen und Netzwerke).

ELEKTROBUS — LADEN

Reichweite und Ladepunkte

Ein Teil der Frage steht schon: Die Ladestrategie-Demo lässt als Fahrzeug auch einen Bus wählen und entscheidet an jeder Schnellladesäule, wie viel geladen und wie lange vorgeheizt wird. Sie rechnet eine Strecke, keinen Umlauf. Ausprobieren: Ladestrategie: Elektrofahrzeug im Winter (mehr auf Tourenplanung optimieren).

Wo ein Verfahren aus einer anderen Demo stammt, steht es hier; wo nur die Kulisse neu wäre, steht es hier ebenfalls, damit Sie es unter dem Namen finden, unter dem Sie danach suchen. Die Ergebnisse einer Demo lassen sich aber nicht ungeprüft auf die andere übertragen: Das Netz, die Regeln und die Größenordnung entscheiden, wie viel welches Verfahren bringt.

Selbst ausprobieren

Vier Demos zum Thema

Die Demos laufen als eigenständige Anwendungen. In der ersten erzeugen Sie per Regler ein Haltestellennetz mit Nachfrage und sehen, wie sich die Verfahren unterscheiden; die weiteren fragen nach der Betriebsform (Rufbus oder Linienbus), dem Preis (Zonentarif) und dem Takt im Betrieb (Bus-Bunching).

LINIENNETZ-DESIGN

ÖPNV-Liniennetz-Optimierung

Legen Sie ein kleines Streckennetz mit Haltestellen und Nachfrage an. Die Anwendung vergleicht ein Sternnetz mit einer nachfrage-optimierten Liniengenerierung und zeigt, wie viele Fahrgäste ihr Ziel ohne Umsteigen erreichen. Auf kleinen Instanzen rechnet sie das exakte Optimum daneben (Aufzählung, CP-SAT) und zeigt, wie weit beide Verfahren davon entfernt liegen.

Demo starten →
RUFBUS

Rufbus oder Linienbus: wo kippt es?

Legen Sie ein Gebiet mit Haltepunkten und Fahrtwünschen an. Die Anwendung vergleicht einen Rufbus mit sieben Linienbus-Entwürfen bei gleicher Qualität und zeigt, dass der Kipppunkt (44 Anfragen pro Stunde im 10 × 10-km-Gebiet bei gleicher mittlerer Wartezeit) am Qualitätsmaß hängt: Bei gleicher mittlerer Gesamtreisezeit von höchstens 30 Minuten gibt es keinen.

Verständlich erklärt: erst für Einsteiger, dann für Fachleute

Demo starten →
TARIFPLANUNG

Tarifplanung: ein Preis, drei Ziele

Stellen Sie Netz, Preisempfindlichkeit, Kostenstruktur und Subvention ein. Die Anwendung berechnet für einen Zonentarif mit Einzel- und Monatskarte drei Preise für drei Ziele (Erlös, Gewinn, möglichst viele Fahrgäste) und zeigt, was das falsche Ziel kostet: Der Erlös-optimale Preis verliert im Mittel über 40 Netze 22,5 Prozentpunkte der Fahrten. Der optimale Preis hängt an der Preisempfindlichkeit, einer Annahme, die sich nicht messen lässt.

Verständlich erklärt: erst für Einsteiger, dann für Fachleute

Demo starten →
BUS-BUNCHING

Bus-Bunching: wie lange hält der Takt?

Fahren Sie eine Ringlinie mit 24 Haltestellen und 8 Bussen und sehen Sie im Zeit-Weg-Diagramm, wie aus kleinen Störungen Pulke werden. Die Anwendung vergleicht die Wartezeit ohne Regelung (14,6 ± 1,0 min statt 3,75 min beim gleichmäßigen Takt) mit Fahrplan- und Headway-Holding (4,1 und 3,9 min) und zeigt, wann das Halten schadet.

Verständlich erklärt: erst für Einsteiger, dann für Fachleute

Demo starten →

Liniennetze im Güterverkehr der Straße (Hauptlauf und Distributionsnetzwerk) und die Touren darauf stehen unter Tourenplanung optimieren. Auf dem Liniennetz baut der Taktfahrplan auf; Abfahrtsminuten, Trassenvergabe, Fahrzeitreserven, Fahrweise, Besatzungseinsatz und Zugbildung stehen unter Schienenverkehr optimieren.

Häufige Fragen

ÖPNV und Fernverkehr: kurze Antworten

Weitere Themen

Das könnte Sie auch interessieren

Tourenplanung optimieren

Nah- und Fernverkehr, Elektro-Lkw und der Anschluss an Netz, Hof und Lager: 7 Demos.

Netzwerkdesign optimieren

Warenflüsse und Linien gestalten: Der Fluss ist einfach, das Design ist schwer.

Schienenverkehr optimieren

Vom Takt bis zur Zugbildung: 7 Demos, jede mit einem gemessenen Befund.

Packen und Zuschnitt optimieren

Container, Paletten und Rollen: weniger Leerraum und Verschnitt, mit mathematischen Untergrenzen.

Lagerlogistik optimieren

Kommissionierung, Tor-Zuordnung, Umschlagpunkte und Wellenfreigabe als Gesamtsystem: 4 Demos.

Hof- und Yard-Management optimieren

Fahraufträge für Wechselbrücken und Ankunftstermine: Fristen halten, Leerfahrten sparen.

Hafenlogistik optimieren

Die ganze Prozesskette vom Kai bis zum Gate: 11 Demos, jede mit einem gemessenen Befund.

Seefracht optimieren

Die Prozesskette einer Reise vom Buchen bis zur Leercontainer-Rückführung: 7 Demos, jede mit einem gemessenen Befund.

Schichtplanung optimieren

Personalbedarf stundengenau decken, und wann eine einfache Rechnung schon exakt ist.

Clusteranalyse

Punkte ohne Vorgaben gruppieren: welches Verfahren zu Ihren Daten passt, von k-Means bis HDBSCAN.

Anomalie-Erkennung

Was aus dem Rahmen fällt, ohne dass vorher jemand sagt, wie es aussieht: neun Verfahren von der robusten Ellipse bis zum Autoencoder.

Bestandsmanagement optimieren

Nachschub, Lieferkette, Losgrößen und Sicherheitsbestand: 2 Demos, dazu vorab gerechnete Anwendungsfälle.

Luftfracht optimieren

ULD-Beladung, Beladeplan, Gefahrgut-Trennung und Buchungsannahme: 4 Demos, jede mit einem gemessenen Befund.

Nächster Schritt

Ihr Liniennetz, Ihre Fahrgäste?

Schildern Sie mir kurz, wie Ihr Netz heute aussieht und wo Fahrgäste umständlich umsteigen müssen. Ob sich eine Optimierung lohnt, lässt sich meist schon im kostenlosen Erstgespräch einschätzen.