Suhl Mellouli Lösungen Tourenplanung PDF

Preview

Summary

Suhl Mellouli Lösungen Tourenplanung...

Description

1) Tourenplanung mit mehreren Touren (aus Suhl/Mellouli: Optimierungssysteme, 3. Auflage, 2013)

2)Tourenplanung mit einer Tour Die Mutter kann einen Bus m it 13 Sitzplätzen (einschließlich Fahrer) nutzen; sie darf diesen auch selbst fahren (vgl. Aufgabe 1). Daher braucht sie einen neuen Tourenplan, wobei alle Kinder in einer Tour abgeholt werden können. Benutzen Sie als Anfangslösung die folgende zufällig generierte Tour: [Sebastian, 2, 6, 5, 1, 3, 4, Sebastian]. Bestimmen Sie einen 2-optimalen Tourenpl an mit dem 2-Opt-Verfahren..

Lösungsvorschlag zu Kapitel 8.10 Aufgabe 8-1: Tourenplanung mit mehreren Touren a) Zunächst plant die Mutter in jede Ortschaft einzeln zu fahren und die Kinder abzuholen. Wie lange ist in diesem Fall die gesamte Fahrstrecke?

3 4

2 5 4

4

2

Sebastian 5

1

5

5 6

Die Lösung ist eine Pendeltour mit sechs Fahrten: Die gesamte Fahrstrecke errechnet sich folgendermaßen: Sebastian  Ort Sebastian  Ort Sebastian  Ort Sebastian  Ort Sebastian  Ort Sebastian  Ort

1 2 3 4 5 6

 Sebastian =  Sebastian =  Sebastian =  Sebastian =  Sebastian =  Sebastian =

2*2 = 2*4 = 2*5 = 2*4 = 2*5 = 2*5 =

4 8 10 8 10 10

Summe: 50

b) Verbessern Sie die Lösung aus a) mit dem Savings- Algorithmus Entfernungsmatrix: S 1 2 S 2 4 1 3 2 3 4 5 6 Savingsmatrix: 1 2 1 3 2 3 4 5 6

3 5 6 6 -

3 1 3 -

4 4 10 8 -

4 1 -

5 5 10 6 -

6 5 4 5 7 -

5 3 -

6 3 4 3 -

Ausgangssituation: Gesamtlänge der Tour: 50; Q=2

3 4

2 5 4

4 2

Sebastian 5

1

5

5 6 Schritt 1: Realisiere Saving von 2 nach 6 Gesamtlänge der Tour: 46; Q=2

3 4

2

5 4

4

2

Sebastian 5

1

5 5

5 6 Schritt 2: Realisiere Saving von 4 nach 5 Gesamtlänge der Tour: 43; Q=2

3 4

2 5 4

4

6

2

Sebastian 5

1

5 5

5 6

Schritt 3: Realisiere Saving von 1 nach 3 Gesamtlänge Tour: 42; Q=2

3 4

2

6 5 4 4

6

2

Sebastian 5

1

5 5

5 6

c) Berechnen Sie einen ersten Tourenplan mit dem Sweep- Algorithmus Schritt 1: Tourenplan 1: [Seb, 1, 2, Seb], [Seb, 3, 4, Seb], [Seb, 5, 6, Seb] Gesamtlänge: 43

3

8

4

2 5 4

4 3 2

Sebastian 5

5

1

5 7

6

Schritt 2: Tourenplan 2: [Seb, 2, 3, Seb], [Seb, 4, 5, Seb], [Seb, 6, 1, Seb] Gesamtlänge: 41

3 6

4

2 5 4

4

6

2

Sebastian 5

1

5 4

5 6 Es wird die Tour aus Schritt 2 gewählt, da die Länge mit 41 kürzer ist als die der ersten Tour. Dort ist die Länge 43. d) Ist einer der bisher gefundenen Tourenpläne optimal? Warum? Allgemein lässt sich folgendes festhalten: Die durch Savings und Sweep gefundenen Lösungen sind nicht unbedingt optimal, da die Algorithmen nur eine begrenzte Anzahl aller möglichen Touren berücksichtigen (heuristische Verfahren). Der Savings-Algorithmus kann nur ein lokales Optimum erreichen, da verbessernde Entscheidungen nicht zugunsten noch besserer (aber noch unerkannter) Entscheidungen wieder verworfen werden (Greedy). Der Sweep-Algorithmus betrachtet nur Standorte, die nach einem festen Verfahren (Polarwinkel) in einem bestimmten Verhältnis zueinander stehen und garantiert damit kein globales Optimum. Speziell auf diese Aufgabe bezogen, lässt sich jedoch folgender Sachverhalt feststellen: Der Tourenplan 2, der durch das Sweep-Verfahren gewonnen wurde, mit Länge 41 ist optimal. Dies lässt sich folgendermaßen begründen: Sebastian muss auf jeden Fall 3 Touren unternehmen, um alle Mädchen abholen zu können (vgl. Kapazitätsrestriktio n Auto). Die maximale Ersparnis wäre im besten Fall 4+3+3=10 (vgl. Savings-Tabelle). Diese kann jedoch nicht erzielt werden, da beim Savings-Algorithmus bereits deutlich wurde, dass man bei Realisation des Saving von 4, nur noch ein einziges Saving von 3 erzielen kann. Die anderen Savings der Größe 3 fallen bei der Realisierung des Savings der Größe 4 weg. Die nächst bessere Ersparnis wäre folglich die Realisation von drei Savings der Größe 3 (Gesamtersparnis von 9). Diese wird durch den Sweep -Algorithmus für diese Aufgabe erzielt!

