So, weiter geht's.
Unterplanung ist damit abgeschlossen.
Kennengelernt hatten wir jetzt das Up-Location-Problem zum Schluss,
das Warehouse-Location-Problem und das Standard Weber-Modell.
Der nächste Schritt, wenn es jetzt...
Also das waren alles sehr statische Sachen, also die Entscheidungen,
die da getroffen werden, sind langfristig.
Es geht um die Entscheidung, bauen oder nicht bauen, wenn bauen, dann
wohin.
Und wir gehen jetzt mehr in den operativen Teil rein, und dazu die
Kürenplanung, weil die Rahmenbedingungen von so einem Netzwerk sind
dann schon abgesteckt, aber die Frage ist nun, wie muss ich meine
Transporte durchführen, um in diesem Logistiknetzwerk so günstig wie
möglich zu fahren.
Das ist bei diesem Bildchen, die wir eben gesehen haben, zum Hub-and
-Spoke -Netzwerk, der Teil, der ganz vorne ist, also die Vorlauftouren
zum Dekot, den kann man da ansiedeln, beziehungsweise die
Nachlauftouren vom Dekot weg zu den einzelnen Endkunden.
Bevor wir hier auf diese beiden Modelle eingehen, erstmal grundlegend
verschiedene Verfahren, mit denen man Tourenplanung vornehmen kann.
Tourenplanung an sich ist auch wieder ein schweres Problem in der
Informatik, das heißt, eine exakte Lösung zu finden, ist sehr
zeitaufwendig, beziehungsweise unmöglich, weil die Verfahren da
einfach noch nicht so weit sind.
Und dazu hat man gerade dann auch in der Vergangenheit, als die
Rechenleistung noch bei weitem nicht so hoch war, wie sie heute ist,
sehr viele Hilfskonstrukte, Hilfsalgorithmen sich dafür überlegt, die
man eingesetzt hat, die aber auch heute noch eingesetzt werden müssen.
In kommerzieller Software zur Tourenplanung findet man häufig noch
diese Heuristiken, weil einfach die Aufgabenstellung so schwer ist,
dass diese exakten Verfahren bei großen Problemen nach wie vor eine
Chance haben, aber eine Heuristik eingesetzt wird.
Man nimmt in Kauf, dass die Lösung nicht optimal ist.
Sie ist gut, aber nicht optimal.
Manchmal ist sie optimal, aber man hat keine Garantie für die
Optimalität, kriegt aber dafür eine gute Lösung in relativ kurzer
Zeit.
Eines der bekanntesten Verfahren ist der Sweep-Algorithmus.
Bei diesem Sweep-Algorithmus beginnt man im Depot, dieses rote, das
blaue sind die Kunden, beginnt im Depot mit einer sogenannten Sweep
-Line.
Und mit dieser Sweep-Line streiche ich jetzt wie mit einem Radar gegen
den Uhrzeigersinn überall meine Kunden.
Und jeweils in der nächsten Sekunde auf diese Sweep-Line wird meine
aktuelle Tour hinzugefügt.
Und die Restriktionen, die dabei einzuhalten sind, sind beispielsweise
auch hier wieder die Kapazitätsrestriktionen, dass man Fahrzeug nicht
mehr als C-Transporteinheiten mitnehmen kann.
Und sobald ich dann so viele Kunden abgefahren habe, dass dieses Ziel
überschritten wird, muss ich diese Tour beenden.
Also ich gehe jetzt nach und nach über diese Punkte drüber, habe in
diesem Beispiel die Restriktion, dass nicht mehr als drei Kunden auf
einer Tour sein dürfen, packe also diesen zweiten Loch hinzu, packe
den dritten Loch hinzu, mache dann diese rote Tour, mache das für die
übrigen genauso.
Und nun, es sind jetzt insgesamt vier Touren, drei Touren mit drei
Kunden drauf, eine Tour mit nur einem Kunden, so eine Stichtour, und
damit auf jeden Fall mal eine zulässige Lösung gefunden.
Ob das jetzt eine gute Lösung ist, sei dahingestellt, aber es ist eine
zulässige Lösung.
Und in einem weiteren Schritt könnte man jetzt, dadurch dass es hier
ein sogenanntes Eröffnungsverfahren ist, das heißt ein Verfahren, bei
dem ich erstmal eine zulässige Lösung suche, ohne den Anspruch darauf,
dass es optimal ist oder eine sehr gute ist, kann ich mit
Verbesserungsverfahren die gefundene Eröffnungslösung verbessern.
Beispielsweise könnte man sich jetzt überlegen, ob denn dieser
einzelne Kunde wirklich einzeln angefahren werden muss, oder ob ich
vielleicht aus einer dieser drei Touren, zum Beispiel dieser
Heldenlaune, dass ich das aufsplitte und mache zwei Zweier-Touren
draus.
Wäre eine Möglichkeit, kommen wir gleich noch dazu, wenn wir bei den
Eröffnungsverfahren, bei den Verbesserungsverfahren ankommen.
Also das sweep-Algorithmus ist ein sehr einfacher Algorithmus.
Ein weiterer einfacher Algorithmus, auch wieder eine Heuristik, ist
das Savingsverfahren.
Bei dem Savingsverfahren beginnt man nun mit Ende-Touren.
Das heißt, ich tue so, als würde ich jeden LKW vom Depot zu meinem
Kunden fahren lassen, um ihn dann auch wieder zurückfahren zu lassen,
ohne eine tatsächliche Tour zu bilden.
Jetzt suche ich mir Ersparnisse raus.
Was könnte ich nämlich sparen, wenn ich zwei dieser Kunden auf eine
Tour legen will.
Ich greife nochmal die beiden raus.
Das ist jetzt die Ende-Tour, die entsteht, wenn ich möglichst gut
einzeln zu diesen Kunden fahre.
Ich überlege mir, könnte ich denn diese beiden Äste einsparen, wenn
ich zusätzlich von einem blauen Punkt zum nächsten blauen Punkt fahre.
Also hier noch eine Strecke einüben.
Ich habe eine Ersparnisse, aber dafür auch Zusatzkosten.
Und kriege einen sogenannten Savingswert, also den Savingswert, wenn
ich die Ersparnisse, diese zwei langen Strecken, minus Zusatzkosten
rechne und kann dann gucken, wo würde ich einsparen.
Das mache ich jetzt paarweise für alle Kombinationen mit blauen
Punkten, die ich habe, auf meiner Tour.
Und kann mir nun anschauen, auf welcher Tour, wo was zusammenliegt,
kriege ich die größere Ersparnisse raus.
Heißt also, für diesen Algorithmus, nachdem wir es mit Einzeltouren
initialisiert haben, gucken, prüfe für die zwei Touren, wie groß die
Ersparnisse bei Zusammenlegung ist, legen wir im dritten Schritt die
Touren zusammen, die den höchsten Savingswert besitzen.
Und man sieht dann, wie sich diese Touren ändern.
Wenn dann keine Ersparnisse mehr möglich ist, kriege ich dieses
Verfahren ab.
Dann habe ich auch wieder eine Lösung gefunden, die gut ist,
vielleicht auch besser als die Lösung im Sweep-Verfahren, muss aber
nicht sein, und könnte mit dieser jetzt weiterrechnen.
Also hier habe ich wieder ein Eröffnungsverfahren dargestellt.
Ich gehe nochmal zurück zum Sweep-Verfahren,
wo wir hier so drüber streichen.
Bei welcher Anordnung von Kunden könnte ich dann relativ sicher sagen,
dass das Sweep-Verfahren eine schlechte Lösung ist.
Im Moment sind diese Kunden hier gleichmäßig verteilt.
Genau, also wenn ich Kunden geclustert habe, das beispielsweise im
Norden ein Cluster ist, im Süden ist ein Cluster, und ich muss jetzt
aufgrund dieses Verfahrens einmal von Norden nach Süden fahren, und
das ist dann natürlich eine große Schwierigkeit.
Das wäre jetzt die unten günstige Lösung.
Genau, wenn das Depot nicht mittig liegt, sind die Lösungen meistens
auch nicht mehr so schön.
Also wenn ich jetzt vorstelle, dass dieses Depot irgendwo ganz unten
links am Rand liegt, und meine ganzen Kunden irgendwo ganz oben
rechts, dann kann es ja wirklich sein, dass wir im Sweep-Verfahren
auch ziemlich schlechte Lösungen ausprobieren werden.
Also man muss halt wissen, es dient in erster Linie dazu, einfach mal
eine zulässige Lösung zu finden.
Verbessern kann man das Ganze dann auch im Nachhinein.
Zu den exakten Verfahren komme ich dann jetzt, nämlich
beispielsweise mit dem kapazitierten Vehicle-Routing-Problem.
Bei diesem Problem ist es von der Problemstellung her ein Problem mit
wenig Einschränkungen, also wenig Rezeptionen, wenig Annahmen für die
Realität.
Also Spezialfälle könnten damit keine abgebildet werden, wie
beispielsweise, dass ich zu einem bestimmten Zeitpunkt irgendwo
ankommen muss, oder das könnte abgebildet werden, dass ich nicht mehr
als drei Kunden auf eine Tour bringe.
Das könnte abgebildet werden.
Aber es ist ein sehr generalistischer Einsatz überhaupt.
Also für die Realität hat man auch Verfahren, die die Statistik mit
reinnehmen.
Ich war vorhin bei der robusten Tourenplanung.
Wenn es darum geht, von welcher Zeit kann ich jetzt ausgehen für
meinen Transport von München nach Hamburg, so etwas wird in diesem
Realitätskreis, in diesem einfachen Modell nicht abgehandelt.
Aber es ist ein sehr wichtiges Modell, nicht nur für die
Tourenplanung, für den Transport, sondern beispielsweise kann man es
einsetzen bei verschiedenen Bedingungen oder bei der Frage, wie muss
ich denn über eine Leiterplatte fahren, um meine ganzen Höhepunkte,
möglichst wenig Strecke für den Roboterarm zurückzulegen.
Teilweise, wenn ich mit mehr Robotern auf dieser Höheplatte arbeite.
Unterschied zum Travelling-Salesman-Problem.
Hier ist beim Travelling-Salesman-Problem, muss ich mit einem
Handlungsreisen oder analog jetzt mit einem Fahrzeug alle Punkte
anfahren.
Hier habe ich mehrere Fahrzeuge zur Verfügung, um alle Punkte
anzufahren.
Und will jetzt wissen, mit welchem Fahrzeug muss ich zu welchem Knoten
fahren, um in Summe die kürzeste Strecke zurückzulegen.
Und die Anzahl der Fahrzeuge ist jetzt hier dargestellt durch das
Fahren.
Die Kosten sind hier auch wieder dargestellt durch CIJ.
Das kostet beispielsweise die Zeit, die Entfernung, um von I nach J zu
kommen.
Und auch hier wieder das XIJ, das binär ist, also ich fahre über IJ
oder ich fahre nicht von I nach J.
Die erste Nebenbedingung.
Und die zweite Nebenbedingung stellt sicher, dass in jedem Knoten, mit
dem ich reinfahre, also für jedes IJ, dass ich in jedes IJ einmal
reinfahre, das ist die Nebenbedingung 3.
Und die Nebenbedingung 4 stellt sicher, dass ich aus jedem dieser IJ
auch rausfahre.
Also da wo ich hinfahre, also wenn ich auf Stuttgart reinfahre zu
meinem Knoten, muss ich auch von Stuttgart wieder wegfahren.
Die Nebenbedingungen 4 und 5, die sagt mir, dass ich von allen I, in
denen ich kommen könnte, immer wieder zu meinem Dekot zurückkehren
muss.
Dekot ist hier wieder dargestellt mit der Null.
Und zwar mit allen Fahrzeugen.
Wenn ich vier Fahrzeuge habe, muss ich mit allen vier Fahrzeugen
wieder im Dekot ankommen.
Nebenbedingung 5.
Und wenn ich vier Fahrzeuge habe, jetzt bin ich wieder in
Nebenbedingung 6, muss ich auch mit allen Fahrzeugen von diesem Dekot
abfahren.
Jetzt haben wir noch die siebte Nebenbedingung.
Und das ist die, die diese ganzen Transportprobleme so schwer macht.
Das ist nämlich die Nebenbedingung, die sicherstellt, dass ich keine
sogenannten Kurzzüge in meinem Transport habe.
Habt ihr mal eine Idee, oder kennt ihr Kurzzüge?
Ich male euch das mal auf, als Beispiel.
Die ersten Nebenbedingungen nämlich.
Sagen wir mal, wir haben hier unser Depot 0, wo wir losfahren.
Und diese eine Nebenbedingung, ich glaube es war die 5 und 6, die hat
gesagt, immer wenn ich aus dem Depot rausfahre zu einem Knoten, muss
ich auch wieder zum Depot zurückfahren.
Das war ja abgebildet durch zwei Nebenbedingungen.
Gleichzeitig hatte ich aber auch eine Nebenbedingung, die sagt, dass
ich, das ist dann dieser Teil,
in dem Knoten, in den ich reinfahre, hier, muss ich auch wieder
rausfahren.
Also ich habe jetzt eigentlich schon vier Nebenbedingungen, die hier
greifen.
Nämlich einmal hier, da wo ich rausfahre, das muss sichergestellt
sein.
In diesem Fall jetzt nur mit, hier ist jetzt K gleich 1 für dieses
Beispiel.
Ich habe die Nebenbedingungen, wo ich sage, ich muss dann auch
irgendwo reinfahren in meinen Knoten.
Hier.
Ich habe dann die Nebenbedingungen, ich muss aus diesem Knoten wieder
rausfahren.
Und ich habe die Nebenbedingungen, dass ich ins Depot wieder
zurückfahren muss.
Jetzt, nach der Formulierung, ohne diese sogenannte
Kurzzyklusbedingungen, könnte sowas passieren.
Ich fahre aus meinem Depot raus, fahre zu meinem Knoten, fahre wieder
zurück, das ist alles super.
Aber ohne die Kurzzyklusbedingungen wäre es auch eine zulässige
Lösung, dass ich bei weiteren Knoten, die ich habe,
einfach von Knoten 2 zu 3 fahre und von Knoten 3 zu 2 wieder zurück.
Dann sind diese ersten vier Nebenbedingungen alle nicht verletzt.
Aber ein bisschen dumm an der Geschichte ist, ich habe keine wirkliche
Tour, weil ich ja nicht vom Depot aus beginne.
Und das muss ich sicherstellen mit diesen Nebenbedingungen, um die
Kurzzyklen zu vermeiden.
Also das hier ist jetzt die 2-3 oder die 0-1, das sind in diesem Fall
jetzt Kurzzyklen, weil ich einfach nicht beim Depot starte.
Und diese Formulierung mit diesem Delta, die werdet ihr ziemlich oft
sehen bei der Formulierung von Transportproblemen.
Und deshalb für die, die das später mal weitermachen werden,
Transportoptimierung, hier ein paar zusätzliche Infos zu der
Schreibweise, die man da verwendet.
Die Nebenbedingungen, die wir da ja stehen hatten, ich schreibe sie
hier nochmal auf, also ihr habt sie ja auf der Folie drauf,
ist gewesen, dass ich ein I habe, das kein Element von S ist und ich
habe ein J, das ein Element von S ist.
S ist jetzt einfach eine Teilmenge aus der Menge all meiner Knoten V.
Also ich habe Knoten von 1 bis 10 und S ist beispielsweise die Menge
1, 2, 3 oder sagen wir 2, 3, 4, wenn 1 das Depot ist.
Diese Nebenbedingung, die hier steht, sagt, xij muss größer sein als
dieses Gamma von S.
Und was bedeutet nun dieses Gamma?
In diesem Fall hier, für den Fall des kapazitierten Vehicle Routing
Problems, kann man das Gamma wie folgt ausrechnen.
Gamma von S ist größer oder gleich der Summe über alle Bi durch die K,
für alle I, die aus der Menge dieses Schnitts kommen.
Bi sind hier die Bedarfe, die jeder Knoten hat.
K ist die Anzahl der Fahrzeuge und das heißt, wenn ich jetzt alle
meine Bedarfe aufaddiere, dividiert durch die Anzahl der Fahrzeuge,
weiß ich, wie viele Fahrzeuge ich mindestens brauche, um dieses
Transportproblem überhaupt zu lösen.
Also ich kann mir das schon mal als eine Mindestschranke an Fahrzeugen
definieren.
Heißt hier, wenn ich beispielsweise nach Berechnungen von Bi durch K
zu dem Ergebnis komme, ich brauche sieben Fahrzeuge insgesamt,
beziehungsweise ich muss siebenmal fahren, andersrum, ich habe
meinetwegen fünf Fahrzeuge, muss aber mit denen siebenmal fahren,
würde ich dieses Gamma entsprechend gleich 7 setzen.
Es wird ein bisschen klarer, wenn ich das mit den Schnitten, die dabei
entstehen, in unserer Lösungsmenge erkläre.
Es gibt nämlich dabei so ein paar Konventionen, die ihr wie gesagt
häufiger finden werdet.
Also hier mal ein Beispiel.
1 ist jetzt das Depot, ich habe die 2, ich habe die 3, eine 4, eine 5
und eine 6.
Und ich sage, das S ist einfach mal die Menge 1, 2, 3.
Und hier haben wir V ohne S, in dem Fall jetzt die Menge 4, 5, 6.
Und was ich jetzt auch habe, ist in diesem Beispiel Verbindungen
zwischen diesen Knoten.
Also hier quellt eine 3 draus, macht mal hier eine 2 draus, hier eine
6 und hier eine 5.
Ich habe eine Verbindung von 1 nach 2, ich habe eine Verbindung von 1
nach 5, eine Verbindung von 2 nach 3, eine von 5 nach 6, eine von 5
nach 4, eine von 4 nach 6 und eine von 3 nach 6.
Gut, die sind alle vollständig.
Ich habe meine Knotenmenge V, 1, 2, 3, 4, 5, 6, dargestellt.
Ich habe den Schnitt, das S, 1, 2, 3.
Und ich habe die Menge meiner Kanten.
Nämlich für alle S, die eine Teilmenge sind von V, gilt, dass ich
Kanten habe, I von S.
Und diese Kanten setzen sich zusammen aus den Kombinationen I und J.
Und I und J sind ein Element von S.
Das heißt, welche Kanten habe ich jetzt hier dargestellt mit E von S?
1, 2 und 2, 3, genau.
In diesem Beispiel jetzt sind das die Kanten 1, 2 und 2, 3.
Und in diesem E oder Betrag von dieser Geschichte, E von S, ist jetzt,
ich habe 2 Elemente drin, 2 Kanten.
Ich habe gleichzeitig Knotengrade, die auch häufig verwendet werden
bei dieser Formulierung.
Oder bei Formulierungen von Transportproblemen.
Die Knotengrade sagen mir, wie häufig wird in eine Knoten rein oder
raus gefahren.
Heißt, ich habe hier nochmal Delta, beispielsweise hier Delta von,
kann man das lesen?
Delta 4 ist 2.
Und warum?
Weil ich mit den zwei Kanten in diesen Knoten reingehe.
Also Knotengrad.
Hier beim Knoten 6, habe ich einen Knotengrad 3.
Bei drei Kanten diesem Knoten anfahren und so weiter.
Beispielsweise auch hier beim Knoten 2, habe ich einen Knotengrad von
2.
Also, ihr werdet häufig finden bei sowas das E von S.
Ihr werdet häufig finden den Knotengrad, der dargestellt ist.
Und ihr werdet, das ist das, was bei dieser Formulierung, die auf der
Folie drauf ist, dargestellt ist.
Nämlich der Schnitt, den habt ihr.
Und das ist allgemein formuliert.
Wie geht das mit dem Grün?
Das ist nämlich die Menge aller Kanten IJ aus I.
Mit der Eigenschaft, dass I aus dem S kommt.
Und J ist kein Element von dem S.
Oder genau umgekehrt, I ist kein Element von dem S, aber J ist ein
Element von dem S.
Könnt ihr das lesen?
Soll ich es nochmal vorlesen?
Passt.
Welche Menge ist denn hiermit gemeint?
1,5 und 3,6, ganz genau.
Also hier nochmal in grün.
Genau nämlich das, was hier die eine Menge verlässt und in die andere
Menge reingeht.
Das ist damit beschrieben.
Einmal und zweimal.
Also hier ist es dann die 3,6 und die 1,5.
Beziehungsweise ist hier jetzt das ganze 2.
Oder auch der Betrag davon ist 2, weil ich habe jetzt 2 Kanten, die
die eine Menge verlassen und in die andere Menge wieder reingehen.
Und was es jetzt noch zum Schluss gibt, wo man auch häufiger bei den
Graphen Sachen drüber stolpert, ist nämlich die Summe über die ganzen
Knotengerade aus der Menge S.
Und das ist nämlich einfach
die Summe über alle Knotengerade.
Also ich habe hier oben meine Knotengerade definieren können oder
herausfinden können.
Hier war es beispielsweise die 2, hier ist es die 3, hier ist es
nochmal die 2.
Hierfür habe ich Grad 2 und hierfür habe ich auch den Grad 2.
Das heißt die Summe für mein S beträgt hier 6.
Ah,
ich habe eine vergessen.
In meinem Beispiel habe ich hier von 3 nach 4 auch noch eine Kante
drin.
Also können wir hier nochmal ergänzen.
Hier kommt noch dazu von 3 nach 4.
Den Strich haben wir schon.
Und das heißt dieser Knotengrad hier bei der 3 ist nicht 2, sondern 3.
Und die Summe hieraus ist dann in diesem Beispiel 7.
Und was nun aus dieser Betrachtung des Graphen, was da immer gilt,
ist, dass zweimal E von S plus diesem D von S, also Delta von S, dem
Groß -D S entspricht.
E von S ist gewesen 2,
Delta von S ist gewesen die 3 und das D von S ist gewesen die 7.
Das Ganze als Beispiel dazu, welche Eigenschaften es in solchen
Graphen gibt, wie sie benannt werden, wie sie häufig im
Transportproblem auch verwendet werden und warum auf dieser Folie
steht Delta von S.
Und das ist nämlich in dem Fall genau die Anzahl an Touren, die von
der Menge S in die Menge Nicht-S reinfahren muss.
Und mit diesen Nebenbedingungen kann ich dann auch die Kurzzyklen
vermeiden.
Zur Vermeidung von diesen Kurzzyklen gibt es auch noch weitere
Nebenbedingungen.
Aber die, die wir hier gesehen haben, ist die allgemeinste Form
eigentlich.
Also es gibt noch einen Ticken, eine allgemeinere, die stelle ich aber
jetzt hier nicht vor, wird aber auch wieder mit diesen Knotengraden
und mit den Schnitten dargestellt.
Das heißt, wenn ich das jetzt anwenden würde, hier für dieses Beispiel
von Ingen, hätte ich beispielsweise hier mein S, hier habe ich mein V
ohne das S, und ich müsste jetzt aber Verbindungen haben, die von
dieser Menge S in die Menge V reingehen, die habe ich hier aber nicht,
und deshalb wäre das keine Tour, die mit der Formulierung, die auf der
PowerPoint draufsteht, gefunden werden dürfte oder zulässig wäre nach
dieser Problemformulierung.
Wenn man sich das mal anschaut, nochmal in Ruhe, wird das eigentlich
ziemlich schnell, ziemlich klar.
So,
jetzt gebe ich euch noch ein paar Infos zu diesem Savingsverfahren,
wie das berechnet wird und wie dieser Algorithmus dann komplett
ausschaut, wenn man dieses Savingsverfahren betrachtet.
Also wir hatten jetzt zunächst mal als Eröffnungsverfahren das
Savingsverfahren und das Sweep-Verfahren, als Heuristiken und als
Eröffnungsverfahren.
Dann haben wir gesehen, es gibt auch exakte Formulierungen dafür,
beispielsweise das kapazitierte Vehicle-Routing-Problem, und wie man
jetzt bei dieser Heuristik dem Savingsverfahren vorgeht, wenn man sie
komplett anwenden möchte, das folgt dann jetzt.
Also das Savingsverfahren,
das geht zurück auf Glark und Wright von 1964, also recht alt, aber
wird nach wie vor eingesetzt.
Zwar natürlich mit vielen Erweiterungen auch, aber grundlegend
verwendet man das auch noch immer so.
Ich habe hier zunächst mein Depot nochmal, habe hier meinen Knoten I,
habe hier diese Pendeltouren, die ich zunächst initialisiere
und fahre dann im ersten Schritt bei dieser Initialisierung alle
Knoten an.
Also erstens Initialisierung,
fahre alle Adressen in Pendeltouren an.
D.h.
ich kriege da M Touren raus,
wenn ich M plus 1 Knoten habe.
Als nächsten Schritt berechne für alle Kundenpaare IJ die Savings,
berechne für alle Kundenpaare I
und J die Savings.
D.h.
die Wegersparnis durch
Zusammenlegung der Pendeltouren.
Und so ein Saving sieht dann so aus.
S I J, mein Savingswert, ist gleich der Distanz von I nach 0 plus der
Distanz von 0 nach J minus der Distanz von I nach J.
Und diese Berechnung nehme ich jetzt vor für alle I und J, die ich
habe und beachte dabei, dass I ungleich J, also ich brauche keine
Ersparnis, um von Stuttgart nach Stuttgart zu kommen.
Diese Werte werden ausgenommen.
Der nächste Schritt ist dann, sortiere die Savings in absteigender
Reihenfolge.
Sortiere die Savings in
absteigender Reihenfolge.
Und was man dann tut, ist eine Tour erstellen.
Also was wir haben im Moment ist, wir haben jetzt M Touren mit
den Touren 0
I 0.
Also soweit sind wir, wir haben jetzt die Savings bestimmt, wir haben
aber nach wie vor unsere Pendeltouren.
Wir wollen jetzt aber eine Ersparnis aus diesen Pendeltouren haben,
indem wir welche zusammenlegen.
Pendeltouren.
Das heißt, wir gehen zum zweiten Schritt, nämlich der Iterationen.
Und da haben wir jetzt zunächst mal die Aufgabe, dass wir die S I J
nach den nächsten Adresspaaren I J untersuchen oder durchsuchen, bei
denen I und J die erste und letzte Adresse auf der Tour sind.
Also durchsuche
die sortierten S I J nach dem nächsten Adresspaar I
J, bei dem I und J die ersten oder
letzten Adressen auf
der Tour sind.
Falls dann die Tour, die durch Zusammenlegung entsteht, ungültig wäre,
beispielsweise weil ich eine Kapazitätsrestriktion oder eine
Zeitrestriktion überschreite, dann nehme ich das nächste Saving.
Also falls die Tour, die
durch die Zusammenlegung
entsteht, ungültig wäre,
z.B.
wegen Kapazität oder Zeit,
nehme dann das nächste Saving S
I J und
beginne dann wieder bei A.
Also B ist dann, falls die Tour, die durch Zusammenlegung entsteht,
ungültig wäre, z.B.
durch Kapazität oder Zeit, nehme dann das nächste Saving S I J und
mache weiter bei A.
A ist bei dieser Iteration der erste Schritt.
Durchsuche die sortierten S I J nach dem nächsten Adresspaar I J.
Ansonsten, wenn es ein gültiges Saving ist, sind wir beim Schritt C.
Sonst bilde neue Tour T
Stern durch Hinzufügen der neuen Verbindung
Durch hinzufügen der neuen Verbindung und
entferne die
Touren Ti und Tj aus der Menge.
Und so würde jetzt eine neue Tour T-Stern aussehen.
Der vierte Schritt, B, lautet, dass man dann, wenn man das getan hat,
zu A geht.
Und der letzte Schritt, E, man ist fertig, falls keine Tour mit
Savings mehr gefunden werden kann.
Man ist fertig,
falls keine Tour mit Savings S-I-J gefunden werden kann.
Fragen zum Savingsverfahren?
Die Frage ist gewesen, nach was man im Schritt A genau sucht.
Aufgabe in diesem Schritt A ist, durchsuchen Sie die sortierten S-I-J
nach den nächsten Adresspaaren I-J, bei denen I-J die erste oder
letzte Adresse auf der Tour ist.
Das heißt, ich male das mal auf,
beginnen wir bei diesen Pendeltouren 0I und
0J, ist das Ganze ja noch leicht, weil ich gucke mir jetzt nachher
alle I und J an.
Es kann aber auch passieren, das wäre jetzt der erste oder letzte
Knoten auf der Tour.
Es könnte aber auch sein, dass ich bereits Touren zusammengelegt habe,
meinetwegen beginne ich bei der 0, fahre zur 1, fahre zur 2, fahre zur
3, fahre wieder zurück.
Und dann ist damit gemeint, dass ich mir nur die ersten oder letzten
anschaue, weil ich kann ja nur ein Saving S-I-J bilden und ich könnte
jetzt hier ein Saving bilden S-1-3 und würde mir dann nur die Savings
anschauen, die in Verbindung mit 1 und 3 entstehen.
Und würde das hier so lassen wie es ist, heißt ich könnte hier jetzt
beispielsweise einen Knoten 4 einfügen und würde dann weiterhin über
die 2 fahren.
Also ich habe hier nur S-I-J und in diesem Algorithmus gucke ich mir
nur den ersten bzw.
letzten Knoten der Tour an.
Und das ist damit gemeint.
Ich wäre ein anderer Algorithmus, wenn ich mir alle anschauen könnte
oder würde und dieses Savings ist ja nur ein Eröffnungsverfahren.
Ich gucke mir alle Knoten an, beispielsweise beim 2-Opt-Verfahren, wo
wir jetzt dazu kommen, da gucke ich mir also nicht nur die Anfangs-
und Endknoten an, sondern gucke auf bestehenden Touren, wie ich die
alle miteinander verknüpfen könnte und laufe dann tatsächlich durch
alle I und alle J.
Und das machen wir dann jetzt.
Also wir hatten jetzt das Savingsverfahren, oder wir hatten also
Eröffnungsverfahren, haben wir das Savings- und Sweep-Verfahren
und jetzt gucken wir uns an ein Verbesserungsverfahren,
nämlich am Beispiel von 2-Opt.
Dieses 2-Opt-Verfahren geht zurück auf Johnson & McGioch
Johnson & McGioch und ist gar nicht mal so alt, das ist nämlich von
1997.
Wir gehen uns jetzt durch am 2-Opt-Verfahren.
Man kann das aber auch verallgemeinern auf das sogenannte K-Opt
-Verfahren.
Und diese Zahl 2 oder K bezieht sich nur darauf, wie viele Kanten wir
miteinander maximal vertauschen.
Oder wie viele Kanten wir beim Durchsuchen von Verbesserungen
vertauschen.
Beim 2-Opt sind es gerade zwei Kanten, bei denen wir ein Vertauschen
zulassen.
Da sind wir auch schon beim Kern dieses Verfahrens.
Es ist nämlich eine Tauschoperation, die mithilfe zweier neuer Fahrten
zwei bereits bestehende ersetzen soll.
Also wir haben Tauschoperationen,
die mithilfe
zweier ich unterstreiche mal, deshalb ist es 2-Opt
neuer Fahrten gleich Kanten
zwei bereits bestehende ersetzen soll.
Tauschoperationen, die mithilfe zweier neuer Fahrten gleich Kanten
zwei bereits bestehende Kanten ersetzen
soll.
Beispielsweise, also Vertauschung der Fahrten
Ich habe zum Beispiel eine Tour, die geht von J nach J plus 1
und eine Tour, die geht von K nach K plus 1
und hätte jetzt aber gerne, dass ich von J nach K fahre also mit, neue
Tour ist dann von J nach K und von J plus 1 nach K plus 1
und machen tue ich diesen Tausch genau dann
wenn die Entfernung von J nach J plus 1 plus die Entfernung von K nach
K plus 1 größer ist als die Entfernung von j nach k plus der
Entfernung von j plus 1 nach k plus 1.
Und, auch hier wieder, nur dann, wenn der Tausch zulässig ist.
Auch hier zum Beispiel wieder wegen Kapazität oder Zeitrestriktionen.
Also Kapazität oder Zeit.
Oder irgendwas anderes, was ich in diesem Problem berücksichtigen
möchte.
So, das ist das Zwei-Okt-Verfahren als das Verbesserungsverfahren, das
Verlernen, Kennenlernen.
Werden in dieser Vorlesung.
Und man kann das beliebig ausweiten auf ein Drei-Okt-Verfahren oder
ein Vier-Okt-Verfahren.
Aber je mehr alternative Tauschoperationen ich untersuche, umso länger
läuft wieder dieser Algorithmus, weil es auch hier wieder exponentiell
steigt.
Und der Zusatzgewinn, den man hat durch Vertauschen von drei oder vier
Kanten, der ist meistens nicht so groß.
Häufig beschränkt man sich auf das Zwei-Okt-Verfahren oder das Drei
-Okt -Verfahren.
Die größeren Vertauschverfahren werden meistens nicht mehr wirklich
untersucht.
Fragen zu diesem Verfahren?
Also hier werden jetzt wirklich, im Gegensatz zu den Savingsverfahren,
wo man nur die Anfangs- und die Endkunden angeschaut hat, um dadurch
Savings zu generieren, wird jetzt durch die gesamte Matrix gelaufen
und ich schaue mir alle I und alle J an, um eine Entscheidung darüber
zu treffen, was ich jetzt mit wem vertausche.
Und in der Übung werden wir dazu nochmal eine Aufgabe haben zum Zwei
-Okt -Verfahren.
Fragen zum Zwei-Okt-Verfahren?
Dann noch ein paar allgemeine Sachen, unter denen wir die Vehicle
-Routing -Probleme hier immer betrachten.
Also bei den Betrachtungen, wir betrachten hier nur einfache Fälle.
In einfachen Fällen
sind alle Fahrzeuge identisch.
Meistens aufgrund gleicher Kapazität, die man diesem Fahrzeug mitgibt.
Komplexere Modelle haben dann den ganzen Fuhrpark abgebildet, die
Sprinter berücksichtigen.
Beispielsweise können die dann 6 oder 7 Paletten fassen, die aber auch
LKWs berücksichtigen mit so um die 17, 18 Paletten.
Oder Sattelzüge, wo man dann auch bis zu 30 Paletten oder mehr laden
kann.
Aber in diesen einfachen Modellen sind diese Fahrzeuge identisch, in
der Regel.
Und was auch häufig der Fall ist bei diesen einfachen Modellen, die
Entfernungsmatrix ist symmetrisch.
Die Entfernungsmatrix ist symmetrisch,
heißt es gibt beispielsweise keine Einbahnstraßen.
Also wenn ich irgendwo hinfahre, muss ich nicht über den Umweg wieder
zurückfahren, weil beispielsweise eine Einbahnstraße in der Realität
dort auftauchen würde.
Sondern ich kann mir meistens helfen mit der Dreiecksmatrix, weil es
eine Symmetrie ist.
Dann haben wir eine Entfernungsmatrix, DIJ, aber das sollte Ihnen
reichend bekannt sein mittlerweile über die Beispiele, die wir haben.
Fahrzeugkapazität oder Fahrzeuganzahl, K, die ist also häufig fest.
Was wir im Vorfeld auch kennen, ist die Nachfrage der Abliefermengen.
Im Vorfeld bekannt die
Abliefermengen der M-Kunden.
Nämlich dann die Mengen B1 bis Bm.
Bei der Tourenplanung
unterscheidet man stochastische
und dynamische Tourenplanung.
Hat jemand eine Idee, was damit gemeint ist?
Stochastische Tourenplanung und dynamische Tourenplanung?
Bei der stochastischen Tourenplanung sind Komponenten dieses
Planungsproblems im Vorfeld häufig nicht bekannt.
Wir hatten das Beispiel mit den Zeiten, die eventuell nicht korrekt
bekannt sind im Vorfeld.
Könnte aber auch sein, dass die Abholmengen nicht im Vorfeld bekannt
sind, sondern sich erst kurz vor der Abholung herausstellen.
Dazu brauche ich dann wiederum andere Verfahren als die einfachen, die
wir uns hier angeschaut haben.
Bei der dynamischen Tourenplanung spricht man von dynamischer
Tourenplanung, wenn die Fahrzeuge bereits unterwegs sind und sich dann
noch Änderungen in der Tour ergeben oder die komplette Tour erst dann
fertiggestellt werden kann.
Beispielsweise wenn bei der DHL der Sprinter losfährt um seine
Auslieferungen, also die machen ja häufig Pickup- und Delivery-Touren,
also dass ich sowohl was mitnehme, also mitnehmen heißt ausliefern zum
Kunden, als auch von diesem Kunden eventuell wieder Pakete mitnehmen
oder zu einem anderen Kunden fahre, um Pakete mitzunehmen.
Und wenn jetzt über den Tagesablauf neue Aufträge hinzukommen und der
Fahrer ist bereits unterwegs, muss das natürlich dynamisch mit
verplant werden.
Wen das mal interessiert, sich genauer anzuschauen, da gab es ein
Forschungsprojekt im Rahmen vom Forschungszyklus Intelligente
Logistik.
Da wurde in Berlin von DHL aus, oder DHL hat an einem
Forschungsprojekt damit gearbeitet, wie man diese dynamische
Tourenplanung im Stadtverkehr nutzen kann, um die Fahrzeuge dort
besser auszulasten.
Also intelligente-logistik.org, da findet ihr eine ganze Reihe von
Projekten, da sind auch wir mit vertreten mit dem Projekt Logotakt,
das auch in der Transportplanung angesiedelt gewesen ist.
Da kann man sich bei Interesse informieren.
Die Optimierungsziele, die wir verfolgen, in der Regel bei diesen
Problemen Optimierungsziele, zum Beispiel minimiere die Anzahl der
notwendigen Fahrzeuge.
Hat jemand eine Idee, wie man das rauskriegen könnte, aus dem
kapazitierten Vehicle Routing Problem, das wir eben vorgestellt haben,
wo die Anzahl der Fahrzeuge mit K angegeben gewesen ist?
Ich habe es nicht verstanden.
Was man machen könnte, wäre das K in die Zielfunktion aufnehmen mit
einem Kostenfaktor.
So wie beispielsweise beim Warehouse Location Problem.
Wenn ich also entscheide, eröffne ich ein Warehouse oder nicht, habe
ich Fixkosten.
Solche Fixkosten könnte ich beispielsweise auch für das K verwenden,
das wäre eine Möglichkeit, wie man es machen könnte.
Wobei dann aber noch nicht klar ist, ob man wirklich die minimale
Anzahl an K rauskriegt.
Es könnte ja einfach sein, dass es immer noch günstiger ist, mit mehr
Fahrzeugen zu fahren, als mit weniger.
Was aber auch geht, ist, dass man dieses kapazitierte Vehicle Routing
Problem einfach mit unterschiedlichen K durchlaufen lässt und guckt,
bei welchem minimalen K es noch möglich ist.
Das sind zwar keine eleganten Wege, aber im Rahmen der beiden Sachen,
die wir hier kennengelernt haben, wären es zulässige Wege, die man
gehen könnte.
Also das ist zum Beispiel ein Ziel.
Und das andere Ziel könnte sein, minimiere die Zahl der zu fahrenden
Kilometer.
Minimiere die Zahl der zu fahrenden Kilometer.
Was aber letzten Endes
immer in die Minimierung der Kosten überläuft.
Also letzten Endes Minimierung
der Kosten.
Also wenn der Spritpreis weiter steigt, kann es vielleicht sein, dass
es günstiger ist, mit mehreren Fahrzeugen kürzere Touren zu fahren,
als mit wenigen Fahrzeugen in Summe ganz große Touren.