Routenoptimierung

Welches Problem löst sie?

In einem Shuttle-Betrieb greifen die Fragen ineinander. Wie viele Fahrzeuge fahren hinaus? Welcher Fahrgast steigt in welches Fahrzeug? Wo liegen die Haltestellen? In welcher Reihenfolge werden sie bedient? Jede Antwort verändert die übrigen. Eine Haltestelle um 200 Meter zu verschieben kann einen Fahrgast auf ein anderes Fahrzeug verlagern — und dieses dann über die Kapazität bringen.

Die klassischen Tourenprobleme aus dem Lehrbuch behandeln nur eine dieser Fragen, und zwar in vereinfachter Form: ein einzelnes Fahrzeug, feste Kapazität, ein unveränderliches Straßennetz, bekannte und konstante Fahrzeiten. Die Praxis sieht anders aus. Ein Shuttle-Plan muss bestehen, während sich die Fahrgastliste wöchentlich ändert, der Verkehr stundenweise schwankt und Fahrzeuge kurzfristig getauscht werden.

Die Optimierung, die in der Praxis trägt, ist deshalb nicht jene, die ein einzelnes Problem perfekt löst, sondern jene, die diese Fragen gemeinsam und anhand realer Daten abwägt.

• Zuordnung der Fahrgäste zu Haltestellen und Platzierung der Haltestellen selbst
• Bestimmung der Fahrzeuganzahl und der Fahrgastgruppe je Fahrzeug
• Ableitung der Reihenfolge der Haltestellen
• Gleichzeitige Einhaltung von Kapazität, maximaler Fahrzeit und Schichtzeiten

Routenoptimierung im Mitarbeiterverkehr

Im Mitarbeiterverkehr sind Abfahrts- und Ankunftszeiten durch die Schicht vorgegeben und nicht verhandelbar. Fahrgäste und Adressen sind bekannt. Die eigentliche Frage lautet: mit wie vielen Fahrzeugen und welchen Haltestellen kommen alle pünktlich zur Schicht?

Die Optimierung weist jede Person der nächstgelegenen Haltestelle innerhalb der Fußweggrenze zu, führt nahe beieinanderliegende Haltestellen zusammen und baut die feste Linie mit den wenigsten Fahrzeugen. Weniger Haltestellen verkürzen die Fahrzeit, verlängern aber den Fußweg; werden beide Vorgaben nicht gemeinsam ausbalanciert, kommt der Plan entweder zu spät oder erzeugt Beschwerden.

Routenoptimierung im Schülerverkehr

Im Schülerverkehr verschiebt sich das Bild: Schülerinnen und Schüler werden an der Tür abgeholt, das Zusammenlegen von Haltestellen ist meist nicht möglich, und die maximale Fahrzeit ist deutlich enger gefasst. Die Toleranz der Eltern ist gering.

Hier baut die Optimierung Tür-zu-Tür-Routen, rechnet von der Schulanfangszeit rückwärts und hält die Zeit jedes Kindes im Fahrzeug innerhalb der Grenze. Können Kinder verschiedener Schulen desselben Gebiets gemeinsame Fahrzeuge nutzen, sinkt die Zahl der Fahrzeuge im Verkehr merklich.

Warum die Luftlinie in die Irre führt

Die Luftlinie zwischen zwei Punkten ist leicht zu berechnen und falsch. Fahrzeuge fahren nicht geradeaus: Einbahnstraßen, getrennte Fahrbahnen, Abbiegeverbote, Brücken und Knotenpunkte verlängern die tatsächliche Strecke. Innerorts liegt die reale Straßendistanz deutlich über der Luftlinie, und der Abstand ist nicht auf jeder Route gleich groß.

Eine saubere Optimierung rechnet auf dem realen Straßennetz, mit Abbiegebeschränkungen und historischen Verkehrsdaten, die sich nach Tageszeit unterscheiden. Eine um 07:30 Uhr gültige Fahrzeit gilt um 10:00 Uhr nicht mehr; wird ein Plan um eine Schichtzeit herum gebaut, müssen auch die verwendeten Fahrzeiten zu dieser Stunde gehören.

Der Ansatz von vitaRoute

Die Routing-Engine von vitaRoute ist ein auf bestärkendem Lernen beruhendes Modell für die Shuttle-Routenplanung, das vitaRoute im Rahmen eines TÜBİTAK-geförderten F&E-Projekts entwickelt hat. Sie wägt Randbedingungen gemeinsam statt nacheinander ab und lernt aus jeder Optimierung auf der Plattform, aus jeder manuellen Korrektur und aus jeder tatsächlich gefahrenen Tour.

In der Praxis heißt das: Der Plan speist sich aus der Historie Ihres eigenen Betriebs statt aus einer festen Formel. Zwei Kunden in derselben Stadt erhalten selbst bei gleichen Randbedingungen nicht denselben Plan.

• Fußweg- und Steigungsgrenze — 300 Meter bergauf sind nicht 300 Meter in der Ebene
• Gemischte Flotte — Fahrzeuge unterschiedlicher Kapazität in einem Plan gemeinsam genutzt
• Gesperrte Linien — Routen, die unverändert bleiben sollen, werden exakt beibehalten
• Zonenregeln — Vorgaben für bestimmte Stadtteile oder Standorte
• Reales Straßennetz und tageszeitabhängige historische Verkehrsdaten