Bachelorarbeit BCLR-0019

Bibliograph.
Daten
Vollmer, Peter: Beschleunigte Berechnung von ressourcenbeschränkten kürzesten Wegen.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Bachelorarbeit Nr. 19 (2013).
37 Seiten, deutsch.
CR-Klassif.G.2.2 (Discrete Mathematics Graph Theory)
G.1.6 (Numerical Analysis Optimization)
Kurzfassung

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.

Volltext und
andere Links
PDF (489158 Bytes)
Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Algorithmik
BetreuerStorandt, Sabine
Eingabedatum14. März 2013
   Publ. Institut   Publ. Informatik