Routenplanung in Straßennetzen

Abstract

Die Berechnung kürzester Wege in einem Graphen ist eines der klassischen Probleme aus der Graphentheorie. Ein besonders praxisrelevanter Spezialfall ist die Bestimmung von schnellsten Routen in Straßennetzwerken. Hierarchische Eigenschaften der betrachteten Netzwerke erlauben es, Verfahren zu entwickeln, die nach einem einmaligen Vorberechnungsschritt in der Lage sind, beweisbar optimale Routen in Graphen mit mehreren Millionen Knoten im Bruchteil einer Sekunde zu ermitteln. Da- bei gibt es unterschiedliche Kompromisse zwischen der Vorberechnungszeit, der Größe der durch die Vorberechnung erzeugten Hilfsdaten und der resultierenden durchschnittlichen Suchzeit. Wir stellen verschiedene Algorithmen vor, die unterschiedliche Kompromisse anbieten, so dass wir durch unsere Arbeit insgesamt ein sehr breites Spektrum an möglichen Anwendungsfällen abdecken – von der High-End-Lösung mit Suchzeiten von wenigen Mikrosekunden bis zur schlanken und flexiblen Lösung, die nur einen sehr geringen Speicheroverhead erfordert und sogar auf Änderungen der Verkehrssituation wie zum Beispiel Staus reagieren kann, ohne die Korrektheit zu beeinträchtigen. Darüber hinaus ist mit einer entsprechenden Variante unserer Verfahren die Berechnung von großen Distanztabellen, wie man sie beispielsweise als Vorstufe zur Lösung des Handlungsreisendenproblem benötigt, sehr effizient möglich.