In dieser Arbeit wird ein neues, dezentrales Verfahren zur intermodalen Reiseplanung vorgestellt, das auf aktuellen Internet-of-Services (IoS) Technologien [7] basiert. Transportdienstleister können beliebige Modalitäten (Flug, Bahn, Bus, Taxi, ...) anbieten und stellen diese über Softwaredienste (Services) bereit, welche für Kunden über einen Marktplatz ansprechbar sind.
Dabei müssen prinzipiell die folgenden Probleme gelöst werden: Finden von Diensten, Routing, und Scheduling. Zunächst müssen die Modalitäten und Dienstanbieter ausgewählt werden, die in Frage kommen. Danach befasst sich Routing mit dem Finden der optimalen Route zwischen zwei Stopps. Anbieter, die auf Basis eines Fahrplanes operieren, schränken die verfügbaren Abfahrtsund Ankunftszeiten ein. Unter Berücksichtigung dieser Constraints befasst sich Scheduling mit der Erstellung eines optimalen Zeitplanes.
Existierende Ansätze lassen sich im Wesentlichen in zwei Kategorien einteilen: Einerseits existieren Systeme mit guten Lösungen für das Routing-und Scheduling-Problem, die allerdings auf zentral gespeicherten Modellen basieren. Das stellt aber eine in der Praxis kaum realisierbare Idealvorstellung dar, da Transportdienstleister die Hoheit über ihre Daten (u.a. gerichtlich) verteidigen. Eine aktive Einbeziehung in die Planung ermöglicht außerdem die bessere Nutzung von domänenspezifischem Wissen. Andererseits existieren SOA-basierte Systeme, die meist Dienste nur auf Grund ihrer technischen Schnittstellen auswählen. Dies ist ineffizient, da im Service Discovery eine wesentlich bessere Vorselektion von Diensten erreicht werden kann.
Im Folgenden stellen wir unseren Ansatz zur intermodalen Reiseplanung vor, der es erlaubt, das Navigations-und Scheduling-Problem in offenen Service-Märkten zu lösen.
Der Rest des Papers ist wie folgt aufgebaut. In Abschnitt 2 werden zunä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.
Graphenbasierte Modellierung mit mehreren Modalitäten wird in [8] vorgeschlagen. Hierbei werden jeweils eigene Kanten für jede Modalität verwendet. Zum Bestimmen von Routen wird eine an SQL angelehnte Abfragesprache vorgeschlagen. Der Ansatz adressiert primär das Routingproblem, berücksichtigt aber Abfahrtszeiten nur eingeschränkt. Im Rahmen des iTransIT -Frameworks [13] wird ein gemeinsames Datenformat für Modalitäten beschrieben, das Common Data Model. Es dient als Abstraktionsschicht, die über Geo-Datenbanken gelegt wird. Ein Reiseplaner ist durch den Smart Traveler Information Service (STIS) [9] realisiert. Für die Routenberechnung werden einzelne, logische Subgraphen für jede Transportmodalität verwendet. Jedoch wählt der Benutzer zuerst eine Modalität aus, danach wird eine Route auf dem entsprechenden Graphen mittels eines Kürzeste-Wege-Algorithmus gesucht, verbleibende "Lücken" werden dann mit weiteren Modalitäten geschlossen. STIS adressiert ebenfalls primär das Routingund nicht das Schedulingproblem.
Ontologiebasierte Modellierung wird in [12] und [16] beschrieben. In [12] wird eine Reise als eine Reihe von geordneten stop points zwischen Start und Ziel modelliert. Lösungen werden mittels einer inferenzbasierten Ontology-Engine ermittelt, die zusätzlich auf Geo-Datenbanken zugreift. Unterschiedliche journey patterns können verwendet werden, um z.B. Routen mit "wenig Fußweg" oder mit "überdachten stop points" zu finden. In [16] wird eine Datenmodellierung mit dem Protégé-Werkzeug und eine Auswertung mit Hilfe des Jena-Frameworks vorgenommen. Die vorgestellte Evaluation ist mit nur 25 Elementen sehr klein.
Andere Ansätze wie [4] setzen auf Constraint Programming. Eine Reise besteht aus tasks, welche zu templates (etwa "tip", "fly") zusammengefasst werden können (Abstraktion). Je ein Teil der Reise wird herausgegriffen, Alternativen verglichen und dem Benutzer zur Auswahl gegeben. Das Constraint-Netzwerk umfasst alle Nebenbedingungen und Berechnungen, durch die Templates wird die Komplexität übersichtlich gehalten. Die Daten stammen von einer Reihe Agenten, etwa Wrapper und Screenscraper für Fahrplanauskünfte. Einerseits muss der Nutzer hier bei jedem Schritt aktiv werden und eine Wahl treffen, andererseits sind dem Aufbau einer Reise durch statische Templates enge Grenzen in der Flexibilität gesetzt [5].
SOA-basierte Systeme werden in [14] und [6] vorgestellt. Der in [14] vorgestellte Dienst ermittelt die günstigste Reise zwischen zwei Städten mittels eines Service-Mashups. Aufgrund beschränkter Granularität und kaum berück-
Der hier vorgestellte Ansatz zur automatischen Reiseplanung basiert auf IoS-Technologien und der Service-Beschreibungssprache USDL, die im Rahmen des Theseus/TEXO-Projekts [7] entwickelt wurden. Ziel von USDL (Unified Service Description Language) [15] ist es, eine umfassende Beschreibung zu schaffen, mit welcher zukünftig Dienstleistungen auf IoS-Marktplätzen angeboten und gefunden werden können. Eine wesentliche Neuerung von USDL ist der Einbezug nichttechnischer Eigenschaften von Diensten ("business", "operational"). Somit können Ort und Zeit der Diensterbringung, sowie weitere nicht-funktionale Eigenschaften beschrieben werden. 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önnen, 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önnen dann vom Planer aktiv mit einbezogen werden (4).
Das Ergebnis der Planung ist ein Reiseprozess, der detailliert beschreibt, wie der Nutzer vom Startort zum Zielort reisen kann. Dieser Prozess könnte später von einer Assistenzanwendung auf einem mobilen Gerät ausgeführt werden und dem Benutzer Navigationsanweisungen geben. Zur Modellierung, Darstellung und Ausführung von Reiseprozessen verwenden wir Methoden aus dem Geschäftsprozessmanagement (BPM).
Das Prozessmodell basiert auf der Sprache PASS (Parallel Activities Specification Scheme) [11]. Unser Verfahren könnte ebenfalls zusammen mit anderen Sprachen, wie z.B. BPEL, angewendet werden. PASS erfüllt allerdings alle unsere Anforderungen und es kann viel an unnötiger Komplexität vermieden werden. Im Weiteren wurde in einer früheren Arbeit eine Engine entwickelt, die PASS-Prozesse auf mobilen Geräten ausführen kann [2]. Damit können Anwendungen zur mobilen Navigationsunterstützung des Benutzers erstellt werden.
Aus der Sicht des Planers betrachten wir den Prozess zunächst abstrakt als Graphen G = (V, E). Die Knoten V in diesem Graphen sind Aktivitäten, die durch unterschiedliche Dienstleistungen erbracht werden, oder Pseudoknoten, wie Start, Ziel, Split, Join, etc. Insbesondere entsprechen die Knoten also nicht räumlichen Orten, wie oftmals in Wegfindungsproblemen verwendet, sondern vielmehr Diensten in einem Prozess. Die Kanten E beschreiben mögliche Übergänge, also die zeitliche Abfolge von Aktivitäten.
Knoten Literatur