Fully realistic multi-criteria timetable information systems [Elektronische Ressource] / von Mathias Schnee

Schnee

Sujets

• Informatik

Informations

• Publié par: technischen_universitat_darmstadt
• Publié le: 01 janvier 2009
• Nombre de lectures: 19
• Langue: English
• Poids de l'ouvrage: 9 Mo

Extrait

Dr.F14.07.1979ullyhenRealisticDr.Multi-CriteriahTimetablehscInformationhSystemsKVmannomagF200acD-17hDernbt:ereicWht:InformatikM?ller-HannderderT08.09.2009ecmhnisc29.10.2009heHoUnivulkersit?tamDarmstadtinzurbacErlangungReferendesProf.akKarstenademeiheiscoreferenhenProf.GradesMatthiaseineseDr.Datumrer.Einreicnat.ung:genehmigteTDissertationderv?ndliconPr?fung:HerrnDarmstadt,Dipl.-Inf.9MathiascSchhneeennzier:geborenAbstract
Millions of people use public transportation and consult electronic timetable informa-
tion 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 “at-
tractive” alternatives. We developed the concept of advanced Pareto optimality as an
evolution of the classical Pareto optimality approach. It delivers more alternatives and
removesunattractivesolutionsfromtheresultstosuitthenotionofattractiveconnections
for all potential customers.
Realistic modeling of the search for attractive connections leads to shortest-path al-
gorithms. 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
toanexactrepresentationsatisfyingallconstraintsofarealschedule. Basedonageneral-
ization of Dijkstra’s shortest-path algorithm, we developed our full-fledged multi-criteria
timetable information system MOTIS (Multi Objective Traffic Information System). It
deliversvalidconnectionsaccordingtotheprincipleofadvanced Pareto optimality. Acus-
tomer may actually buy a ticket for the connections determined by our system. Further-
more, 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
tocatchallconnectingtrainsofatrip. Moreover, wepresentapproaches tothesearchfor
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 suit-
ableforourscenario. Inanextensivecomputationalstudywediscussthecostofregarding
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 connec-
tions 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
iii Abstract
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
isregisteredinCoCoAS(ourConnectionControllerandAlternativesSystem). Whilethe
passenger travels, the system continously checks the status of the connection. As soon as
thesystemdeterminesthattheconnectionwillbreak,itoffersalternatives. Bycomputing
these alternatives as early as possible, an asset of our system, more and better options
can be explored.Zusammenfassung
Millionen Menschen nutzen t¨aglich offen¨ tliche Verkehrsmittel. Die Deutsche Bahn AG
bef¨orderte in den Jahren 2007 und 2008 jeweils ub¨ er 1,4 Milliarden Passagiere, welche
ipro Jahr ub¨ er 70 Milliarden Personenkilometer zuruc¨ klegten [Deu09]. Herk¨ommliche
elektronische Fahrplanauskunftssysteme berechnen mogli¨ che Verbindungen fu¨r Kunden.
iiDer Anbieter der Auskunft fu¨r die Deutsche Bahn AG, HaCon, gibt an, mehr als 20
Millionen Verbindungen t¨aglich zu berechnen [Haf09]. Sie werden bislang unter Angabe
der Abfahrts- und Ankunftszeit, der Reisezeit, der Anzahl der Umstiege und des Preises
dem Nutzer pr¨asentiert. Unter den angebotenen Alternativen wah¨ lt der Kunde nach
individuellen Gesichtspunkten, basierend auf zeitlichen Rahmenbedingungen, Komfort
und Budget. Da diese Entscheidung auf naturl¨ iche Weise multikriteriell abl¨auft, sollten
Fahrplanauskun¨ fte auch nach multikriteriellen Ans¨atzen berechnet werden, um m¨oglichst
”attraktiveAlternativen”anzubieten. WirhabendasKonzeptadvanced Pareto Optimali-
t¨at alseineWeiterentwicklungdesklassischenPareto-Prinzipseingefuhr¨ t. UnserKonzept
liefert nun mehr geeignete Verbindungen und unterdru¨ckt dabei gleichzeitig unpassende
L¨osungen des klassischen Ansatzes, um der Zielvorstellung attraktiver Verbindungen fur¨
alle potenziellen Kunden gerecht zu werden.
Die realistische Modellierung der Suche nach Verbindungen auf Bahnfahrpl¨anen fu¨hrt
zu Kur¨ zeste-Wege-Algorithmen. Um Kundenanfragen in wenigen Millisekunden beant-
worten zu k¨onnen, werden schnelle Algorithmen ben¨otigt, da die Modellierung des Fahr-
plans zu großen Graphen mit mehreren hunderttausend Knoten und Kanten fuh¨ rt. Diese
Graphen sind entweder zeit-expandiert oder zeit-abh¨angig, 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¨ane
wirklichkeitsgetreuundohneEinschr¨ankungenabzubilden, undzumandereneinengeeig-
neten Algorithmus entworfen, eine Generalisierung von Dijkstra’s Kurze¨ ste-Wege-Algo-
rithmus. AufdieserBasisberuhtunsermultikriteriellesFahrplanauskunftssystemMOTIS
(Multi Objective Traffic Information System). Es berechnet nach dem Prinzip der ad-
vanced Pareto Optimalitat¨ gul¨ tige Verbindungen, fu¨r die ein Kunde am Bahnschalter ein
regul¨ares Ticket erwerben kann. Darub¨ er hinaus haben wir das zeit-abh¨angige Modell
erforscht und einen ebenfalls vollkommen realistischen Prototypen auf Grundlage dieses
Graphenmodells entwickelt.
iAnzahl der Passagiere mal durchschnittliche Reisel¨ange. Zahlen fu¨r Fern- und Regionalverkehr, ohne
Stadtverkehre.
iiDas Fahrplanauskunftssystem HAFAS von HaCon wird in 16 La¨ndern eingesetzt, darunter Deutsch-
land, England, Frankreich und die Schweiz.
iiiiv Zusammenfassung
Außerdemhabenwireinigezus¨atzlicheKriterienuntersucht,diebisdatonichtberuc¨ k-
sichtigt worden sind, wie zum Beispiel Angebotspreise (d.h. reduzierte Tickets zu beson-
deren Konditionen, z.B. nach der Verfu¨gbarkeit von Kontingenten) oder die Zuverlas¨ sig-
keitvonUmstiegen,alseinMaßzurBewertungderWahrscheinlichkeit,alleAnschlusszuge¨
einerVerbindungauchtats¨achlicherreichenzukonn¨ en(interessantbeiZugversp¨atungen).
Zus¨atzlich gelang es uns zwei unterschiedliche Herangehensweisen fu¨r die Suche nach
Nachtzugverbindungen zu entwerfen. In diesem Anwendungsfall geht es darum, ausrei-
chend lange Teilstrecken in Nachtzugen¨ ohne hinderliche Umstiege zu verbringen. Unsere
Algorithmen,diedieseKriterienberuc¨ ksichtigen,sindschnellundermittelnansprechende
Alternativen.
Die Suche unter mehreren Zielkriterien auf zeit-expandierten Graphen ist deutlich
anspruchsvoller als z.B. auf statischen Straßengraphen. Wir haben verschiedene exis-
tierendeBeschleunigungstechnikenuntersuchtundgeeigneteanunserSzenarioangepasst,
sowie neue Techniken entwickelt. In einer ausfuh¨ rlichen Studie diskutieren wir sowohl
die Kosten der Kriterien im Einzelnen und in Kombination, als auch den Effekt unter-
schiedlicher 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¨onnen in weniger als
einer Sekunde beantwortet werden.
Im offe¨ ntlichen Verkehrswesen treten h¨aufig Verspatun¨ gen aufgrund unterschiedlicher
Ursachen auf. Diese k¨onnen Verbindungen unmogl¨ ich werden lassen, indem Anschlu¨sse
brechen, da z.B. ein Anschlu