Buch: Planungsheuristiken für periodische, kantenbasierte Sammelprobleme der Entsorgungslogistik

 

Im Dr. Hut Verlag erscheint ein Fachbuch zum Thema Revierplanung der haushaltsnahen Sammlung. Darin werden sowohl die praktischen Probleme bei der Planung von periodischen Sammel- und Tourenplanungsprobleme angesprochen. Gefolgt von einer Reihe von verschiedenen Verfahren, die Lösungen anbieten. Besondere Aufmerksamkeit sind die sog. “akzeptablen” Lösungen, die auch von manuellen Planern akzeptiert würden. Dafür sind eigens neue Verfahren und Vergleichskriterien erstellt worden, um menschlichen Akzeptanz messbar zu machen. (ISBN 978-3-8439-0848-1)

 

Links:

http://www.dr.hut-verlag.de/978-3-8439-0848-1.html

Wartezeiten bei zyklischen Bedienungen an Kanten

Bei der Betrachtung von periodischen Kantenproblemen gibt es einen Planungshorizont H. In H sollen Kanten / Jobs erledigt werden. Bis zur nächsten Bedienung der Kante gibt es dann ein Zeitfenster als Abstand zu der letzten Bedienung: einen Minimalen Abstand minspan (u) und einen maximalen Abstand maxspan(u) einer Kante u. Daraus ergibt sich eine Kombination comb(u) der möglichen Bedientage.
Bei einem Planungshorizont H von einer Woche gibt es np = 7  Perioden : { 1,2,3,4,5,6,7=np}, um täglich Bedienung durch zuführen, oder bei einer 2xwöchentlichen Bedienung einer Kante kann z.B. comb(u)  = {1,4} oder {2,5} sein. Da aber an Samstagen und Sonntagen keine Bedientage sind reduzieren sich die Möglichkeiten:

• 1 mal pro Woche: {1},{2},{3},{4},{5} // Mo, ... Fr
• 2 Mal pro Woche: {1,4}, {2,5}
• 5 mal pro Woche: {1,2,3,4,5} // täglich

Periodizität an den Kanten

Periodische Kantenprobleme

An m Kanten (Straßenabschnitten) in einem gerichteten Graph G  gibt es einen bestimmten Planungshorizont H mit einer Anzahl von np Perioden.
Jeder Job oder Kante hat einen bestimmte Frquenz. Dabei ist bei den ungerichteten Kanten darauf zu achten, dass nicht nur die Kosten einmalig für beide Kanten u und v anfallen, sondern auch die Frequenz f(u) gleich ist (f(u)  = f(inv(u)). So muss eine Kante u 1<= f(u) <= np mal im Planungshorizont H bedient werden.
Die Summe aller Frequenzen ns im Planungshorituont H zerteilt das Problem in bestimmte Tagesrhytmen. Unglücklicherweise können die Bedientage nicht willkurlich gewählt werden, sondern sie sollen auch Abstandsregeln einhalten; somit sollen 2 Bedientage in der Persiode wöchentlich nicht z.B. Montag-Dienstag stattfinden, sondern dazwischen mindestens ein Bedienpausentag liegen (z.B. Montag- Donnerstag).

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.