Alleinstellungsmerkmale MOTIS

MOTIS ist ein Fahrplan- und Mobilitätsauskunftssystem.

Eine einführende Darstellung durch das Fachgebiet Algorithmik der Technischen Universität Darmstadt findet sich auf https://www.algo.informatik.tu-darmstadt.de/#motis.

Die nachstehenden Kapitel stellen Alleinstellungsmerkmale dar, die zumindest nach unserem Wissen bei anderen Systemen nicht zu finden sind.

Mathematische Optimalität garantiert

Die Grundlagen der marktgängigen kommerziellen Systeme bei Bahnen und Verkehrsverbünden wurden in den 80er Jahren gelegt. Wer sich noch erinnert, es war die Zeit des Intel 286 Prozessors und mit dem 386 kam zum ersten Mal ein Prozessor für PC-Systeme auf den Markt, mit dem man auch „richtige“ Betriebssysteme unterstützen konnte. Optimierungsalgorithmen wie eine Fahrplanauskunft kämpften damals massiv mit dem Problem langer und in den Anfängen inakzeptabler Rechenzeiten. Dazu kommt, dass bei Algorithmen dieser Art die Rechenzeit mit dem Datenumfang nicht nur linear, sondern stärker steigt. Also war man kreativ und erfand Heuristiken, welche das Problem der Rechenzeit beherrschbar machten. Bei nach wie vor guter Qualität. Die Ergebnisse waren nach wie vor von guter Qualität, aber ein optimales Ergebnis konnte nicht mehr garantiert werden.

In der Beschäftigung mit einem solchen kommerziellen System für einen großen deutschen Mobilitätsdienstleister stellten wir insbesondere bei funktionalen Weiterentwicklungen oder deutlichen Erweiterungen des Umfangs der Fahrplandaten fest, dass die Einstellung der vielen Parameter zur Steuerung der diversen Heuristiken immer wieder zu einem Geduldsspiel wurde. Grund: weil Interdependenzen einfache Regeln wie "Parameter numerisch vergrößern führt zu besserer Qualität zu Lasten der Performance" außer Kraft setzen.

Bei einer weiteren großen funktionalen Erweiterung der Fahrplanauskunft dieses Kunden entstand daher die Idee, eine weitere Fahrplanauskunft nach dem Prinzip der diversitären Redundanz zu entwickeln. Dieser Ansatz wurde gewählt, weil sich die Optimalität der Ergebnisse eines komplexen Systems wie einer auf heuristischen Ansätzen beruhenden Fahrplanauskunft nicht beweisen lässt. Das zu schaffende neue System sollte daher auf Heuristiken verzichten und vor allem der Qualitätssicherung des kommerziellen Systems dienen und dessen Verbesserungspotenziale aufzeigen.

Dabei war eine der Grundvorgaben, dass durch Verzicht auf Heuristiken die mathematische Optimalität der Ergebnisse garantiert sein sollte. Das führte auch noch am Beginn des 21. Jahrhunderts zu Rechenzeiten, die einen produktiven Einsatz zur Beauskunftung von Reisenden aus Kostengründen unmöglich machten. Aber das war im Rahmen eines reinen Qualitätssicherungssystems ja auch nicht erforderlich.

Damals galt und bis in die heutige Zeit gilt weitestgehend immer noch das Mooresche Gesetz. Das heißt, die mathematische Optimalität kostet nach wie vor vergleichsweise viel Rechenzeit, aber dies ist im kommerziellen Sinne nicht mehr wirklich relevant, weil sich zwischenzeitlich das Preis-/Leistungsverhältnis bei Rechnern drastisch verändert hat.

Aber auch bei MOTIS wurde viel zu Beschleunigungstechniken geforscht, auch Heuristiken wurden mit gutem Erfolg erprobt. Der Vorteil von MOTIS an dieser Stelle ist aber, dass die Qualität eines so durch Heuristiken beschleunigten MOTIS durch ein die Optimalität weiterhin garantierendes (unbeschleunigtes) MOTIS überprüft werden konnte. Damit ist die diversitäre Redundanz zur Qualitätsicherung eines "schnellen" MOTIS durch MOTIS selbst gegeben.

Multikriterielle Suche

Mitte der 90er Jahre waren kommerzielle Fahrplanauskunftssysteme noch ausschließlich auf die Suche von zeitschnellsten Verbindungen ausgelegt. Es zeigte sich mit der Verbreitung der elektronischen Fahrplanauskunft auch als Basis für das Ticketing bei Anbietern und in Reisebüros schnell, dass diese Form der Optimierung allein die Bedürfnisse der Kunden nicht erfüllt.

