1 2 3 6 7 5 4 Keine Rechnung erforderlich! (Bitte wenden!)

Klausur Logistik II SS 04 (neue PO)
Prof. Dr. Bernhard Fleischmann - Lehrstuhl für Produktion und Logistik - Universität Augsburg
B. Becker ist Bäcker. Seine Bäckerei bendet sich im Knoten 1. Er beliefert jeden Morgen seine Filialen (Knoten 2 bis 7) mit einem Lieferwagen. Die Kantenbewertungen geben die Längen
möglicher Straÿenverbindungen in [km] an.
7
2
4
4
1
1
6
5
3
3
7
4
5
2
6
3
9
7
5
1. (50 Minuten)
a) Bestimmen Sie für Herrn Becker mit der Heuristik des Besten Nachfolgers eine zulässige
Rundreise, die bei Knoten 1 beginnt und endet! Geben Sie die Länge der Rundreise an!
b) Nennen Sie zwei weitere Heuristiken, mit denen man symmetrische Traveling Salesman
Probleme lösen kann!
c) Berechnen Sie eine untere Schranke für die optimale Rundreise mit Hilfe der 1-Baum-
Relaxation, wobei Knoten 1 im Zyklus enthalten sein soll! Geben Sie unter Verwendung des
Ergebnisses aus 1.a) ein Intervall [LB; UB] an, in dem die Länge der optimalen Rundreise
liegt! Welcher relative GAP folgt daraus?
d) Einige Kunden von Herrn Becker wohnen in den Straÿen, die im Graph oben eingezeichnet
sind. Er überlegt sich, einen Direktbelieferungsservice für diese Kunden einzurichten, falls
die zurückzulegende Entfernung dabei nicht zu groÿ wird. Bestimmen Sie dazu eine optimale
Briefträgertour! Geben Sie die Länge an!
e) Beckers Bäckerei expandiert, weshalb sich der Bedarf der sechs Filialen bald verdoppeln
wird. Sie bekommen dann je 10 Kisten Gebäck, wobei der Lieferwagen nur Kapazität für
insgesamt 30 Kisten hat. Deshalb kauft Becker einen zweiten Lieferwagen, ebenfalls mit
der Kapazität von 30 Kisten. Zudem sollen die Filialen 2 und 3 beide als erstes um genau
6:00 Uhr beliefert werden, weshalb Becker bereits folgenden unvollständigen Tourenplan
notiert hat:
Tour 1: 1 - 2 - ... - 1
Tour 2: 1 - 3 - ... - 1
Sie haben gehört, dass man anstelle des Savings-Verfahrens auch das Einfüge-Verfahren
zur Erstellung eines Tourenplans verwenden kann, wobei Sie nacheinander die Knoten 4,
5, 6, 7 in Beckers Tourenplan einfügen wollen.
Erläutern Sie dafür eine parallele und eine sequentielle Vorgehensweise!
Keine Rechnung erforderlich!
(Bitte wenden!)
1
Klausur Logistik II SS 04 (neue PO)
Prof. Dr. Bernhard Fleischmann - Lehrstuhl für Produktion und Logistik - Universität Augsburg
2. (40 Minuten)
Im selben Straÿennetz wie bei Aufgabe 1 hat ein Kurierdienst (Depot D entspricht Knoten 1)
heute 3 Fahraufträge (A1, A2, A3) zu erledigen, nämlich von 5 nach 7 (A1), von 3 nach 4 (A2)
und von 1 nach 6 (A3). Die Aufträge sollen von nur einem Fahrzeug nacheinander ausgeführt
werden, da ein Auftrag das Fahrzeug jeweils komplett auslastet. Da es keine Einschränkungen
hinsichtlich der Reihenfolge gibt, bieten die Leerfahrten zwischen den Aufträgen Optimierungspotenzial. Hierzu wurde bereits folgende (asymmetrische) Leerfahrten-Matrix aufgestellt:
nach D A1 A2 A3
von
D
∞ 11
3
0
A1
6
∞
3
6
A2
9
2
∞
9
A3
5
12
4
∞
a) Geben Sie, ausgehend von dieser Matrix, eine untere Schranke für die Leerfahrten an,
indem Sie die Lower Bound Berechnung nach dem Branch & Bound Verfahren von Little
anwenden!
b) Verzweigen Sie das Ausgangsproblem (P0 ) und berechnen Sie die Lower Bounds für die
beiden entstehenden Teilprobleme! Verwenden Sie dazu die Spezikation des Branch &
Bound Verfahrens von Little! (Keine weiteren Verzweigungen verlangt!)
c) Mittels einer Heuristik wird nun die zulässige Auftragsabfolge D → A3 → A2 → A1 → D
mit Leerfahrtenlänge 12 ermittelt. Ist diese zulässige Lösung auch optimal ? Begründen Sie
anhand eines kleinen B&B Entscheidungsbaums der folgenden Form unter Verwendung der
Ergebnisse aus b).
P0
P1
P2
Viel Erfolg!
2

Download Report