Strafen für schlechte Abbiegemanöver
Ein Weg, um in routingfähigen Graphen unvorteilhafte Abbiegemanöver darzustellen, ist besteht darin zwischen zwei Kanten Abbiegestrafen zu hinterlegen.
Das Betrifft Linksabbiegungen bei Ampeln oder sog. U-Turns, die sich mit größeren Fahrzeugen schwer durchführen lassen.
Bei dem o.a. Beispiel sind von der eingehenden Kante u vier verschiedene, zulässige Abbiegungen zu den Kanten v1,...v4 (turn (u,v1), turn (u,v2), ...) möglich .
Abbiegestrafen würden hier wegen des U-Turns zwischen u und v1 mit der Straf-Funktion pen (u,v1) abgebildet.
Um von einer Kante u zu einer Kante v einen zulässigen Pfad µ zu bekommen, werden nur zulässige Abbigemöglichkeiten (turns) in Betracht gezogen.
In der Liste der zu bedienenden Kanten µ werden bei der Berechnung der Kosten die Kosten der Quellkante u und die Kosten der Senke v nicht mit berücksichtigt.
Verbotene Abbiegemönover wenden in einer m x m Distanzmatrix D zwischen den m Kanten berücksichtigt, so dass sich die Distanzfunktion d(u,v) die kürzeste, zulässige Entfernung zwischen den Kanten u und v berechnet. Die Distanzmatrix pro Pfad kann via Dijkstra in O( m log m) berechnet werden.
v1 | v2 | v3 | v4 | |
u | U-Turn | L-Turn | 0 | 0 |
Zusätzlich sind noch die Regiefahrten ins Revier und zum Depot zu berücksichtigen.
Keine Kommentare:
Kommentar veröffentlichen