So wurden z.B. zu zeitschnellen Verbindungen keine Alternativen mit weniger Umstiegen ausgewiesen, auch wenn diese nur wenige Minuten mehr Reisezeit benötigten. Die ausgewiesenen Verbindungen waren also gerade für Menschen mit Mobilitätseinschränkungen, Reisende mit Kleinkindern oder großem Gepäck unnötig beschwerlich. Das weckte den Wunsch nach "bequemen" Reisealternativen, also Alternativen mit weniger Umstiegen, bei denen die Reisezeit nicht viel länger wird. Und dann gab es natürlich immer das Thema "gibt es nicht auch preiswertere Alternativen?".

Dies führte dazu, dass im bedienten Verkauf von Tickets mit oft vorhandenem Verkehrswissen oder schlicht nach Methode "trial and error" diverse Anfrageparameter modifiziert wurden, um evtl. zur Beauskunftung preiswerter Reisealternativen zu gelangen. Klassisch ist dabei die Anfrage "ohne ICE/IC", weil gerade auf mittleren Distanzen bei Verzicht auf den teureren Fernverkehr oft preiswertere Verbindungen gefunden werden konnten. Und das mit nur geringfügiger Verlängerung der Reisezeit. 

Aber Reisende ziehen auch noch andere Kriterien zur Auswahl von Verbindungen heran. Wie voll ist der Zug? Hat er Air Condition? Hat er WLAN? Gibt es ein Restaurant/Bistro? Kann man Sitzplätze reservieren? Gibt es Ruhebereiche? Wie sicher klappen meine Anschlüsse? Wie touristisch interessant ist die vorbeiziehende Landschaft?

Aus diesem Grunde wurde MOTIS so ausgelegt, dass prinzipiell eine beliebige Zahl von Kriterien bei der Suche berücksichtigt werden kann. Stellt man sich jede Reisealternative als einen Vektor vor, der die verschiedenen Kriterien darstellt, dann kann man eine Verbindung z.B. als Vektor mit den Komponenten Reisezeit, Anzahl Umstiege und Preis darstellen. Bei der Ermittlung von auszugebenden Alternativen gilt nun das Grundprinzip, dass eine Alternative eine andere nur dann verdrängt, wenn sie in keinem Kriterium schlechter und in mindestens einem Kriterium besser als die Alternative ist. Diese Grundprinzip muss natürlich durch die zeitliche Lage der Alternativen und die absoluten numerischen Größen verfeinert werden, z.B. wird niemand eine Reisezeitverlängerung von 2 auf 3 Stunden in Kauf nehmen, nur um einen Umstieg zu sparen. Für das Verständnis ist aber das Grundprinzip wichtig und dass relativ einfach weitere Kriterien durch MOTIS berücksichtigt werden können

Eine praktische Bedeutung erhielt der multikriterielle Ansatz in Experimenten zur Verbesserung der Anfang des 21. Jahrhunderts noch stark verbesserungswürdigen Nachtzugauskunft. Der Grund liegt darin, dass Nachtzüge oft und Fähren fast immer deutlich langsamer sind als reguläre Reisezüge. Das kommerziellen Systemen zugrunde liegende Prinzip zur Beauskunftung zeitschnellster Verbindungen konnte daher langsamere Verbindungen mit Nachtzügen und Fähren nicht finden.

Der Grund für die Nutzung von Nachtzügen und z.B. Ostseefähren ist aber oft, dass man an Bord ununterbrochen mehrere Stunden am Stück schlafen kann. Und dabei verliert die Reisegeschwindigkeit an Bedeutung. Für MOTIS wurde daher ein Modul "Nachtzugauskunft" entwickelt, bei der Verbindungen mit ununterbrochener Schlafmöglichkeit durch andere Alternativen nicht verdrängt wurden, solange die Schlafzeit z.B. mindestens 6 Stunden betrug. Die Möglichkeit zu schlafen wurde damit zu einem völlig neuen Kriterium bei der Verbindungssuche.

Denkbar wäre analog eine Reiseauskunft mit einer Suche für ganz Europa, die auch Flüge datenseitig integriert. Da bei Reisen ab ca. 600 km Reiseketten mit Fluganteilen n in der Regel schneller sind als z.B. reine Zugverbindungen, könnte man durch Verdrängungsregeln erreichen, dass Flugverbindungen Verbindungen ohne Flug nur dann verdrängen, wenn diese mindestens eine Stunde schneller sind. Man hätte durch die multikriterielle Suche aber immer noch eine optimale Kombination von landgebundenem Verkehr und der Luftfahrt. Eine Funktionalität, die auch heute in kommerziellen Auskunftssystemen mit garantierter mathematischer Optimalität gemäß den vorgegebenen Kriterien nach wie vor nicht vorhanden ist.

