Tianshu Zhu Seminar Transportnetze und Umstapelprobleme ANDOR, Herr Prof. Dr. Hammer Universität...

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

Problemformulierung für eine exakte Lösung

Das Suspensory Heuristic (SH) Verfahren

Diskussion über Einflussparameter

Einführung

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?

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

Einführung

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)

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

Zielfunktion:11

1 1 1 1 1

( , )jN N R C

ijvi j i v i r c

Nebenbedingungen: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

kjv ik j i v 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

4 ( , ) ( 1, ) 1

2,..., , 1,..., 1, 1,...,

5 ( , ), ( , ) 0, 1

j j pN N

ipj ipvi p j i p j v j

x r c x r c

j N r R c C

x r c y r c

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

Einführung

Wichtige Begriffe und neue Variablen

geeignet

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

: Zusätzliche Kosten in Hafen i (falls Wiedersortierung bis m)

Myopic Shifting Rule

m mi i i i i

i m j i m m jj i j i

M G P M G Q P

mi i i im i m m j

mi ij i m

Q M G Q P

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

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.

G G G G

P M G und P P M G

Am Hafen i=2

Aufzuladende Container: 5,3,5,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)

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 }

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 }

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

Beispiel

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

Stowage planning an Hafen 1:

Hängen → Füllen → Fallen

Beispiel

3’ 3’ 3’ 4

3’ 5 3 4

3’ 3’ 3’ 4

3’ 5 3 4

4’ 5 3 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��

3.2A�� 3.2, 3.3A A��

4-Container (k4=6)

5-Container (k5=6)

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

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

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

.1A��

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 6’

5 5’ 5 6

5 5’ 5 6 6’

5 5 5 6 6’

6 6’

6’ 6 6

U�� .1, 3.3A A��

.1, 3.3A A��

U��

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

Agenda

Einführung

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ß

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

S im Zusammenhang mit C,R und N

TYP A-Mixed C=170

10 15 20 25 30

Ports N

R=6 Fr.

R=8 Fr.

R=10 Fr.

R=6 Not.

R=8 Not.

R=10 Not.

TYP A-Mixed N=30

50 80 110 140 170

Colum ns C

R=6 Fr.

R=8 Fr.

R=10 Fr.

R=6 Not.

R=8 Not.

R=10 Not.

TYP B-Long Dis. N=30

50 80 110 140 170

Colum ns C

R=6 Fr.

R=8 Fr.

R=10 Fr.

R=6 Not.

R=8 Not.

R=10 Not.

TYP B-Long Dis. N=30

50 80 110 140 170

Colum ns C

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

Tianshu Zhu Seminar Transportnetze und Umstapelprobleme ANDOR, Herr Prof. Dr. Hammer Universität...

Documents

Zhu, Lin Liu, Yang Zhu, Yuelong. 1. Theoretisches Grundlagen Medium Hypermedia Multimedia 2. Analysebeispiel von Website SONY Vorteile Nachteile 3. Quellen

Herstellung von Zementklinker Verfahrensbeschreibung und ......Forschungszentrum Karlsruhe Technik und Umwelt Wissenschaftliche Berichte Forschungszentrum Karlsruhe GmbH, Karlsruhe

Combo Hip Hop Kulturzentrum Karlsruhe€¦ · Hip Hop Kulturzentrum Karlsruhe Farbschall e.V. & Mobile Jugendarbeit Karlsruhe 21.07.2015 Uwe Buchholz 1. DAS HIP HOP KULTURZENTRUM

380-kV-Netzverstärkung Urberach-Weinheim-Karlsruhe · 2016-06-21 · 380-kV-Netzverstärkung Urberach-Weinheim-Karlsruhe • Erhöhung der Übertragungskapazität im Raum Frankfurt-Karlsruhe

Der Weg zu - Nachbarschaftsverband Karlsruhe · Karlsruhe, 04.10.2010. Erfolg durch partnerschaftliches ... Energie-agentur Kreis Karlsruhe Energie-agentur Kreis Karlsruhe "Der Weg

LANDESBANK BADEN-WÜRTTEMBERG, KARLSRUHE ......Landesbank Baden-Württemberg, Karlsruhe, Neubau Planungsbeginn 2004 Bauzeit 2005-2007 Standort Ludwig-Erhard-Allee 4, 76131 Karlsruhe

Mark A. Andor Manuel Frondel Sonja Rinne ......Mark A. Andor, Manuel Frondel und Sonja Rinne 1Wie unbeliebt ist Kohle und wie beliebt sind die Erneuerbaren? Eine empirische Regionalanalyse

HfM Karlsruhe

FINEBOOK#310 SAMMLUNG ANDOR FOLDES Miteigenh.,vierzeiligerWidmungSamuelBeckett’s«ForAndor+LiliFoldeswithallgood wishes,SamuelBeckett,ParisNov.67». 7 Beckett,Samuel.Molloy

Fotografie Karlsruhe Portfolio

Die Rache der Wardracks A - Die Legenden von Andor

STADT KARLSRUHE KARLSRUHE · inhaltsverzeichnis grusswort 1 geschichte des ortsteils karlsruhe-grÖtzingen 2 ortschaftsrÄte, stadtrÄte, bundes- und landtagsabgeordnete 5

WIrtschaft. PolItIk. WIssenschaft. Seit 1928 Managerinnen ... · 154 IKEA Deutschland Verkaufs-GmbH & Co. Einrichtungs KG Zuzana Poláková, Claudia Willvonseder, Angela Zhu 157 Dirk

KOCH - Karlsruhe

Karlsruhe: Stadtinformation

Die 98 Formen Sun-Stil TaiJiQuan -Die 98 Formen Sun-Stil TaiJiQuan 28.07.2020 Wenjun Zhu Inhaltsverzeichnis I.....- 5 -

Jiangchen Zhu- Portfolio&Resume

Ökologische Tragfähigkeitsstudie für den Raum Karlsruhe€¦ · Planungsstelle NVK Umweltamt Stadt Karlsruhe Fachgutachter Regionalverband MO Landratsamt Karlsruhe Abb. 1.2 Beschluss

Stadt Karlsruhe Sozial- und Jugendbehörde | Mobile ... · PDF file„COMBO“ HIPHOP-KULTURZENTRUM KARLSRUHE Im September 2005 ernete die Mobile Jugendarbeit des Jugendamtes Karlsruhe

50. Internationale Schwimmsport-Tage KArlsruhe · Schwimmrichter Radu Ulsamer ( )SG Region Karlsruhe Auswerter Ralf Storch ( )SG Region Karlsruhe Protokollführer Dirk Scherer ( )SG