Tianshu Zhu Seminar Transportnetze und Umstapelprobleme ANDOR, Herr Prof. Dr. Hammer Universität Karlsruhe (TH) Karlsruhe, 03. Juni 2003 Suspensory Heuristik

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“




Agenda

2

Problemformulierung für eine exakte Lösung

Das Suspensory Heuristic (SH) Verfahren

Diskussion über Einflussparameter

Einführung




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




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




Agenda

5




Einführung




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)




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)




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




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




Agenda

10




Einführung




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)




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)




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




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




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





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





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





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




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




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


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




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


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��




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


U�� .1, 3.3A A��

.1, 3.3A A��


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




Agenda




Einführung

23




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




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




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.





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.





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.





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.




Vielen Dank für Ihre Aufmerksamkeit!

Schluss

Documents

Tianshu Zhu Seminar Transportnetze und Umstapelprobleme ANDOR, Herr Prof. Dr. Hammer Universität Karlsruhe (TH) Karlsruhe, 03. Juni 2003 Suspensory Heuristik