TU Darmstadt / ULB / TUbiblio

Fully Realistic Multi-Criteria Timetable Information Systems

Schnee, Mathias (2009)
Fully Realistic Multi-Criteria Timetable Information Systems.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

Kurzbeschreibung (Abstract)

Millions of people use public transportation and consult electronic timetable information systems. A customer selects from the connections offered by the system according to personal preferences. The chosen connection is typically a compromise based on the importance of several criteria, including departure and arrival time, travel time, comfort and ticket cost. Consequently, multi-criteria optimization should be used to deliver “attractive” alternatives. We developed the concept of advanced Pareto optimality as an evolution of the classical Pareto optimality approach. It delivers more alternatives and removes unattractive solutions from the results to suit the notion of attractive connections for all potential customers. Realistic modeling of the search for attractive connections leads to shortest-path algorithms. Fast search algorithms are needed to answer customer requests in only a few milliseconds since the schedules are modeled as large graphs (several hundred thousand edges and nodes). The graphs are either time-expanded or time-dependent to model the dimension of time. In contrast to the majority of scientific work on the subject, our approach is fully realistic without simplifying assumptions. We extended the time-expanded graph model to an exact representation satisfying all constraints of a real schedule. Based on a generalization of Dijkstra’s shortest-path algorithm, we developed our full-fledged multi-criteria timetable information system MOTIS (Multi Objective Traffic Information System). It delivers valid connections according to the principle of advanced Pareto optimality. A customer may actually buy a ticket for the connections determined by our system. Furthermore, we also explored the time-dependent model and built a prototype system working on that model as a proof of concept. We also investigated several additional criteria that had not been considered before, for example special offers (reduced ticket cost under certain conditions, e.g. based on the availability of contingents) or the reliability of interchanges, a measure of how likely it is to catch all connecting trains of a trip. Moreover, we present approaches to the search for night trains with the additional objective of ensuring reasonable sleeping times without the need for train changes. Our algorithms respecting these criteria are fast and deliver attractive alternatives. We explored and adapted existing speed-up techniques and developed new ones suitable for our scenario. In an extensive computational study we discuss the cost of regarding the criteria, the effect of various parameterizations of our algorithm, and the impact of the developed speed-up techniques. Applying these, we achieve runtimes of about one quarter of a second on average and solve most of the queries (95%) in less than a second. Delays occur quite frequently in public transportation. They may invalidate connections as interchanges become infeasible. Current systems do not take that into account. At the utmost, they add changed departure or arrival times to connections calculated according to the static schedule. By incorporating information about delays into our model, we are able to deliver valid connections. We propose a multi-server architecture that allows several search servers to be updated by a central server distributing delay data. The simulation of a whole day with more than 6 million status messages takes less than two minutes. In our architecture, update phases may be scheduled to guarantee the availability of service at all times. We have built user interfaces and visualization tools for our system. Additionally, we have created a new service: proactive route guidance. Within this service a planned trip is registered in CoCoAS (our Connection Controller and Alternatives System). While the passenger travels, the system continously checks the status of the connection. As soon as the system determines that the connection will break, it offers alternatives. By computing these alternatives as early as possible, an asset of our system, more and better options can be explored.

Typ des Eintrags: Dissertation
Erschienen: 2009
Autor(en): Schnee, Mathias
Art des Eintrags: Erstveröffentlichung
Titel: Fully Realistic Multi-Criteria Timetable Information Systems
Sprache: Englisch
Referenten: Weihe, Prof. Dr. Karsten ; Müller-Hannemann, Prof. Dr. Matthias
Publikationsjahr: 9 Dezember 2009
Ort: Darmstadt
Verlag: Technische Universität
Datum der mündlichen Prüfung: 29 Oktober 2009
URL / URN: urn:nbn:de:tuda-tuprints-19894
Kurzbeschreibung (Abstract):

Millions of people use public transportation and consult electronic timetable information systems. A customer selects from the connections offered by the system according to personal preferences. The chosen connection is typically a compromise based on the importance of several criteria, including departure and arrival time, travel time, comfort and ticket cost. Consequently, multi-criteria optimization should be used to deliver “attractive” alternatives. We developed the concept of advanced Pareto optimality as an evolution of the classical Pareto optimality approach. It delivers more alternatives and removes unattractive solutions from the results to suit the notion of attractive connections for all potential customers. Realistic modeling of the search for attractive connections leads to shortest-path algorithms. Fast search algorithms are needed to answer customer requests in only a few milliseconds since the schedules are modeled as large graphs (several hundred thousand edges and nodes). The graphs are either time-expanded or time-dependent to model the dimension of time. In contrast to the majority of scientific work on the subject, our approach is fully realistic without simplifying assumptions. We extended the time-expanded graph model to an exact representation satisfying all constraints of a real schedule. Based on a generalization of Dijkstra’s shortest-path algorithm, we developed our full-fledged multi-criteria timetable information system MOTIS (Multi Objective Traffic Information System). It delivers valid connections according to the principle of advanced Pareto optimality. A customer may actually buy a ticket for the connections determined by our system. Furthermore, we also explored the time-dependent model and built a prototype system working on that model as a proof of concept. We also investigated several additional criteria that had not been considered before, for example special offers (reduced ticket cost under certain conditions, e.g. based on the availability of contingents) or the reliability of interchanges, a measure of how likely it is to catch all connecting trains of a trip. Moreover, we present approaches to the search for night trains with the additional objective of ensuring reasonable sleeping times without the need for train changes. Our algorithms respecting these criteria are fast and deliver attractive alternatives. We explored and adapted existing speed-up techniques and developed new ones suitable for our scenario. In an extensive computational study we discuss the cost of regarding the criteria, the effect of various parameterizations of our algorithm, and the impact of the developed speed-up techniques. Applying these, we achieve runtimes of about one quarter of a second on average and solve most of the queries (95%) in less than a second. Delays occur quite frequently in public transportation. They may invalidate connections as interchanges become infeasible. Current systems do not take that into account. At the utmost, they add changed departure or arrival times to connections calculated according to the static schedule. By incorporating information about delays into our model, we are able to deliver valid connections. We propose a multi-server architecture that allows several search servers to be updated by a central server distributing delay data. The simulation of a whole day with more than 6 million status messages takes less than two minutes. In our architecture, update phases may be scheduled to guarantee the availability of service at all times. We have built user interfaces and visualization tools for our system. Additionally, we have created a new service: proactive route guidance. Within this service a planned trip is registered in CoCoAS (our Connection Controller and Alternatives System). While the passenger travels, the system continously checks the status of the connection. As soon as the system determines that the connection will break, it offers alternatives. By computing these alternatives as early as possible, an asset of our system, more and better options can be explored.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

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.

Deutsch
Freie Schlagworte: shortest-path algorithm, multi-criteria optimization, delays, timetable, realistic model
Sachgruppe der Dewey Dezimalklassifikatin (DDC): 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik
20 Fachbereich Informatik > Algorithmik
Hinterlegungsdatum: 16 Dez 2009 08:33
Letzte Änderung: 05 Mär 2013 09:28
PPN:
Referenten: Weihe, Prof. Dr. Karsten ; Müller-Hannemann, Prof. Dr. Matthias
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 29 Oktober 2009
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen