Bachelor Thesis BCLR-0019

BibliographyVollmer, Peter: Beschleunigte Berechnung von ressourcenbeschränkten kürzesten Wegen.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 19 (2013).
37 pages, german.
CR-SchemaG.2.2 (Discrete Mathematics Graph Theory)
G.1.6 (Numerical Analysis Optimization)
Abstract

Die Lösung NP-schwerer Probleme wie die ressourcenbeschränkten kürzesten Wege Berechnungen ist zur Zeit exakt nicht in akzeptabler Zeit möglich. Bisher lassen sich akzeptable Lösungen nur durch Abstriche im Hinblick auf den optimalen Pfad und lange Berechnungszeiten finden. In dieser Arbeit behandeln wir, wie durch Vorberechnung einer Contraction Hierarchy eine Beschleunigung einer Lösungsheuristik für ressourcenbeschränkte kürzeste Wege Berechnungen erreicht werden kann. Dazu haben wir ein Werkzeug erstellt, mit dem man die Vorberechnung vornehmen kann. Anschließend wurde auf den erstellten CH-Graphen getestet, wie erfolgreich die Beschleunigung ist. In unseren Messung wir, dass sich die Antwortzeiten um den Faktor 141-248 beschleunigen lassen.

Full text and
other links
PDF (489158 Bytes)
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Algorithmic
Superviser(s)Storandt, Sabine
Entry dateMarch 14, 2013
   Publ. Computer Science