Routenplanung mit Nebenbedingungen

Abstract

Um unterschiedliche Geschwindigkeiten beim energieoptimalen Routing mit zeitlichen Nebenbedingungen betrachten und optimieren zu können, erweitert diese Diplomarbeit das Constrained Shortest Path Problem um weitere Parameter bei den Kantenkostenfunktionen. Nach der Erweiterung wird die Anwendbarkeit der Beschleunigungstechnik "Contraction Hierarchy" gezeigt und mit dieser Technik das Problem in praktikabler Zeit gelöst. Ebenfalls wird eine Heuristik entwickelt, die das Optimierungsproblem in kurzer Zeit löst und für viele praktische Anwendungsgebiete verwendbar ist.