Beschleunigte Berechnung von ressourcenbeschränkten kürzesten Wegen

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.