Zusammenfassung In dieser Arbeit wird ein dezentrales Verfahren zur Planung von Reiseprozessen vorgestellt. Transportdienstleister bieten ihre Dienste u¨ber einen Service-Marktplatz an und ko¨nnen mit Hilfe der Unified Service Description Language (USDL) effektiv vorselektiert werden. Der Reiseprozess wird durch schrittweise Verfeinerung und Graphtransformation erstellt. Auf diese Transformationen k¨onnen Dienste direkt Einfluss nehmen. Das macht unser Verfahren im Gegensatz zu zentralen Planungsansa¨tzen flexibel, offen und erweiterbar.
Im Folgenden stellen wir unseren Ansatz zur intermodalen Reiseplanung vor, der es erlaubt, das Navigations- und Scheduling-Problem in offenen ServiceMa¨rkten zu lo¨sen.
Der Rest des Papers ist wie folgt aufgebaut. In Abschnitt 2 werden zuna¨chst verwandte Arbeiten diskutiert. In Abschnitt 3 wird die Systemarchitektur vorgestellt, danach die Planungsmethode in Abschnitt 4. Abschnitt 5 beschreibt die Implementierung. Der Artikel schließt mit der Zusammenfassung in Abschnitt 6. 2
Graphenbasierte Modellierung mit mehreren Modalita¨ten wird in [
Ontologiebasierte Modellierung wird in [
Andere Ans¨atze wie [
SOA-basierte Systeme werden in [
Berlin, Alex. Ziel 11:30 Uhr Start
Start 1 2 4
Start ? ? 09:F3R0AUhr
Reise Flugreise Lufthansa ? ? ...
Lufthansa ...
TXL 10:35 Uhr Ziel
Ziel
Ziel
Ziel
(a) Systemarchitektur
(b) Schrittweise Prozessverfeinerung
sichtigter zeitlicher Nebenbedingungen eignet sich dieses Vorgehen kaum fu¨r ein
allgemeineres Reiseproblem. A¨hnlich ist Self-Serv [
Der hier vorgestellte Ansatz zur automatischen Reiseplanung basiert auf
IoSTechnologien und der Service-Beschreibungssprache USDL, die im Rahmen des
Theseus/TEXO-Projekts [
Die Architektur ist in Abbildung 1a dargestellt und unterscheidet vier Arten von Teilnehmern: Service Repository, Planer, Dienstleister und Clients. Der Ablauf gestaltet sich wie folgt: Reisedienstleister beschreiben ihre Dienste mit USDL, also an welchen Orten diese in Anspruch genommen werden k¨onnen, sowie Webservices zur Planung, und hinterlegen diese im Repository (1). Schickt ein Client eine Reiseplanungsanfrage an den Planer (2), erzeugt dieser mittels Graphtransformation einen Reiseprozess und fragt dabei die zu verwendenden Dienste am Repository ab (3). Dienste k¨onnen dann vom Planer aktiv mit einbezogen werden (4). 4
Das Ergebnis der Planung ist ein Reiseprozess, der detailliert beschreibt, wie der Nutzer vom Startort zum Zielort reisen kann. Dieser Prozess k¨onnte sp¨ater von einer Assistenzanwendung auf einem mobilen Gera¨t ausgefu¨hrt werden und dem Benutzer Navigationsanweisungen geben. Zur Modellierung, Darstellung und Ausfu¨hrung von Reiseprozessen verwenden wir Methoden aus dem Gescha¨ftsprozessmanagement (BPM).
Das Prozessmodell basiert auf der Sprache PASS (Parallel Activities
Specification Scheme) [
Aus der Sicht des Planers betrachten wir den Prozess zun¨achst abstrakt als Graphen G = (V, E). Die Knoten V in diesem Graphen sind Aktivit¨aten, die durch unterschiedliche Dienstleistungen erbracht werden, oder Pseudoknoten, wie Start, Ziel, Split, Join, etc. Insbesondere entsprechen die Knoten also nicht ra¨umlichen Orten, wie oftmals in Wegfindungsproblemen verwendet, sondern vielmehr Diensten in einem Prozess. Die Kanten E beschreiben mo¨gliche U¨ berga¨nge, also die zeitliche Abfolge von Aktivita¨ten.
Knoten sind mit Kontextinformationen attributiert, insbesondere sind dies Ort und Zeit. Diese Attribute existieren zweimal pro Knoten, n¨amlich fu¨r den geplanten Beginn der Aktion, sowie dem Ende. Weiterhin k¨onnen alle NichtPseudoknoten mit einer in USDL beschriebenen Dienstleistung versehen werden. Verwendet man einen Graphen mit ausgezeichnetem Start- und Zielknoten als Reiseprozess, dann ergibt sich mit jedem linearisierten Pfad zwischen Start und Ziel ein Reiseplan, der angibt, wann und wo welche Dienstleistung genutzt werden soll. Durch parallele Teilpfade lassen sich mehrere Alternativen ausdru¨cken, etwa dass ein Bus oder alternativ wenige Minuten spa¨ter eine Straßenbahn verwendet werden kann. Durch einen derart gestalteten Graphen k¨onnen auch komplexe Anfragen ausgedru¨ckt werden, indem weitere Knoten fu¨r einen Hotelaufenthalt oder gewu¨nschte Zwischenaufenthalte in den Ausgangsgraphen eingefu¨gt werden.
Die Durchfu¨hrung einer Reiseplanung erfolgt durch Anwendung einer Reihe
von Regeln zur Transformation des Prozessgraphen. Die Kernidee dabei ist, mit
einem sehr einfachen Graphen zu beginnen und diesen schrittweise zu verfeinern,
also die Reise auszugestalten (Abbildung 1b). Der Graph wird mit dem
JavaFramework Graph Rewrite Library (GRL) [
Abbildung 1: Graphtransformationen (b) Substitution ko¨nnen Transformationen auch alternativ in Java implementiert werden. Das ist fu¨r komplexe Ersetzungen oft hilfreich.
Zu Beginn besteht der Graph nur aus dem Start- und Zielknoten, sowie einer Kante dazwischen. Zur schrittweisen Verfeinerung des Reiseprozesses dienen nun die folgenden drei Grundkonzepte: Einfu¨gen, Substitution und Adaption. Einfu¨gen: Beim Einfu¨gen wird im Repository ein Dienst gesucht, der die Transportlu¨cke zwischen vf (from) und vt (to) mo¨glichst gut schließt. Hierbei werden Ortsinformationen aus USDL-Beschreibungen ausgewertet. Weitere Kriterien, wie die aktuelle Komplexita¨t des Graphen, sind mo¨glich. Auch Vorlieben des Nutzers sind denkbar. Der neue Knoten vs repr¨asentiert dann diesen Dienst. Kante e wird durch zwei neue Kanten e0 und e00 ersetzt, deren summierte verbleibende Transportlu¨cke ku¨rzer als die von e sein muss. Mehrere Alternativen (parallele Pfade) sind ebenfalls mo¨glich. Abbildung 1a zeigt diese Transformation. Substitution: Im Falle der Substitution wird ein Knoten vs, dessen USDLBeschreibung einen Webservice zur Substitution umfasst, durch einen Subgraphen Gs ersetzt. Damit kann vs an einen anderen Dienst delegieren, z.B. kann der abstrakte Knoten Flugreise durch den konkreten Anbieter Lufthansa ersetzt werden, oder Gs kann als Template fu¨r einen komplexen Subgraphen dienen. Der Anbieter Lufthansa kann etwa beschreiben, dass dieser Teil der Reise aus Checkin, Gep¨ackaufgabe, Boarding, Flug, ... besteht. Ein Dienstleister kann somit selbst die Transformation bestimmen, und damit den Reiseprozess entscheidend beeinflussen. Der Ansatz wird damit auch offen hinsichtlich beliebiger, neuer Transportmodalita¨ten. Dieses Vorgehen wird in Abbildung 1b illustriert. Adaption: Die Adaption ist die schwa¨chste Form der Transformation und wirkt sich nur auf die Attributierung eines Knotens aus. Auch hier wird ein durch die USDL-Beschreibung gegebener Webservice abgefragt. Sinnbildlich kann man diesen als Fahrplanauskunft betrachten. Dieses Konzept erlaubt die Handhabung von fahrplanbasierten und nicht-fahrplanbasierten Transportdiensten. Bei fahrplanbasierten Diensten erfolgt eine Anpassung an die Zeiten. Vor der Adaption k¨onnte man etwa von einer unbestimmten Busfahrt sprechen, danach von einer festen Verbindung mit Haltestellen und Fahrzeiten. Nicht-fahrplanbasierte Dienste, wie eine Taxifahrt, stehen zu jeder Zeit zur Verfu¨gung. Deshalb wa¨re es nicht mo¨glich, diese Zeiten statisch in der USDL-Beschreibung zu hinterlegen.
Insgesamt wurden basierend auf diesen Konzepten 12 verschiedene Transformationsregeln entwickelt. Fu¨r Adaption und Substitution existieren mehrere Regeln um Optimierungsziele abzudecken, etwa ob von der Ankunftszeit bevorzugt zuru¨ckgeplant wird oder ob die Abfahrtszeit maßgeblich ist. Weitere Regeln der Adaption k¨onnen etwaige Wartezeiten minimieren. Pruning-Regeln dienen zum Entfernen von schlechten Alternativen. Da Services direkt Transformationsregeln fu¨r den Prozess mit einbringen ko¨nnen, sind außerdem Validierungsschritte notwendig, um die Terminierung des Transformationsprozesses und korrekte Prozesse sicherzustellen.
Alle Regeln liegen in einer Priorit¨atsreihenfolge vor. Pruning hat eine hohe
Priorit¨at, Einfu¨gen aus dem Repository sollte dagegen nur durchgefu¨hrt
werden, falls eine Transportlu¨cke nicht anderweitig geschlossen werden kann. Der
Algorithmus fu¨hrt eine Reihe von Transformationsphasen bestehend aus Suche
und Transformation durch. Jede Phase beginnt mit der Suche. Dabei wird
immer mit der Regel h¨ochster Priorit¨at begonnen. Trifft die Bedingung der Regel
(LHS) auf dem Graphen an keiner Stelle zu, wird mit der jeweils na¨chsten Regel
fortgesetzt. Trifft keine Regel zu, endet der Algorithmus. Nach der Suche wird
die Transformation der Regel auf alle Treffer angewendet und die aktuelle Phase
endet [
Beispiel: Der Nutzer m¨ochte von Darmstadt Mitte ab 07:00 Uhr nach Berlin Alexanderplatz (m¨oglichst bis 11:30 Uhr) reisen. Der Planer konstruiert aus dieser Anfrage einen Graphen mit zwei attributierten Knoten: Start (07:00 Uhr, Darmstadt) und Ziel (11:30 Uhr, Berlin Alex.). Eine Kante zwischen beiden Knoten symbolisiert die Abfolge zwischen den Knoten, also den Reisewunsch, und somit die Aufgabestellung (Abbildung 1b, Schritt 0). Beide Knoten haben kein USDL-Attribut, daher scheiden Adaption und Substitution aus, es verbleibt das Einfu¨gen. Entsprechend der Ortsangaben sowie des geringen Umfangs des Graphen liefert das Repository einen allgemeinen Dienst zuru¨ck, hier als Beispiel der Reise-Dienst der Lufthansa in Form einer USDL-Beschreibung. Daraus wird ein neuer Knoten (mit USDL-Attribut) erstellt und eingefu¨gt (Schritt 1). Der neue Knoten besitzt noch keine Kontextattribute (Ort & Zeit), ist aber nach der USDL-Beschreibung substituierbar und wird daher in der n¨achsten Phase transformiert. Ein per USDL beschriebener Webservice des Reisedienstes wird mit den umrahmenden Kontextinformationen (von Start und Ziel) aufgerufen. Dieser w¨ahlt, hier anhand der Distanz, Fliegen als sinnvollste Reise-Modalit¨at und liefert den Flugreise-Dienst zuru¨ck (Schritt 2). Da dem neuen Dienst ebenfalls noch Kontextinformationen fehlen, und kein Webservice zur Substitution enthalten ist, wird in Phase 3 eine Adaption durchgefu¨hrt und ein Webservice der Flugreise aufrufen. Der Service sucht nach entsprechenden Flugh¨afen und Flu¨gen, hier Flug LH176 um 9:30 Uhr von Flughafen Frankfurt nach Berlin Tegel, und liefert diesen als Kontextinformationen zuru¨ck (Schritt 3). Hier wird auch deutlich, dass durch simultane Wahl von Orten (wie Flugh¨afen) und Zeiten Routing- sowie Scheduling kombiniert betrachtet werden. Der Dienst wa¨hlt, a¨hnlich der Verbindungssuche der Deutschen Bahn, Haltestellen, Verkehrsmittel sowie Abfahrtszeiten, um die Gesamtreisedauer zu minimieren, und nutzt dazu das umfangreiche doma¨nenspezifische Wissen des Dienstleisters. Ein großer Teil der Transportlu¨cke ist jetzt geschlossen. Es verbleiben kleinere Lu¨cken, die in weiteren Phasen analog geschlossen werden. Natu¨rlich k¨onnen bei der Substitution auch Graphen mit alternativen Dienstleistungen zuru¨ckgeliefert werden, etwa Flug- sowie Bahnreise als auch bereits mit Kontextinformationen (Flu¨ge) versehene alternative Flugreise-Dienste. Mit der Adaption sind auch nachtra¨gliche A¨nderungen mo¨glich, beispielsweise ein spa¨terer Flug aufgrund langer Anreise. 5
Im Rahmen der Arbeit wurde ein USDL-basiertes Service-Repository auf Basis von PostgreSQL und PostGIS entwickelt. Die Ortsinformationen werden aus den USDL-Beschreibungen extrahiert und k¨onnen bei der Servicesuche verwendet werden. Der Zugriff auf das Repository erfolgt u¨ber SOAP/HTTP. Fu¨r ein realita¨tsnahes Szenario wurden eine Reihe von Diensten entwickelt, darunter ein Flug-Dienst auf Basis eines Crawlers fu¨r Lufthansa-Webseiten, Dummy-Services mit etlichen Haltestellen und zuf¨alligen Verbindungen fu¨r die Deutsche Bahn, den RMV, die Berliner Verkehrsbetriebe, sowie ein Fußga¨ngerservice.
Ein exemplarischer Client wurde als Android App realisiert (Abbildung 2).
Eine Reise von Darmstadt nach Berlin wurde als Szenario zur Abdeckung der
Dienste verwendet, hier kommen die Modalita¨ten zu Fuß, Bus, Zug, Flugzeug und
S-Bahn kombiniert zum Einsatz. Die Kommunikation zwischen Planer und Client
wurde mit der Kommunikations-Middleware MundoCore [
Nach ersten Tests korreliert die Laufzeit einer Reiseplanung mit dem Umfang der Aufgabestellung. Der Haupteinflussfaktor sind die Zugriffe des Planers auf Webservices der Reisedienstleister, einschließlich einer Anfrage an das Repository sind dies maximal 3 Aufrufe fu¨r jeden Knoten. Das Beispielszenario umfasst final 8 echte Knoten, involviert 5 verschiedene Teilnehmer und wurde mit 17 Transformationen erstellt.
(a) Zieleingabe (b) Reiseplan (Teil 1)
(c) Reiseplan (Teil 2)
Abbildung 2: Screenshots der Android App
Eine Reiseplanung auf dieser Basis kann Dienstleister aktiv in die Planung mit einbeziehen, auf deren Fahrplanausku¨nfte und Buchungssysteme zuru¨ckgreifen und somit ideale, intermodale Reisepl¨ane erstellen. Weiterhin wird im Rahmen der Verbreitung von Smartphones und Assistenzdiensten der Weg zu einer ineinandergreifenden Reiseunterstu¨tzung ero¨ffnet.
Danksagung. Diese Arbeit wurde unterstu¨tzt durch das Theseus-Programm, gefo¨rdert durch das Bundesministerium fu¨r Wirtschaft und Technologie (Kennziffer: 01MQ07012).