Aufgabe 8-2: Tourenplanung mit einer Tour

Die Lösung der Aufgabe erfolgt mit Hilfe des 2-opt- Verbesserungsverfahren. Die gegebene Anfangslösung [S, 2, 6, 5, 1, 3, 4, S] hat eine Tourlänge von 44 Einheiten. Index der äußeren Schleife: i Index der inneren Schleife: j I,i+1;j,j+1 =>i,j; i+1,j+1 Start des 2-opt- Algorithmus: i=1, j=3: c[S,2] + c[6,5] > c[S,6] + c[2,5] 4+7 > 5+9  Aussage falsch i=1, j=4: c[S,2] + c[5,1] > c[S,5] + c[2,1] 4+10 > 5+3  Aussage wahr Die Kanten [S,2] und [5,1] können gegen die Kanten [S,5] und [2,1] ausgetauscht werden. Dadurch verringert sich die Länge der Tour um 14-8 = 6 Einheiten, so dass die neue Tour eine Länge von 38 Einheiten hat. Zusammenfassung: Neue Tour: [S, 5, 6, 2, 1, 3, 4, S] hat eine Länge von 38 Einheiten. 1. Neustart des 2-opt- Algorithmus: i=1, j=3: c[S,5] + c[6,2] i=1, j=4: c[S,5] + c[2,1] i=1, j=5: c[S,5] + c[1,3] i=1, j=6: c[S,5] + c[3,4]

> > > >

c[S,6] + c[S,2] + c[S,1] + c[S,3] +

c[5,2] c[5,1] c[5,3] c[5,4]

5+5 > 5+9 5+3 > 4+10 5+6 > 2+10 5+8 > 5+6

 Aussage falsch  Aussage falsch  Aussage falsch  Aussage wahr

Wir tauschen nun die Kanten [S,5] und [3,4] gegen die Kanten [S,3] und [5,4] aus. Die Tourlänge verringert sich um 13-11 = 2 Einheiten, was die Gesamtlänge der Tour auf 36 Einheiten reduziert.

Zusammenfassung: Neue Tour: [S, 3, 1, 2, 6, 5, 4, S] hat eine Länge von 36 Einheiten. 2. Neustart des Algorithmus: i=1, j=3: c[S,3] + c[1,2] > c[S,1] + c[3,2] i=1, j=4: c[S,3] + c[2,6] > c[S,2] + c[3,6] i=1, j=5: c[S,3] + c[6,5] > c[S,6] + c[3,5] i=1, j=6: c[S,3] + c[5,4] > c[S,5] + c[3,4] i=2, j=4: c[3,1] + c[2,6] > c[3,2] + c[1,6]

5+3 > 2+6 5+5 > 4+10 5+7 > 5+10 5+6 > 5+8 6+5 > 6+4

 Aussage falsch  Aussage falsch  Aussage falsch  Aussage falsch  Aussage wahr

Wir tauschen nun die Kanten [3,1] und [2,6] gegen die Kanten [3,2] und [1,6] aus. Die Tourlänge verringert sich um 11-10 = 1 Einheit, was die Gesamtlänge der Tour auf 35 Einheiten reduziert. Zusammenfassung: Neue Tour: [S, 3, 2, 1, 6, 5, 4, S] hat eine Länge von 35 Einheiten. 3. Neustart des Algorithmus: i=1, j=3: c[S,3] + c[2,1] > c[S,2] + c[3,1] i=1, j=4: c[S,3] + c[1,6] > c[S,1] + c[3,6] i=1, j=5: c[S,3] + c[6,5] > c[S,6] + c[3,5] i=1, j=6: c[S,3] + c[5,4] > c[S,5] + c[3,4] i=2, j=4: c[3,2] + c[1,6] > c[3,1] + c[2,6] i=2, j=5: c[3,2] + c[6,5] > c[3,6] + c[1,5] i=2, j=6: c[3,2] + c[5,4] > c[3,5] + c[2,4] i=3, j=5: c[2,1] + c[6,5] > c[2,6] + c[1,5] i=3, j=6: c[2,1] + c[5,4] > c[2,5] + c[1,4] i=4, j=6: c[1,6] + c[5,4] > c[1,5] + c[6,4]

5+3 5+4 5+7 5+6 6+4 6+7 6+6 3+7 3+6 4+6

> > > > > > > > > >

4+6 2+10 5+10 5+8 6+5 10+9 10+8 5+10 9+10 10+9

 Aussage falsch  Aussage falsch  Aussage falsch  Aussage falsch  Aussage falsch  Aussage falsch  Aussage falsch  Aussage falsch  Aussage falsch  Aussage falsch

Ende: Der Algorithmus ist nun einmal komplett durchgelaufen ohne dass eine kürzere Tour als die zuletzt Entdeckte gefunden wurde. Somit liefert das 2-opt- Verfahren bei der gegebenen Anfangstour die folgende optimale Lösung: [S, 3, 2, 1, 6, 5, 4, S] Länge dieser Tour: 35 Einheiten...