Routensuche in zeitlich variablen Netzen

Beschreibung

Das Buch beschäftigt sich mit Routensuchalgorithmen, die eine optimale Route zwischen genau einem Startpunkt und genau einem Zielpunkt berechnen. Die Verfahren verwenden einen Restdistanzschätzer zur Beschleunigung der Suche und können zusätzlich auf dynamische Veränderungen der Kosten innerhalb des Graphenmodells effizient reagieren. Verschiedene Anwendungen wie zum Beispiel die Fahrzeugnavigation oder auch das Routing von Datenpaketen im Internet bedienen sich solcher Methoden der Routensuche. Dabei wird meist von einem Start zu einem Zielpunkt eine optimale Route gesucht und es können Störungen oder Sperrungen im Netz auftreten, die zu Routenveränderungen führen. Die Aufgabe der hier betrachteten Verfahren besteht darin auf Grund von einer schon berechneten optimalen Route eine Neue zu berechnen, sofern eine Veränderung im Netz die Gültigkeit der zuerst berechneten Route beeinflusst. Neben der Betrachtung existierender dynamischer Algorithmen wird für das beschriebene Problem auch ein neues Verfahren namens Dynamic A* vorgestellt. In verschiedenen Szenarien werden anschließend diese dynamischen Verfahren untersucht und miteinander verglichen. Dazu dienen eine reale Straßenkarte und ein künstlich erzeugtes Grid als Grundlage. Die Ergebnisse dieser verschiedenartigen Tests zeigen dann einige Eigenschaften der betrachteten Verfahren.

Autor*in

Sven Baselau

Themen in »Routensuche in zeitlich variablen Netzen«

Graphentheorie Dynamik Straßenverkehr A* Restdistanzschätzer Informatik kürzeste Wege Routensuche

Stimmen zu »Routensuche in zeitlich variablen Netzen«

Details

Link teilen