Master Thesis MSTR-2023-68

BibliographyKrenz, Dominik: Das Rastplatzproblem.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Master Thesis No. 68 (2023).
47 pages, german.
Abstract

Ob zu Fuß, mit dem Fahrrad oder mit dem Auto, es ist für längere Routen immer wichtig zu entscheiden wo ein Halt gemacht wird um eine Pause zu machen. Nun sollte dieser Halt auch an dem richtigen Ort sein, aber trotzdem nicht die Strecke deutlich verlängern. Mit diesem Problem beschäftigt sich das Rastplatzproblem. Bei dem Rastplatzproblem ist nach einer Menge von besonderen Knoten gesucht. Passend zu dem Kontext des Problems werden diese Knoten Rastplätze genannt. Es soll zu zwei beliebigen Knoten, die eine Route bilden, eine Menge an Rastplätzen bestimmt werden, die die originale Route nicht mehr als einen gegebenen Faktor erhöht. Um die Lösungsmenge zu bestimmen muss also die Distanz von den Start- und Zielknoten zu den Rastplätzen bestimmt werden. Somit gehört das Rastplatzproblem zu der Gruppe der One-To-Many Problemen. Für das Problem ist es sinnvoll im Besonderen Straßengraphen zu betrachten. Diese sind typisch für den geringen Grad der Knoten im Vergleich zur Menge der Knoten. Contraction Hierarchies wurden hierzu entwickelt um Knoten nach ihrer Wichtigkeit für die kürzesten Pfade im Graphen zu sortieren. Zudem wird der Graph hierbei durch neue Kanten, Shortcuts genannt, erweitert. Die Contraction Hierarchies ermöglichen, im Gegenzug zu einer erhöhten Vorverarbeitungsphase, eine beschleunigte Version des standardmäßigen bidirektionalen Dijkstras. Eine Möglichkeit das Rastplatzproblem zu lösen ist, es als eine Reihe von One-To-One Problemen zu betrachten. Daher wird in dieser Arbeit ein naiver Lösungsansatz betrachtet, in dem die Rastplätze durch einzelne Pfadsuchen über den CH-Dijkstra bestimmt werden. So werden für jeden Rastplatz jeweils zwei Pfadsuchen durchgeführt. Ein anderer einfacher Ansatz der in dieser Arbeit betrachtet wird ist der One-To-All Dijkstra, welcher zu jeder Anfrage die Distanzen von den Start- und Zielknoten zu allen anderen Knoten berechnet. Im Anschluss muss nur noch die Distanz der Rastplätze abgelesen werden. Zu diesen einfachen Ansätzen wird der Lazy-PHAST Algorithmus verglichen. Die Basis für diesen Algorithmus ist der PHAST Algorithmus, welcher die Contraction Hierarchies nutzt, um effizient die Distanz von einem Knoten zu allen anderen zu berechnen. Der Lazy-PHAST Algorithmus ist eine Anpassung mit der One-To-Many Probleme gelöst werden können. Um den Algorithmus weiter für das Rastplatzproblem zu optimieren, wurden Sektoren implementiert. Die Sektoren speichern die Mindestdistanz zu jeweils allen anderen Sektoren. So werden bei einer Anfrage nur Rastplätze aus Sektoren betrachtet die unter der maximalen Distanz liegen. So ist es möglich die Menge der betrachteten Rastplätze frühzeitig auszufiltern und die Bearbeitungszeit der Anfragen weiter zu reduzieren. Die drei beschriebenen Algorithmen werden in dieser Arbeit unter verschiedenen Bedingungen untersucht und getestet. Der Lazy-PHAST Algorithmus weist eine deutlich bessere Performanz als der CH-Dijkstra über alle Mengen an Rastplätzen. Gegenüber den One-To-All Dijkstra wiederum, ist die Performanz des Lazy-PHAST Algorithmus ähnlich sobald die Menge an Rastplätze näher an die Menge aller Knoten kommt. Durch die Einführung von Sektoren kann dem jedoch entgegengewirkt werden.

Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Algorithmic
Superviser(s)Funke, Prof. Stefan; Proissl, Claudius
Entry dateFebruary 20, 2024
   Publ. Computer Science