Intermodalität mit Individualverkehr

Seit 2013 wird MOTIS um die Funktionalität erweitert, neben dem öffentlichen, fahrplangebundenen Verkehr im Vor- und Nachlauf auch beliebige andere Möglichkeiten (z.B. Fahrrad, Auto, Taxi, längere Fußwege usw.) zu unterstützen. Durch den integrierten algo­rithmischen Ansatz, die Verbindungen alle im selben, den gesamten Datenbestand umfassenden Netzwerk (statt in einem verteilten System) zu berechnen, kann auch hier die Optimalität der Verbindungen bei adäquaten Antwort­zeiten garantiert werden.

Die heute gebräuchlichen Auskunftssysteme unterstützen bislang nur Fußwege begrenzten Umfangs, um im Rahmen einer "Suche von Haus zu Haus" mit Vorgabe von Adressen für Start und Ziel ein Fußweg-Routing zu nahe gelegenen Haltestellen vornehmen zu können.

MOTIS hebt diese räumlichen Begrenzungen auf und erlaubt z.B. auch typische Rad-Distanzen von 5 km oder gerade im ländlichen Raum auch Fahrten mit dem Pkw von mehr als 10 km zu Park + Ride Parkplätzen, was zu einer deutlichen Verbesserung bei der Beauskunftung intermodaler Reiseketten führt. Ebenfalls unterstützt wird Kiss-and-Ride, also das Bringen mit dem Pkw zu größeren Bahnhöfen, was gerade am Wochenende oder in Tagesrandlagen von Bedeutung ist. 

In einer Kooperation mit flinc und der Deutschen Bahn wurde MOTIS in 2014 prototypisch erweitert, um Verbindungen zu beauskunften, die neben dem öffentlichen Verkehr und dem Individual­verkehr auch dynamische Mitfahr­angebote beinhalten. Diese können im Vor- und Nachlauf, aber auch für Teilstrecken von Bahnhof zu Bahnhof innerhalb des Mitnahmeangebots genutzt werden.

Die vielversprechenden Ergebnisse des Proof of Concept konnten dann in der Zusammenarbeit mit flinc nicht weiter ausgebaut werden, weil flinc im September 2017 von der Daimler AG übernommen wurde und die öffentliche Plattform zum Ende des gleichen Jahres geschlossen wurde.

Unseres Wissens nach ist dies der erste integrierte Lösungsansatz zur Beauskunftung intermodaler Verbindungen als Kombination von fahrplangebundenen öffentlichen Verkehren mit Ridesharing-Angeboten

Intermodalität mit Bedarfsverkehren

Erste Überlegungen haben es als wahrscheinlich erscheinen lassen, dass Lösungen wie die für die Integration von flinc-Mitfahrangeboten sich in erweiterter Form auch für die Einbindung von (ggf. autonom agierenden) Bedarfs­verkehren eignen. Vorteil des integrierten Ansatzes von MOTIS gegenüber anderen Ansätzen ist, dass diese Verkehre sofort in Reise­ketten mit beliebigen anderen Verkehren kombinierbar sind. Dabei beruhen Fahrzeiten nicht fahrplangebundener Verkehre auf Erfahrungswerten, wie bei Navigationssystemen für den Einsatz im Straßenverkehr. Dieser integrierte Ansatz erlaubt weiter sichere Aussagen zur Qualität ermittelter Reiseketten bei gegenüber verteilten (vernetzten) Systemen deutlich niedrigeren Antwortzeiten.

Weitere MOTIS-orientierte Forschung

Aktuell (April 2019) befinden sich im Fachbereich Informatik Arbeitsgebiet Algorithmik geleitet von Prof. Dr. Karsten Weihe nachstehende Dissertationen mit unterschiedlichen Fertigstellungsgraden in Bearbeitung:

• Intermodale Echtzeit-Verbindungssuche
• Prognose von Reisendenströmen (in Zusammenarbeit mit DB Fernverkehr)
• Optimale Reisendenstromlenkung (Strategien im Störungsfall)

MOTIS hat eine lange Historie in der Forschung und dabei etliche Leistungsmerkmale entwickelt, die nach wie vor als innovativ anzusehen sind. Diese möchte wir gerne mit Partnern zu einem Produktivsystem weiterentwickeln.

Insbesondere im Kontext "intermodal" in Verbindung mit z.B. On-Demand-Angeboten würden wir gerne aktuelle Forschungsansätze mit interessierten Partner auch im Rahmen von Forschungsprojekten weiterentwickeln.