Erweiterung des Routenplanungsproblems (VRPTW)

Hallo,

nahezu alle Beschreibungen von Routenplanungsproblemen (Vehicle Route
Planning with Time Windows) die ich kenne beschreiben im Wesentlichen die
vollständige Zuordnung von Bedarfen (Liefer.- bzw. Abholmengen) zu Touren
bzw. Fahrzeugen. Bei manchen neueren Arbeiten kommt unter Umständen noch
eine dynamische Komponente (Kunde ruft an während Fahrzeug unterwegs ist)
hinzu.  (Die eigentliche Problembeschreibung steht am Ende des Postings
falls Sie jemanden interessiert*)

Leider kenne ich keine einzige Arbeit die sich mit der Planung von
Tagestouren, die für jeweils einen Tag lediglich einen Teil der vorhandenen
Bedarfe befriedigt, befasst.

Anders ausgedrückt, gerade bei den weiten Touren sind wir bemüht diese max.
1-2 mal / Woche zu fahren. Wir wissen (aus Erfahrung) wenn ein offener
Auftrag beispielsweise in einer Ortschaft 300 km vom Depot entfernt vorliegt
das wahrscheinlich noch weitere Aufträge folgen werden. Deswegen bemühen wir
uns diese Aufträge zusammenzufassen bzw. den Auftrag auch mal
"liegenzulassen"

Auch die meisten Arbeiten zu dynamischen VRPs die ich gelesen habe sind
nicht wirklich das Gelbe vom Ei. Diese basieren meist auf der bereits
beschriebenen vollständigen Aufteilung der Bedarfe und dem anschließenden
Ändern des Routenplanes bei neu hinzukommenden / wegfallenden Aufträgen. Ein
menschlicher Planer mit seiner Erfahrung leistet hier deutlich mehr.

Nun zu meiner bisher gefundenen Lösung :

Ich verwende zum Setup eine relativ einfache Konstruktionsheuristik und
anschließend einen genetischen Algorithmus zur Lösung des VRPTW. Für mein
eigentliches Problem habe ich auch einen Ansatz entwickelt der mich aber
noch nicht ganz befriedigt.

Meine Überlegung geht dahin die Kunden in zwei Gruppen aufzuteilen, eine
Muss Gruppe die alle Kunden umfasst die innerhalb eines bestimmten
Zeitfensters (beispielsweise die nächsten 3 Werktage) abgeholt werden müssen
und gleichzeitig innerhalb eines Tages gefahren werden können sowie dem
Rest. In einem ersten Schritt löse ich das VRPTW für die Muss Kunden wie
gehabt. Der Optimierungsvorgang bricht nach einer voreingestellten Anzahl an
Generationen ab wenn "noch Luft ist" für weitere Optimierungen. In einem
zweiten Schritt plane ich die Kann - Kunden hinzu. Dazu habe ich 3
zusätzliche Mutationsoperatoren implementiert - Kann Kunde hinzufügen, Kann
Kunde entfernen, kann Kunde "austauschen"  - die Muss Kunden bleiben immer
im Routenplan.

Die Bewertungsfunktion minimiert die Durchschnittsentfernung zu den Kunden
unter Einbeziehung der Priorität des Kunden.

Das Ergebnis ist, nun ja,  passabel. Allerdings konvergiert das Verfahren
sehr langsam (was wohl aufgrund der Größe des Suchraumes so ist) so das ich
mir derzeít ganz und gar nicht sicher bin ob ich nicht mit einer
entsprechend "tieferen" (sprich längeren bzw. auf einem größeren
Cluster
laufenden) Suche weiterkommen würde bzw. bessere Ergebnisse erzielen würde.

Hat evtl. jemand einen Link für mich, oder Anregungen, oder irgendwas was
mich auch nur ein wenig weiterbringt ?


cu Ha-Jö





Wir sitzen mit unserem Unternehmen fast in der Mitte Bayerns (Großmehring b.
Ingolstadt). Für die Stiftung GRS sammeln wir bei ca. 11000 verschiedenen
Sammelstellen, verteilt über ganz Bayern (ca. 40-50 Aufträge werktäglich)
Trockenbatterien ein und lagern diese bis zum Weitertransport bei uns
zwischen. Für die Erledigung eines Auftrages stehen uns max. 12 Werktage
(Samstag zählt als Werktag) zur Verfügung.  Bei dem hier beschriebenen
Problem zählt interessiert momentan nur die Sammlung. Zwischenlagerkapazität
kann als unendlich angenommen werden.

Gleichzeitig haben wir noch ca. 3000 Kunden bei denen wir in
unterschiedlichen Intervallen verschiedene Abfälle abholen und im gleichen
Depot zwischenlagern / weiterverarbeiten. Diese Kunden erteilen uns entweder
einen Auftrag zur Abholung weil deren Sammelbehälter voll sind / werden
(wird wie anderer Auftrag innerhalb von 12 Werktagen abgehandelt, ca. 5-7
täglich), oder aufgrund einer Art Fälligkeitsberechnung (Abholung nicht
zwingend).

Öffnungszeiten und feste Terminvereinbarungen, Lenk und Ruhezeiten und alle
sonst üblichen Restriktionen sind ebenfalls zu berücksichtigen.
Zusammenladeverbote exestieren nicht.

Aufgrund des max. Planungszeitraumes (mx. 12 Werktage) ergibt sich max.
700-750 offene Aufträge die zu verteilen sind, reale Größen bei
täglicher
Auftragsplanung sind ca.
150 - 250 Bedarfe aufzuteilen auf einen heterogenen Fuhrpark mit 7
verschiedenen Fahrzeugen.
[ Auf dieses Posting antworten ]
Antworten

Roland Damm (27.05.2008 23:56)