Was ist ein Kürzeste-Wege-Problem

Die Bestimmung von kürzesten oder schnellsten Wegen zwischen Punkten in einem Netzwerk ist ein schon lange bekanntes Problem in der Informatik bzw. dem Operations Research. Ziel ist es, die Länge und enthaltenen Kanten eines Weges zwischen 2 oder allen Punkten in einem Netzwerk zu bestimmen. Bereits in den fünfziger Jahren des vergangenen Jahrhunderts haben die Mathematiker Edsger W. Dijkstra und George Dantzig dafür ein Algorithmus entwickelt.

Heute müssen in vielen Anwendungsgebieten, wie z. B. der Tourenplanung, Strecken und Fahrzeiten zwischen hunderten, tausenden oder zehntausenden von Orten in riesigen Straßennetzen (z. B. alle Straßen in Europa) ermittelt werden. Dafür wurde der Dijkstra-Algorithmus in den letzten zehn Jahren erheblich weiterentwickelt, damit dies mit kurzen Laufzeiten ermöglicht wird.

Mit den aktuellen Algorithmen ist es möglich, große Distanzmatrizen in sehr kurzer Zeit zu berechnen. Darüber hinaus bieten Tourenplanungssysteme wie TransIT, die Möglichkeit, Straßensperren zu berücksichtigen und das Wenden von Lkw möglichst zu verhindern, was noch umfangreichere Anpassungen der Algorithmen erfordert.

Was ist ein Kürzeste-Wege-Problem - gts systems

gts uses cookies to personalize your visit to gts-systems.com. By using the website, you consent to the use of cookies.