42021_KE2_3_231 Naechster Nachbar Verfahren

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

Download Report