Seit mehr als zwanzig Jahren kooperiert Prof. Dr. Karsten Weihe mit der Deutschen Bahn AG zu verschiedenen Forschungsfragen rund um das Thema Fahrplanauskunft, seit 2001 an der TU Darmstadt, von Anfang an unter fachlicher Begleitung von Wolfgang Sprick (datagon GmbH). Felix Gündling und Dr. Mathias Schnee bearbeiten konkret das hier vorgestellte Projekt, multimodale Reiseplanung. Weitere aktuelle Forschungsfragen sind Reisepläne, mit denen man mit hoher Wahrscheinlichkeit einen festen Termin am Zielort einhält, sowie spezielle Verbindungen in Tagesrandlagen. Alle diese Projekte werden durch die Deutsche Bahn finanziert. Gemeinsam haben wir begonnen, zu speziellen Aspekten von intermodaler Mobilität auch mit Anbietern anderer Verkehrsarten zu kooperieren.

 

Mit MOTIS haben wir 2002-2009 ein System zur multi-kriteriellen Reiseplanung entwickelt. Die von MOTIS vorgeschlagene Liste von Alternativen zu einer Reiseanfrage ist umfassend in dem Sinne, dass alle möglichen Kundenprofile abgedeckt sind, die sich aus verschiedenen Gewichtungen von Gesamtfahrzeit, Gesamtfahrpreis und Unbequemlichkeit (durch Umstiege) ergeben. Darauf aufbauend entwickeln wir seit einigen Jahren ein prototypisches Softwaresystem, das multi-kriterielle Reisepläne nunmehr aus sehr unterschiedlichen, nicht nur fahrplangebundenen Verkehrsmitteln zusammensetzt. Unser Fokus liegt auf dem komplexesten realen Fall: Bahnverbindungen plus öffentliche Nahverkehrsmittel wie Busse und Straßenbahnen bilden das Kernstück des Reiseplans, individuelle Verkehrsmittel aller Art werden am Anfang und Ende der Reise genutzt, um von Adresse X in Stadt A zur Starthaltestelle und von der Zielhaltestelle zu Adresse Y in Stadt B zu kommen.

Unser algorithmischer Ansatz basiert auf einer multi-kriteriellen Erweiterung des bekannten Algorithmus von Dijkstra zur Berechnung kürzester Pfade in Netzwerken, der im Grundstudium Informatik gelehrt wird und auch die Basis unter anderem für die Algorithmen in Navis für Kfz bildet. Natürlich reicht dieser Algorithmus in einfacher Lehrbuchform für das von uns ins Auge gefasste komplexe Szenario bei weitem nicht aus. Unser Suchalgorithmus schließt keine einzige Option von vornherein von der Suche aus. Auch während der eigentlichen Suche nach Reisealternativen ist das Vorgehen konservativ, das heißt, nur hochgradig aussichtslose Optionen werden von der weiteren Suche ausgeschlossen. Vielfältige, komplexe Entscheidungstechniken zur Steuerung des Suchprozesses und zur frühzeitigen Elimination aussichtsloser Optionen mussten von uns entwickelt und integriert werden, um einerseits Optionen nicht voreilig auszuschließen, andererseits die Zahl der zu berücksichtigenden Optionen - die während der Suche explosionsartig wächst - zu bändigen. Die Kriterien Fahrzeit und Bequemlichkeit sind dabei noch ein relativ geringes Problem, da sie sich in die Logik von multi-kritieriellen Kürzeste-Wege-Suchen einfügen. Insbesondere die Komplexität des Tarifsystems der Deutschen Bahn und der Spezialtarife beim Übergang in den öffentlichen Nahverkehr bringt immer wieder neue algorithmische Herausforderungen mit sich. Die traditionellen Individualverkehrsmittel sind in unserem System schon integriert und evaluiert: Fußwege, Fahrrad, Taxi, Fahrt mit dem eigenen Kfz sowie private Mitfahrgelegenheiten. Eine erste Basisversion für Parkplatzsuche in der näheren Umgebung von Haltestellen ist integriert. Aktuell arbeiten wir an der Integration von Sharing-Angeboten aller Art: Car Sharing, Bike Sharing, Dynamic Ride Sharing. Unser System ist offen angelegt, das heißt, auch jede weitere Art von Verkehr lässt sich mit vertretbarem Implementationsaufwand integrieren, sobald die notwendigen Daten für die Beauskunftung zur Verfügung stehen.

