Personalized route planning : on finding your way in theory and practice

Abstract

Personalisierung ist ein wichtiger Trend in der heutigen digitalen Welt. Im Bereich der Routenplanung hatte dieser jedoch noch keine starken Auswirkungen. Diese Dissertation beschäftigt sich mit dem multikriteriellen Routenplanungsansatz, der “personalized route planning model” genannt wird. Das Modell optimiert Konvexkombinationen von Routenplanungskriterien wie z.B. Reisezeit, Distanz oder Straßentyp und berechnet unterschiedliche Routen basierend auf den Präferenzen des Nutzers. Wir nennen die optimalen Pfade dieses Modells personalisierte Pfade. Das Angeben solcher Präferenzen ist keine einfache Aufgabe für einen Nutzer. Daher haben wir uns im praktischen Teil unserer Forschung auf Anwendungen konzentriert, die die Präferenzen im Backend verarbeiten ohne den Nutzer mit ihnen zu konfrontieren. Wir stellen drei praxisorientierte Anwendung und eine theoretische Analyse des Models vor. Für jede der Anwendungen entwickelten wir effiziente Algorithmen und verifizierten die Qualität und Laufzeit experimentell. Die erste Anwendung findet große Mengen von Alterantivrouten, die nicht zu sehr überlappen. Dazu entwickeln wir einen Algorithmus, der alle personalisierten Pfade aufzählen kann. Dieser wird dann erweitert um optional das Berechnen von Pfaden zu vermeiden, die zusätzliche Optimalitätskriterien nicht erfüllen. Darüber hinaus zeigen wir ‘erfundene’ Routenplanungskriterien, die die Ergebnisse noch weiter diversifizieren. In unseren Experimenten beobachteten wir große Mengen an sinnvollen Alternativrouten. Im Gegensatz zur ersten Anwendung sind die nächsten beiden Anwendung nicht an Endnutzer gerichtet, sondern dienen zum Lernen aus bestehenden Trajektorien. Die zweite Anwendung identifiziert Zwischenziele in Trajektorien. Wir nehmen an, dass Fahrer auf längeren Fahrten mit mehreren Zielen personalisierte Pfade zwischen den einzelnen Zielen wählen. Daher verwenden wir einen Trajektoriensegmentierungsansatz, der die Trajektorien in personalisierte Pfade aufteilt. Unser Ansatz konnte ca. 60% aller bekannten Zwischenziele in einem echt Welt Datensatz exakt erkennen und 90% waren sehr nahe an den errechneten Zwischenzielen. Unsere letzte Anwendung hat das Ziel Trajektorien nach Präferenzen zu clustern. Hier ist die Idee eine Menge an Trajektorien durch eine kleine Menge Präferenzen zu erklären, so dass jede Trajektorie für eine der Präferenzen optimal ist. Das erlaubt es wichtige Präferenzen für einzelne Fahrer zu finden oder eine Menge von Fahrern zu kategorisieren. Wir berechnen den Präferenzbereich für alle Trajektorien und lösen eine darauf basierende geometrische “Hitting Set” Instanz. Obwohl beide Schritte im schlimmsten Fall teuer zu berechnen sind, stellten wir fest, dass der gesamte Prozess häufig in Sekunden bis Minuten berechnet werden kann für Instanzen mit tausenden Trajektorien. Im letzten Teil der Dissertation analysieren wir wie viele personalisierte Pfade es abhängig von der Graphgröße zwischen zwei Knoten geben kann. Unsere Analyse basiert auf zwei speziellen Graphfamilien und wird dann auf alle Graphen generalisiert. Wir beweisen, dass die Anzahl der personalsierten Pfade subexponentiell in der Graphgröße und exponentiell in der Zahl der Routenplanungskriterien ist.