Millionen Menschen nutzen täglich öffentliche Verkehrsmittel. Die Deutsche Bahn AG beförderte in den Jahren 2007 und 2008 jeweils über 1,4 Milliarden Passagiere, welche pro Jahr über 70 Milliarden Personenkilometer zurücklegteni [Deu09]. Herkömmliche elektronische Fahrplanauskunftssysteme berechnen mögliche Verbindungen für Kunden. Der Anbieter der Auskunft für die Deutsche Bahn AG, HaCon,ii gibt an, mehr als 20 Millionen Verbindungen täglich zu berechnen [Haf09]. Sie werden bislang unter Angabe der Abfahrts- und Ankunftszeit, der Reisezeit, der Anzahl der Umstiege und des Preises dem Nutzer präsentiert. Unter den angebotenen Alternativen wählt der Kunde nach individuellen Gesichtspunkten, basierend auf zeitlichen Rahmenbedingungen, Komfort und Budget. Da diese Entscheidung auf natürliche Weise multikriteriell abläuft, sollten Fahrplanauskünfte auch nach multikriteriellen Ansätzen berechnet werden, um möglichst ”attraktive Alternativen” anzubieten. Wir haben das Konzept advanced Pareto Optimalität als eine Weiterentwicklung des klassischen Pareto-Prinzips eingeführt. Unser Konzept liefert nun mehr geeignete Verbindungen und unterdrückt dabei gleichzeitig unpassende Lösungen des klassischen Ansatzes, um der Zielvorstellung attraktiver Verbindungen für alle potenziellen Kunden gerecht zu werden. Die realistische Modellierung der Suche nach Verbindungen auf Bahnfahrplänen führt zu Kürzeste-Wege-Algorithmen. Um Kundenanfragen in wenigen Millisekunden beantworten zu können, werden schnelle Algorithmen benötigt, da die Modellierung des Fahrplans zu großen Graphen mit mehreren hunderttausend Knoten und Kanten führt. Diese Graphen sind entweder zeit-expandiert oder zeit-abhängig, um die zeitliche Komponente des Fahrplans abzubilden. Im Gegensatz zu den meisten wissenschaftlichen Arbeiten zum Thema haben wir ein vollkommen realistisches Modell ohne jegliche vereinfachenden Annahmen entwickelt. Dazu haben wir zum einen das zeit-expandierte Graphenmodell erweitert, um Fahrpläne wirklichkeitsgetreu und ohne Einschränkungen abzubilden, und zum anderen einen geeigneten Algorithmus entworfen, eine Generalisierung von Dijkstra’s Kürzeste-Wege-Algorithmus. Auf dieser Basis beruht unser multikriterielles Fahrplanauskunftssystem MOTIS (Multi Objective Traffic Information System). Es berechnet nach dem Prinzip der advanced Pareto Optimalität gültige Verbindungen, für die ein Kunde am Bahnschalter ein reguläres Ticket erwerben kann. Darüber hinaus haben wir das zeit-abhängige Modell erforscht und einen ebenfalls vollkommen realistischen Prototypen auf Grundlage dieses Graphenmodells entwickelt. Außerdem haben wir einige zusätzliche Kriterien untersucht, die bis dato nicht berücksichtigt worden sind, wie zum Beispiel Angebotspreise (d.h. reduzierte Tickets zu besonderen Konditionen, z.B. nach der Verfügbarkeit von Kontingenten) oder die Zuverlässigkeit von Umstiegen, als ein Maß zur Bewertung derWahrscheinlichkeit, alle Anschlusszüge einer Verbindung auch tatsächlich erreichen zu können (interessant bei Zugverspätungen). Zusätzlich gelang es uns zwei unterschiedliche Herangehensweisen für die Suche nach Nachtzugverbindungen zu entwerfen. In diesem Anwendungsfall geht es darum, ausreichend lange Teilstrecken in Nachtzügen ohne hinderliche Umstiege zu verbringen. Unsere Algorithmen, die diese Kriterien berücksichtigen, sind schnell und ermitteln ansprechende Alternativen. Die Suche unter mehreren Zielkriterien auf zeit-expandierten Graphen ist deutlich anspruchsvoller als z.B. auf statischen Straßengraphen. Wir haben verschiedene existierende Beschleunigungstechniken untersucht und geeignete an unser Szenario angepasst, sowie neue Techniken entwickelt. In einer ausführlichen Studie diskutieren wir sowohl die Kosten der Kriterien im Einzelnen und in Kombination, als auch den Effekt unterschiedlicher Parametrisierungen und den Einfluss der Beschleunigungstechniken. Damit konnten wir durchschnittliche Laufzeiten im Bereich einer Viertelsekunde (275ms) pro Anfrage erzielen. Die meisten (95%) der Verbindungsanfragen können in weniger als einer Sekunde beantwortet werden. Im öffentlichen Verkehrswesen treten häufig Verspätungen aufgrund unterschiedlicher Ursachen auf. Diese können Verbindungen unmöglich werden lassen, indem Anschlüsse brechen, da z.B. ein Anschlusszug nicht auf einen Zubringer warten kann. Aktuell eingesetzte Systeme berücksichtigen dies nicht. Wenn Verspätungsinformationen überhaupt einbezogen werden, dann werden sie oftmals einfach an Verbindungen, die auf Basis des Originalfahrplans berechnet wurden, angehängt. Hierbei kann es allerdings zur Beauskunftung nicht mehr realisierbarer Umstiege kommen. Verspätungsinformationen wurden von uns daher so in unser System integriert, dass im Falle von Zugverspätungen gültige Auskünfte anhand der aktuellen Verspätungslage berechnet werden. Wir haben eine Architektur mit mehreren Servern entwickelt, die den Einsatz eines zentralen Servers erlaubt, der die Verspätungsinformationen an mehrere Auskunftsserver verteilt. Die Simulation des Verspätungsaufkommens eines gesamten Tages mit mehr als 6 Millionen Verspätungsmeldungen ist so in unter zwei Minuten möglich. Alle notwendigen Aktualisierungsphasen, um die aktuelle Situation abzubilden, nehmen pro Auskunftsserver nur 0,1% des Tages in Anspruch und können so eingeplant werden, dass die durchgängige Verfügbarkeit des Auskunftsdienstes garantiert ist. Wir haben darüber hinaus Nutzerschnittstellen und Werkzeuge zur Visualisierung implementiert und zusätzlich einen neuen Dienst geschaffen. Dieser erlaubt es, eine geplante Reise in unserem System CoCoAS (Connection Controller and Alternatives System) zu registrieren und von diesem fortwährend prüfen zu lassen. Sobald die Verbindung eine große Verspätung aufweist, oder gar, im ungünstigsten Fall, unmöglich wird, bietet unser System alternative Verbindungen an. Diese werden nicht erst dann berechnet, wenn ein Umstieg bereits gescheitert ist und der Kunde sich ohne Anschlusszug am Umstiegsbahnhof befindet, sondern bereits sobald eine solche Situation absehbar wird. Daher bestehen meist mehrere und bessere Alternativen, über die unser System Auskunft geben kann.