Tourenplanung mit dem Savings-Verfahren (Clarke-Wright)
Bei der Tourenplanung geht es allgemein darum, eine gegebene, nach Gewicht und Volumen sowie Bestimmungsorten spezifizierte Menge von Warensendungen durch eine Flotte von Auslieferungsfahrzeugen mit begrenzten Kapazitäten (bzgl. Gewicht, Volumen, Tourdauer) an die Abnehmer auszuliefern. Dies soll zu minimalen Auslieferungskosten erreicht werden. Oft wird davon ausgegangen, daß die Auslieferungskosten dann minimal sind, wenn die Gesamtlänge aller gefahrenen Touren minimal ist. Ein Beispiel hierzu ist in Günther/Tempelmeier (2020a) beschrieben.
Tourenplanung wird in einer unübersehbaren Anzahl von Software-Produkten angeboten. Dabei kommen unterschiedliche Optimierungsmethoden zum Einsatz. Das wohl bekannteste und auch von vielen Software-Herstellern implementierte Verfahren ist das Saving-Verfahren von Clarke und Wright (1964). Die Ursprungsversion dieses Verfahren wurde mehrfach modifiziert. In diesem Modul wird die einfachste "Standard-"Version des Verfahrens implementiert.
Ausgangspunkt ist ein Straßennetz mit einem Depot-Standort $0$ und mehreren Abnehmerorten. Zur Belieferung der Abnehmer stehen Fahrzeuge mit identischer Kapazität, die in Mengeneinheiten beschrieben wird, zur Verfügung. Jeder Abnehmerort soll eine Lieferung erhalten. Die Gesamtmenge aller Lieferungen ist größer als die Fahrzeugkapazität, so daß mindestens zwei Fahrzeuge eingesetzt werden müssen. Daher entsteht - im Gegensatz zum Problem des Handlungsreisenden - nicht nur das Problem der Bestimmung der Rundreise eines Fahrzeugs, sondern es muß auch noch entschieden werden, wie die Abnehmer zu Touren zusammengefaßt werden sollen. Die Anzahl der Touren ist das Ergebnis der Planung.
Betrachten wir das folgende Netzwerk mit 10 Orten. Der Standort der Fahrzeugflotte (Depot) ist der Ort 2. Die Kapazität eines Fahrzeugs ist 40.
Die Streckenlängen und die Transportmengen sind in der folgenden Tabelle wiedergegeben:
| $c_{ij}$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | - | 0 | 0 | 0 | 0 | 343 | 0 | 1435 | 464 | 0 |
| 2 | 0 | - | 0 | 0 | 0 | 879 | 954 | 811 | 0 | 524 |
| 3 | 0 | 0 | - | 0 | 1364 | 1054 | 0 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | - | 0 | 0 | 433 | 0 | 0 | 1053 |
| 5 | 0 | 0 | 1364 | 0 | - | 1106 | 0 | 0 | 0 | 766 |
| 6 | 343 | 879 | 1054 | 0 | 1106 | - | 0 | 0 | 0 | 0 |
| 7 | 0 | 954 | 0 | 433 | 0 | 0 | - | 837 | 0 | 0 |
| 8 | 1435 | 811 | 0 | 0 | 0 | 0 | 837 | - | 0 | 0 |
| 9 | 464 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | - | 0 |
| 10 | 0 | 524 | 0 | 1053 | 766 | 0 | 0 | 0 | 0 | - |
| Menge | 20 | 0 | 15 | 5 | 10 | 5 | 10 | 20 | 8 | 10 |
Im betrachteten Beispiel sind die Strecken in beiden Richtungen befahrbar. Dies wird im graphischen Editor erreicht, indem man einen Pfeil von einem Ort $i$ zum Ort $j$ hin und einen Pfeil vom Ort $j$ zurück zum Ort $i$ einzeichnet.
Im Saving-Verfahren wird nun zunächst davon ausgegangen, daß jeder Abnehmer direkt in einer Einzelfahrt (Pendeltour) beliefert wird. Diese Lösung erfordert $n$ Hin- und Rückfahrten und verursacht offensichtlich extrem hohe Fahrkosten.
Die insgesamt zurückzulegende Distanz beträgt bei einem Depot $0$ und zwei Orten $i$ und $j$ genau $d_{0i}+d_{i0}+d_{0j}+d_{j0}$. Werden nun die Orte i und j zu einer Tour verbunden, dann muß zwar zusätzlich eine Strecke der Länge $d_{ij}$ gefahren werden; dem steht aber eine Einsparung der Rückfahrt von Ort $i$ ($d_{i0}$) und der Hinfahrt zum Ort $j$ ($d_{0j}$) gegenüber. Bei Verbindung der Ort $i$ und $j$ ergibt sich also insgesamt eine Fahrstrecken-Ersparnis (saving) in Höhe von $s_{ij}=d_{i0}+d_{0j}-d_{ij}$. Jeder Verbindungsstrecke zweier Kundenstandorte kann ein solcher Saving-Wert zugeordnet werden. Im weiteren Verlauf des Verfahrens, wenn "echte" Touren gebildet worden sind, betrachtet man als mögliche Orte, zwischen denen Saving-Werte berechnet werden, die Startorte und die Endorte der Touren.
Um die Saving-Werte berechnen zu können, muß man für ein gegebenes Straßennetz zunächst die Entfernungen zwischen allen Orte berechnen. Dazu kann man das Floyd-Warshall-Verfahren einsetzen. Im Beispiel erhält man folgende Entfernungsmatrix:
| $d_{ij}$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 1222 | 1397 | 2609 | 1449 | 343 | 2176 | 1435 | 464 | 1746 |
| 2 | 1222 | 0 | 1933 | 1387 | 1290 | 879 | 954 | 811 | 1686 | 524 |
| 3 | 1397 | 1933 | 0 | 3183 | 1364 | 1054 | 2887 | 2744 | 1861 | 2130 |
| 4 | 2609 | 1387 | 3183 | 0 | 1819 | 2266 | 433 | 1270 | 3073 | 1053 |
| 5 | 1449 | 1290 | 1364 | 1819 | 0 | 1106 | 2244 | 2101 | 1913 | 766 |
| 6 | 343 | 879 | 1054 | 2266 | 1106 | 0 | 1833 | 1690 | 807 | 1403 |
| 7 | 2176 | 954 | 2887 | 433 | 2244 | 1833 | 0 | 837 | 2640 | 1478 |
| 8 | 1435 | 811 | 2744 | 1270 | 2101 | 1690 | 837 | 0 | 1899 | 1335 |
| 9 | 464 | 1686 | 1861 | 3073 | 1913 | 807 | 2640 | 1899 | 0 | 2210 |
| 10 | 1746 | 524 | 2130 | 1053 | 766 | 1403 | 1478 | 1335 | 2210 | 0 |
Nach der obigen Formel für die Saving-Berechnung erhält man dann folgende Savings-Matrix:
| $s_{uv}$ | 1 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | - | 1758 | 0 | 1063 | 1758 | 0 | 598 | 2444 | 0 |
| 3 | 1758 | - | 137 | 1859 | 1758 | 0 | 0 | 1758 | 327 |
| 4 | 0 | 137 | - | 858 | 0 | 1908 | 928 | 0 | 858 |
| 5 | 1063 | 1859 | 858 | - | 1063 | 0 | 0 | 1063 | 1048 |
| 6 | 1758 | 1758 | 0 | 1063 | - | 0 | 0 | 1758 | 0 |
| 7 | 0 | 0 | 1908 | 0 | 0 | - | 928 | 0 | 0 |
| 8 | 598 | 0 | 928 | 0 | 0 | 928 | - | 598 | 0 |
| 9 | 2444 | 1758 | 0 | 1063 | 1758 | 0 | 598 | - | 0 |
| 10 | 0 | 327 | 858 | 1048 | 0 | 0 | 0 | 0 | - |
Offensichtlich ist die Ersparnis umso größer, je näher die beiden betrachteten Orte beieinander liegen und je weiter sie vom Depot entfernt sind. Andererseits kann ein Saving-Wert auch negativ sein. Die Verbindung der beiden Orte führt dann zu einer Erhöhung des gesamten Fahrstrecke. Eine solche Verbindung wird man wohl nicht in die Lösung einbeziehen.
Nach der Bestimmung der Saving-Werte wird nun - ausgehend von der Start-Lösung (Pendeltouren), bei der jeder Abnehmer im Rahmen einer Einzelfahrt beliefert wird - schrittweise versucht, jeweils die beiden Abnehmerstandorte zu einer Tour zusammenzufassen, deren Verbindung den größten Saving-Wert aufweist. Dabei wird jeweils darauf geachtet, daß diese Verbindung zulässig ist, d.h.
Im Beispiel hat die Verbindung $9-1$ (oder $1-9$, wegen der symmetrischen Entfernungen) den größten Saving-Wert. Damit ergibt sich folgende neue Zwischenlösung:
Im nächsten Schritt erhalten wir:
und nach einigen weiteren Schritten ergibt sich folgende optimale Lösung:
Die Lösung lautet:
| Lösung | |||
|---|---|---|---|
| 2 - 6 - 1 - 9 - 2 | Menge = 33 | Tourlänge = 3372 | |
| 2 - 10 - 5 - 3 - 2 | Menge = 35 | Tourlänge = 4587 | |
| 2 - 4 - 7 - 8 - 2 | Menge = 35 | Tourlänge = 3468 | |
| Gesamtlänge = 11427.00 | |||
Bei der Implementierung des Saving-Verfahrens bieten sich zahlreiche Möglichkeiten. So ist in der ursprünglichen Formulierung des Verfahrens durch Clarke und Wright vorgesehen, alle Saving-Werte vor Beginn der eigentlichen Touren-Konstruktion, d.h. verfahrensextern zu berechnen und in einer Liste zu speichern, die man leicht sortieren kann. Das ist auch die Vorgehensweise, die in diesem Modul implementiert ist.
Symbole:
| i | Indix eines Ortes |
| c(i,j) | Bewertung (Entfernung, Kosten, etc.) des Pfeiles von i nach j (Eingabewert) |
| s(u,v) | Saving-Wert zwischen Ort u und v (wird intern berechnet) |
| d(i,j) | Entfernung vom Ort i zum Ort j (wird intern berechnet) |
Annahmen:
Ansicht:
- Günther/Tempelmeier (2020b)
Datenschutz | © 2021 POM Prof. Tempelmeier GmbH | Imprint