Transcript
42021- KE2 – 3_ 231 Nächster Nachbar Verfahren
3. 2.3.1 Sukzessivverfahren
Nächster Nachbar Aufgabenstellung (Klausur 12-9-2b): Ein Unternehmen, welches im 10. Bezirk einer Stadt ansässig ist, muss vier Einzelhandelsgeschäfte mit Ware beliefern. Für den Transport der benötigten Waren reicht ein LKW aus. Es sind folgende Daten gegeben: cij die Distanz zwischen dem Geschäft in Bezirk i und Bezirk j c ij 2 4 10 12 18
2 0 6 9 12 14
4 3 0 10 14 18
10 8 10 0 16 8
12 24 14 6 0 14
18 12 22 18 13 0
Zu bestimmen sind für das Unternehmen die Routen nach dem Nächsten-Nachbar-Verfahren. Zu diskutieren ist anschließend ob das errechnete Ergebnis eine optimale Lösung ist. Diskutieren Sie dies kurz anhand weiterer vorhandener Verfahren! Dabei soll die Vorgehensweise ausführlich erläutert werden, indem Sie jeden Schritt inklusive Zwischenlösung beschreiben.
Rolf.Baumanns/ Alexandra Ackermann
WS 2012/13
Seite 1
42021- KE2 – 3_ 231 Nächster Nachbar Verfahren
Lösungsskizze: c ij 2 4 10 12 18
2 0 6 9 12 14
4 3 0 10 14 18
10 8 10 0 16 8
12 24 14 6 0 14
18 12 22 18 13 0
Start in (10) und auch gleich das Streichen der Spalte (10) Minimum von (10): min {9;10;6;18} → c10,12 = 6 Streichen der Spalte (12) Streckenlänge = 6 Minimum von (12): min {12;14;13} → c12,2 =12 Die Wert von (10) werden dabei nicht beachtet Streichen der Spalte (2) Streckenlänge: 6+12=18 Minimum von (2): min {3;12} → c2,4 = 3 Streichen der Spalte (4) Streckenlänge: 18+3=21 Minimum von (4): min {22} → c4,18 = 22 Streichen der Spalte (18) Streckenlänge: 21+22=43 Rückfahrt zu (10): c18,10 = 8 Streckenlänge: 43+8=51 optimale Route nach dem Nächsten-Nachbar-Verfahren: (10→12→2→4→18→10) Durch Verbesserungsverfahren (z. B. Heuristiken oder Näherungsverfahren) kann eine kürzere Route erreicht werden. Damit erzielt dieses Verfahren hier keine optimale Lösung.
Rolf.Baumanns/ Alexandra Ackermann
WS 2012/13
Seite 2
42021- KE2 – 3_ 231 Nächster Nachbar Verfahren
Aufgabenstellung (Lehrstuhlvorbereitung): Ein Unternehmen, das sich in Knoten 1 befindet, möchte die Tour zu seinen Kunden, die ihre Standorte in den Knoten 2-6 haben, kostenminimal gestalten. Ausgangspunkt dieser Tour ist das Unternehmen in Knoten 1, zu dem das Fahrzeug auch am Ende der Tour wieder zurückkehren muss. Dabei liegen folgende Fahrtstrecken zwischen den Kunden sowie zum Unternehmen vor:
Fahrtstrecke nach 1 in km
2
3
4
5
6
von 1 2
310
310 -
530 740
240 510
680 120
410 340
3
530
740
-
330
290
180
4
240
510
330
-
430
420
5 6
680 410
120 340
290 180
430 420
610
610 -
Bestimmen Sie den optimalen Tourenplan mit dem Nächster-Nachbar-Verfahren. Lösungsskizze: Start in (1) und streichen der Spalte (1) Minimum von Zeile (1): min {310; 530; 240; 680; 410} → c1,4 = 240 Streichen der Spalte (4) Steckenlänge: 240 Minimum von Zeile (4): min {510; 330; 430; 420} → c4,3 = 330 ; Wert von (1) nicht beachtet Streichen der Spalte (3) Streckenlänge: 240+330= 570 Minimum von Zeile (3): min {740; 290; 180} → c3,6 = 180 Streichen der Spalte (6) Streckenlänge: 240+330+180= 750 Minimum von (6): min {340; 610} → c6,2 = 340 Streichen der Spalte (2) Streckenlänge: 240+330+180+610= 1360 Minimum von (2): min {120} → c5,2 = 120 Streichen der Spalte (5) Streckenlänge: 240+330+180+340+120= 1480 Rückfahrt zu (1): c5,1 = 680 Streckenlänge: 240+330+180+340+120+680= 1890 optimale Route nach dem Nächster-Nachbar-Verfahren: (1→4→3→6→2→5→1) Rolf.Baumanns/ Alexandra Ackermann
WS 2012/13
Seite 3
