Strafen für schlechte Abbiegemanöver

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.