WEBVTT 00:19.140 --> 00:21.360 So, weiter geht's. 00:22.500 --> 00:24.220 Unterplanung ist damit abgeschlossen. 00:25.740 --> 00:29.740 Kennengelernt hatten wir jetzt das Up-Location-Problem zum Schluss, 00:29.880 --> 00:33.200 das Warehouse-Location-Problem und das Standard Weber-Modell. 00:34.940 --> 00:37.020 Der nächste Schritt, wenn es jetzt... 00:37.020 --> 00:39.680 Also das waren alles sehr statische Sachen, also die Entscheidungen, 00:39.760 --> 00:41.480 die da getroffen werden, sind langfristig. 00:41.480 --> 00:45.740 Es geht um die Entscheidung, bauen oder nicht bauen, wenn bauen, dann 00:45.740 --> 00:47.380 wohin. 00:47.680 --> 00:51.620 Und wir gehen jetzt mehr in den operativen Teil rein, und dazu die 00:51.620 --> 00:55.820 Kürenplanung, weil die Rahmenbedingungen von so einem Netzwerk sind 00:55.820 --> 00:59.800 dann schon abgesteckt, aber die Frage ist nun, wie muss ich meine 00:59.800 --> 01:03.900 Transporte durchführen, um in diesem Logistiknetzwerk so günstig wie 01:03.900 --> 01:04.740 möglich zu fahren. 01:05.820 --> 01:09.180 Das ist bei diesem Bildchen, die wir eben gesehen haben, zum Hub-and 01:09.180 --> 01:14.060 -Spoke -Netzwerk, der Teil, der ganz vorne ist, also die Vorlauftouren 01:14.060 --> 01:17.920 zum Dekot, den kann man da ansiedeln, beziehungsweise die 01:17.920 --> 01:22.040 Nachlauftouren vom Dekot weg zu den einzelnen Endkunden. 01:24.440 --> 01:30.540 Bevor wir hier auf diese beiden Modelle eingehen, erstmal grundlegend 01:30.540 --> 01:35.000 verschiedene Verfahren, mit denen man Tourenplanung vornehmen kann. 01:35.920 --> 01:40.560 Tourenplanung an sich ist auch wieder ein schweres Problem in der 01:40.560 --> 01:44.360 Informatik, das heißt, eine exakte Lösung zu finden, ist sehr 01:44.360 --> 01:49.920 zeitaufwendig, beziehungsweise unmöglich, weil die Verfahren da 01:49.920 --> 01:50.960 einfach noch nicht so weit sind. 01:52.220 --> 01:55.000 Und dazu hat man gerade dann auch in der Vergangenheit, als die 01:55.000 --> 01:59.160 Rechenleistung noch bei weitem nicht so hoch war, wie sie heute ist, 01:59.160 --> 02:05.880 sehr viele Hilfskonstrukte, Hilfsalgorithmen sich dafür überlegt, die 02:05.880 --> 02:09.280 man eingesetzt hat, die aber auch heute noch eingesetzt werden müssen. 02:09.780 --> 02:13.620 In kommerzieller Software zur Tourenplanung findet man häufig noch 02:13.620 --> 02:18.480 diese Heuristiken, weil einfach die Aufgabenstellung so schwer ist, 02:18.600 --> 02:23.600 dass diese exakten Verfahren bei großen Problemen nach wie vor eine 02:23.600 --> 02:26.500 Chance haben, aber eine Heuristik eingesetzt wird. 02:26.500 --> 02:30.520 Man nimmt in Kauf, dass die Lösung nicht optimal ist. 02:30.560 --> 02:31.900 Sie ist gut, aber nicht optimal. 02:32.040 --> 02:34.540 Manchmal ist sie optimal, aber man hat keine Garantie für die 02:34.540 --> 02:40.420 Optimalität, kriegt aber dafür eine gute Lösung in relativ kurzer 02:40.420 --> 02:40.780 Zeit. 02:42.780 --> 02:48.200 Eines der bekanntesten Verfahren ist der Sweep-Algorithmus. 02:48.200 --> 02:55.640 Bei diesem Sweep-Algorithmus beginnt man im Depot, dieses rote, das 02:55.640 --> 03:01.200 blaue sind die Kunden, beginnt im Depot mit einer sogenannten Sweep 03:01.200 --> 03:01.660 -Line. 03:03.180 --> 03:09.200 Und mit dieser Sweep-Line streiche ich jetzt wie mit einem Radar gegen 03:09.200 --> 03:11.160 den Uhrzeigersinn überall meine Kunden. 03:11.980 --> 03:18.240 Und jeweils in der nächsten Sekunde auf diese Sweep-Line wird meine 03:18.240 --> 03:20.260 aktuelle Tour hinzugefügt. 03:21.480 --> 03:26.680 Und die Restriktionen, die dabei einzuhalten sind, sind beispielsweise 03:26.680 --> 03:30.000 auch hier wieder die Kapazitätsrestriktionen, dass man Fahrzeug nicht 03:30.000 --> 03:35.560 mehr als C-Transporteinheiten mitnehmen kann. 03:36.940 --> 03:40.920 Und sobald ich dann so viele Kunden abgefahren habe, dass dieses Ziel 03:40.920 --> 03:42.840 überschritten wird, muss ich diese Tour beenden. 03:43.520 --> 03:46.880 Also ich gehe jetzt nach und nach über diese Punkte drüber, habe in 03:46.880 --> 03:51.200 diesem Beispiel die Restriktion, dass nicht mehr als drei Kunden auf 03:51.200 --> 03:56.640 einer Tour sein dürfen, packe also diesen zweiten Loch hinzu, packe 03:56.640 --> 04:00.300 den dritten Loch hinzu, mache dann diese rote Tour, mache das für die 04:00.300 --> 04:01.080 übrigen genauso. 04:01.080 --> 04:05.860 Und nun, es sind jetzt insgesamt vier Touren, drei Touren mit drei 04:05.860 --> 04:11.020 Kunden drauf, eine Tour mit nur einem Kunden, so eine Stichtour, und 04:11.020 --> 04:14.280 damit auf jeden Fall mal eine zulässige Lösung gefunden. 04:15.500 --> 04:19.200 Ob das jetzt eine gute Lösung ist, sei dahingestellt, aber es ist eine 04:19.200 --> 04:20.200 zulässige Lösung. 04:21.340 --> 04:24.800 Und in einem weiteren Schritt könnte man jetzt, dadurch dass es hier 04:24.800 --> 04:30.120 ein sogenanntes Eröffnungsverfahren ist, das heißt ein Verfahren, bei 04:30.120 --> 04:34.840 dem ich erstmal eine zulässige Lösung suche, ohne den Anspruch darauf, 04:35.000 --> 04:38.000 dass es optimal ist oder eine sehr gute ist, kann ich mit 04:38.000 --> 04:44.920 Verbesserungsverfahren die gefundene Eröffnungslösung verbessern. 04:46.020 --> 04:48.540 Beispielsweise könnte man sich jetzt überlegen, ob denn dieser 04:48.540 --> 04:52.900 einzelne Kunde wirklich einzeln angefahren werden muss, oder ob ich 04:52.900 --> 04:55.320 vielleicht aus einer dieser drei Touren, zum Beispiel dieser 04:55.320 --> 04:59.160 Heldenlaune, dass ich das aufsplitte und mache zwei Zweier-Touren 04:59.160 --> 04:59.620 draus. 05:01.400 --> 05:04.760 Wäre eine Möglichkeit, kommen wir gleich noch dazu, wenn wir bei den 05:04.760 --> 05:07.760 Eröffnungsverfahren, bei den Verbesserungsverfahren ankommen. 05:09.040 --> 05:11.480 Also das sweep-Algorithmus ist ein sehr einfacher Algorithmus. 05:14.020 --> 05:19.760 Ein weiterer einfacher Algorithmus, auch wieder eine Heuristik, ist 05:19.760 --> 05:21.800 das Savingsverfahren. 05:22.460 --> 05:26.500 Bei dem Savingsverfahren beginnt man nun mit Ende-Touren. 05:28.420 --> 05:32.480 Das heißt, ich tue so, als würde ich jeden LKW vom Depot zu meinem 05:32.480 --> 05:37.500 Kunden fahren lassen, um ihn dann auch wieder zurückfahren zu lassen, 05:37.640 --> 05:39.360 ohne eine tatsächliche Tour zu bilden. 05:39.360 --> 05:42.500 Jetzt suche ich mir Ersparnisse raus. 05:42.720 --> 05:46.880 Was könnte ich nämlich sparen, wenn ich zwei dieser Kunden auf eine 05:46.880 --> 05:47.780 Tour legen will. 05:52.340 --> 05:54.160 Ich greife nochmal die beiden raus. 05:56.300 --> 06:01.880 Das ist jetzt die Ende-Tour, die entsteht, wenn ich möglichst gut 06:01.880 --> 06:03.440 einzeln zu diesen Kunden fahre. 06:05.780 --> 06:10.480 Ich überlege mir, könnte ich denn diese beiden Äste einsparen, wenn 06:10.480 --> 06:18.200 ich zusätzlich von einem blauen Punkt zum nächsten blauen Punkt fahre. 06:19.820 --> 06:22.240 Also hier noch eine Strecke einüben. 06:22.420 --> 06:24.660 Ich habe eine Ersparnisse, aber dafür auch Zusatzkosten. 06:26.420 --> 06:32.260 Und kriege einen sogenannten Savingswert, also den Savingswert, wenn 06:32.260 --> 06:37.580 ich die Ersparnisse, diese zwei langen Strecken, minus Zusatzkosten 06:37.580 --> 06:41.280 rechne und kann dann gucken, wo würde ich einsparen. 06:41.920 --> 06:45.900 Das mache ich jetzt paarweise für alle Kombinationen mit blauen 06:45.900 --> 06:48.020 Punkten, die ich habe, auf meiner Tour. 06:49.020 --> 06:53.340 Und kann mir nun anschauen, auf welcher Tour, wo was zusammenliegt, 06:53.520 --> 06:55.000 kriege ich die größere Ersparnisse raus. 06:57.500 --> 07:01.080 Heißt also, für diesen Algorithmus, nachdem wir es mit Einzeltouren 07:01.080 --> 07:08.520 initialisiert haben, gucken, prüfe für die zwei Touren, wie groß die 07:08.520 --> 07:13.200 Ersparnisse bei Zusammenlegung ist, legen wir im dritten Schritt die 07:13.200 --> 07:16.400 Touren zusammen, die den höchsten Savingswert besitzen. 07:18.220 --> 07:20.780 Und man sieht dann, wie sich diese Touren ändern. 07:22.860 --> 07:26.660 Wenn dann keine Ersparnisse mehr möglich ist, kriege ich dieses 07:26.660 --> 07:27.460 Verfahren ab. 07:28.520 --> 07:33.440 Dann habe ich auch wieder eine Lösung gefunden, die gut ist, 07:33.720 --> 07:38.180 vielleicht auch besser als die Lösung im Sweep-Verfahren, muss aber 07:38.180 --> 07:40.940 nicht sein, und könnte mit dieser jetzt weiterrechnen. 07:41.280 --> 07:46.440 Also hier habe ich wieder ein Eröffnungsverfahren dargestellt. 07:48.820 --> 07:52.280 Ich gehe nochmal zurück zum Sweep-Verfahren, 07:58.330 --> 08:00.830 wo wir hier so drüber streichen. 08:01.790 --> 08:07.490 Bei welcher Anordnung von Kunden könnte ich dann relativ sicher sagen, 08:07.830 --> 08:11.670 dass das Sweep-Verfahren eine schlechte Lösung ist. 08:18.490 --> 08:20.770 Im Moment sind diese Kunden hier gleichmäßig verteilt. 08:31.810 --> 08:37.430 Genau, also wenn ich Kunden geclustert habe, das beispielsweise im 08:37.430 --> 08:41.450 Norden ein Cluster ist, im Süden ist ein Cluster, und ich muss jetzt 08:41.450 --> 08:45.570 aufgrund dieses Verfahrens einmal von Norden nach Süden fahren, und 08:45.570 --> 08:47.410 das ist dann natürlich eine große Schwierigkeit. 08:47.610 --> 08:50.250 Das wäre jetzt die unten günstige Lösung. 08:55.380 --> 09:00.720 Genau, wenn das Depot nicht mittig liegt, sind die Lösungen meistens 09:00.720 --> 09:01.720 auch nicht mehr so schön. 09:02.000 --> 09:04.860 Also wenn ich jetzt vorstelle, dass dieses Depot irgendwo ganz unten 09:04.860 --> 09:09.260 links am Rand liegt, und meine ganzen Kunden irgendwo ganz oben 09:09.260 --> 09:12.440 rechts, dann kann es ja wirklich sein, dass wir im Sweep-Verfahren 09:12.440 --> 09:15.760 auch ziemlich schlechte Lösungen ausprobieren werden. 09:17.600 --> 09:22.140 Also man muss halt wissen, es dient in erster Linie dazu, einfach mal 09:22.140 --> 09:23.580 eine zulässige Lösung zu finden. 09:24.140 --> 09:26.280 Verbessern kann man das Ganze dann auch im Nachhinein. 09:30.360 --> 09:35.700 Zu den exakten Verfahren komme ich dann jetzt, nämlich 09:39.420 --> 09:44.740 beispielsweise mit dem kapazitierten Vehicle-Routing-Problem. 09:47.500 --> 09:53.800 Bei diesem Problem ist es von der Problemstellung her ein Problem mit 09:53.800 --> 09:58.780 wenig Einschränkungen, also wenig Rezeptionen, wenig Annahmen für die 09:58.780 --> 09:59.420 Realität. 10:01.120 --> 10:04.100 Also Spezialfälle könnten damit keine abgebildet werden, wie 10:04.100 --> 10:07.360 beispielsweise, dass ich zu einem bestimmten Zeitpunkt irgendwo 10:07.360 --> 10:14.020 ankommen muss, oder das könnte abgebildet werden, dass ich nicht mehr 10:14.020 --> 10:16.820 als drei Kunden auf eine Tour bringe. 10:16.940 --> 10:18.100 Das könnte abgebildet werden. 10:18.680 --> 10:20.640 Aber es ist ein sehr generalistischer Einsatz überhaupt. 10:21.320 --> 10:25.900 Also für die Realität hat man auch Verfahren, die die Statistik mit 10:25.900 --> 10:26.360 reinnehmen. 10:26.360 --> 10:28.920 Ich war vorhin bei der robusten Tourenplanung. 10:29.280 --> 10:33.060 Wenn es darum geht, von welcher Zeit kann ich jetzt ausgehen für 10:33.060 --> 10:38.540 meinen Transport von München nach Hamburg, so etwas wird in diesem 10:38.540 --> 10:42.660 Realitätskreis, in diesem einfachen Modell nicht abgehandelt. 10:42.820 --> 10:46.820 Aber es ist ein sehr wichtiges Modell, nicht nur für die 10:46.820 --> 10:51.280 Tourenplanung, für den Transport, sondern beispielsweise kann man es 10:51.280 --> 10:57.780 einsetzen bei verschiedenen Bedingungen oder bei der Frage, wie muss 10:57.780 --> 11:01.540 ich denn über eine Leiterplatte fahren, um meine ganzen Höhepunkte, 11:02.060 --> 11:06.280 möglichst wenig Strecke für den Roboterarm zurückzulegen. 11:06.800 --> 11:10.820 Teilweise, wenn ich mit mehr Robotern auf dieser Höheplatte arbeite. 11:12.240 --> 11:15.980 Unterschied zum Travelling-Salesman-Problem. 11:16.600 --> 11:23.760 Hier ist beim Travelling-Salesman-Problem, muss ich mit einem 11:23.760 --> 11:27.660 Handlungsreisen oder analog jetzt mit einem Fahrzeug alle Punkte 11:27.660 --> 11:28.820 anfahren. 11:29.420 --> 11:33.660 Hier habe ich mehrere Fahrzeuge zur Verfügung, um alle Punkte 11:33.660 --> 11:34.440 anzufahren. 11:34.440 --> 11:40.460 Und will jetzt wissen, mit welchem Fahrzeug muss ich zu welchem Knoten 11:40.460 --> 11:44.760 fahren, um in Summe die kürzeste Strecke zurückzulegen. 11:45.580 --> 11:50.340 Und die Anzahl der Fahrzeuge ist jetzt hier dargestellt durch das 11:50.340 --> 11:51.360 Fahren. 11:55.640 --> 11:59.540 Die Kosten sind hier auch wieder dargestellt durch CIJ. 12:00.080 --> 12:05.880 Das kostet beispielsweise die Zeit, die Entfernung, um von I nach J zu 12:05.880 --> 12:06.140 kommen. 12:06.580 --> 12:10.640 Und auch hier wieder das XIJ, das binär ist, also ich fahre über IJ 12:10.640 --> 12:12.820 oder ich fahre nicht von I nach J. 12:13.800 --> 12:15.220 Die erste Nebenbedingung. 12:15.740 --> 12:21.660 Und die zweite Nebenbedingung stellt sicher, dass in jedem Knoten, mit 12:21.660 --> 12:28.760 dem ich reinfahre, also für jedes IJ, dass ich in jedes IJ einmal 12:28.760 --> 12:31.320 reinfahre, das ist die Nebenbedingung 3. 12:32.260 --> 12:36.940 Und die Nebenbedingung 4 stellt sicher, dass ich aus jedem dieser IJ 12:36.940 --> 12:40.660 auch rausfahre. 12:41.820 --> 12:44.820 Also da wo ich hinfahre, also wenn ich auf Stuttgart reinfahre zu 12:44.820 --> 12:47.980 meinem Knoten, muss ich auch von Stuttgart wieder wegfahren. 12:49.280 --> 12:58.320 Die Nebenbedingungen 4 und 5, die sagt mir, dass ich von allen I, in 12:58.320 --> 13:03.040 denen ich kommen könnte, immer wieder zu meinem Dekot zurückkehren 13:03.040 --> 13:03.420 muss. 13:03.780 --> 13:05.720 Dekot ist hier wieder dargestellt mit der Null. 13:06.360 --> 13:08.080 Und zwar mit allen Fahrzeugen. 13:08.460 --> 13:12.560 Wenn ich vier Fahrzeuge habe, muss ich mit allen vier Fahrzeugen 13:12.560 --> 13:14.260 wieder im Dekot ankommen. 13:14.860 --> 13:15.800 Nebenbedingung 5. 13:17.160 --> 13:19.720 Und wenn ich vier Fahrzeuge habe, jetzt bin ich wieder in 13:19.720 --> 13:24.380 Nebenbedingung 6, muss ich auch mit allen Fahrzeugen von diesem Dekot 13:24.380 --> 13:25.460 abfahren. 13:29.370 --> 13:31.550 Jetzt haben wir noch die siebte Nebenbedingung. 13:33.430 --> 13:40.330 Und das ist die, die diese ganzen Transportprobleme so schwer macht. 13:41.390 --> 13:45.050 Das ist nämlich die Nebenbedingung, die sicherstellt, dass ich keine 13:45.050 --> 13:49.230 sogenannten Kurzzüge in meinem Transport habe. 13:50.750 --> 13:53.150 Habt ihr mal eine Idee, oder kennt ihr Kurzzüge? 14:21.400 --> 14:24.020 Ich male euch das mal auf, als Beispiel. 14:24.940 --> 14:27.080 Die ersten Nebenbedingungen nämlich. 14:27.420 --> 14:31.220 Sagen wir mal, wir haben hier unser Depot 0, wo wir losfahren. 14:31.820 --> 14:35.740 Und diese eine Nebenbedingung, ich glaube es war die 5 und 6, die hat 14:35.740 --> 14:42.980 gesagt, immer wenn ich aus dem Depot rausfahre zu einem Knoten, muss 14:42.980 --> 14:44.230 ich auch wieder zum Depot zurückfahren. 14:45.500 --> 14:48.440 Das war ja abgebildet durch zwei Nebenbedingungen. 14:49.700 --> 14:54.500 Gleichzeitig hatte ich aber auch eine Nebenbedingung, die sagt, dass 14:54.500 --> 14:56.120 ich, das ist dann dieser Teil, 15:01.200 --> 15:04.180 in dem Knoten, in den ich reinfahre, hier, muss ich auch wieder 15:04.180 --> 15:04.740 rausfahren. 15:05.680 --> 15:09.260 Also ich habe jetzt eigentlich schon vier Nebenbedingungen, die hier 15:09.260 --> 15:09.740 greifen. 15:10.460 --> 15:14.860 Nämlich einmal hier, da wo ich rausfahre, das muss sichergestellt 15:14.860 --> 15:15.120 sein. 15:15.780 --> 15:19.320 In diesem Fall jetzt nur mit, hier ist jetzt K gleich 1 für dieses 15:19.320 --> 15:19.700 Beispiel. 15:20.620 --> 15:22.960 Ich habe die Nebenbedingungen, wo ich sage, ich muss dann auch 15:22.960 --> 15:24.640 irgendwo reinfahren in meinen Knoten. 15:25.640 --> 15:26.020 Hier. 15:27.180 --> 15:30.600 Ich habe dann die Nebenbedingungen, ich muss aus diesem Knoten wieder 15:30.600 --> 15:31.100 rausfahren. 15:31.440 --> 15:35.400 Und ich habe die Nebenbedingungen, dass ich ins Depot wieder 15:35.400 --> 15:36.400 zurückfahren muss. 15:38.500 --> 15:41.760 Jetzt, nach der Formulierung, ohne diese sogenannte 15:41.760 --> 15:48.440 Kurzzyklusbedingungen, könnte sowas passieren. 15:52.700 --> 15:59.580 Ich fahre aus meinem Depot raus, fahre zu meinem Knoten, fahre wieder 15:59.580 --> 16:01.040 zurück, das ist alles super. 16:02.000 --> 16:06.240 Aber ohne die Kurzzyklusbedingungen wäre es auch eine zulässige 16:06.240 --> 16:08.780 Lösung, dass ich bei weiteren Knoten, die ich habe, 16:13.480 --> 16:17.660 einfach von Knoten 2 zu 3 fahre und von Knoten 3 zu 2 wieder zurück. 16:17.660 --> 16:21.960 Dann sind diese ersten vier Nebenbedingungen alle nicht verletzt. 16:22.680 --> 16:26.560 Aber ein bisschen dumm an der Geschichte ist, ich habe keine wirkliche 16:26.560 --> 16:28.440 Tour, weil ich ja nicht vom Depot aus beginne. 16:29.580 --> 16:33.680 Und das muss ich sicherstellen mit diesen Nebenbedingungen, um die 16:33.680 --> 16:35.120 Kurzzyklen zu vermeiden. 16:35.260 --> 16:39.780 Also das hier ist jetzt die 2-3 oder die 0-1, das sind in diesem Fall 16:39.780 --> 16:43.220 jetzt Kurzzyklen, weil ich einfach nicht beim Depot starte. 16:44.780 --> 16:52.900 Und diese Formulierung mit diesem Delta, die werdet ihr ziemlich oft 16:52.900 --> 16:56.220 sehen bei der Formulierung von Transportproblemen. 16:57.200 --> 17:00.900 Und deshalb für die, die das später mal weitermachen werden, 17:01.500 --> 17:07.740 Transportoptimierung, hier ein paar zusätzliche Infos zu der 17:07.740 --> 17:10.780 Schreibweise, die man da verwendet. 17:30.100 --> 17:34.040 Die Nebenbedingungen, die wir da ja stehen hatten, ich schreibe sie 17:34.040 --> 17:36.180 hier nochmal auf, also ihr habt sie ja auf der Folie drauf, 17:42.820 --> 17:50.540 ist gewesen, dass ich ein I habe, das kein Element von S ist und ich 17:50.540 --> 17:54.340 habe ein J, das ein Element von S ist. 17:54.340 --> 17:59.640 S ist jetzt einfach eine Teilmenge aus der Menge all meiner Knoten V. 18:00.480 --> 18:03.620 Also ich habe Knoten von 1 bis 10 und S ist beispielsweise die Menge 18:03.620 --> 18:08.880 1, 2, 3 oder sagen wir 2, 3, 4, wenn 1 das Depot ist. 18:10.040 --> 18:20.360 Diese Nebenbedingung, die hier steht, sagt, xij muss größer sein als 18:20.360 --> 18:22.020 dieses Gamma von S. 18:24.600 --> 18:27.760 Und was bedeutet nun dieses Gamma? 18:27.760 --> 18:33.340 In diesem Fall hier, für den Fall des kapazitierten Vehicle Routing 18:33.340 --> 18:38.860 Problems, kann man das Gamma wie folgt ausrechnen. 18:41.760 --> 18:52.980 Gamma von S ist größer oder gleich der Summe über alle Bi durch die K, 18:54.820 --> 19:00.760 für alle I, die aus der Menge dieses Schnitts kommen. 19:02.540 --> 19:08.040 Bi sind hier die Bedarfe, die jeder Knoten hat. 19:09.060 --> 19:14.600 K ist die Anzahl der Fahrzeuge und das heißt, wenn ich jetzt alle 19:14.600 --> 19:17.720 meine Bedarfe aufaddiere, dividiert durch die Anzahl der Fahrzeuge, 19:18.260 --> 19:22.120 weiß ich, wie viele Fahrzeuge ich mindestens brauche, um dieses 19:22.120 --> 19:23.980 Transportproblem überhaupt zu lösen. 19:24.960 --> 19:28.900 Also ich kann mir das schon mal als eine Mindestschranke an Fahrzeugen 19:28.900 --> 19:29.560 definieren. 19:29.560 --> 19:37.140 Heißt hier, wenn ich beispielsweise nach Berechnungen von Bi durch K 19:37.140 --> 19:41.580 zu dem Ergebnis komme, ich brauche sieben Fahrzeuge insgesamt, 19:43.880 --> 19:48.140 beziehungsweise ich muss siebenmal fahren, andersrum, ich habe 19:48.140 --> 19:51.140 meinetwegen fünf Fahrzeuge, muss aber mit denen siebenmal fahren, 19:52.740 --> 19:56.960 würde ich dieses Gamma entsprechend gleich 7 setzen. 19:59.220 --> 20:06.740 Es wird ein bisschen klarer, wenn ich das mit den Schnitten, die dabei 20:06.740 --> 20:10.560 entstehen, in unserer Lösungsmenge erkläre. 20:10.840 --> 20:19.800 Es gibt nämlich dabei so ein paar Konventionen, die ihr wie gesagt 20:19.800 --> 20:21.080 häufiger finden werdet. 20:25.780 --> 20:28.220 Also hier mal ein Beispiel. 20:30.680 --> 20:39.260 1 ist jetzt das Depot, ich habe die 2, ich habe die 3, eine 4, eine 5 20:39.260 --> 20:41.720 und eine 6. 20:43.820 --> 20:49.640 Und ich sage, das S ist einfach mal die Menge 1, 2, 3. 20:53.670 --> 21:00.670 Und hier haben wir V ohne S, in dem Fall jetzt die Menge 4, 5, 6. 21:02.810 --> 21:10.470 Und was ich jetzt auch habe, ist in diesem Beispiel Verbindungen 21:10.470 --> 21:11.510 zwischen diesen Knoten. 21:18.550 --> 21:27.070 Also hier quellt eine 3 draus, macht mal hier eine 2 draus, hier eine 21:27.070 --> 21:27.970 6 und hier eine 5. 21:29.770 --> 21:34.950 Ich habe eine Verbindung von 1 nach 2, ich habe eine Verbindung von 1 21:34.950 --> 21:42.710 nach 5, eine Verbindung von 2 nach 3, eine von 5 nach 6, eine von 5 21:42.710 --> 21:49.130 nach 4, eine von 4 nach 6 und eine von 3 nach 6. 21:54.050 --> 21:55.970 Gut, die sind alle vollständig. 21:57.410 --> 22:11.570 Ich habe meine Knotenmenge V, 1, 2, 3, 4, 5, 6, dargestellt. 22:12.470 --> 22:19.270 Ich habe den Schnitt, das S, 1, 2, 3. 22:25.300 --> 22:27.460 Und ich habe die Menge meiner Kanten. 22:28.620 --> 22:41.240 Nämlich für alle S, die eine Teilmenge sind von V, gilt, dass ich 22:41.240 --> 22:42.980 Kanten habe, I von S. 22:48.110 --> 22:55.970 Und diese Kanten setzen sich zusammen aus den Kombinationen I und J. 23:01.930 --> 23:10.870 Und I und J sind ein Element von S. 23:13.570 --> 23:20.470 Das heißt, welche Kanten habe ich jetzt hier dargestellt mit E von S? 23:27.760 --> 23:30.060 1, 2 und 2, 3, genau. 23:32.120 --> 23:42.740 In diesem Beispiel jetzt sind das die Kanten 1, 2 und 2, 3. 23:46.240 --> 23:53.100 Und in diesem E oder Betrag von dieser Geschichte, E von S, ist jetzt, 23:53.360 --> 23:56.460 ich habe 2 Elemente drin, 2 Kanten. 23:58.640 --> 24:04.380 Ich habe gleichzeitig Knotengrade, die auch häufig verwendet werden 24:04.380 --> 24:05.560 bei dieser Formulierung. 24:06.200 --> 24:09.460 Oder bei Formulierungen von Transportproblemen. 24:10.180 --> 24:14.820 Die Knotengrade sagen mir, wie häufig wird in eine Knoten rein oder 24:14.820 --> 24:15.460 raus gefahren. 24:16.240 --> 24:25.270 Heißt, ich habe hier nochmal Delta, beispielsweise hier Delta von, 24:27.690 --> 24:28.990 kann man das lesen? 24:29.550 --> 24:32.370 Delta 4 ist 2. 24:32.850 --> 24:33.210 Und warum? 24:33.730 --> 24:36.830 Weil ich mit den zwei Kanten in diesen Knoten reingehe. 24:37.290 --> 24:38.190 Also Knotengrad. 24:48.260 --> 24:55.260 Hier beim Knoten 6, habe ich einen Knotengrad 3. 24:56.480 --> 25:01.900 Bei drei Kanten diesem Knoten anfahren und so weiter. 25:02.460 --> 25:08.240 Beispielsweise auch hier beim Knoten 2, habe ich einen Knotengrad von 25:08.240 --> 25:08.560 2. 25:11.720 --> 25:16.540 Also, ihr werdet häufig finden bei sowas das E von S. 25:16.720 --> 25:19.820 Ihr werdet häufig finden den Knotengrad, der dargestellt ist. 25:21.320 --> 25:25.560 Und ihr werdet, das ist das, was bei dieser Formulierung, die auf der 25:25.560 --> 25:29.360 Folie drauf ist, dargestellt ist. 25:30.300 --> 25:33.140 Nämlich der Schnitt, den habt ihr. 25:34.140 --> 25:39.040 Und das ist allgemein formuliert. 25:45.190 --> 25:47.250 Wie geht das mit dem Grün? 25:50.450 --> 26:00.030 Das ist nämlich die Menge aller Kanten IJ aus I. 26:00.030 --> 26:05.350 Mit der Eigenschaft, dass I aus dem S kommt. 26:07.210 --> 26:09.870 Und J ist kein Element von dem S. 26:12.030 --> 26:19.350 Oder genau umgekehrt, I ist kein Element von dem S, aber J ist ein 26:19.350 --> 26:20.350 Element von dem S. 26:31.810 --> 26:32.870 Könnt ihr das lesen? 26:33.210 --> 26:33.910 Soll ich es nochmal vorlesen? 26:35.370 --> 26:35.790 Passt. 26:38.030 --> 26:39.850 Welche Menge ist denn hiermit gemeint? 26:52.600 --> 26:54.300 1,5 und 3,6, ganz genau. 26:55.040 --> 26:56.420 Also hier nochmal in grün. 26:56.980 --> 27:00.540 Genau nämlich das, was hier die eine Menge verlässt und in die andere 27:00.540 --> 27:01.340 Menge reingeht. 27:01.700 --> 27:02.660 Das ist damit beschrieben. 27:03.400 --> 27:05.160 Einmal und zweimal. 27:07.520 --> 27:16.360 Also hier ist es dann die 3,6 und die 1,5. 27:21.400 --> 27:26.480 Beziehungsweise ist hier jetzt das ganze 2. 27:26.920 --> 27:31.840 Oder auch der Betrag davon ist 2, weil ich habe jetzt 2 Kanten, die 27:31.840 --> 27:35.140 die eine Menge verlassen und in die andere Menge wieder reingehen. 27:40.280 --> 27:47.680 Und was es jetzt noch zum Schluss gibt, wo man auch häufiger bei den 27:47.680 --> 27:52.300 Graphen Sachen drüber stolpert, ist nämlich die Summe über die ganzen 27:52.300 --> 27:54.600 Knotengerade aus der Menge S. 27:56.680 --> 28:00.840 Und das ist nämlich einfach 28:08.350 --> 28:11.950 die Summe über alle Knotengerade. 28:11.950 --> 28:16.030 Also ich habe hier oben meine Knotengerade definieren können oder 28:16.030 --> 28:16.830 herausfinden können. 28:16.930 --> 28:20.490 Hier war es beispielsweise die 2, hier ist es die 3, hier ist es 28:20.490 --> 28:21.150 nochmal die 2. 28:22.670 --> 28:28.030 Hierfür habe ich Grad 2 und hierfür habe ich auch den Grad 2. 28:29.890 --> 28:36.130 Das heißt die Summe für mein S beträgt hier 6. 28:36.130 --> 28:36.970 Ah, 28:43.980 --> 28:44.700 ich habe eine vergessen. 28:47.860 --> 28:52.200 In meinem Beispiel habe ich hier von 3 nach 4 auch noch eine Kante 28:52.200 --> 28:52.480 drin. 28:53.320 --> 28:54.980 Also können wir hier nochmal ergänzen. 29:01.860 --> 29:03.760 Hier kommt noch dazu von 3 nach 4. 29:04.500 --> 29:05.520 Den Strich haben wir schon. 29:06.840 --> 29:12.960 Und das heißt dieser Knotengrad hier bei der 3 ist nicht 2, sondern 3. 29:13.880 --> 29:17.520 Und die Summe hieraus ist dann in diesem Beispiel 7. 29:19.540 --> 29:28.840 Und was nun aus dieser Betrachtung des Graphen, was da immer gilt, 29:28.840 --> 29:50.820 ist, dass zweimal E von S plus diesem D von S, also Delta von S, dem 29:50.820 --> 29:54.480 Groß -D S entspricht. 29:55.600 --> 29:58.740 E von S ist gewesen 2, 30:02.260 --> 30:18.590 Delta von S ist gewesen die 3 und das D von S ist gewesen die 7. 30:28.300 --> 30:33.760 Das Ganze als Beispiel dazu, welche Eigenschaften es in solchen 30:33.760 --> 30:36.320 Graphen gibt, wie sie benannt werden, wie sie häufig im 30:36.320 --> 30:41.120 Transportproblem auch verwendet werden und warum auf dieser Folie 30:41.120 --> 30:43.460 steht Delta von S. 30:43.460 --> 30:49.120 Und das ist nämlich in dem Fall genau die Anzahl an Touren, die von 30:49.120 --> 30:53.320 der Menge S in die Menge Nicht-S reinfahren muss. 30:56.780 --> 31:00.580 Und mit diesen Nebenbedingungen kann ich dann auch die Kurzzyklen 31:00.580 --> 31:01.240 vermeiden. 31:06.030 --> 31:11.050 Zur Vermeidung von diesen Kurzzyklen gibt es auch noch weitere 31:11.050 --> 31:12.110 Nebenbedingungen. 31:12.110 --> 31:18.190 Aber die, die wir hier gesehen haben, ist die allgemeinste Form 31:18.190 --> 31:18.750 eigentlich. 31:19.590 --> 31:23.990 Also es gibt noch einen Ticken, eine allgemeinere, die stelle ich aber 31:23.990 --> 31:27.630 jetzt hier nicht vor, wird aber auch wieder mit diesen Knotengraden 31:27.630 --> 31:29.170 und mit den Schnitten dargestellt. 31:50.780 --> 31:56.460 Das heißt, wenn ich das jetzt anwenden würde, hier für dieses Beispiel 31:56.460 --> 32:04.000 von Ingen, hätte ich beispielsweise hier mein S, hier habe ich mein V 32:04.000 --> 32:08.260 ohne das S, und ich müsste jetzt aber Verbindungen haben, die von 32:08.260 --> 32:11.520 dieser Menge S in die Menge V reingehen, die habe ich hier aber nicht, 32:12.340 --> 32:15.540 und deshalb wäre das keine Tour, die mit der Formulierung, die auf der 32:15.540 --> 32:20.100 PowerPoint draufsteht, gefunden werden dürfte oder zulässig wäre nach 32:20.100 --> 32:21.340 dieser Problemformulierung. 32:24.140 --> 32:27.560 Wenn man sich das mal anschaut, nochmal in Ruhe, wird das eigentlich 32:27.560 --> 32:28.940 ziemlich schnell, ziemlich klar. 34:04.880 --> 34:05.640 So, 34:28.320 --> 34:32.880 jetzt gebe ich euch noch ein paar Infos zu diesem Savingsverfahren, 34:34.200 --> 34:40.560 wie das berechnet wird und wie dieser Algorithmus dann komplett 34:40.560 --> 34:42.940 ausschaut, wenn man dieses Savingsverfahren betrachtet. 34:45.600 --> 34:51.320 Also wir hatten jetzt zunächst mal als Eröffnungsverfahren das 34:51.320 --> 34:58.680 Savingsverfahren und das Sweep-Verfahren, als Heuristiken und als 34:58.680 --> 34:59.230 Eröffnungsverfahren. 35:00.060 --> 35:03.660 Dann haben wir gesehen, es gibt auch exakte Formulierungen dafür, 35:03.980 --> 35:10.140 beispielsweise das kapazitierte Vehicle-Routing-Problem, und wie man 35:10.140 --> 35:13.660 jetzt bei dieser Heuristik dem Savingsverfahren vorgeht, wenn man sie 35:13.660 --> 35:16.940 komplett anwenden möchte, das folgt dann jetzt. 35:17.940 --> 35:19.160 Also das Savingsverfahren, 35:40.260 --> 35:53.540 das geht zurück auf Glark und Wright von 1964, also recht alt, aber 35:53.540 --> 35:55.260 wird nach wie vor eingesetzt. 35:55.900 --> 35:59.300 Zwar natürlich mit vielen Erweiterungen auch, aber grundlegend 35:59.300 --> 36:01.140 verwendet man das auch noch immer so. 36:07.240 --> 36:13.220 Ich habe hier zunächst mein Depot nochmal, habe hier meinen Knoten I, 36:14.500 --> 36:18.260 habe hier diese Pendeltouren, die ich zunächst initialisiere 36:27.670 --> 36:32.670 und fahre dann im ersten Schritt bei dieser Initialisierung alle 36:32.670 --> 36:33.370 Knoten an. 36:33.510 --> 36:35.070 Also erstens Initialisierung, 36:40.610 --> 36:44.810 fahre alle Adressen in Pendeltouren an. 37:08.050 --> 37:09.130 D.h. 37:09.310 --> 37:11.970 ich kriege da M Touren raus, 37:15.800 --> 37:22.600 wenn ich M plus 1 Knoten habe. 37:25.900 --> 37:35.340 Als nächsten Schritt berechne für alle Kundenpaare IJ die Savings, 37:40.880 --> 37:48.300 berechne für alle Kundenpaare I 37:52.450 --> 37:57.670 und J die Savings. 38:04.260 --> 38:04.980 D.h. 38:05.220 --> 38:09.200 die Wegersparnis durch 38:16.610 --> 38:18.450 Zusammenlegung der Pendeltouren. 38:35.680 --> 38:41.900 Und so ein Saving sieht dann so aus. 38:42.340 --> 38:58.080 S I J, mein Savingswert, ist gleich der Distanz von I nach 0 plus der 38:58.080 --> 39:07.940 Distanz von 0 nach J minus der Distanz von I nach J. 39:08.900 --> 39:14.500 Und diese Berechnung nehme ich jetzt vor für alle I und J, die ich 39:14.500 --> 39:22.460 habe und beachte dabei, dass I ungleich J, also ich brauche keine 39:22.460 --> 39:24.860 Ersparnis, um von Stuttgart nach Stuttgart zu kommen. 39:26.320 --> 39:28.220 Diese Werte werden ausgenommen. 39:36.500 --> 39:41.220 Der nächste Schritt ist dann, sortiere die Savings in absteigender 39:41.220 --> 39:42.100 Reihenfolge. 39:47.200 --> 39:51.760 Sortiere die Savings in 39:58.890 --> 40:00.190 absteigender Reihenfolge. 40:19.690 --> 40:24.050 Und was man dann tut, ist eine Tour erstellen. 40:51.940 --> 41:07.400 Also was wir haben im Moment ist, wir haben jetzt M Touren mit 41:14.140 --> 41:17.840 den Touren 0 41:21.320 --> 41:23.320 I 0. 41:23.320 --> 41:26.300 Also soweit sind wir, wir haben jetzt die Savings bestimmt, wir haben 41:26.300 --> 41:27.980 aber nach wie vor unsere Pendeltouren. 41:28.580 --> 41:33.000 Wir wollen jetzt aber eine Ersparnis aus diesen Pendeltouren haben, 41:33.080 --> 41:34.540 indem wir welche zusammenlegen. 41:35.460 --> 41:35.940 Pendeltouren. 41:37.040 --> 41:41.860 Das heißt, wir gehen zum zweiten Schritt, nämlich der Iterationen. 41:51.790 --> 41:58.070 Und da haben wir jetzt zunächst mal die Aufgabe, dass wir die S I J 41:58.070 --> 42:05.050 nach den nächsten Adresspaaren I J untersuchen oder durchsuchen, bei 42:05.050 --> 42:09.870 denen I und J die erste und letzte Adresse auf der Tour sind. 42:09.870 --> 42:11.210 Also durchsuche 42:17.180 --> 42:45.520 die sortierten S I J nach dem nächsten Adresspaar I 42:50.350 --> 43:08.240 J, bei dem I und J die ersten oder 43:13.840 --> 43:20.160 letzten Adressen auf 43:24.790 --> 43:25.590 der Tour sind. 43:46.360 --> 43:52.100 Falls dann die Tour, die durch Zusammenlegung entsteht, ungültig wäre, 43:52.980 --> 43:56.620 beispielsweise weil ich eine Kapazitätsrestriktion oder eine 43:56.620 --> 44:00.960 Zeitrestriktion überschreite, dann nehme ich das nächste Saving. 44:02.100 --> 44:09.840 Also falls die Tour, die 44:17.160 --> 44:18.900 durch die Zusammenlegung 44:27.180 --> 44:30.720 entsteht, ungültig wäre, 44:44.160 --> 44:45.100 z.B. 44:45.340 --> 44:46.740 wegen Kapazität oder Zeit, 45:03.080 --> 45:09.720 nehme dann das nächste Saving S 45:15.880 --> 45:18.760 I J und 45:27.720 --> 45:28.820 beginne dann wieder bei A. 45:31.960 --> 45:36.500 Also B ist dann, falls die Tour, die durch Zusammenlegung entsteht, 45:36.620 --> 45:37.960 ungültig wäre, z.B. 45:38.120 --> 45:43.480 durch Kapazität oder Zeit, nehme dann das nächste Saving S I J und 45:43.480 --> 45:44.480 mache weiter bei A. 45:45.240 --> 45:49.180 A ist bei dieser Iteration der erste Schritt. 45:49.780 --> 45:53.820 Durchsuche die sortierten S I J nach dem nächsten Adresspaar I J. 46:12.800 --> 46:18.440 Ansonsten, wenn es ein gültiges Saving ist, sind wir beim Schritt C. 46:24.100 --> 46:30.020 Sonst bilde neue Tour T 46:33.220 --> 46:37.940 Stern durch Hinzufügen der neuen Verbindung 46:47.380 --> 46:55.420 Durch hinzufügen der neuen Verbindung und 47:02.450 --> 47:05.570 entferne die 47:09.140 --> 47:15.300 Touren Ti und Tj aus der Menge. 47:36.340 --> 47:41.100 Und so würde jetzt eine neue Tour T-Stern aussehen. 47:49.250 --> 47:55.490 Der vierte Schritt, B, lautet, dass man dann, wenn man das getan hat, 47:56.830 --> 47:58.150 zu A geht. 48:00.730 --> 48:07.210 Und der letzte Schritt, E, man ist fertig, falls keine Tour mit 48:07.210 --> 48:09.410 Savings mehr gefunden werden kann. 48:14.950 --> 48:17.590 Man ist fertig, 48:24.560 --> 48:46.760 falls keine Tour mit Savings S-I-J gefunden werden kann. 49:20.090 --> 49:23.310 Fragen zum Savingsverfahren? 49:32.600 --> 49:39.860 Die Frage ist gewesen, nach was man im Schritt A genau sucht. 49:41.800 --> 49:45.560 Aufgabe in diesem Schritt A ist, durchsuchen Sie die sortierten S-I-J 49:45.560 --> 49:51.060 nach den nächsten Adresspaaren I-J, bei denen I-J die erste oder 49:51.060 --> 49:52.900 letzte Adresse auf der Tour ist. 49:52.900 --> 49:56.180 Das heißt, ich male das mal auf, 49:59.700 --> 50:09.020 beginnen wir bei diesen Pendeltouren 0I und 50:13.180 --> 50:17.800 0J, ist das Ganze ja noch leicht, weil ich gucke mir jetzt nachher 50:17.800 --> 50:19.180 alle I und J an. 50:20.880 --> 50:25.180 Es kann aber auch passieren, das wäre jetzt der erste oder letzte 50:25.180 --> 50:26.520 Knoten auf der Tour. 50:27.940 --> 50:31.660 Es könnte aber auch sein, dass ich bereits Touren zusammengelegt habe, 50:33.640 --> 50:37.780 meinetwegen beginne ich bei der 0, fahre zur 1, fahre zur 2, fahre zur 50:37.780 --> 50:39.160 3, fahre wieder zurück. 50:43.970 --> 50:49.170 Und dann ist damit gemeint, dass ich mir nur die ersten oder letzten 50:49.170 --> 50:53.890 anschaue, weil ich kann ja nur ein Saving S-I-J bilden und ich könnte 50:53.890 --> 51:01.830 jetzt hier ein Saving bilden S-1-3 und würde mir dann nur die Savings 51:01.830 --> 51:05.370 anschauen, die in Verbindung mit 1 und 3 entstehen. 51:06.290 --> 51:10.710 Und würde das hier so lassen wie es ist, heißt ich könnte hier jetzt 51:10.710 --> 51:15.490 beispielsweise einen Knoten 4 einfügen und würde dann weiterhin über 51:15.490 --> 51:16.330 die 2 fahren. 51:18.790 --> 51:24.230 Also ich habe hier nur S-I-J und in diesem Algorithmus gucke ich mir 51:24.230 --> 51:26.490 nur den ersten bzw. 51:26.670 --> 51:28.410 letzten Knoten der Tour an. 51:30.670 --> 51:31.570 Und das ist damit gemeint. 51:37.350 --> 51:41.690 Ich wäre ein anderer Algorithmus, wenn ich mir alle anschauen könnte 51:41.690 --> 51:46.510 oder würde und dieses Savings ist ja nur ein Eröffnungsverfahren. 51:47.330 --> 51:51.990 Ich gucke mir alle Knoten an, beispielsweise beim 2-Opt-Verfahren, wo 51:51.990 --> 51:54.890 wir jetzt dazu kommen, da gucke ich mir also nicht nur die Anfangs- 51:54.890 --> 51:59.350 und Endknoten an, sondern gucke auf bestehenden Touren, wie ich die 51:59.350 --> 52:02.370 alle miteinander verknüpfen könnte und laufe dann tatsächlich durch 52:02.370 --> 52:03.410 alle I und alle J. 52:04.850 --> 52:06.330 Und das machen wir dann jetzt. 52:30.660 --> 52:35.460 Also wir hatten jetzt das Savingsverfahren, oder wir hatten also 52:35.460 --> 52:54.150 Eröffnungsverfahren, haben wir das Savings- und Sweep-Verfahren 52:59.840 --> 53:05.180 und jetzt gucken wir uns an ein Verbesserungsverfahren, 53:14.470 --> 53:17.930 nämlich am Beispiel von 2-Opt. 53:34.800 --> 53:42.120 Dieses 2-Opt-Verfahren geht zurück auf Johnson & McGioch 53:47.580 --> 53:58.180 Johnson & McGioch und ist gar nicht mal so alt, das ist nämlich von 53:58.180 --> 53:58.900 1997. 54:00.540 --> 54:03.980 Wir gehen uns jetzt durch am 2-Opt-Verfahren. 54:04.160 --> 54:07.880 Man kann das aber auch verallgemeinern auf das sogenannte K-Opt 54:07.880 --> 54:08.200 -Verfahren. 54:09.380 --> 54:14.240 Und diese Zahl 2 oder K bezieht sich nur darauf, wie viele Kanten wir 54:14.240 --> 54:17.500 miteinander maximal vertauschen. 54:18.180 --> 54:20.780 Oder wie viele Kanten wir beim Durchsuchen von Verbesserungen 54:20.780 --> 54:21.100 vertauschen. 54:21.780 --> 54:25.700 Beim 2-Opt sind es gerade zwei Kanten, bei denen wir ein Vertauschen 54:25.700 --> 54:26.240 zulassen. 54:27.560 --> 54:31.060 Da sind wir auch schon beim Kern dieses Verfahrens. 54:31.100 --> 54:37.420 Es ist nämlich eine Tauschoperation, die mithilfe zweier neuer Fahrten 54:37.420 --> 54:40.880 zwei bereits bestehende ersetzen soll. 54:41.660 --> 54:45.020 Also wir haben Tauschoperationen, 54:55.140 --> 54:58.120 die mithilfe 55:04.390 --> 55:11.110 zweier ich unterstreiche mal, deshalb ist es 2-Opt 55:14.980 --> 55:21.370 neuer Fahrten gleich Kanten 55:25.810 --> 55:29.510 zwei bereits bestehende ersetzen soll. 55:38.200 --> 55:42.440 Tauschoperationen, die mithilfe zweier neuer Fahrten gleich Kanten 55:42.440 --> 55:51.340 zwei bereits bestehende Kanten ersetzen 55:56.930 --> 55:57.230 soll. 55:59.810 --> 56:06.190 Beispielsweise, also Vertauschung der Fahrten 56:17.920 --> 56:25.980 Ich habe zum Beispiel eine Tour, die geht von J nach J plus 1 56:29.280 --> 56:34.560 und eine Tour, die geht von K nach K plus 1 56:42.660 --> 56:55.280 und hätte jetzt aber gerne, dass ich von J nach K fahre also mit, neue 56:55.280 --> 57:05.400 Tour ist dann von J nach K und von J plus 1 nach K plus 1 57:11.680 --> 57:15.660 und machen tue ich diesen Tausch genau dann 57:18.900 --> 57:34.160 wenn die Entfernung von J nach J plus 1 plus die Entfernung von K nach 57:34.160 --> 57:47.660 K plus 1 größer ist als die Entfernung von j nach k plus der 57:47.660 --> 57:54.700 Entfernung von j plus 1 nach k plus 1. 57:58.180 --> 58:05.000 Und, auch hier wieder, nur dann, wenn der Tausch zulässig ist. 58:13.140 --> 58:19.220 Auch hier zum Beispiel wieder wegen Kapazität oder Zeitrestriktionen. 58:27.570 --> 58:30.870 Also Kapazität oder Zeit. 58:32.210 --> 58:37.410 Oder irgendwas anderes, was ich in diesem Problem berücksichtigen 58:37.410 --> 58:38.230 möchte. 58:46.320 --> 58:52.920 So, das ist das Zwei-Okt-Verfahren als das Verbesserungsverfahren, das 58:52.920 --> 58:54.040 Verlernen, Kennenlernen. 58:55.680 --> 58:57.060 Werden in dieser Vorlesung. 58:59.060 --> 59:03.120 Und man kann das beliebig ausweiten auf ein Drei-Okt-Verfahren oder 59:03.120 --> 59:04.240 ein Vier-Okt-Verfahren. 59:04.980 --> 59:09.520 Aber je mehr alternative Tauschoperationen ich untersuche, umso länger 59:09.520 --> 59:12.460 läuft wieder dieser Algorithmus, weil es auch hier wieder exponentiell 59:12.460 --> 59:13.000 steigt. 59:13.740 --> 59:18.140 Und der Zusatzgewinn, den man hat durch Vertauschen von drei oder vier 59:18.140 --> 59:22.160 Kanten, der ist meistens nicht so groß. 59:23.440 --> 59:27.020 Häufig beschränkt man sich auf das Zwei-Okt-Verfahren oder das Drei 59:27.020 --> 59:27.860 -Okt -Verfahren. 59:28.820 --> 59:33.820 Die größeren Vertauschverfahren werden meistens nicht mehr wirklich 59:33.820 --> 59:34.340 untersucht. 59:39.910 --> 59:41.430 Fragen zu diesem Verfahren? 59:42.110 --> 59:46.230 Also hier werden jetzt wirklich, im Gegensatz zu den Savingsverfahren, 59:46.370 --> 59:50.230 wo man nur die Anfangs- und die Endkunden angeschaut hat, um dadurch 59:50.230 --> 59:54.230 Savings zu generieren, wird jetzt durch die gesamte Matrix gelaufen 59:54.230 --> 01:00:00.190 und ich schaue mir alle I und alle J an, um eine Entscheidung darüber 01:00:00.190 --> 01:00:02.710 zu treffen, was ich jetzt mit wem vertausche. 01:00:03.450 --> 01:00:07.730 Und in der Übung werden wir dazu nochmal eine Aufgabe haben zum Zwei 01:00:07.730 --> 01:00:08.450 -Okt -Verfahren. 01:00:12.110 --> 01:00:15.450 Fragen zum Zwei-Okt-Verfahren? 01:00:15.450 --> 01:00:24.310 Dann noch ein paar allgemeine Sachen, unter denen wir die Vehicle 01:00:24.310 --> 01:00:26.210 -Routing -Probleme hier immer betrachten. 01:00:59.980 --> 01:01:06.440 Also bei den Betrachtungen, wir betrachten hier nur einfache Fälle. 01:01:08.520 --> 01:01:10.840 In einfachen Fällen 01:01:16.720 --> 01:01:23.500 sind alle Fahrzeuge identisch. 01:01:39.960 --> 01:01:45.360 Meistens aufgrund gleicher Kapazität, die man diesem Fahrzeug mitgibt. 01:01:57.440 --> 01:02:02.040 Komplexere Modelle haben dann den ganzen Fuhrpark abgebildet, die 01:02:02.040 --> 01:02:02.880 Sprinter berücksichtigen. 01:02:04.120 --> 01:02:08.160 Beispielsweise können die dann 6 oder 7 Paletten fassen, die aber auch 01:02:08.160 --> 01:02:11.040 LKWs berücksichtigen mit so um die 17, 18 Paletten. 01:02:12.680 --> 01:02:16.500 Oder Sattelzüge, wo man dann auch bis zu 30 Paletten oder mehr laden 01:02:16.500 --> 01:02:16.740 kann. 01:02:17.840 --> 01:02:22.020 Aber in diesen einfachen Modellen sind diese Fahrzeuge identisch, in 01:02:22.020 --> 01:02:22.360 der Regel. 01:02:23.220 --> 01:02:28.380 Und was auch häufig der Fall ist bei diesen einfachen Modellen, die 01:02:28.380 --> 01:02:30.360 Entfernungsmatrix ist symmetrisch. 01:02:37.540 --> 01:02:39.800 Die Entfernungsmatrix ist symmetrisch, 01:02:44.430 --> 01:02:48.510 heißt es gibt beispielsweise keine Einbahnstraßen. 01:02:49.070 --> 01:02:52.130 Also wenn ich irgendwo hinfahre, muss ich nicht über den Umweg wieder 01:02:52.130 --> 01:02:55.790 zurückfahren, weil beispielsweise eine Einbahnstraße in der Realität 01:02:55.790 --> 01:02:56.730 dort auftauchen würde. 01:02:56.730 --> 01:03:01.270 Sondern ich kann mir meistens helfen mit der Dreiecksmatrix, weil es 01:03:01.270 --> 01:03:02.770 eine Symmetrie ist. 01:03:10.410 --> 01:03:16.990 Dann haben wir eine Entfernungsmatrix, DIJ, aber das sollte Ihnen 01:03:16.990 --> 01:03:19.590 reichend bekannt sein mittlerweile über die Beispiele, die wir haben. 01:03:21.430 --> 01:03:26.290 Fahrzeugkapazität oder Fahrzeuganzahl, K, die ist also häufig fest. 01:03:30.380 --> 01:03:36.320 Was wir im Vorfeld auch kennen, ist die Nachfrage der Abliefermengen. 01:03:42.040 --> 01:03:46.840 Im Vorfeld bekannt die 01:03:54.550 --> 01:04:05.740 Abliefermengen der M-Kunden. 01:04:08.160 --> 01:04:15.420 Nämlich dann die Mengen B1 bis Bm. 01:04:29.270 --> 01:04:32.690 Bei der Tourenplanung 01:04:38.760 --> 01:04:47.160 unterscheidet man stochastische 01:05:11.620 --> 01:05:14.120 und dynamische Tourenplanung. 01:05:28.380 --> 01:05:30.660 Hat jemand eine Idee, was damit gemeint ist? 01:05:30.780 --> 01:05:33.540 Stochastische Tourenplanung und dynamische Tourenplanung? 01:05:40.010 --> 01:05:46.230 Bei der stochastischen Tourenplanung sind Komponenten dieses 01:05:46.230 --> 01:05:48.950 Planungsproblems im Vorfeld häufig nicht bekannt. 01:05:48.950 --> 01:05:55.550 Wir hatten das Beispiel mit den Zeiten, die eventuell nicht korrekt 01:05:55.550 --> 01:05:56.750 bekannt sind im Vorfeld. 01:05:58.570 --> 01:06:03.710 Könnte aber auch sein, dass die Abholmengen nicht im Vorfeld bekannt 01:06:03.710 --> 01:06:08.050 sind, sondern sich erst kurz vor der Abholung herausstellen. 01:06:08.370 --> 01:06:11.450 Dazu brauche ich dann wiederum andere Verfahren als die einfachen, die 01:06:11.450 --> 01:06:12.650 wir uns hier angeschaut haben. 01:06:12.650 --> 01:06:17.350 Bei der dynamischen Tourenplanung spricht man von dynamischer 01:06:17.350 --> 01:06:24.050 Tourenplanung, wenn die Fahrzeuge bereits unterwegs sind und sich dann 01:06:24.050 --> 01:06:27.710 noch Änderungen in der Tour ergeben oder die komplette Tour erst dann 01:06:27.710 --> 01:06:29.410 fertiggestellt werden kann. 01:06:29.670 --> 01:06:35.170 Beispielsweise wenn bei der DHL der Sprinter losfährt um seine 01:06:35.170 --> 01:06:39.110 Auslieferungen, also die machen ja häufig Pickup- und Delivery-Touren, 01:06:39.190 --> 01:06:45.150 also dass ich sowohl was mitnehme, also mitnehmen heißt ausliefern zum 01:06:45.150 --> 01:06:49.170 Kunden, als auch von diesem Kunden eventuell wieder Pakete mitnehmen 01:06:49.170 --> 01:06:51.930 oder zu einem anderen Kunden fahre, um Pakete mitzunehmen. 01:06:52.510 --> 01:06:56.510 Und wenn jetzt über den Tagesablauf neue Aufträge hinzukommen und der 01:06:56.510 --> 01:06:59.510 Fahrer ist bereits unterwegs, muss das natürlich dynamisch mit 01:06:59.510 --> 01:07:00.230 verplant werden. 01:07:00.230 --> 01:07:05.170 Wen das mal interessiert, sich genauer anzuschauen, da gab es ein 01:07:05.170 --> 01:07:10.470 Forschungsprojekt im Rahmen vom Forschungszyklus Intelligente 01:07:10.470 --> 01:07:11.230 Logistik. 01:07:12.510 --> 01:07:16.970 Da wurde in Berlin von DHL aus, oder DHL hat an einem 01:07:16.970 --> 01:07:19.430 Forschungsprojekt damit gearbeitet, wie man diese dynamische 01:07:19.430 --> 01:07:23.490 Tourenplanung im Stadtverkehr nutzen kann, um die Fahrzeuge dort 01:07:23.490 --> 01:07:24.410 besser auszulasten. 01:07:26.090 --> 01:07:31.310 Also intelligente-logistik.org, da findet ihr eine ganze Reihe von 01:07:31.310 --> 01:07:34.810 Projekten, da sind auch wir mit vertreten mit dem Projekt Logotakt, 01:07:35.030 --> 01:07:38.450 das auch in der Transportplanung angesiedelt gewesen ist. 01:07:39.890 --> 01:07:42.670 Da kann man sich bei Interesse informieren. 01:07:44.370 --> 01:07:50.190 Die Optimierungsziele, die wir verfolgen, in der Regel bei diesen 01:07:50.190 --> 01:08:13.810 Problemen Optimierungsziele, zum Beispiel minimiere die Anzahl der 01:08:16.420 --> 01:08:17.620 notwendigen Fahrzeuge. 01:08:34.260 --> 01:08:39.560 Hat jemand eine Idee, wie man das rauskriegen könnte, aus dem 01:08:39.560 --> 01:08:44.080 kapazitierten Vehicle Routing Problem, das wir eben vorgestellt haben, 01:08:44.560 --> 01:08:48.260 wo die Anzahl der Fahrzeuge mit K angegeben gewesen ist? 01:09:01.870 --> 01:09:03.390 Ich habe es nicht verstanden. 01:09:10.540 --> 01:09:18.340 Was man machen könnte, wäre das K in die Zielfunktion aufnehmen mit 01:09:18.340 --> 01:09:19.500 einem Kostenfaktor. 01:09:20.660 --> 01:09:25.220 So wie beispielsweise beim Warehouse Location Problem. 01:09:25.800 --> 01:09:29.740 Wenn ich also entscheide, eröffne ich ein Warehouse oder nicht, habe 01:09:29.740 --> 01:09:30.480 ich Fixkosten. 01:09:30.880 --> 01:09:34.380 Solche Fixkosten könnte ich beispielsweise auch für das K verwenden, 01:09:34.500 --> 01:09:37.080 das wäre eine Möglichkeit, wie man es machen könnte. 01:09:38.160 --> 01:09:40.620 Wobei dann aber noch nicht klar ist, ob man wirklich die minimale 01:09:40.620 --> 01:09:42.000 Anzahl an K rauskriegt. 01:09:42.300 --> 01:09:45.400 Es könnte ja einfach sein, dass es immer noch günstiger ist, mit mehr 01:09:45.400 --> 01:09:50.120 Fahrzeugen zu fahren, als mit weniger. 01:09:51.380 --> 01:09:56.480 Was aber auch geht, ist, dass man dieses kapazitierte Vehicle Routing 01:09:56.480 --> 01:10:00.700 Problem einfach mit unterschiedlichen K durchlaufen lässt und guckt, 01:10:00.940 --> 01:10:04.080 bei welchem minimalen K es noch möglich ist. 01:10:04.080 --> 01:10:09.360 Das sind zwar keine eleganten Wege, aber im Rahmen der beiden Sachen, 01:10:09.400 --> 01:10:12.780 die wir hier kennengelernt haben, wären es zulässige Wege, die man 01:10:12.780 --> 01:10:13.340 gehen könnte. 01:10:14.240 --> 01:10:15.700 Also das ist zum Beispiel ein Ziel. 01:10:16.520 --> 01:10:21.700 Und das andere Ziel könnte sein, minimiere die Zahl der zu fahrenden 01:10:21.700 --> 01:10:22.260 Kilometer. 01:10:27.500 --> 01:10:34.960 Minimiere die Zahl der zu fahrenden Kilometer. 01:10:45.120 --> 01:10:46.960 Was aber letzten Endes 01:10:51.210 --> 01:10:59.030 immer in die Minimierung der Kosten überläuft. 01:10:59.030 --> 01:11:03.310 Also letzten Endes Minimierung 01:11:07.850 --> 01:11:11.010 der Kosten. 01:11:13.350 --> 01:11:16.810 Also wenn der Spritpreis weiter steigt, kann es vielleicht sein, dass 01:11:16.810 --> 01:11:20.070 es günstiger ist, mit mehreren Fahrzeugen kürzere Touren zu fahren, 01:11:20.290 --> 01:11:24.230 als mit wenigen Fahrzeugen in Summe ganz große Touren.