Aufgabe 7 Tourenplanung PDF

Preview

Summary

Übung...

Description

Aufgaben zur Tourenplanung Aufgabe 7/1 – Nearest Neighbor Heuristik (1 Punkt) Die Post AG muss Pakete an 6 Kunden (Kostenmatrix von den jeweiligen Knoten finden sie unten angegeben) zustellen und startet vom Depot (0) aus. Welche Route würden Sie der Post AG, nach Anwendung der Nearest Neighbor Heuristik, empfehlen (ohne Anwendung von Verbesserungsschritten)? Wie kann mit dem Nearest Neighbor Verfahren noch eine bessere Lösung erzeugt werden (stellen Sie sich vor, dass der Fahrer den Wagen am Vortag schon beladen hat und am nächsten Tag ausliefert)?

Kosten 0 1 2 3 4 5 6

0 0 25 44 4 37 14 16

1 25 0 25 29 15 12 17

2 44 25 0 48 31 30 12

3 4 29 48 0 41 18 30

4 37 15 31 41 0 26 18

5 14 12 30 18 26 0 26

6 16 17 12 30 18 26 0

Aufgabe 7/2 – 2-opt first improvement (2,5 Punkte) In eine Metallplatte sollen fünf Löcher gebohrt werden. Die Distanzen (in mm) der Löcher 0, 1, 2, … 4 sind in der folgenden Tabelle zu entnehmen:

mm A B C D E

A 0 15 8 10 9

B 15 0 12 9 10

C D 8 10 12 9 0 6 6 0 8 4

E 9 10 8 4 0

Um wie viel kann die langjährig verwendete Lösung B-D-E-C-A-B mit Hilfe des 2-opt Verfahrens (first improvement) verbessert werden?

Aufgabe 7/3 – 2-opt best improvement (2,5 Punkte) Die Post AG hat an Ihren Lösungen Gefallen gefunden. Sie sollen eine Tour mithilfe des 2-opt Verfahrens (best improvement) die bestehende Tour verbessern. Angegeben finden Sie die Kostenmatrix von den 6 Knoten (= Kunden). Der Fahrer hat bereits die Waren verladen und ist über Nacht nachhause gefahren, von diesem Ort startet er und will auch wieder dorthin gelangen. Der Fahrer hat sich ursprünglich folgende Route überlegt 3-0-5-1-4-2-3. Versuchen Sie diese, wenn möglich, zu verbessern. Machen Sie genau 15 Vertauschungen!

IK Produktion und Logistik  PLM

Seite 1/2

Kosten 0 1 2 3 4 5

0 0 25 44 4 37 14

1 25 0 25 29 15 12

2 44 25 0 48 31 30

3 4 29 48 0 41 18

4 37 15 31 41 0 26

5 14 12 30 18 26 0

IK Produktion und Logistik  PLM

Seite 2/2...