Takt und Periodizität: ein Fahrplan, der sich jede Stunde wiederholt, erklärt
Stellen Sie sich vor: Zwei Buslinien treffen sich an einem Umsteigeknoten. Jede fährt jede Stunde zur selben Minute, den ganzen Tag lang. Wer von der einen in die andere umsteigt, wartet auf den Rest einer Uhr: Kommt er zehn Minuten nach der Abfahrt an, fährt der Anschluss erst in fünfzig Minuten. Verschiebt man eine der beiden Linien um ein paar Minuten, ändert sich die Wartezeit für alle, die dort umsteigen. Das verändert aber zugleich die Wartezeit an allen anderen Anschlüssen im Netz. Gibt es überhaupt einen Fahrplan, in dem alle Umsteiger kurz warten?
Das ist ein Taktfahrplan: Jedes Ereignis, also jede Abfahrt und jede Ankunft, wiederholt sich im festen Takt von hier 60 Minuten. Bedingungen wie Fahrzeit, Haltezeit, Wende und Umsteigen sind Zeitabstände zwischen zwei Ereignissen, und weil sich alles wiederholt, zählen diese Abstände modulo Takt: Eine Wartezeit von 70 Minuten ist eine Wartezeit von 10. Die Leitfrage dieser Linie lautet: Was erzwingt ein Takt schon vor jeder Optimierung, und wie findet und beweist man trotzdem einen guten?
Vier Stücke gehen dem nach. Sie handeln von der Frage, wann ein Plan aus Mindest- und Höchstabständen überhaupt möglich ist, vom Rest einer Uhr als Wartezeit des Umsteigers, von Kreisgleichungen, die dasselbe Modell besser rechnen lassen, und vom Betriebstag, an dem aus dem Plan eine Regel wird: warten oder abfahren. Wer erst einen Fahrplan sucht und misst, findet ihn in der Fall-Demo zum Taktfahrplan, dazu gibt es eine Erklärseite, die das Thema zuerst im Alltagsbild erzählt, ganz ohne Formeln.
Was diese Linie ist und was nicht: Alle Netze sind synthetisch und kommen aus einem Generator, die Zahlen gelten für diese Netze und die genannten Einstellungen. Die Demos sagen nichts über ein echtes Verkehrsnetz, einen echten Betreiber oder echte Fahrgäste.
In short: Interactive demos on periodic timetables: when a schedule of time lags is feasible, how long transfer passengers wait, why cycle equations solve the same model better, and whether a train should hold for a late feeder. Synthetic networks only.
Hintergrund zum Thema: Schienenverkehr · ÖPNV und Fernverkehr.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. So lesen Sie sie: Das Diagramm zeigt, wie die Stücke zusammenhängen. Jede Kachel darunter öffnet eine interaktive Demo, wo es eine gibt, mit einer Erklärseite für Einsteiger und Fachleute. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
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:
Welches Verfahren passt zu Ihrem Fall? Zum Entscheidungsbaum ↓
Zum Nachlesen: erst einfach, dann fachlich
Zeitabstände im Fahrplan verständlich erklärt
Warum ein Fahrplan schon an seinen Mindestzeiten scheitern kann, wenn Hin- und Rückanschluss derselben beiden Strecken verlangt werden, und was der Spielraum jedes Ereignisses sagt: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Uhr und Anschluss verständlich erklärt
Warum ein Umsteiger im Stundentakt auf den Rest einer Uhr wartet und warum Hin- und Rückweg zusammen mindestens eine feste Zahl von Minuten kosten, gleich wie die Buslinien gegeneinander verschoben sind: erst für Einsteiger am Zifferblatt, dann für Fachleute mit Formeln und Messwerten.
Warten oder abfahren verständlich erklärt
Warum ein verspäteter Zubringer den Betrieb vor eine Abwägung stellt: Soll der Folgezug warten oder abfahren, und wie nah kommt eine einfache Wartegrenze an die beste Entscheidung im Rückblick? Erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Die vier Stücke im Überblick
Der Graph zeigt, wie die vier Stücke zusammenhängen. Am Anfang stehen die Zeitabstände: Dort gilt jeder Plan nur einmal, und die Demo zeigt, wann er überhaupt möglich ist. Davon führt ein durchgezogener Pfeil zu Uhr und Anschluss, denn ein einmaliger Plan kennt nur „möglich“ oder „unmöglich“, im Takt wiederholt sich alles, und die Wartezeit der Umsteiger hängt am Rest einer Uhr. Von dort führt ein zweiter durchgezogener Pfeil zu den Kreisen und der Spannung: Wer Linienpaare versteht, sieht noch keine Kreise über drei und mehr Linien, und dort entscheidet, wie man das Modell aufschreibt.
Der Betriebstag steht zu den Kreisen im Kontrast und ist kein Fix: Er plant nicht den Takt, sondern prüft ihn, wenn ein Zubringer verspätet ist. Er ist ausdrücklich eine Gegenprobe, denn ein Takt mit kürzeren Planwartezeiten nimmt Puffer weg. Der kritische Pfad aus der Linie Abhängigkeiten führt als Baustein zu den Zeitabständen, das Bellman-Ford-Verfahren aus der Linie Kürzeste Wege ebenso. Weitere Fall-Demos grenzen sich ab: Die Taktfahrplan-Demo sucht und misst Fahrpläne am ganzen Netz, die Fahrzeitreserve-Demo legt Puffer auf einer einzelnen Strecke ohne Umsteiger fest.
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- Gegenstück: derselbe Zweck, andere Bauweise (kein Fix)
- übernimmt nur eine Idee
- Baustein aus einer anderen Linie
Durchgezogene Pfeile beheben eine Schwäche des Vorgängers, der gestrichelte Doppelpfeil ist ein Kontrast (derselbe Zweck, andere Bauweise), gepunktete Pfeile übernehmen nur eine Idee, graue gestrichelte Knoten sind Bausteine aus anderen Linien. Die Stücke lassen sich auch einzeln lesen.
Verwandt in anderen Linien
- Ordnung und Abhängigkeit — Der kritische Pfad rechnet früheste und späteste Lagen ohne Höchstabstände für Aufgaben eines Projekts. Die Demo Zeitabstände führt Höchstabstände ein und überträgt die Rechnung auf einen Fahrplan, in dem sie einen Plan unmöglich machen können.
- Kürzeste Wege — Das Bellman-Ford-Verfahren erkennt Kreise von negativer Länge. Die Demo Zeitabstände nutzt es auf dem Bedingungsgraphen eines Fahrplans, wo ein Kreis positiver Länge einen unmöglichen Plan bedeutet.
Zeitabstände: Wann ist ein Plan überhaupt möglich?
Sehen Sie, wann ein Fahrplan aus Mindest- und Höchstabständen überhaupt möglich ist: Jede Bedingung ist ein Abstand zwischen zwei Zeitpunkten, und ein Kreis, der sich nicht ausgeht, macht den Plan unmöglich. Verlangt man mit den vier wichtigsten Anschlüssen beide Richtungen, sind 38,3 % der Pläne schon ohne Höchstwartezeit unmöglich. Der Haken: Der Plan gilt nur einmal, und die Netze sind synthetisch.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Uhr und Anschluss: Wie lange wartet ein Umsteiger im Takt?
Verfolgen Sie, wie viel von der Wartezeit eines Umsteigers im Takt schon feststeht: Ein Hin- und Rückweg zwischen zwei Linien kostet bei fester Haltezeit mindestens eine feste Zahl von Minuten, wie auch immer die Linien verschoben sind. Alle Umstiege je Linienpaar zusammen erklären 95,3 % des Aufschlags eines gefundenen Takts. Der Haken: Gegen den Zufalls-Aufschlag gerechnet sind es nur 67,6 %.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Kreise und Spannung: Warum dasselbe Modell mit anderen Gleichungen besser rechnet
Sehen Sie, wie dasselbe Fahrplanmodell mit anderen Gleichungen besser rechnet: Statt je Ereignis eine Phase zu wählen, schreibt man je Kreis des Netzes eine Gleichung, und ein Spannbaum legt fest, welche Kreise gelten. Bei sechs Linien beweist HiGHS in 15 s mit einem Baum nach Spannweite 11,0 von 12 Netzen, mit dem Bogenmodell nur 3,3. Der Haken: Warum das so ist, bleibt ungeklärt.
Demo starten →Anschluss halten oder abfahren
Sehen Sie, wie der Betriebstag einen Takt auf die Probe stellt: Ist ein Zubringer verspätet, soll der Folgezug warten oder abfahren? Die Demo rechnet je Störtag das beste Vorgehen und misst, wie nah eine einfache Wartezeitregel kommt: Bei einem Verlust von 60 min je verpasstem Anschluss liegt die beste feste Regel 3,1 % über dem Optimum. Der Haken: Ein Takt mit kürzerer Planwartezeit macht mehr Anschlüsse kritisch.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Welches Stück passt zu meiner Frage?
Stellen Sie sich einen Fahrplan vor, der sich jede Stunde wiederholt. Was wollen Sie wissen? Der Baum führt von Ihrer Frage zum passenden Stück: Geht es um die Möglichkeit eines Plans, um die Wartezeit der Umsteiger, um die Rechnung dahinter oder um den Betriebstag?
Welches Stück passt zu meiner Frage?
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Mehrere Fragen können zugleich zutreffen; der Baum zeigt die Frage, die in den Demos zuerst gestellt wird. Alle Antworten gelten für die synthetischen Netze der Demos.
Weitere Linien in diesem Bereich
Exakte Suche
Bewiesen beste statt nur guter Lösungen: zwei Linien, Rucksack und Cutting Stock, von Branch & Bound bis Column Generation und Branch & Price.
Lineare Programmierung
Was steckt in einem LP-Löser? Elf Stücke vom Tableau-Simplex über Schattenpreise und Innere Punkte bis zum Crossover, alle von Grund auf geschrieben und gemessen.
Nichtlineare Optimierung
Wie findet man ein Minimum, wenn nichts linear ist? Acht Stücke vom ersten Schritt bergab über Krümmung und Nebenbedingungen bis zur Brücke ins Deep Learning, jedes mit gemessenem statt behauptetem Befund.
Konvexe und konische Optimierung
Wann ist ein Ergebnis beweisbar optimal, wie rechnet ein Löser mit Kegeln, und welcher Löser passt zu welcher Aufgabe? Sechzehn Stücke von der Lücke als Beweis bis zur Verfahrenswahl.
Anordnen: relaxieren und runden
Wie weit unter dem Besten liegt die beste Zahl, die man beweisen kann, und wie rundet man eine Lockerung zurück auf eine Anordnung? Fünfzehn Stücke von der Mini-Halle bis zur Verfahrenswahl.
Populations-Metaheuristiken
Wie durchsucht eine ganze Population den Lösungsraum? Elf Verfahren von der Kreuzung über Kovarianzmatrizen bis zu Pheromonspuren, jedes mit seiner gemessenen Grenze.
Trajektorien-Metaheuristiken
Wie kommt eine einzelne Lösung über ihr erstes lokales Optimum hinaus? Zwölf Verfahren von Verschlechterungen akzeptieren bis Destroy-and-Repair, jedes mit seiner gemessenen Grenze.
Heuristische Baumsuche
Was bleibt von der Suche, wenn man das Optimum nicht abwarten kann? Acht Verfahren von der gierigen Suche bis Monte Carlo Tree Search, jedes mit seiner gemessenen Grenze.
Novelty Search und Quality-Diversity
Ein Hof-Roboter im täuschenden Labyrinth, zwölf Stücke: von der Sackgasse der Fitness über Novelty Search und MAP-Elites bis zu Go-Explore, Routing und POET.
Standortplanung
Welche Standorte eröffnen, wenn jeder Kunde zum nächsten offenen geht? Sechs Stücke von der einfachen Fixkosten-Entscheidung über Kapazität, Maximum statt Summe und Lagerbestand bis zum Wettbewerb zweier Spieler und zum Hub mit Rabatt.
Klassische Scheduling-Theorie
Ein wachsendes Beispiel von einer Maschine bis zum allgemeinen Ressourcenmodell: elf Stücke, jedes hebt genau eine Annahme des vorigen auf.
Optimierung unter Unsicherheit
Eine Kapazität, die vor der unbekannten Nachfrage gewählt wird, sechs Stücke: vom Wert der Information über Stichprobe, CVaR, Robustheit und Garantie bis zur rollierenden Planung.
Bayessche Optimierung und Gauß-Prozesse
Eine teure Simulation, sieben Stücke: vom Gauß-Prozess und der erwarteten Verbesserung über Rauschen und Nebenbedingungen bis zu hohen Dimensionen, parallelen Läufen und mehreren Genauigkeiten.
Online-Algorithmen
Wie man entscheidet, bevor die Zukunft bekannt ist, und was die Garantie für den schlimmsten Fall im Betrieb kostet: sieben Stücke von Mieten oder Kaufen bis zu Vorhersagen.
Zielfunktionsdesign
Was ändert sich, wenn nur das Ziel wechselt? Vierzehn Stücke von der Wahl zwischen Summe und Maximum über Fairness und Ersatzziele bis zur Frage, wie man ein Ziel vor dem Einsatz testet.
Bestandspolitiken
Wie viel bestellen, wenn jede Periode zählt? Sieben Demos mit demselben Artikel: von der Rückwärtsrechnung über Fixkosten, Lieferzeit, Verderb und zwei Lager bis zur Frage, welche einfache Regel reicht.
Komplexitätsklassen
Was sagt es aus, wenn ein Problem als NP-schwer gilt, und welcher Ausweg passt zu welchem Grund der Härte? Zehn Stücke über Reduktionen, typische Instanzen, große Zahlen, Garantien, Parameter, Zufall, Zählen, Spiele und lokale Optima.
SAT und Constraint Programming
Wie merkt sich ein Löser, warum eine Sackgasse eine war? Sechzehn Stücke vom Konfliktlernen über Beweise, Zähler und Symmetrie bis zu Mengen- und Maschinenschlüssen, lokaler Suche und der Wahl der Modellwelt.
Packen: Reihenfolge und Platzierungsregel
Wie packt man Pakete, Rechtecke und Quader in wenige Behälter, und wie nah am Besten liegt eine einfache Regel? Vierzehn Stücke von der Sortierung bis zur Verfahrenswahl.
Umstauen: Untergrenze und Suche
Wie viele Container müssen mindestens umgestapelt werden, und wann lohnt sich die Suche nach dem Besten? Fünfzehn Stücke von der einfachen Regel bis zur Verfahrenswahl.
Tourenbildung: eine Reihenfolge, optimal zerlegt
Wie bildet man Touren aus einer einzigen Reihenfolge aller Kunden, und wann schlagen Savings, Sweep oder Suche sie? Fünfzehn Demos von der Aufzählung bis zur Verfahrenswahl.
Ressourcenwege und Spaltenerzeugung
Wie findet man unter unüberschaubar vielen möglichen Touren die mit dem größten Nutzen, wenn jede Zeit- und Lastgrenzen einhalten muss? Dreizehn Demos vom Weg mit Grenze bis zur Wahl des Verfahrens.