Das Verfahren gliedert sich in eine äußere und in eine innere Iteration (Abbildung 106).
- Die äußere (globale) Iteration mit dem Iterator n dient zur Routensuche. Diese Schleife wird so oft durchgeführt, bis entweder n = N oder bis keine neuen kürzesten Routen gefunden werden.
- Die innere Iteration mit dem Iterator m dient zur Aufteilung der Belastung auf die Routen. Diese Schleife wird so oft durchgeführt, bis entweder m = M oder bis die Abweichungen der Widerstände auf den Netzobjekten und die Abweichung der Belastungen auf den Routen zwischen zwei Iterationsschritten sehr klein wird.
Abbildung 106: Ablauf der Stochastischen Umlegung
Die Alternativroutensuche durch stochastische Variation der Widerstände ist eng verwandt mit anderen Verfahren zur Bestimmung k-kürzester Wege und hat mit diesen den Nachteil gemeinsam, dass oft neue Routen gefunden werden, die sich nur unwesentlich von vorherigen Routen unterscheiden. Solche Routen sind unerwünscht, da sie die Belastungssituation im Netz kaum verändern und lediglich die Routenmenge aufblähen, was zu verlängerter Rechenzeit und höherem Speicherbedarf führt. Im Rahmen der Stochastischen Umlegung wird deshalb ein Umwegtest angeboten, der eine Route r2 verwirft, wenn bereits eine Route r1 existiert, die bis auf ein Teilstück mit r2 übereinstimmt, und dieses Teilstück in r2 wesentlich länger ist als in r1. Genauer gesagt, wird r2 gegenüber r1 verworfen, wenn Folgendes gilt (Abbildung 107):
- r1 = AT1B
- r2 = AT2B
- Fahrzeit(T2) > Faktor • Fahrzeit(T1)+ Summand
Abbildung 107: Verwerfen von Routen
Die Teilrouten A, B können leer sein, falls sich das Teilstück am Anfang oder am Ende der Routen befindet.
Gibt es Bewertungen auf Ebene der Wege, d.h. wird zum allgemein geglätteten Widerstand des Verkehrssystems zusätzlich ein Widerstandsterm auf Ebene des Wegs für ein Nachfragesegment definiert, wird dieser Umwegtest modifiziert. Der Grund dafür ist, dass die Masche eine für die Bewertung des Weges bestimmende Strecke umgeht und daher trotzdem interessant ist. Ergibt der Umwegtest, dass ein Weg unterlegen ist, müssen beide Wege auf der Ebene des Weges, d.h. inklusive der Abschnitte A und B bewertet werden. Wenn der unterlegene Weg bezüglich mindestens eines Koeffizientensatzes die bessere Bewertung des Weges hat, wird er beibehalten. Koeffizientensätze werden dazu verwendet mehrere unterschiedliche Wege zu erzeugen. Da der zusätzliche Widerstandsterm pro Nachfragesegment definiert wird, wird auch dieser Teil des Tests je Nachfragesegment durchgeführt.
Der Widerstand aus den Eigenschaften des Weges ist ein Element der Routenwahl, nicht aber der Suche. Daher ist anzustreben, die Definition des Suchwiderstands möglichst vollständig zu halten und nur dann Elemente auf der Ebene der Wege zu verwenden, wenn sich diese aus der Teilroutenmenge definieren.
