Post on 05-Apr-2015
transcript
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
Suspensory Heuristik zum Container Stowage Problem
Seminar „Transportnetze und Umstapelprobleme“
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
Agenda
2
Problemformulierung für eine exakte Lösung
Das Suspensory Heuristic (SH) Verfahren
Diskussion über Einflussparameter
Einführung
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
3
Zahlen und Fakten – Wichtigkeit und Notwendigkeit
Containerisierung als Weiterentwicklung des traditionellen
Stückgutverkehrs
Daten des modernsten und größten Containerschiffs
- Länge: 347 m
- Breite: 42,9 m
- Höhe: 9 Containers übereinander
- Kapazität: 5000-7000; 7500 Containers
Blick auf den Hafen in Shanghai
- Umschlagkapazität: 8,61 Mio. TEU (2002)
- Rangiert auf Platz 4 (2002) unter der größte Hafen der Welt
(Platz 10 - 1998, Platz 7 - 1999)
- Durchschnittlich 28% Wachstumsrate seit 10 Jahren
- Ladefertig innerhalb 24 Stunden
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
Allgemeine Problemvorstellung – Worum geht es überhaupt?
4
Stowage Planning
(Stauraumplanung für Containerschiffe)
Aufgabe → Suchen einer optimalen Containeranordnung
für ein Containerschiff Shifting
(Umstapelung)
Kurzfristiges Entfernen und Ersetzen (Ausladen und
Wiederbeladen) von Containern in einem Containerstapel
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
Agenda
5
Problemformulierung für eine exakte Lösung
Das Suspensory Heuristic (SH) Verfahren
Diskussion über Einflussparameter
Einführung
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
6
Annahmen
Stabilität und Kraftanforderungen werden nicht berücksichtigt
Verstauen in einer einzelnen Bucht eines Schiffes
Anzahl der Hafen gegeben
Anzahl der zu transportierenden Containers bekannt
Alle Containers haben eine Standardgröße
Im letzten Hafen n, wird das Schiff vollständig entladen
T (Transportmatrix) ist zulässig
gleiche Kosten, einen Container zu verlagern, in allen Häfenund für alle Container (=1)
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
7
Wichtige Definitionen und Erklärung der Variablen
Horizontale Zeilen r = 1,…R
Vertikale Spalten c = 1,…C X = R * C
rechteckige Bucht
Abfahrthafen i = 1,…N Zielhafen j = i + 1,…N
Transportmatrix T = [Tij]
Feasible (zulässig)
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
Zielfunktion und Nebenbedingungen
8
Zielfunktion:11
1 1 1 1 1
( , )jN N R C
ijvi j i v i r c
x r c
Nebenbedingungen:1
,1 1 1 1 1 1
1 1 1
1 ( , ) ( , )
1,..., 1, 1,...,
2 ( , ) ( , )
1,..., 1, 1,..., , 1,...,
3 ( , ) ( 1, ) 0
1,..., 1, 1,..., 1, 1,..
j R C i R C
ijv kji i jv i r c k r c
ji N
kjv ik j i v i
i i
x r c x r c T
i N j i N
x r c y r c
i N r R c C
y r c y r c
i N r R c
1 1
1 1 1 1
.,
4 ( , ) ( 1, ) 1
2,..., , 1,..., 1, 1,...,
5 ( , ), ( , ) 0, 1
j j pN N
ipj ipvi p j i p j v j
ijv i
C
x r c x r c
j N r R c C
x r c y r c
Min
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
9
Anwendung von Heuristikmethoden
LP Relaxion hilft nicht. (ZF = 0) Rechenaufwand ist groß für große Probleme
NP-Vollständig für R = ∞
► Anwendung von Heuristikmethoden
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
Agenda
10
Problemformulierung für eine exakte Lösung
Das Suspensory Heuristic (SH) Verfahren
Diskussion über Einflussparameter
Einführung
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
11
Wichtige Begriffe und neue Variablen
geeignet
imG
ijP
j-container
in-order
out of order
blockierende Container
notwendige Verlagerung
optionale Verlagerung
Wiedersortierung bis m
: minimale Anzahl der optionalen Umstaplungen, die zur Wiedersortierung der Spalte bis m in Hafen i benötigt werden
1i i im m mQ G G
: gesamte Anzahl der aufzuladenden Container in Hafen i : gesamte Anzahl der j-Containers in Hafen i auf dem Dock oder in der Spalte
iM
: Zusätzliche Kosten in Hafen i (falls Wiedersortierung bis m)
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
Myopic Shifting Rule
12
11 1
m mi i i i i
i m j i m m jj i j i
M G P M G Q P
11
11
mi i i im i m m j
j i
mi ij i m
j i
Q M G Q P
P M G
0imwenn Q
Spalten wiedersortiert bis zu dem größten m(m = i + 1,…,N)
Zusätzliche Kosten in Hafen m:
(wenn nicht wieder sortiert bis m in Hafen i)
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
Beispiel
14
2 2 23 4 5
2 2 2 22 3 4 5
2 2 23 4 5
2 2 2 2 23 2 2 3 4 2 3
4, 3, 4,
0, 4, 6, 6,
4, 2, 0.
P P P
G G G G
Q Q Q
P M G und P P M G
3
3
3
3
4
4
4
5
5
5
5
3
3
4
3
5
4
5
Am Hafen i=2
Aufzuladende Container: 5,3,5,4
M2=4
Spalte wird bis 4 wieder sortiert
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
Spaltenselektionsregeln
Spaltenselektionsregeln:
Function rule max ∑{1/Yrc: für Yrc≠0}+ln(Fc+1)
Necessary shift rule min (Anzahl notwendiger Verlagerungen verursacht durch Zuordnen der Container zu diesen Spalten)
14
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
Beschreibung der SH-Procedure
Input: R, C, TOutput: Stauraumplanung & Anzahl der UmstapelungenStart: Anzahl Umstapelungen = 0
Stauraumplanung am Hafen 1: H (Hängen): - Containers in einer steigenden Folge zuordnen - „aufhängen“ der j-Container in einer leeren Spalte - falls Spalte voll → nächste leere Spalte - Alle Containers zugeordnet → F.5
F (Füllen): l = 1 F.1 falls l voll → F.3
F.2 Zuordnen der k1-Containers zum Boden der Spalte l. Falls notwendig, aktualisieren von J1.
F.3 l < C → l = l + 1 → F.1F.4 Zuordnen der übrigen Container ohne Umstaplungen
F.5 Fallen aller aufhängenden Containers. Setze i=2.
1 1k =max{j: j J }
15
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
Beschreibung der SH-Procedure
Stauraumplanung am Hafen i: U (Umladen der i-Container): - Umladen aller i-Container - Anzahl der Umstapelungen aktualisieren - T aktualisieren - Setze j = i + 1
A (Zuordnen (Assign) der j-Container): A.1 - alle j-Containers zugeordnet → A.4.2
- zulässige Spalte mit einem j-Container in der obersten Reihe & ohne z-Container, z < j in der Spalte → zuordnen der nicht zugewiesenen Container in der Spalte.
A.2 - eine zulässige Spalte ohne z-Container, z < kj → zuordnen der nicht zugewiesenen Container in der Spalte
- alle j-Container zugeordnet → A.4.2
j jk =max{d: d J }
16
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
Beschreibung der SH-Procedure
17
A.3 in jedem folgenden Fall, sind alle j-Container zugeordnet → A.4.2 A.3.1 Zulässige Spalte ohne aufgehängte Container
Oberste h-Container mit j < h < kj
→ hängen j-Containers in dieser Spalte auf. A.3.2 Zulässige Spalte mit aufgehängten Containern
Nicht hängende sind y-Containers mit y > j. j‘ ist der Hafen, der in den hängenden Containern mit j‘ < j die weiteste Entfernung hat → anordnen der j-Container direkt unter den j‘- Containern
A.3.3 Aufhängen der j-Container in einer leeren Spalte A.3.4 → A.5
A.4 A.4.1 Wiederholung von A.1-A.3 bis alle j-Containers zugeordnet sind
A.4.2 - j < N → j = j + 1, A.1 - j = N →Anzahl der Umstapelungen aktualisieren
Fallen alle aufgehängten Container - i < N - 1 → i = i + 1, U - Gehe zu End
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
Beschreibung der SH-Procedure
A.5 Unassign - Zuordnung aller h Container mit h < j aufheben, die vorher an Hafen i zugeordnet waren - Zuordnen der j-Container: 1. ganz oben in einer zulässigen Spalte ohne h-Container, h < j
2. nicht zugeordnete j-Container → ganz unten in einer leeren Spalte
A.6 Spaltenselektion: - gewählte Spalte: - Zuordnen möglichst vieler j-Container zu - Wiederhole A.6 bis alle j-Containers zugeordnet sind - Setze j = i + 1 → A.1
End: Ende des SH-Verfahrens
cc
18
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
Beispiel
Tij
Ziel→Start ↓
2 3 4 5 6
1 9 2 5 3 0
2 0 4 1 3 0
3 0 0 0 3 4
4 0 0 0 2 2
5 0 0 0 0 4
2 2 2 3 4
2 2 3 4
2 2 4
2 2 4
2 2 2 3 4
2 2 5 3 4
2 2 5 4
2 2 5 4 4
2 2 2 4
2 2 5 3 4
2 2 5 3 4
2 2 5 4 4
Stowage planning an Hafen 1:
Hängen → Füllen → Fallen
19
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
Beispiel
20
4
5 3 4
5 3 4
5 4 4
3’ 3’ 3’ 4
3’ 5 3 4
5 3 4
5 4 4
3’ 3’ 3’ 4
3’ 5 3 4
4’ 5 3 4
5 4 4
3’ 3’ 3’ 4
3’ 5 3 4
5’ 4’ 5 3 4
5’ 5’ 5 4 4
Stowage planning an Hafen 2:
3-Container (k3=6)
U��������������.1
3.1, 3.3
A
A A��������������
3.2A�������������� 3.2, 3.3A A��������������
4-Container (k4=6)
5-Container (k5=6)
Tij
Ziel→Start ↓
2 3 4 5 6
1 9 2 5 3 0
2 0 4 1 3 0
3 0 0 0 3 4
4 0 0 0 2 2
5 0 0 0 0 4
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
Beispiel
21
4’ 4
5 6’ 4
5 4 5 6’ 4
5 5 5 6’ 4
4’ 4
6’ 5 6’ 4
5 4 5 6’ 4
5 5 5 6’ 4
4
5 4
5 4 5 4
5 5 5 4 4
5’ 5’ 4
5’ 5 4
5 4 5 4
5 5 5 4 4
5 5 4 4
5 6 5 6 4
5 4 5 6 4
5 5 5 6 4
Stowage planning an Hafen 3:
U�������������� .1A��������������
5-Container (k5=6)
Spaltenselektion +Myopic Shifting Rule
Spaltenselektion +Myopic Shifting Rule
.1A��������������
Tij
Ziel→Start ↓
2 3 4 5 6
1 9 2 5 3 0
2 0 4 1 3 0
3 0 0 0 3 4
4 0 0 0 2 2
5 0 0 0 0 4
.5, .6A A�������������� .5, .6A A��������������
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
Beispiel
5
5 5 6
5 5 6
5 5 5 6
5 6’
5 5’ 5 6
5 5’ 5 6 6’
5 5 5 6 6’
6
6
6 6
6 6
6 6’
6 6’
6’ 6 6
6’ 6 6
Stowage planning an Hafen 5:
U�������������� .1, 3.3A A��������������
.1, 3.3A A��������������
Stowage planning an Hafen 4:
U��������������
Tij
Ziel→Start ↓
2 3 4 5 6
1 9 2 5 3 0
2 0 4 1 3 0
3 0 0 0 3 4
4 0 0 0 2 2
5 0 0 0 0 4
22
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
Agenda
Problemformulierung für eine exakte Lösung
Das Suspensory Heuristic (SH) Verfahren
Diskussion über Einflussparameter
Einführung
23
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
Typ der Transportmatrix
gemischte Matrix
Long Distance Matrix ► Elemente nahe an der Diagonalen sind relativ klein
Short Distance Matrix ► Elemente nahe an der Diagonalen sind relativ groß
24
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
Wahl der Spaltenselektionsregeln
Anzahl der Spalten (C) und Art der Transportmatrix irrelevant
In der Realität ist oft R≤10 und n≥10 ►Die Funktionsregel wird bevorzugt
Anzahl der Zeilen ist relativ groß und Anzahl der Hafen ist relativ klein ►Die notwendige Verlagerungsregel wird bevorzugt
25
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
S im Zusammenhang mit C,R und N
26
TYP A-Mixed C=170
0
10
20
30
40
50
60
70
80
90
10 15 20 25 30
Ports N
Sh
ifts
S
R=6 Fr.
R=8 Fr.
R=10 Fr.
R=6 Not.
R=8 Not.
R=10 Not.
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
S im Zusammenhang mit C,R und N
27
TYP A-Mixed N=30
0
10
20
30
40
50
60
70
80
90
50 80 110 140 170
Colum ns C
Sh
ifts
S
R=6 Fr.
R=8 Fr.
R=10 Fr.
R=6 Not.
R=8 Not.
R=10 Not.
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
S im Zusammenhang mit C,R und N
28
TYP B-Long Dis. N=30
0
20
40
60
80
100
120
50 80 110 140 170
Colum ns C
Sh
ifts
S
R=6 Fr.
R=8 Fr.
R=10 Fr.
R=6 Not.
R=8 Not.
R=10 Not.
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
S im Zusammenhang mit C,R und N
29
TYP B-Long Dis. N=30
0
20
40
60
80
100
120
50 80 110 140 170
Colum ns C
Sh
ifts
S
R=6 Fr.
R=8 Fr.
R=10 Fr.
R=6 Not.
R=8 Not.
R=10 Not.
Tianshu Zhu Seminar Transportnetze und
UmstapelproblemeANDOR, Herr Prof. Dr. HammerUniversität Karlsruhe (TH)
Karlsruhe,03. Juni 2003
Vielen Dank für Ihre Aufmerksamkeit!
Schluss