Alle diese Verkehrsmittel und deren Kombinationen lassen wir in unserem System in Konkurrenz zueinander antreten. Der Auskunftssuchende kann also vorgeben, welche Verkehrsmittel für ihn in Frage kommen. Er erhält dann für seine Anfrage eine Liste von Reiseplänen, in denen die Verkehrsmittel unterschiedlich kombiniert sein können. Wie oben erwähnt, bilden Bahnverbindungen plus öffentlicher Nahverkehr in unserem Konzept das Kernstück der Reiseplanung. Darin sind auch (sinnvolle) Fußwege zwischen zwei nahe beieinander liegenden Stationen eingeschlossen. Ebenso schließt dies schon jetzt Fälle ein wie etwa den Bus „Airliner“ zwischen Darmstadt Hauptbahnhof und Frankfurt (Main) Flughafen, dessen Nutzung inklusive Fußweg am Flughafen vom Terminal zum Fernbahnhof durchaus mitten in einer Bahnverbindung sinnvoll sein kann. Flüge und Fernbusse sowie jede weitere fahrplangebundene Verkehrsart können gleichermaßen integriert werden, letztendlich ist das nur eine Frage der Datenverfügbarkeit. Neuland betreten wir hingegen mit unserem Versuch, individuelle Verkehrsmittel von Taxi bis Car Sharing, aber auch kurze Wege mit eigenem, mitgeführtem Fahrrad oder unter Nutzung von Bike Sharing mitten in einer Bahnverbindung zuzulassen, von einer Haltestelle zu einer anderen, an der die Bahnfahrt fortgesetzt wird. Der Unterschied etwa zum Beispiel Airliner ist, dass Start- und Zielbahnhof bei individuellen Verkehrsmitteln nicht per Fahrplan vorgegeben, sondern frei im Umkreis wählbar sind, so dass eine quadratische Zahl von Kombinationen aus potentiellem Start- und Zielbahnhof zu berücksichtigen ist. Allerdings scheinen die Fälle, wo ein Intermezzo mit individuellen Verkehrsmitteln überhaupt sinnvoll sein könnte, eher überschaubar und leicht identifizierbar zu sein, so dass sie gesondert behandelt werden können. Insbesondere dürften sich die aufwändigsten Berechnungen aus der Suche in die Datenaufbereitung auslagern lassen, so dass die eigentliche Suche davon entlastet wird.

Zusammen mit der flinc AG arbeiten wir an der Integration von Dynamic Ride Sharing. Durch Umrouten des Fahrers können potentielle Mitfahrer an ihrer Startadresse abgeholt oder an ihrer Zieladresse abgesetzt werden. Auch Fahrten mit flinc mitten in einer Bahnverbindung, also von Bahnhof zu Bahnhof, erscheinen prinzipiell möglich. Die Zahl möglicher Reiseoptionen wächst hier allerdings in eine algorithmisch kaum mehr handhabbare Größenordnung, da (1) beliebig weit entfernte Bahnhöfe zu berücksichtigen sind und (2) beliebig weit entfernte flincFahrer potentiell in Frage kommen, weil auch großräumige Routenänderungen Sinn machen können (zum Beispiel kann ein Fahrer auf der Strecke von Heidelberg nach Stuttgart einen Passagier von Karlsruhe nach Pforzheim ohne ernsthaften zeitlichen Umweg mitnehmen, obwohl er ursprünglich über Heilbronn, nicht über Karlsruhe fahren wollte).

Was ist nun der Erkenntnisgewinn aus unserer bisherigen Arbeit an einer multimodalen Reiseauskunft? Es ist noch zu früh für abschließende Aussagen, dennoch kann ein erstes vorsichtiges, aber durchaus belastbares Fazit aus unserer bisherigen Arbeit schon gezogen werden.

Zunächst einmal lässt sich festhalten, dass multimodale Reiseauskunft mit den von uns entwickelten algorithmischen Techniken auf jeden Fall eine realistische Zukunftsperspektive ist. Die Antwortzeiten, die unser System in umfassenden, realistischen Simulationen zeigt, sind schon jetzt vielversprechend, obwohl etliche Möglichkeiten zur Beschleunigung der Suche noch gar nicht implementiert sind, vom Einsatz zukünftiger schnellerer Hardware gar nicht zu reden.

Aufgrund unserer bisherigen Erfahrungen mit der schrittweisen Integration immer neuer Verkehrsmittel und auf Basis unserer Vorabanalyse der geplanten weiteren Integrationsschritte sind wir zudem zuversichtlich, dass unser Integrationskonzept “skaliert”. Weitere Verkehrsmittel werden selbstverständlich neue algorithmische Fragestellungen mit sich bringen, aber diese werden lösbar sein, und die Antwortzeiten werden nicht exorbitant, sondern nur “linear” steigen.

Zusammenfassend sind schon viele Schritte auf dem Weg zu einer realistischen multimodalen Reiseauskunft erfolgreich zurückgelegt worden, es besteht aber weiterhin umfangreicher Forschungsbedarf, um die verschiedenen kleinen und großen algorithmischen Herausforderungen auf dem weiteren Weg zu meistern. Dazu ist allerdings zu sagen, dass wir einen integrierten Ansatz verfolgen, das heißt, alle Daten liegen unserem System vor. Wir sind sehr skeptisch, dass eine multimodale Reiseplanung ausreichend performant sein kann, wenn stattdessen Server der verschiedenen Anbieter während der Reiseplanung anzufragen sind. Multimodale Reiseplanung dürfte daher kaum realisierbar sein ohne eine Übereinkunft der verschiedenen Reiseanbieter, ihre Daten den Auskunftsbetreibern in geeigneter Form und mit adäquaten Nutzungs- und Lizensierungsbedingungen zu überlassen.

Die Deutsche Bahn als Verkehrsunternehmen und zukünftig zunehmend integrierter intermodaler Verkehrsdienstleister ist stark an derartigen Auskunftsverfahren interessiert und unterstützt daher die Forschung, um die Nutzbarkeit dieser Ansätze in algorithmischer und prozessualer Hinsicht laufend zu validieren.

Felix Gündling
Dr. Mathias Schnee
Wolfgang Sprick (datagon GmbH)
Prof. Dr. Karsten Weihe