Master Thesis MSTR-2023-66

BibliographyAhmed, Aimn: Das Treffpunktproblem in Straßengraphen.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Master Thesis No. 66 (2023).
41 pages, german.
Abstract

Reale Straßennetzwerke und die Ermittlung kürzester Pfade stellt ein facettenreiches und praktisch relevantes Problem dar. Besonders herausfordernd wird es, wenn man ein Treffpunkt zwischen mehreren Teilnehmern vereinbaren möchte. Das sogenannte Treffpunktproblem ist Thema dieser Masterarbeit. Gegeben sind mehrere Verkehrsteilnehmer für die ein optimaler Treffpunkt ermittelt werden soll. Hierbei wird zwischen zwei Kriterien unterschieden: die Summe der Reisezeit oder die Minimierung des längsten Pfades aller Verkehrsteilnehmer. Die vorliegende Masterarbeit stellt verschiedene Algorithmen und Heuristiken vor, welche das Treffpunktproblem für das jeweilige Kriterium optimal lösen. Dabei werden die Algorithmen gegenübergestellt und deren Laufzeiten verglichen. Dabei werden verschiedene Anzahlen an Verkehrsteilnehmer getestet und am Ende evaluiert.

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. Institute   Publ. Computer Science