133 56 2MB
German Pages 285 Year 2009
Leif Hendrik Meier Koordination interdependenter Planungssysteme in der Logistik
GABLER EDITION WISSENSCHAFT
Leif Hendrik Meier
Koordination interdependenter Planungssysteme in der Logistik Einsatz multiagentenbasierter Simulation im Planungsprozess von Container-Terminals im Hafen
Mit einem Geleitwort von Prof. em. Dr. Dr. h. c. Jürgen Bloech
GABLER EDITION WISSENSCHAFT
Bibliografische Information der Deutschen Nationalbibliothek Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über abrufbar.
Dissertation Universität Göttingen 2008
. . lage Dezember 1997 1. Auflage 2008 Alle Rechte vorbehalten © Gabler | GWV Fachverlage GmbH, Wiesbaden 2008 Lektorat: Frauke Schindler / Jutta Hinrichsen Gabler ist Teil der Fachverlagsgruppe Springer Science+Business Media. www.gabler.de Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Jede Verwertung außerhalb der engen Grenzen des Urheberrechtsgesetzes ist ohne Zustimmung des Verlags unzulässig und strafbar. Das gilt insbesondere für Vervielfältigungen, Übersetzungen, Mikroverfilmungen und die Einspeicherung und Verarbeitung in elektronischen Systemen. Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten wären und daher von jedermann benutzt werden dürften. Umschlaggestaltung: Regine Zimmer, Dipl.-Designerin, Frankfurt/Main Gedruckt auf säurefreiem und chlorfrei gebleichtem Papier Printed in Germany ISBN 978-3-8349-1418-7
Geleitwort
V
Geleitwort Für große Logistiksysteme im nationalen und internationalen Güteraustausch der Industrie und des Handels erschwert die hohe Komplexität der Logistiknetze den guten Überblick für die verantwortlichen Entscheidungsträger hinsichtlich guter Planungen und Steuerungen. Dies gilt insbesondere für vermaschte Logistiksysteme aus teilweise getrennt liegenden Komponenten, wie diese in Container-Terminals vorkommen. Untersuchungen über große Logistiksysteme versprechen daher einen hohen Informationsgewinn. Eine abgestimmte Steuerung der Positionierung der Containerschiffe, der Zuweisung der Containerbrücken, der Lagerort-Festlegung auf dem Lagergelände und in dem Containerstapel sowie die Transportplanung für die Beförderung der Container aus dem Lager heraus sind Herausforderungen der Analyse in diesem Buch. In informativer Art werden im ersten Teil der Darstellung die Grundaktivitäten einer Container-Logistik in Häfen beschrieben. Dabei kommen auch die Grundstrukturen und Prozesse einer Transportlogistik gut zur Sprache. Es wird auch deutlich, dass für die verantwortlichen Logistik-Manager einer ContainerLogistik wirtschaftlich bedeutsame Planungsprobleme auftreten, die einer Optimierung bedürfen. Konsequenterweise werden deshalb auch Modelle und Ansätze zur Optimierung verschiedener Teilbereiche der Container-Logistik knapp und kritisch dargestellt. Die Entwicklungstrends der Container-Terminals führen zu größerer Bedeutung einer abgestimmten Planung, welche die Interdependenzen der einzelnen Planungsstrukturen berücksichtigt. Für die Lösung dieser Fragestellung stellt der Autor Leif Hendrik Meier das vielversprechende Konzept eines Multiagentenmodells vor. Dieses Konzept wird eingehend dargelegt und diskutiert. Die Struktur und das Zusammenwirken der Agenten für die Planungsbereiche werden eingehend beschrieben und die menschlichen Eingriffsmöglichkeiten aufgezeigt. Die Arbeit führt schließlich auch die Umsetzung des Multiagenten-Planungsmodells durch ein einsetzbares Programm vor und zeigt umfangreiche Anwendungen des Optimierungsprogramms mit vielversprechenden Ergebnissen.
VI
Geleitwort
Das Buch wird von mir Wissenschaftlern und Praktikern empfohlen, die ein Interesse für moderne Logistiksysteme hegen und deren komplexe Strukturen und Prozessverknüpfungen gedanklich durchdringen wollen. Auch Studierende verschiedener Institutionen können sich durch diese Schrift ein großes Wissen über eine Logistik aneignen, die ihnen in der Gestalt der transportierten Container bereits täglich auf den Straßen dieser Welt begegnet und ihnen in den modernen Häfen dieser Erde durch unübersehbar große ContainerTerminals ins Auge fällt.
J. Bloech
Vorwort
VII
Vorwort Nahezu täglich ist den Medien zu entnehmen, dass der Logistik eine wachsende Bedeutung zukommt. Die Bedeutung insbesondere der maritimen Logistik konnte ich, unweit von Bremerhaven aufgewachsen, „hautnah“ miterleben. Mit dem Wachstum des Umschlags wuchs auch meine Begeisterung für diese Aufgabenstellung. Ohne die Unterstützung all derer, die mich während meiner Dissertation angetrieben und begleitet haben, hätte ich die Arbeit nicht in dieser Form fertig stellen können. Hierfür möchte ich mich herzlich bedanken. An erster Stelle danke ich meinem Doktorvater Herrn Prof. Dr. Dr. h.c. Jürgen Bloech am Institut für Betriebswirtschaftliche Produktions- und Investitionsforschung, mit dem ich meine Ideen jederzeit diskutieren konnte. Herrn Prof. Dr. Matthias Schumann möchte ich für die Übernahme des Zweitgutachtens und u.a. für die Bereitstellung der notwendigen Rechenkapazitäten für die Simulationen sowie für die finanzielle Unterstützung auf Konferenzen danken. Herrn Prof. Dr. Wolfgang König danke ich für die Übernahme der mündlichen Prüfung. Herrn Prof. Dr. Jörg Biethahn gebührt großer Dank, weil er mich durch sein Interesse an meiner Arbeit immer wieder motivieren konnte und mir einen idealen Einstieg in die Promotion ermöglicht hat. Meinen ehemaligen Kollegen danke ich für ihre hervorragende Unterstützung. Hier ist es mir wichtig, insbesondere Herrn Dr. Andreas Lackner, Herrn Dr. Ole Brodersen und Herrn Dr. Helge Fischer zu nennen, weil mir ihre Unterstützung ganz besonders wichtig war. Danken möchte ich auch Herrn Prof. Dr. Antonio Maçada, der sich während unserer Aufenthalte in Brasilien mit voller Aufopferung für uns eingesetzt hat. Für die dieser Arbeit zur Verfügung gestellten Daten und die jederzeit freundlichen Diskussionen möchte ich mich bei Herrn Prof. Dr. Carsten Boll und Herrn Dr. Holger Schütt bedanken, die immer ein offenes Ohr für meine Ideen hatten und mich unterstützt haben, diese auch zu verwirklichen. Für die praktische Unterstützung möchte ich Herrn Norbert Klettner und Herrn Stefan Müller danken. Sie haben mir einen tollen Einblick in die Hafen- und Containerwelt ermöglicht.
VIII
Vorwort
Weiterhin möchte ich mich bei allen Korrekturlesern bedanken. Hier seien für ihr erhebliches Engagement vor allem meine Eltern, Frau Angelika Hebold, Herr Dr. Sebastian Rieger, Frau Kerstin Sandrock und Herr Matthias Theubert erwähnt. Herrn René Schumann danke ich für die interessanten Diskussionen und die gemeinsame Beteiligung an der Konferenz in Bremen. Ihm selbst - und auch Herrn Theubert - wünsche ich ebenfalls alles Gute für die eigenen Promotionsvorhaben. Zudem möchte ich allen weiteren Freunden und Bekannten aus Bremerhaven und aus Göttingen danken, auf deren Unterstützung ich immer zählen konnte. Auch für die zahlreichen guten Tipps, die ich während dieser Zeit sammeln konnte - sei es fachlicher Art: „Entwickle doch den Algorithmus, wo man immer mit muss!“ - oder auch grammatikalischer Art: „Ich setze Kommata einfach nach jedem fünften Wort.“ Manchmal saß ich am Computer und musste einfach schmunzeln. Danke dafür. Abschließend möchte ich mich für den starken privaten Rückhalt bei meinen Eltern und meinem Bruder bedanken. Meine Jana lässt mich jeden Tag glücklicher werden. Auch ihre Familie, die mich so liebevoll aufgenommen hat, ist für mich besonders wertvoll. Die Arbeit ist meiner Familie gewidmet.
Göttingen im August 2008 Leif Hendrik Meier
Inhaltsüberblick
IX
Inhaltsüberblick GELEITWORT........................................................................................................................ V VORWORT .......................................................................................................................... VII INHALTSÜBERBLICK ............................................................................................................IX INHALTSVERZEICHNIS .........................................................................................................XI ABBILDUNGSVERZEICHNIS ................................................................................................ XV TABELLENVERZEICHNIS ..................................................................................................XIX ABKÜRZUNGSVERZEICHNIS .............................................................................................XXI 1 EINLEITUNG ...................................................................................................................... 1 2 GRUNDLAGEN LOGISTISCHER SYSTEME UND PROZESSE ................................................ 9 3 PLANUNG IN CONTAINER-TERMINALS .......................................................................... 61 4 LEISTUNG UND GRENZEN BESTEHENDER CT-MODELLE ............................................ 141 5 ENTWICKLUNG EINES MULTIAGENTENBASIERTEN MODELLS ZUR CTPROZESSKOORDINATION .............................................................................................. 157 6 KOORDINATION DES PLANUNGSPROZESSES IN CONTAINER-TERMINALS .................. 183 7 SCHLUSSBETRACHTUNG ............................................................................................... 229 ANHANG ............................................................................................................................. 233 LITERATURVERZEICHNIS .................................................................................................. 253
Inhaltsverzeichnis
XI
Inhaltsverzeichnis GELEITWORT........................................................................................................................ V VORWORT .......................................................................................................................... VII INHALTSÜBERBLICK ............................................................................................................IX INHALTSVERZEICHNIS .........................................................................................................XI ABBILDUNGSVERZEICHNIS ................................................................................................ XV TABELLENVERZEICHNIS ..................................................................................................XIX ABKÜRZUNGSVERZEICHNIS .............................................................................................XXI 1 EINLEITUNG ...................................................................................................................... 1 1.1 Motivation und Problemstellung............................................................................ 1 1.2 Zielsetzung................................................................................................................ 4 1.3 Methodik und Aufbau der Arbeit .......................................................................... 6 2 GRUNDLAGEN LOGISTISCHER SYSTEME UND PROZESSE ................................................ 9 2.1 Kennzeichen der Logistik ....................................................................................... 9 2.1.1 Einordnung in die Betriebswirtschaftslehre ................................................... 9 2.1.2 Funktionen und Ziele ................................................................................... 12 2.1.3 Systemtheoretische Grundlagen................................................................... 16 2.2 Modellierung und Optimierung ........................................................................... 17 2.2.1 Modellgestützte Planung.............................................................................. 18 2.2.2 Klassifizierung relevanter Methoden des Operations Research................... 22 2.2.3 Optimierung ................................................................................................. 25 2.2.3.1 Prioritätsregeln ............................................................................... 25 2.2.3.2 Greedy-Verfahren .......................................................................... 27 2.2.3.3 Metaheuristiken.............................................................................. 28 2.2.3.3.1 Allgemeine Kennzeichen............................................... 28 2.2.3.3.2 Genetische Algorithmen................................................ 29 2.2.3.3.3 Particle Swarm Optimization ........................................ 32 2.2.3.3.4 Simulated Annealing ..................................................... 34
XII
Inhaltsverzeichnis
2.2.3.3.5 Weitere Metaheuristiken................................................37 2.2.3.4 Branch and Bound-Verfahren ........................................................38 2.2.3.5 Hybride Verfahren .........................................................................40 2.2.3.6 Kommerzielle Optimierungstools ..................................................41 2.2.4 Simulation ....................................................................................................41 2.2.4.1 Grundlagen der Simulation ............................................................42 2.2.4.2 Position der Simulation in der Logistik .........................................42 2.2.4.3 Anforderungen an eine Simulationssprache...................................43 2.3 Koordination betrieblicher Entscheidungen.......................................................44 2.3.1 Defekte Strukturen in Planungssystemen.....................................................44 2.3.2 Koordinationsbedarf.....................................................................................47 2.3.3 Klassische Koordinationsinstrumente ..........................................................49 2.3.3.1 Simultanplanung ............................................................................49 2.3.3.2 Sukzessivplanung...........................................................................49 2.3.3.3 Retrograde/ progressive Planung und Gegenstromverfahren ........50 2.3.3.4 Rollende Planung ...........................................................................51 2.3.3.5 Alternative Betrachtungsperspektive .............................................52 2.4 Einsatz von Multiagentensystemen ......................................................................55 2.4.1 Grundlagen ...................................................................................................55 2.4.2 Koordination und Zusammenarbeit..............................................................57 3 PLANUNG IN CONTAINER-TERMINALS...........................................................................61 3.1 Grundlagen.............................................................................................................61 3.1.1 Einordnung in die Logistik...........................................................................61 3.1.2 Entwicklung..................................................................................................67 3.1.3 CT-Struktur und -Prozesse ...........................................................................71 3.1.4 Umschlag- und Flurfördergeräte ..................................................................73 3.2 Analyse von Modellen in Container-Terminal-Problemstellungen ..................79 3.2.1 Überblick ......................................................................................................80 3.2.2 Liegeplatzplanung (Berth Allocation Problem) ...........................................81 3.2.2.1 Ansätze in der Literatur..................................................................81 3.2.2.2 Berth Allocation Problem nach GUAN und CHEUNG .....................88 3.2.2.3 Annahmen und Kritik.....................................................................92 3.2.3 Containerbrückeneinsatzplanung (Crane Scheduling Problem)...................93 3.2.3.1 Ansätze in der Literatur..................................................................94 3.2.3.2 Crane Scheduling Problem nach ZHU und LIM ...........................100 3.2.3.3 Annahmen und Kritik...................................................................105 3.2.4 Yardorganisation (Storage Space Allocation und Location Assignment)..107 3.2.4.1 Ansätze in der Literatur................................................................107 3.2.4.2 Storage Location Problem nach ZHANG ET AL. ...........................117
Inhaltsverzeichnis
XIII
3.2.4.3 Annahmen und Kritik .................................................................. 127 3.2.5 Transportplanung (Vehicle Dispatching Problem) .................................... 127 3.2.5.1 Ansätze in der Literatur................................................................ 127 3.2.5.2 Vehicle Dispatching Problem nach BÖSE ET AL.......................... 129 3.2.5.3 Annahmen und Kritik .................................................................. 133 3.2.6 Weitere Planungssysteme und -ansätze ..................................................... 134 3.3 Interdependenzen ................................................................................................ 136 4 LEISTUNG UND GRENZEN BESTEHENDER CT-MODELLE ............................................ 141 4.1 Zusammenfassung wesentlicher Trends............................................................ 141 4.2 Leistung und Grenzen isolierter Modelle.......................................................... 143 4.3 Implikationen....................................................................................................... 150 5 ENTWICKLUNG EINES MULTIAGENTENBASIERTEN MODELLS ZUR CTPROZESSKOORDINATION .............................................................................................. 157 5.1 Das Container-Terminal Management Problem (CTMP) .............................. 157 5.1.1 Modellbeschreibung und -architektur ........................................................ 157 5.1.2 Definition eines Zielsystems im CT-Modell.............................................. 165 5.1.2.1 Klassifizierung von Zielen ........................................................... 165 5.1.2.2 Übergreifende Ziele des Modells................................................. 168 5.1.2.3 Konkurrierende Zielsetzungen..................................................... 171 5.1.3 Modellkritik................................................................................................ 173 5.2 Technische Realisierung ..................................................................................... 175 5.2.1 Java............................................................................................................. 175 5.2.2 JADE und Ontologien ................................................................................ 176 5.2.3 Protégé........................................................................................................ 179 5.2.4 Extensible Markup Language (XML) ........................................................ 180 5.2.5 Unterstützende Tools ................................................................................. 181 6 KOORDINATION DES PLANUNGSPROZESSES IN CONTAINER-TERMINALS .................. 183 6.1 Experimenteller Aufbau und Durchführung.................................................... 183 6.1.1 Methoden- und Parameteranalyse in isolierter Umgebung ........................ 184 6.1.1.1 Analyse von Methoden zur Lösung des BAP .............................. 184 6.1.1.2 Analyse von BAP-Parametern ..................................................... 190 6.1.1.3 Analyse von Methoden zur Lösung des CSP............................... 196 6.1.1.4 Analyse von CSP-Parametern...................................................... 201 6.1.1.5 Analyse von Methoden zur Lösung des SLP ............................... 205 6.1.1.6 Analyse von SLP-Parametern ...................................................... 207 6.1.2 Analyse von Koordinationsinstrumenten in MAS-Umgebung .................. 210 6.1.2.1 Untersuchung von Teilmengen des CTMP.................................. 211
XIV
Inhaltsverzeichnis
6.1.2.1.1 Koordination von BAP und CSP .................................211 6.1.2.1.2 Koordination von BAP und SLP .................................217 6.1.2.2 Untersuchung des CTMP .............................................................220 6.1.2.2.1 Sequenzielle Koordination als Benchmark..................220 6.1.2.2.2 Multiagentenbasierte Koordination .............................222 6.2 Übertragbarkeit und Interpretation der Ergebnisse........................................225 6.3 Erweiterbarkeit und Modellkritik .....................................................................227 7 SCHLUSSBETRACHTUNG ...............................................................................................229 ANHANG .............................................................................................................................233 A1: Konstruktive Verfahren und lokale Suche ........................................................233 A2: CSP-Eröffnungsheuristiken ................................................................................234 A3: CSP-Nachbarschaft (SA).....................................................................................236 A4: Visualisierung von Ergebnissen isolierter Modelle...........................................238 A5: Port Model in Protégé..........................................................................................240 A6: Kommunikation in JADE....................................................................................242 A7: Verwendeter Datensatz........................................................................................243 A8: Yard-Layout .........................................................................................................244 A9: XML-Daten...........................................................................................................245 A10: XML-Parameter.................................................................................................246 A11: Adjazenzmatrix (aus dem Liegeplatzplan resultierend) ................................251 LITERATURVERZEICHNIS ..................................................................................................253
Abbildungsverzeichnis
XV
Abbildungsverzeichnis Abbildung 2-1: Logistische Grundfunktionen TUIL........................................................... 14 Abbildung 2-2: Netzstrukturen ............................................................................................ 15 Abbildung 2-3: Greedy-Heuristik........................................................................................ 27 Abbildung 2-4: Spezifikationslevel von Heuristiken........................................................... 28 Abbildung 2-5: Pseudocode evolutionärer Algorithmen ..................................................... 31 Abbildung 2-6: Ablauf der PSO für kombinatorische Problemstellungen .......................... 33 Abbildung 2-7: Akzeptanzwahrscheinlichkeiten beim SA.................................................. 36 Abbildung 2-8: Pseudocode des Simulated Annealing........................................................ 37 Abbildung 2-9: Lösungsbaum zu den Branch and Bound-Verfahren ................................. 39 Abbildung 2-10: Systemrelationen im statischen und dynamischen Fall............................ 48 Abbildung 2-11: Retrograde (a), progressive (b) und Gegenstrom-Planung (c) ................. 50 Abbildung 2-12: Prinzip rollender Planung......................................................................... 52 Abbildung 2-13: Formen der Koordination nach ADAM ET AL........................................... 52 Abbildung 2-14: Schritte des CDPS .................................................................................... 58 Abbildung 3-1: Klassifizierung von Terminals in Seehäfen ............................................... 63 Abbildung 3-2: CT-Prozess ................................................................................................. 72 Abbildung 3-3: Aufbau des Zwischenlagers unterschiedlicher Betriebssysteme................ 78 Abbildung 3-4: Entscheidungsbereiche ............................................................................... 80 Abbildung 3-5: Idealtypische Liegeplatzplanung mit time-space-Diagramm..................... 82 Abbildung 3-6: Planung von Liegeplätzen für Containerschiffe......................................... 82 Abbildung 3-7: Chromosom-Repräsentation einer BAP-Lösung für den GA von NISHIMURA ET AL. ..................................................................................... 84 Abbildung 3-8: Drei Terminals in Singapur ........................................................................ 85 Abbildung 3-9: Zuordnung von Containerschiffen auf einem Zylinder (rechts) statt auf einer Fläche (links) .................................................................................... 87 Abbildung 3-10: Die Lösungsprozedur von GUAN und CHEUNG als Pseudocode.............. 91 Abbildung 3-11: Composite Heuristik von GUAN und CHEUNG ........................................ 92
XVI
Abbildungsverzeichnis
Abbildung 3-12: Vorgänger- Beziehung zwischen Jobs im CSP ........................................96 Abbildung 3-13: (Q)CSP-Modellentwicklung (KIM und PARK) .........................................98 Abbildung 3-14: Entwicklung von CSP-Modellen (LIM ET AL.) ........................................99 Abbildung 3-15: Bestimmung der Containerposition in dem Yard-Block, LAP ..............107 Abbildung 3-16: Einfluss des Equipments auf die Lagerfähigkeit in TEU/Hektar ...........109 Abbildung 3-17: Anzahl der zu im-, bzw. exportierenden Container eines bestimmten Schiffes im Yard ......................................................................................112 Abbildung 3-18: Unterschiedliche Yard-Zuordnung.........................................................113 Abbildung 3-19: Bezeichnung der Containertypen nach ZHANG ET AL............................118 Abbildung 3-20: Auswahl einer Metrik zur Bestimmung der Distanz im CT-Modell......125 Abbildung 3-21: Darstellung des SLP ...............................................................................126 Abbildung 3-22: Restriktionen für das VDP unter verschiedenen Zuordnungsstrategien.132 Abbildung 3-23: Optimale QC-Auslastung .......................................................................133 Abbildung 5-1: Komponenten des CTMP-Modells...........................................................158 Abbildung 5-2: Black Box-Betrachtung ............................................................................160 Abbildung 5-3: CTMP-Struktur.........................................................................................160 Abbildung 5-4: Konkretisierung der Planung....................................................................161 Abbildung 5-5: Architektur der Agenten im Modell .........................................................162 Abbildung 5-6: In die Terminal-Umgebung eingesetzte Agenten.....................................163 Abbildung 5-7: CT-Entity Relationship Modell (ohne Attribute) .....................................164 Abbildung 5-8: Überblick behandelter Entscheidungsbereiche im Modell.......................165 Abbildung 5-9: Zieldefinition ............................................................................................169 Abbildung 5-10: Zielkonflikt zwischen Transportdistanz und Wartezeit..........................171 Abbildung 6-1: BAP-Ergebnisse für GA und PSO (Boxplots) .........................................188 Abbildung 6-2: Vergleich eingesetzter BAP-Methoden....................................................189 Abbildung 6-3: Variation der Kailänge .............................................................................191 Abbildung 6-4: Optimale Kailänge (S*) in Abhängigkeit von Z und k .............................194 Abbildung 6-5: Zielkonflikt BAP-Parameter (Kailänge)...................................................195 Abbildung 6-6: CSP-Ergebnisse für SA und GA (Boxplots) ............................................199
Abbildungsverzeichnis
XVII
Abbildung 6-7: CSP Heuristiken ....................................................................................... 200 Abbildung 6-8: Optimierung der Eröffnungsheuristik mit SA und GA ............................ 201 Abbildung 6-9: Variation der Anzahl eingesetzter Containerbrücken .............................. 202 Abbildung 6-10: Optimale Containerbrückenanzahl (m*) in Abhängigkeit von Z und k 204 Abbildung 6-11: SLP-Ergebnisse mit GA und FRE nach MURTY .................................... 207 Abbildung 6-12: Versuchsaufbau SLP-Parameter............................................................. 208 Abbildung 6-13: Variation der SLP-Parameter ................................................................. 209 Abbildung 6-14: Entscheidungsbaum des CTMP ............................................................. 210 Abbildung 6-15: Iterativer Verlauf für BAP und CSP ...................................................... 212 Abbildung 6-16: MAS-basiertes Vorgehen für BAP und CSP.......................................... 214 Abbildung 6-17: Lösungsvielfalt in der Population des GA ............................................. 215 Abbildung 6-18: Vergleich sequenzieller, iterativer und MAS-basierter Koordination ... 217 Abbildung 6-19: Ablauf iterativer/ MAS-basierter Koordination für BAP und SLP........ 219 Abbildung 6-20: Sequenzielles CTMP-Ergebnis (Boxplot).............................................. 221 Abbildung 6-21: MAS-basierte Koordination im CTMP .................................................. 222 Abbildung 6-22: Entwicklung der Zielgrößen des CTMP im Planungsprozess................ 224 Abbildung A-1: Greedy-Konstruktion einer TSP-Lösung (suboptimal) ........................... 233 Abbildung A-2: CSP-Eröffnungsheuristik (Pseudocode).................................................. 235 Abbildung A-3: Erweiterte CSP-Eröffnungsheuristik (Pseudocode) ................................ 236 Abbildung A-4: Erzeugen einer benachbarten Lösung für das CSP (NB1) ...................... 237 Abbildung A-5: Erzeugen einer benachbarten Lösung für das CSP (NB2) ...................... 237 Abbildung A-6: Greedy CSP-Zuordnung .......................................................................... 238 Abbildung A-7: Containerbrückenbewegung am Kai mit EH2......................................... 239 Abbildung A-8: Yard-Auslastung im Planungszeitraum................................................... 240 Abbildung A-9: Klassenhierarchie in Protégé................................................................... 241 Abbildung A-10: Vessel-Entity in Protégé ....................................................................... 241 Abbildung A-11: Kommunikation bei sequenzieller Koordination .................................. 242 Abbildung A-12: Kommunikation bei MAS-basierter Koordination................................ 243 Abbildung A-13: Beispiel Liegeplatzzuordnung und resultierende Adjazenzmatrix........ 251
Tabellenverzeichnis
XIX
Tabellenverzeichnis Tabelle 1-1: Containerumschlag im weltweiten Vergleich ................................................... 3 Tabelle 2-1: Logistikprozesse und durch sie bewirkte Gütertransformation....................... 12 Tabelle 2-2: Statische Dimensionen der Systemkomplexität und Kompliziertheit ............. 47 Tabelle 2-3: Konzeptionen der Planungsmethodik.............................................................. 55 Tabelle 4-1: Untersuchung bestehender Modelle .............................................................. 146 Tabelle 4-2: Defektanalyse in CT-Modellen ..................................................................... 149 Tabelle 4-3: Experimente des MAS und Planungsebene................................................... 153 Tabelle 6-1: Anzahl operierender QC für Schiffstyp (Annahme) ..................................... 185 Tabelle 6-2: BAP-Parametereinstellungen für GA............................................................ 187 Tabelle 6-3: BAP-Parametereinstellungen für PSO .......................................................... 187 Tabelle 6-4: BAP-Ergebnisse für GA und PSO................................................................. 189 Tabelle 6-5: BAP-Ergebnisse unter Variation der Kailänge ............................................. 191 Tabelle 6-6: Nutzen und Kosten der verlängerten Kailänge.............................................. 192 Tabelle 6-7: Optimale Kailänge (S*) in Abhängigkeit von Z und k .................................. 194 Tabelle 6-8: CSP-Parametereinstellungen für SA ............................................................. 198 Tabelle 6-9: CSP-Parametereinstellungen für GA............................................................. 198 Tabelle 6-10: CSP-Ergebnisse für SA und GA ................................................................. 199 Tabelle 6-11: Fitnesswert und Standardabweichung für CSP-Parametervariation ........... 203 Tabelle 6-12: Kumulierte Reduktion der Aufenthaltszeit für CSP-Parametervariation .... 203 Tabelle 6-13: Optimale Containerbrückenanzahl (m*) in Abhängigkeit von Z und k ...... 204 Tabelle 6-14: SLP-Einstellungen für GA .......................................................................... 206 Tabelle 6-15: Ergebnisse der iterativen Untersuchung für BAP und CSP ........................ 213 Tabelle 6-16: Vergleich von Koordinationsmethoden zwischen BAP und CSP............... 216 Tabelle 6-17: Vergleich von Koordinationsmethoden zwischen BAP und SLP ............... 219 Tabelle 6-18: Vergleich sequenzieller und MAS-basierter Koordination ......................... 223 Tabelle A-1: Verwendeter Datensatz................................................................................. 244 Tabelle A-2: Yard-Layout ................................................................................................. 245
Abkürzungsverzeichnis
XXI
Abkürzungsverzeichnis ACO
Ant Colony Optimization
ACL
Agent Communication Language
ALV
Automated Lifting Vehicle
AGSC
Automated Guided Straddle Carrier
AGV
Automated Guided Vehicle
API
Application Programming Interface, Programmierschnittstelle
(S)BAP
(Static) Berth Allocation Problem, Liegeplatzplanung
BMVBS
Bundesministerium für Verkehr, Bau und Stadtentwicklung
BMWi
Bundesministerium für Wirtschaft und Technologie
CDPS
Kooperativ verteiltes Problemlösen (Cooperative Distributed Problem Solving)
CH
Composite Heuristic
CLM
Council of Logistics Management
CORBA
Common Object Request Broker Architecture
CSI
Container Security Initiative
CSP
Crane Scheduling Problem, Containerbrückenplanung
CSV
Comma Separated Values
CT
Container-Terminal
CTMP
Container-Terminal Management Problem
CYGD
Container Yard Grounding-Container (Bezeichner aus dem Modell von ZHANG ET AL.)
CYPI
Container Yard Pickup-Container (Bezeichner aus dem Modell von ZHANG ET AL.)
DSS
Decision Support System
ERM
Entity Relationship Modell
FIFO/ FIFS
First In First Out/ First In First Served
FIPA
Foundation for Intelligent Physical Agents
FRE
Fill Ratio Equalization
GA
Genetischer Algorithmus
GRASP
Greedy Randomized Adaptive Search Procedure
XXII
Abkürzungsverzeichnis
GUI
Graphical User Interface
h
Stunden
HGB
Handelsgesetzbuch
HTML
Hypertext Markup Language
ISL
Institut für Seeverkehrswirtschaft und Logistik
IT
Informationstechnologie
JADE
Java Agent Developvent Environment
KI
Künstliche Intelligenz
KTP
Klassisches Transportproblem
LAP
Location Assignment Problem
LIFO
Last In First Out
Lkw
Lastkraftwagen
LMTT
Linear Motor Based Transfer Technology
m
Meter
MA(B)S
Multiagentensystem (Multi Agent Based Simulation)
min
Minuten
MODI
Modified Distribution Methode
MTT
Multitrailer Train, Zugmaschine
NWE
Nordwesteckenregel
OR
Operations Research
ÖTV
Gewerkschaft für Öffentliche Dienste, Transport und Verkehr
PGP
Partial Global Planning
PSO
Particle Swarm Optimization
PWE
Pairwise-Exchange
QC
Containerbrücke (Quay Crane)
RMG
Rail Mounted Gantry Crane
RMI
Remote Method Invocation
RTG
Rubber Tyred Gantry Crane
s
Sekunden
SA
Simulated Annealing
(S)BS
(Stochastic) Beam Search
sd
Standardabweichung
Abkürzungsverzeichnis SLP
Storage Location Problem, Yardplanung
SL
Semantic Language
SOAP
Simple Object Access Protocol
SRM
Stakeholder Relationship Management
TEU
Twenty Foot Equivalent Unit
TIP
Time in Port, Aufenthaltszeit
TS
Tabu Search
TSP
Tree-Search-Procedure
UM
Ungarische Methode
VAM
Vogel’sche Approximationsmethode
VC
Van Carrier (Transportfahrzeug)
VDP
Vehicle Dispatching Problem, Transportplanung
VSDS
Vessel Discharge-Container (Bezeichner aus dem Modell von ZHANG ET AL.)
VSLD
Vessel Loading-Container (Bezeichner aus dem Modell von ZHANG ET AL.)
XML
eXtensible Markup Language
XXIII
Einleitung
1
1 Einleitung „Das Ganze ist mehr als die Summe seiner Teile“ (Aristoteles) Dieses Kapitel dient der Einführung in die Thematik der vorliegenden Dissertation. Hierzu werden zuerst Motivation und Problemstellung sowie die verfolgte Zielsetzung dargestellt. Anschließend wird auf den Aufbau dieser Arbeit eingegangen.
1.1 Motivation und Problemstellung Die Logistik ist auf die bedarfsgerechte Verfügbarkeit von Objekten ausgerichtet. Zu den logistischen Prozessen zählen alle Transport- und Lagerprozesse, das dazugehörige Beund Entladen, Ein- und Auslagern (der Umschlag) sowie das Kommissionieren.1 Es liegt damit ein wesentlicher Unterschied zur Produktion vor, die sich mit der Transformation von Produktionsfaktoren in Güter und Dienstleistungen in einem Kombinationsprozess beschäftigt.2 Die Logistik dient der Raumüberbrückung von Objekten durch Transport, der Zeitüberbrückung von Objekten durch Lagerung und der Veränderung der Anordnung von Objekten durch Kommissionierung.3 Güterverkehr und Logistik sind entscheidende Faktoren für die internationale Wettbewerbsfähigkeit der Weltmarkt orientierten deutschen Wirtschaft.4 Die Logistik ist unverzichtbarer Bestandteil aller modernen und wettbewerbsfähigen Produktions- und Dienstleistungsprozesse. Sie bildet damit die Grundlage für wirtschaftliche Wertschöpfung, materiellen Wohlstand und die soziale Basis der deutschen Gesellschaft.5 So ist in Deutschland nahezu jeder Arbeitsplatz direkt oder indirekt von einem funktionierenden Güterverkehrssystem abhängig. Die Attraktivität des Industriestandortes ist maßgeblich von der Leistungsfähigkeit des Güterverkehrssystems und der Logistik beeinflusst. Eine Studie des BUNDESMINISTERIUMS
1
Vgl. FLEISCHMANN, B. (2004), S. A1-3.
2
Vgl. BLOECH, J. et al. (2008), S. 3f.
3
Vgl. FLEISCHMANN, B. (2004), S. A1-3.
FÜR
VERKEHR, BAU
UND
STADTENTWICKLUNG
4
Bundesministerium für Verkehr, Bau und Stadtentwicklung (BMVBS) (2007a), S. 2.
5
Vgl. Bundesministerium für Verkehr, Bau und Stadtentwicklung (BMVBS) (2007a), S. 2.
2
Einleitung
(BMVBS) schätzt, dass das Güterverkehrsaufkommen in Deutschland bis zum Jahr 2050 um etwa die Hälfte zunehmen wird. Die Güterverkehrsleistung wird sich mehr als verdoppeln.6 Gleichzeitig liegen die Anforderungen an die Anpassungsfähigkeit des Transport- und Logistiksektors sehr hoch, weil dieser Wirtschaftsbereich von „stetigen Veränderungen der Rahmenbedingungen“ betroffen ist: Anforderungen durch die Globalisierung, das Zusammenwachsen Europas, der demographische Wandel, Klima- und Umweltschutzbelange, Beschäftigungschancen und Arbeitsbedingungen sowie die Sicherheit der Transportkette.7 Die Unternehmen agieren somit in einer hochdynamischen Umwelt. Beispielsweise starteten die USA als Folge der Anschläge vom 11. September 2001 die Container Security Initiative (CSI), deren Ziel es war, hochgefährliche (high-risk) Container bereits im Exporthafen zu identifizieren. Häfen, die nicht in der Lage sind, die entsprechenden Maßnahmen zu gewährleisten, ist es nicht erlaubt, Güter in die USA exportieren.8 Deutschland stellt mit Hamburg und Bremen-Bremerhaven zwei der zwanzig größten Containerhäfen weltweit. Zusammen mit Rotterdam bilden diese Häfen eine bedeutende Schnittstelle für die Anbindung des globalen Güterverkehrs an Europa. Die folgende Tabelle zeigt den Umschlag dieser Häfen in TEU zusammen mit den größten drei Containerhäfen im weltweiten Vergleich.
6
Vgl. Bundesministerium für Verkehr, Bau und Stadtentwicklung (BMVBS) (2007a), S. 2f.
7
Vgl. Bundesministerium für Verkehr, Bau und Stadtentwicklung (BMVBS) (2007a), S. 3ff.
8
Vgl. World Trade Organization (2006), S. 39. Für den Bereich Containersicherheit sind in Folge dessen immer mehr wissenschaftliche Publikationen zu finden. Vgl. hierzu u.a. den Workshop „Container Security“ der Gesellschaft für Informatik GI, vom 24.- 27. September in Bremen und die dort angegebene Literatur, vgl. KOSCHKE, R. et al. (2007), S. 1- 22.
Einleitung
3
Rang
Hafen
1
Singapur
2
Shanghai
3
Hongkong
6
Rotterdam
9
Hamburg
20
Bremen-Bremerhaven
Umschlag 2007
Umschlag 2006
27.932.000
24.792.400
(+12,66%)
(+6,90%)
26.150.000
21.710.000
(+20,45%)
(+20,05%)
23.881.000
23.538.580
(+1,45%)
(+4,14%)
10.790.604
9.654.508
(+11,77%)
(+3,96%)
9.889.792
8.861.804
(+11,60%)
(+9,57%)
4.912.177
4.444.389
(+10,53%)
(+18,97%)
Umschlag 2005
23.192.000
18.084.000
22.602.000
9.286.757
8.087.545
3.735.574
Tabelle 1-1: Containerumschlag im weltweiten Vergleich9 Das starke Wachstum in jedem der aufgezeigten Häfen ist ein Beleg für die Bedeutung des Containerverkehrs weltweit. Der Container-Terminal (CT) des Hafens bildet dabei eine wichtige Schnittstelle für die globale Transportkette. Das Interesse wissenschaftlicher Forschung im Bereich der (Container-)Logistik ist, gemessen an der Anzahl wissenschaftlicher Publikationen, in den vergangenen Jahren erheblich gestiegen. Das erhöhte Interesse steht im Zusammenhang mit dem nicht nur seit Jahren anhaltenden sondern auch weiterhin für die Zukunft prognostizierten Boom.10 Ohne den Einsatz moderner Informationstechnologien und deren fortschreitende Entwicklung im Rahmen der Planung in Container-Terminals wären die Prozesse in ihrer heutigen Form nicht denkbar. Methoden des Operations Research unterstützen die Entscheidungsfindung in Optimierungsproblemen des Container-Terminals.11
9
Vgl. Hafen Hamburg (2007). Die angegebenen Zahlen sind um die prozentuale Veränderung zum Vorjahr ergänzt.
10
Vgl. MEIER, L. (2006), S. 209 und STEENKEN, D.; VOß, S.; STAHLBOCK, R. (2004), S. 13 und S. 34ff. Eine Prognose geben u.a. Bundesministerium für Verkehr, Bau und Stadtentwicklung (BMVBS) (2007b), S. 2. Die Entwicklung der Containerhäfen zeigt Tabelle 1-1.
11
Von STEENKEN, D.; VOß, S.; STAHLBOCK, R. (2004) wird ein umfassender Überblick gegeben. Der Artikel wird von STAHLBOCK, R.; VOß, S. (2007) aktualisiert.
4
Einleitung
Bisherige Ansätze zur Planung in CT-Prozessen zerlegen die Problemstellung aufgrund ihrer Komplexität in beherrschbare Teilprobleme. In der Literatur finden sich zahlreiche Modelle, die jeweils einen Teilbereich aufgreifen und mit unterschiedlichen Methoden optimieren. Obwohl die Bedeutung koordinierender Ansätze in der Literatur erkannt ist, liegt der Forschungsschwerpunkt noch immer auf der Entwicklung isolierter Modelle von Teilproblemen des CT. In diesen werden Beziehungen zu anderen Modellen vernachlässigt bzw. vereinfacht. Verfügbare Modelle unterscheiden sich in den betrachteten Zielfunktionen, den Restriktionen und den dem Modell zugrunde liegenden Annahmen. Zur Synthese der isoliert optimierten Teilprobleme ist die Unterstützung menschlicher Experten erforderlich. SAANEN gibt die Kosten für das Informationssystem des Terminals mit 4.000.000 € - 20.000.000 € an. Die Kosten eines Containerschiffs im Hafen werden in einer Untersuchung von KIA, SHAYAN und GHOTB mit 45.000 € - 65.000 € pro Tag angegeben.12 Aus diesem Grund stellt die durchschnittliche Aufenthaltszeit der Containerschiffe im Hafen eine wesentliche Größe im Zielsystem des Terminals dar. Oberziel der europäischen Verkehrspolitik ist die Sustainable Mobility, d.h. die „auf Dauer erträgliche Mobilität.“13 Damit rückt der Container auch in das politische Interesse. Der kombinierte Verkehr stellt auf weiten Strecken ein wirtschaftliches Transportangebot dar und trägt zur europäischen Kohäsion, d.h. zur Förderung des innereuropäischen Handels, bei. Das europäische Straßennetz kann entlastet werden, was wiederum zu einer umweltgünstigen Verkehrsabwicklung beiträgt.14
1.2 Zielsetzung Ziel dieser Arbeit ist die Konzeption eines Ansatzes zur Koordination interdependenter Planungssysteme. Am Beispiel von Container-Terminals im Hafen werden interdependente Planungssysteme untersucht, implementiert und in gemeinsamer Umgebung koordiniert.
12
Vgl. KIA, M.; SHAYAN, E.; GHOTB, F. (2000), S. 333.
13
Vgl. SEIDELMANN, C. (2004), S. C3-18. Vgl. hierzu auch IHDE, G. (1996), S. 1047f aus der Mitteilung der Kommission der Europäischen Gemeinschaft Nr. 92 (494), Brüssel 1992.
14
Vgl. SEIDELMANN, C. (2004), S. C3-18.
Einleitung
5
Hierfür wird es notwendig sein, zunächst vorhandene Probleme zu betrachten und Interdependenzen untereinander zu analysieren. Wenn feststeht, wo Abhängigkeiten bestehen, lassen sich diese Modelle verknüpfen und gemeinsam untersuchen. Es soll auf bestehende isolierte Modellformulierungen zurückgegriffen werden, die über zu identifizierende Schnittstellen miteinander zu verknüpfen sind. Zu untersuchende Problemstellungen sind
die Liegeplatzplanung (Berth Allocation Problem, BAP),
die Containerbrückenaufteilung (Crane Scheduling Problem, CSP),
die Containerlagerung im Yard (Storage Location Problem, SLP) und
die Transportplanung (Vehicle Dispatching Problem, VDP).15
Für die genannten Entscheidungsprobleme sind Modelle und Lösungsverfahren der Literatur vorzustellen und ihre Beziehungen untereinander zu untersuchen. Für jede Problemstellung sind unterschiedliche Lösungsverfahren denkbar, die sich in unterschiedliche Gruppen gliedern lassen. Folgende Gruppen sollen in dieser Arbeit zum Einsatz kommen:
Einfache Entscheidungsregeln, Prioritätsregeln
Greedy- bzw. myopische Verfahren
Metaheuristiken
Modellspezifische Verfahren der Literatur
Es soll versucht werden, die mit isolierten Modellen und unter Einsatz dieser Methoden gewonnenen Erkenntnisse zur Gestaltung eines übergreifenden Koordinationsmodells zu verwenden.
15
In der Literatur werden häufig die englischsprachigen Begriffe verwendet, deswegen sollen an dieser Stelle ebenfalls diese Bezeichnungen eingeführt werden.
6
Einleitung
1.3 Methodik und Aufbau der Arbeit Diese Arbeit gliedert sich wie folgt. Die Einleitung stellt die Motivation der Arbeit vor und spricht die Problemstellung und ihre Zielsetzung an. Es wird der Aufbau vorgestellt und eine inhaltliche und methodische Abgrenzung der Arbeit vorgenommen. Kapitel 2 und 3 stellen die Grundlagen der Arbeit heraus: Das zweite Kapitel beschäftigt sich mit den Grundlagen logistischer Systeme und deren Prozessen im Allgemeinen. Hierfür werden zunächst Kennzeichen der Logistik vorgestellt, bevor gezeigt werden soll, mit welchen Methoden die modellgestützte Planung in Logistiksystemen erfolgen kann. Aus der Optimierung von Teilsystemen einer Problemstellung entsteht das Koordinationsproblem, das im Anschluss daran, zusammen mit betriebswirtschaftlichen Koordinationsinstrumenten, vorgestellt werden soll. In der Literatur treten zur Abbildung und Modellierung vermehrt multiagentenbasierte Systeme auf. Ihre Darstellung bildet den Abschluss des zweiten Kapitels. Die erforderlichen einzusetzenden Begrifflichkeiten werden in den jeweiligen Teilabschnitten definiert. Kapitel 3 geht daraufhin auf die speziellen Anforderungen und die Planung in ContainerTerminals ein. Zunächst werden hier die Grundlagen des Containerverkehrs dargestellt. Es wird die Entwicklung beschrieben, um daran folgend allgemeine und idealtypische Prozesse moderner Container-Terminals zusammen mit dem eingesetzten Equipment für den Containerumschlag beschreiben zu können. Im Anschluss daran wird umfassend auf Optimierungsmodelle für CT-Teilprobleme eingegangen. Es werden Unterschiede zwischen bestehenden Modellen herausgearbeitet und nach geeigneten Modellen für die Umsetzung in einem integrierten Ansatz gesucht. Abschließend werden wechselseitige Abhängigkeiten zwischen den Entscheidungsbereichen untersucht. Kapitel 4 stellt zusammenfassend die Leistung und die Grenzen bestehender Modelle der CT-Logistik zusammen und zeigt Anforderungen für zukünftige Ansätze auf. In den Kapiteln 5 und 6 wird gezeigt, wie sich ein Modell zur Koordination interdependenter Planungssysteme der CT-Logistik umsetzen lässt. In Kapitel 5 soll das Container-Terminal Management Problem vorgestellt werden. Es ist die Architektur des multiagentenbasierten Modells aufzuzeigen und das Zielsystem für den
Einleitung
7
CT zu definieren. Daran folgt die kritische Untersuchung des entwickelten Modells, bevor abschließend auf die technische Realisierung eingegangen wird. Das entwickelte und implementierte Modell soll in Kapitel 6 getestet werden. Es werden unterschiedliche Experimente definiert. Diese erfolgen zunächst in isolierter Umgebung, um Lösungsmethoden und die Wirkung der Modellparameter zu untersuchen. Im Anschluss daran werden die isolierten Planungssysteme in die gemeinsame Multiagentensystem-Umgebung eingesetzt, um ihre Wirkung modellübergreifend im Rahmen des Container-Terminal Management Problems untersuchen zu können. Es wird die Entwicklung eines multiagentenbasierten Koordinationsmodells aufgezeigt, das mit bestehenden vorherrschenden Koordinationsmethoden zur Synthese isolierter Planungssysteme verwendet wird. Es schließen sich die Diskussion der Übertragbarkeit der beobachteten Ergebnisse sowie die Betrachtung der Modellkritik an dieses Kapitel an. Kapitel 7 fasst die Ergebnisse der Arbeit abschließend zusammen und gibt einen Ausblick für zukünftige Forschungsarbeiten.
Grundlagen logistischer Systeme und Prozesse
9
2 Grundlagen logistischer Systeme und Prozesse In diesem Kapitel sollen die logistischen Grundlagen für die weitere Arbeit gelegt werden. Es werden Begriffsdefinitionen aufgezeigt, wie sie im Rahmen der Logistik und im Kontext der zu behandelnden CT-Prozesse innerhalb dieser Arbeit zum Einsatz kommen. Es sollen Kennzeichen der Logistik im Allgemeinen aufgezeigt und eine Einordnung in die Betriebswirtschaftslehre vorgenommen werden. Im Anschluss daran wird gezeigt, wie sich logistische Systeme modellieren und optimieren lassen. Aus der Dekomposition von Systemen erwächst das Koordinationsproblem, das im Anschluss an die Darstellung von Optimierungsmethoden vorzustellen ist. Multiagentensysteme erweitern klassische Koordinationsinstrumente der Betriebswirtschaftslehre. Ihre Darstellung bildet den Abschluss dieses Kapitels.
2.1 Kennzeichen der Logistik In diesem Abschnitt werden die Kennzeichen der Logistik behandelt. Es soll hier zunächst die Entwicklung der Logistik vorgestellt werden, da sie für das Begriffsverständnis von Bedeutung ist. Daran folgend wird ein Überblick über die logistischen Grundfunktionen gegeben. Anschließend werden systemtheoretische Grundlagen aufgezeigt.
2.1.1 Einordnung in die Betriebswirtschaftslehre Der Ursprung des Logistikbegriffs ist im militärischen Bereich zu finden und wird dort als Sammelbegriff für die Gesamtheit der Aufgaben genutzt, die mit der Unterstützung der Streitkräfte zusammenhängen.16 Erst in den 50er Jahren wurde die Logistik in den USA auf betriebswirtschaftliche Problemstellungen übertragen. Im deutschsprachigen Raum tritt der Begriff seit Anfang der 70er Jahre auf.17 Eine flussorientierte Definition des Logistikbegriffs kommt vom amerikanischen Logistikverband, dem Council of Logistics Management (CLM):
16
Vgl. PFOHL, H. C. (2004a), S. 3ff. Vergleich hierzu auch IHDE, G. (2001), S. 20- 25, FLEISCHMANN, B. (2004), S. A1-3 und MIKUS, B. (2003), S. 5- 9.
17
Vgl. PFOHL, H. C. (2004a), S. 4.
10
Grundlagen logistischer Systeme und Prozesse „Logistics is that part of the supply chain process that plans, implements and controls the efficient, effective forward and reverse flow and storage of goods, services, and related information between the point of origin and the point of consumption in order to meet customer’s requirements.”18
Flussorientierte Definitionen stellen den Güterfluss in den Mittelpunkt der logistischen Betrachtung. Beispielsweise nennt PFOHL die „4r-Regel“ aus der klassischen Materialwirtschaft.19 Im Idealfall erstreckt sich dieser Fluss auf die gesamte Versorgungskette. Nach der genannten Definition erstreckt sich die Logistik keinesfalls nur auf die (physische) Durchführung von logistischen Grundfunktionen.20 Planung, Durchführung und Kontrolle stellen Managementfunktionen dar, so dass auch eine Managementkomponente explizit in dieser Logistikdefinition enthalten ist. Zudem wird die besondere Bedeutung von Informationen in der Definition berücksichtigt.21 Selbst interorganisatorische Systeme werden von der Logistik durchdrungen. Es soll hier auf das Verständnis der Logistik nach PFOHL zurückgegriffen werden. Demnach umfasst die Logistik sowohl das integrative Management als auch die integrative Erfüllung eines Bündels von güterflussbezogenen Aufgaben in- und außerhalb des Unternehmens.22 Mit integrativ beschreibt der Autor nicht die Behandlung des Güterflusses allein, sondern zusätzlich die Berücksichtigung weiterer Flüsse, die mit diesem zusammen-
18
PFOHL, H. C. (2004a), S. 4. Zitiert in Anlehnung an die dort genannte Internetquelle. Die angegebene Quelle ist zu diesem Zeitpunkt nicht aktiv. Eine ähnliche, ebenfalls flussorientierte Definition kommt von der europäischen Dachgesellschaft der nationalen logistischen Gesellschaften in Europa, vgl. hierzu European Logistics Association (2008).
19
Vgl. PFOHL, H. C. (2004a), S. 4. Zu dieser Regel existieren in der Literatur unterschiedliche Varianten. Von DAVIDSSON wird sie, in Anlehnung an die Definition von SHAPIRO, mit “7r” gekennzeichnet, vgl. DAVIDSSON, P. et al. (2005), S. 1. SAANEN gibt die folgende - wiederum leicht veränderte - Definition: “Material handling means providing the right amount of the right material, in the right condition, at the right place, at the right time, in the right position, in the right sequence, and for the right cost, by using the right methods.”, vgl. SAANEN, Y. A. (2004), S. 4.
20
Vgl. PFOHL, H. C. (2004a), S. 4f.
21
Neue Anforderungen der Logistik hängen eng mit der Entwicklung der Informationstechnologie zusammen. So stellt PFOHL heraus, dass erhöhte Anforderungen hinsichtlich Ort-, Zeit- und Mengengenauigkeit innerhalb des Güterflusses einen schnellen, sicheren und effizienten Informationsfluss bedingen, vgl. hierzu PFOHL, H. C. (2004a), S. 14ff. Hierfür lassen sich Beispiele finden: So lässt sich der Status der Auftragsabwicklung bei dem Onlinehändler AMAZON jederzeit nachvollziehen, vgl. hierzu amazon.de (2008).
22
PFOHL, H. C. (2004a), S. 5.
Grundlagen logistischer Systeme und Prozesse
11
hängen. Diese Flüsse, die auch von VAHRENKAMP in einem Netzwerkmodell dargestellt werden,23 sind in das Management einzubeziehen.24 Weiterhin existieren lebenszyklusorientierte und dienstleistungsorientierte Definitionen des Logistikbegriffs, auf die hier nicht näher eingegangen werden soll.25 Eine Klassifikation zur institutionalen Abgrenzung logistischer Systeme wird von PFOHL bereitgestellt. Unter einem makrologistischen System versteht er ein System gesamtwirtschaftlicher Art, bspw. das Verkehrssystem einer Region, einer Volkswirtschaft oder der Weltwirtschaft. Ein mikrologistisches System stellt im Gegensatz dazu das logistische System eines Unternehmens dar. Weiterhin lassen sich metalogistische Systeme differenzieren, die auf der Betrachtungsebene zwischen mikro- und makrologistischen Systemen liegen.26 Einen umfassenden Rahmen zur Klassifizierung von Systemen der Logistik stellt auch MIKUS zur Verfügung.27 Innerhalb der betrieblichen Funktionen lässt sich die Logistik u.a. in Beschaffungslogistik, Produktionslogistik, Distributionslogistik und Entsorgungslogistik einteilen.28 Weil die Logistik somit die betrieblichen Grundfunktionen durchdringt, kann sie als betriebswirtschaftliche Querschnittsfunktion bezeichnet werden.29 Die innerbetrieblichen Aspekte der Logistik, von der Beschaffung bis zur Verteilung von Gütern, sind in dieser Arbeit jedoch nicht weiter zu betrachten.30
23
Vgl. VAHRENKAMP, R. (2005), S. 9.
24
Vgl. PFOHL, H. C. (2004a), S. 5.
25
Vgl. PFOHL, H. C. (2004b), S. 12- 14.
26
Vgl. PFOHL, H. C. (2004b), S. 14f. Dieser Betrachtung zufolge stellen Container-Terminals metalogistische Systeme dar, vgl. die Darstellungen in Kapitel 3.
27
Vgl. MIKUS, B. (2003), S. 24- 33.
28
Vgl. VAHRENKAMP, R. (2005), S. 7. Von anderen Autoren kommen leicht abgewandelte und weiter differenzierte Klassifizierungen, u.a. PFOHL, H. C. (2004b), S. 17ff zur funktionalen Abgrenzung von Logistiksystemen.
29
Vgl. PFOHL, H. C. (2004b), S. 44f.
30
Container-Terminals erbringen logistische Leistungen für andere Unternehmen innerhalb der Transportkette. Damit kommt ihnen eine übergreifende Rolle zu, vgl. ausführlich die Darstellungen in Kapitel 3.
12
Grundlagen logistischer Systeme und Prozesse
2.1.2 Funktionen und Ziele Logistische Grundfunktionen werden als Dienstleistungen verstanden, weil sie Güter bewegen und verwalten, nicht aber umformen, wie dies im Sinne der Produktionswirtschaft der Fall ist. Die Überbrückung von Differenzen im Güter- und Informationsstrom spielt in der Logistik eine zentrale Rolle.31 Die nachfolgende Tabelle gibt eine Zuordnung von Logistikprozessen und die durch sie bewirkten Arten der Gütertransformation. Logistikprozesse GüterTransformation
Transportieren, Lagern
Umschlagen (Handhaben)
Zeitänderung
Umschlagen (Zusammen-
Umschlagen
Verpacken,
fassen,
(Sortieren)
Signieren
Auflösen)
Aufträge übermitteln, bearbeiten
x
Raumänderung Mengenänderung
x x
Sortenänderung
x
Änderung in den Transport-, Um-
x
schlags- und Lagereigenschaften Änderung in der logistischen Deter-
x
miniertheit des Gutes
Güterfluss
Informationsfluss
Tabelle 2-1: Logistikprozesse und durch sie bewirkte Gütertransformation32 In der Tabelle werden logistische Prozesse vorgestellt. Transportprozesse von einer Quelle zu einer Senke dienen der Überwindung von Raumdifferenzen. Logistiksysteme stiften Nutzen, indem sie ein Gut an einem anderen (gewünschten) Ort zur Verfügung stellen.33
31
Vgl. VAHRENKAMP, R. (2005), S. 8 sowie FLEISCHMANN, B. (2004), S. A1- 3 und BLOECH, J. et al. (2008), S. 3f.
32
Vgl. PFOHL, H. C. (2004b), S. 9. Geänderte Tabelle nach JÜNEMANN, übernommen aus der angegebenen Quelle.
33
Vgl. VAHRENKAMP, R. (2005), S. 8.
Grundlagen logistischer Systeme und Prozesse
13
Umschlagprozesse können auf zwei unterschiedliche Weisen betrachtet werden. Zum einen gehören das Zusammenfassen bzw. das Auflösen von Gütern zum Umschlag, zum anderen kann das Sortieren als Umschlag bezeichnet werden. Als Beispiel soll ein Fall aus der Containerlogistik im Hafen vorgestellt werden. In einem Container-Terminal werden Container umgeschlagen. Container liegen zusammengefasst auf einem Schiff. Zu importierende Container werden von dem Schiff gelöscht und ins Hinterland verteilt. In entgegengesetzter Richtung werden zu exportierende Container aus dem Hinterland gesammelt und auf dem Schiff zusammengefasst.34 Für diese Arbeit spielt die (in der Tabelle) zuerst genannte Umschlagfunktion eine wesentliche Rolle. Zu den Lagerprozessen gehören die Einlagerung, die Lagerung selbst und die Auslagerung. Hierfür existieren spezielle Techniken, die aufeinander abzustimmen sind. Die Überwindung der Zeit stellt die durch die Lagerung bewirkte Gütertransformation dar.35 Begleitet werden die genannten Prozesse von Informationsflüssen. Weil diese Prozesse zu den Grundfunktionen der Logistik gehören, ist in der Literatur der Begriff TUIL-Logistik zu finden.36 Mit der in der folgenden Abbildung gegebenen Darstellung können die logistischen Grundfunktionen verdeutlicht werden.
34
Vgl. Abbildung 2-1.
35
Vgl. FLEISCHMANN, B. (2004), S. A1-7. Lagerprozesse spielen für Container-Terminals eine wesentliche Rolle. SAANEN erklärt, dass durch diese Funktion der interkontinentale von dem kontinentalen Güterfluss zeitlich entkoppelt werden kann. Ohne diese Koordinationsfunktion wäre die Verknüpfung zwischen diesen Punkten zu komplex und deshalb unmöglich, vgl. SAANEN, Y. A. (2004), S. 1f.
36
TUIL steht für Transport, Umschlag, Information und Lagerung, vgl. hierzu auch VAHRENKAMP, R. (2005), S. 3.
14
Grundlagen logistischer Systeme und Prozesse Sammeln
Lagern
Verteilen
Transportieren
Information
Abbildung 2-1: Logistische Grundfunktionen TUIL37 Das Logistikmanagement hat nach PFOHL zwei grundlegende Funktionen. Zum einen dient es dem Management der einzelnen logistischen Teilfunktionen, z.B. die physische Lagerung. Zum anderen erkennt PFOHL einen weitaus wichtigeren Aspekt, den er als die Umsetzung der Logistikkonzeption durch koordinierende und integrierende Managementaktivitäten darstellt.38 Dieser Ansicht folgend verlangt insbesondere das System- und Wertdenken die Koordination und ganzheitliche Betrachtung von Logistiksystemen und Prozessen.39 Um die außerbetrieblichen Güterflüsse gewährleisten zu können, wird auf unterschiedliche Verkehrsträger zurückgegriffen. Zu den Verkehrsträgern zählen Schiene, Straße, Wasser, Luft und auch Rohrleitungen. Für die Logistik ist das Flusskonzept von besonderer Bedeutung. Die physischen Güterströme sollen stetig durch das Logistiksystem fließen. Schnittstellen zwischen Subsystemen sind so zu gestalten, dass der Fließprozess einen minimalen Widerstand erfährt.40 Gerade die Koordination an den Umschlagpunkten zwischen Quelle und Senke muss gewährleistet werden. In diesem Zusammenhang wird von der Überwindung einer Schnittstelle gesprochen.41
37
VAHRENKAMP, R. (2005), S. 8.
38
Vgl. PFOHL, H. C. (2004a), S. 16ff.
39
PFOHL, H. C. (2004a), S. 18.
40
Vgl. VAHRENKAMP, R. (2005), S. 10- 13.
41
Vgl. VAHRENKAMP, R. (2005), S. 13. Aus diesem Ansatz gelangt VAHRENKAMP zu einer Sichtweise der Ganzheitlichkeit, S. 14.
Grundlagen logistischer Systeme und Prozesse
15
Speditionen, Lagereien und auch Container-Terminals erbringen logistische (Dienst-) Leistungen für andere Unternehmen, die alle Transport-, Lager- und Umschlagprozesse umfassen. Hub and Spoke-Netzwerke stellen wichtige Systeme der Transportlogistik dar. Ein Hub ist ein zentraler Umschlagpunkt, an dem die Ferntransporte synchronisiert ankommen und Sendungen sortiert und umgeladen werden können. Mit Hilfe von Feeder-Hubs kann diese Struktur weiter verdichtet werden.42 Das Ziel dieser Netzstrukturen ist die Realisierung einer ökonomischen Verbindung zwischen Quellen und Senken in einem Logistiksystem. Das Netz muss in der Lage sein, die Depots so miteinander zu verbinden, dass Transporte von und zu jedem Depot möglich sind.43 Transportströme werden somit gebündelt, um die Transportkosten zu senken.44 Der direkte Transport zwischen einem Produzenten und Konsumenten ist in vielen Fällen nicht wirtschaftlich. Diese Netzstrukturen sind in der folgenden Abbildung dargestellt.
a) Hub- and Spoke- Netz
b) Netz mit Feeder- Hubs
c) Multi- Hub- Netz
d) Mischstruktur Hub
Feeder- Hub
Depot
Kunde
Abbildung 2-2: Netzstrukturen45 SCHÖNSLEBEN zeigt den Beitrag der Logistik auf die Unternehmensziele auf. Er klassifiziert die vier Bereiche QUALITÄT, KOSTEN, LIEFERUNG und FLEXIBILITÄT und leitet daraus die wesentliche Bedeutung der Logistik für die Leistungsfähigkeit des Unternehmens ab. Zwischen den genannten Zielbereichen bestehen Konflikte. Aus diesem Grund ist von den
42
Vgl. FLEISCHMANN, B. (2004), S. A1-17.
43
Es lässt sich nur problemspezifisch bestimmen, welches die ökonomisch sinnvollste Netzstruktur ist.
44
Vgl. FLEISCHMANN, B. (2004), S. A1-13.
45
FLEISCHMANN, B. (2004), S. A1-17.
16
Grundlagen logistischer Systeme und Prozesse
Unternehmen ein Zielprofil zu erstellen, das auf die Ansprüche ihrer Kunden ausgerichtet sein muss. Beispielsweise führt ein hohes Maß an Produkt- und Prozessqualität potenziell zu höheren Kosten.46 Das Kernelement der Logistik sieht PFOHL nicht in dem Auftreten des Logistikbegriffs, sondern in der veränderten Wahrnehmung der Logistik für das Unternehmen, deren Grundlage die systemtheoretische Betrachtung darstellt.47 Der Autor hebt, mit Blick auf die Literatur, die abgestimmte und koordinierte Gestaltung von Güterflüssen hervor. Weil die systemtheoretische Betrachtungsweise für die Logistik von besonderer Bedeutung ist, ist im Folgenden auf diese Grundlagen einzugehen.
2.1.3 Systemtheoretische Grundlagen Der Systemansatz stellt eine Wissenschaftskonzeption dar, die eine zweckdienliche Basis für die Gestaltung und Schaffung einer effizienten Informationsverarbeitung bietet. In den Wirtschaftswissenschaften findet der Systemansatz Verwendung, weil sein Einsatz die Anwendung systemtheoretischer Modelle und Methoden erlaubt. Die Aufgabe einer Wissenschaftskonzeption sehen BIETHAHN, MUCKSCH und RUF in der Festlegung des Untersuchungsfeldes und der Analyseschwerpunkte einer Wissenschaft, um dem in der Wissenschaft Tätigen einen Leitfaden für seine Arbeit zur Verfügung zu stellen.48 Ein System lässt sich über seine Elemente und Subsysteme abbilden, wobei Beziehungen zwischen Elementen und Subsystemen auftreten können.49 Elemente stellen dabei nicht weiter zergliederbare Bestandteile des Systems dar, während es für Subsysteme möglich ist, diese weiter zu zerlegen. Dabei kommt es auf die Zweckmäßigkeit hinsichtlich des gewünschten Abstraktionsgrades an, inwieweit die Zerlegung der Subsysteme erforderlich ist. Beziehungen und Schnittstellen können das gesamte System beeinflussen und existieren zwischen Elementen und Subsystemen. Insgesamt ist die Struktur eines Systems durch
46
Vgl. SCHÖNSLEBEN, P. (2007), S. 13ff.
47
Vgl. PFOHL, H. C. (2004b), S. 25ff.
48
Vgl. BIETHAHN, J.; MUCKSCH, H.; RUF, W. (2004), S. 138ff.
49
In diesem Zusammenhang wird auch von der Architektur eines Systems gesprochen.
Grundlagen logistischer Systeme und Prozesse
17
die Menge der Elemente, die Menge der Subsysteme sowie die Menge und die Art der Beziehungen bestimmt. Eine Systemklassifizierung wird u.a. von BIETHAHN, MUCKSCH und RUF gegeben. Die Autoren klassifizieren Systeme nach unterschiedlichen Aspekten: Für den weiteren Verlauf der Arbeit sind insbesondere die Unterscheidung nach Systementstehungsart, Systembeziehungen und Systemverhalten von Bedeutung. Für die Entstehungsart wird zwischen künstlichen und natürlichen Systemen differenziert. Die Beziehungen zur Umwelt werden als offen bzw. geschlossen klassifiziert. Zudem können die internen Systemelemente einfache oder komplexe Beziehungen aufweisen. Das Systemverhalten kann statisch oder dynamisch sein.50 Unternehmen lassen sich so als künstliche, offene und dynamische Systeme begreifen. Die Leistungsfähigkeit des Systemdenkens liegt in der Aussicht, neue Aussagen terminologischer (definitorischer), deskriptiver (beschreibender), theoretischer (erklärender) und praxeologischer (gestaltender) Art zu gewinnen.51 Durch die Analyse der Beziehungsstruktur komplexer Systeme werden Logistikentscheidungen unter Berücksichtigung bestehender Ressourcen- und Prozessinterdependenzen getroffen. Dies hat zur Folge, dass suboptimale Insellösungen vermieden und stattdessen eine Gesamtlösung angestrebt werden kann. Die Denkweise hilft, unter Einsatz der Abstraktion, komplexe Beziehungen in Systemen zu überblicken.52 Nach Darstellung der Leistungsfähigkeit des Systemdenkens und dessen Bezug auf die Logistik sollen im folgenden Abschnitt Methoden zur Modellierung und auch Optimierung logistischer Systeme und Prozesse aufgezeigt werden.
2.2 Modellierung und Optimierung In diesem Abschnitt werden Methoden zur Modellierung und Optimierung logistischer Systeme vorgestellt. Von besonderer Bedeutung sind Methoden des Operations Research,
50
Vgl. BIETHAHN, J.; MUCKSCH, H.; RUF, W. (2004), S. 142f. Es werden weitere Ansatzpunkte zur Klassifizierung von Systemen genannt.
51
Vgl. PFOHL, H. C. (2004b), S. 27f.
52
Vgl. PFOHL, H. C. (2004b), S. 29, BIETHAHN, J.; MUCKSCH, H.; RUF, W. (2004), S. 153- 156 und auch VAHRENKAMP, R. (2005), S. 10.
18
Grundlagen logistischer Systeme und Prozesse
auf die detailliert eingegangen werden soll. In diesem Zusammenhang sind insbesondere die Begriffe der Planung, des Modells und der Koordination für diese Arbeit einzuführen.
2.2.1 Modellgestützte Planung Operations Research (OR) kann als modellgestützte Planung im Unternehmen definiert werden.53 Im deutschen Sprachgebrauch lassen sich unterschiedliche Synonyme finden, z.B. Unternehmensforschung oder auch Optimalplanung. Die Begriffe sollen für diese Arbeit synonym verwendet werden. Zu den Merkmalen des OR zählen das Optimalitätsstreben, das Modelldenken, die Quantifizierung von Entscheidungsproblemen und auch die Vorbereitung optimaler Entscheidungen.54 Unter einem Modell versteht man die vereinfachte Abbildung der Realität. Mit Hilfe von Modellen wird versucht, Ausschnitte der Realität nachzubilden und so deren Vorgänge zu erklären, zu prognostizieren oder auch Entscheidungen vorzubereiten.55 In der Logistik werden Modelle eingesetzt, um komplexe Systeme der Realität abzubilden, zu erklären und zu gestalten. Planung ist die gedankliche Vorwegnahme zukünftigen Handelns. Das bedeutet, dass mit der Planung Entscheidungen getroffen werden, die in die Zukunft gerichtet sind.56 Die Planung ist Teil des Führungsprozesses im Unternehmen.57 Von besonderer Bedeutung ist das ökonomische Prinzip, das sich in der Planung wiederfindet. Dieses Prinzip fordert, dass entweder ein gegebenes Ziel mit minimalen Mitteln zu erreichen ist, oder mit gegebenen Mitteln das maximale Ergebnis, bezogen auf eine festzulegende Zielgröße, anzustreben ist.58
53
In dieser Arbeit soll der Begriff wie angegeben verwendet werden. Zu den Schwierigkeiten der Begriffsdefinition, vgl. u.a. MÜLLER-MERBACH, H. (1992), S. 1f.
54
Vgl. BIETHAHN, J.; MUCKSCH, H.; RUF, W. (2004), S. 161- 166.
55
Vgl. HAX, H. (1974), S. 11.
56
Vgl. WÖHE, G.; DÖRING, U. (2002), S. 103ff.
57
Vgl. BEA, F. X.; FRIEDL, B.; SCHWEITZER, M. (2005), S. 16ff.
58
MÜLLER-MERBACH, H. (1992), S. 4 und ähnlich DOMSCHKE, W.; SCHOLL, A. (2002), S. 3f.
Grundlagen logistischer Systeme und Prozesse
19
Wegen der hohen Bedeutung des Planungsbegriffs in dieser Arbeit sind zudem Arten der Planung nach ihren Bezugsobjekten vorzustellen. Bezugsobjekte bilden eine Möglichkeit, Planungen zu klassifizieren.59 Von BEA, FRIEDL und SCHWEITZER werden der Bezugszeitraum, der Funktionsbereich, die Leitungshierarchie, die Planungshierarchie, die Beeinflussbarkeit der Umwelt und die Planungsgegenstände genannt.60 Der Bezugszeitraum gibt die Zeitdauer an, auf die sich ein Plan bezieht. Es lassen sich kurz-, mittel- und langfristige Pläne unterscheiden.61 Funktionsbereichsplanungen unterscheiden die Planung über Funktionsbereiche des Unternehmens, beispielsweise die Absatzplanung, Finanzplanung, Lagerhaltungsplanung, etc.62 In der Leitungshierarchie werden - unter Berücksichtigung der Aufbauorganisation - die Unternehmensplanung, die Bereichsplanung, die Stellenplanung usw. unterschieden. Von besonderer Bedeutung ist die Planungshierarchie. Sie gibt an, in welchem Verhältnis einzelne Pläne des Unternehmens zueinander stehen. Ein Plan ist einem anderen Plan übergeordnet, wenn er den Handlungsrahmen absteckt, in dem der untergeordnete Plan formuliert werden muss. Die Pläne stehen in einem Ableitungsverhältnis: Ein taktischer Plan ist aus dem strategischen Plan abzuleiten, der operative Plan wiederum aus dem taktischen. Gleichzeitig tritt dabei eine zunehmende Präzisierung der Pläne auf, so dass von einer Plankonkretisierung gesprochen werden kann. Eine Gleichsetzung mit den drei Planungsarten nach dem Bezugszeitraum ist nicht ohne Weiteres möglich, weil die strategische, taktische und operative Planung durch mehrere Merkmale gekennzeichnet ist.63
59
In Kapitel 2.3.3 werden Arten der Planung zusätzlich nach Abstimmungs- und auch Anpassungsformen klassifiziert, vgl. BEA, F. X.; FRIEDL, B.; SCHWEITZER, M. (2005), S. 34- 50.
60
Vgl. BEA, F. X.; FRIEDL, B.; SCHWEITZER, M. (2005), S. 34- 38.
61
Es ist dabei relativ, ab welchem Zeitraum ein Plan einem dieser Bezugszeiträume zuzuordnen ist. BEA, FRIEDL und SCHWEITZER geben für kurzfristige Pläne einen Bezugszeitraum von bis zu einem Jahr an. Mittelfristige Pläne sehen sie in einem Zeitraum von einem bis fünf Jahre. Für langfristige Pläne wird ein Zeitraum angegeben, der weiter als fünf Jahre entfernt liegt. Sie nennen zusätzlich unterschiedliche Faktoren, die Einfluss auf die Fristigkeit der Pläne nehmen, vgl. BEA, F. X.; FRIEDL, B.; SCHWEITZER, M. (2005), S. 34f.
62
Vgl. BEA, F. X.; FRIEDL, B.; SCHWEITZER, M. (2005), S. 35.
63
Vgl. BEA, F. X.; FRIEDL, B.; SCHWEITZER, M. (2005), S. 35f.
20
Grundlagen logistischer Systeme und Prozesse
Zur Beeinflussbarkeit der Umwelt führen BEA, FRIEDL und SCHWEITZER die Planung von außen nach innen sowie die Planung von innen nach außen an.64 Nach Planungsgegenständen lassen sich zudem die Potenzial-, Programm-, und Prozessplanung unterscheiden.65 Der Planungsprozess wird von den Autoren in Phasen zerlegt. Zu den Phasen zählen die Problemfeststellung, die Zielbildung, die Alternativensuche, die Prognose sowie die Bewertung und Entscheidung.66 Von MÜLLER-MERBACH wird eine schematische Vorgehensweise für die Planung mit mathematischen Methoden aufgezeigt, deren Voraussetzung ist, dass sich das betrachtete Realproblem in ein mathematisches Formalproblem übertragen lässt.67 Diese Vorgehensweise soll an dieser Stelle aufgezeigt werden, weil sich so die im folgenden Kapitel vorzustellenden Entscheidungsmodelle aus dem CT-Bereich kritisch beurteilen lassen.68 Weil die vollständige Abbildung der Realität in einem mathematischen Modell nicht möglich ist, ist lediglich ein relevanter Ausschnitt zu betrachten. Dieser Ausschnitt ergibt sich aus der zu betrachtenden Problemstellung. Aus dem zu betrachtenden Realitätsausschnitt ist ein mathematisches Modell zu formulieren, das zusammen mit der zu lösenden Aufgabe (die Fragestellung der Realität) das Formalproblem darstellt.69 ADAM
ET AL.
führen an,
dass die Zielsetzung für die Gestaltung eines Modells entscheidend ist und stellen fest: „Die Güte eines Modells zur vereinfachten Abbildung der Wirklichkeit kann […] nicht anhand des Modells selbst, sondern lediglich an den Zwecken, für das es entworfen wurde, beurteilt werden.“70 Demnach können lediglich dem Zweck angemessene und nicht angemessene Modelle unterschieden werden.
64
Vgl. BEA, F. X.; FRIEDL, B.; SCHWEITZER, M. (2005), S. 37f.
65
Vgl. BEA, F. X.; FRIEDL, B.; SCHWEITZER, M. (2005), S. 38.
66
Vgl. BEA, F. X.; FRIEDL, B.; SCHWEITZER, M. (2005), S. 50.
67
Vgl. MÜLLER-MERBACH, H. (1992), S. 14ff.
68
Die kritische Beurteilung von Entscheidungsmodellen der Containerlogistik soll in Kapitel 4.2 anhand dieser Kriterien erfolgen.
69
Vgl. MÜLLER-MERBACH, H. (1992), S. 14ff.
70
ADAM, D. et al. (2004), S. 2. Vgl. hierzu auch BIETHAHN, J.; MUCKSCH, H.; RUF, W. (2004), S. 163.
Grundlagen logistischer Systeme und Prozesse
21
Das Formalproblem lässt sich häufig mit unterschiedlichen Methoden lösen. MÜLLERMERBACH spricht in diesem Zusammenhang von der Problemhomogenität der Methoden. Während Methoden die Mittel der Planung darstellen, handelt es sich bei zu lösenden Problemen um die Zwecke der Planung.71 MÜLLER-MERBACH weist darauf hin, dass in der Theorie der schwierigste Schritt dieser Vorgehensweise die Abbildung der relevanten Merkmale aus dem Realitätsausschnitt umfasst.72 Der sich anschließende Teil basiert lediglich auf technischen Problemen, weil sich Übertragungs- und Rechenfehler anschließen können. Er führt an, dass Planungsaufwand und Planungsergebnisse in einem optimalen Verhältnis stehen müssen.73 So lässt sich beispielsweise die Qualität der Daten durch Mehreinsatz von Ressourcen (beliebig) verbessern, es ist jedoch auf den mit den Daten zu erzielenden Nutzen zu achten. An dieser Stelle sind weitere wesentliche Begriffe des Operations Research zu klären. Bereits zu diesem Zeitpunkt wurden die Begriffe Methode, Verfahren, Algorithmus verwendet, ohne dass ihre Bedeutung bisher definiert wurde.74 Hier sollen die Begriffe Methode und Verfahren synonym verwendet werden. HANSEN und NEUMANN definieren eine Methode „als eine systematische Vorgehensweise zur Lösung eines Problems“.75 Unter einem Algorithmus verstehen die Autoren eine spezielle Methode, bei der die Verfahrensvorschrift exakt und vollständig formuliert ist.76 Auch Heuristiken stellen spezielle Methoden dar, die im Folgenden ausführlich zu klassifizieren sind. In den folgenden Abschnitten sollen die Methoden des Operations Research vorgestellt werden. Dabei soll, nach einer allgemeinen Klassifizierung, der Schwerpunkt auf diejeni-
71
Vgl. MÜLLER-MERBACH, H. (1992), S. 8f. Da sich die Methoden häufig auch für unterschiedliche Problemstellungen einsetzen lassen, wird in diesen Zusammenhang zudem von Methodenhomogenität der Probleme gesprochen.
72
Vgl. MÜLLER-MERBACH, H. (1992), S. 15. Auch andere Autoren heben die Leistung der Modellbildung heraus, die sich nicht automatisieren lässt. ADAM stellt sogar fest, dass unterschiedliche Planer in schlecht strukturierten Entscheidungssituationen zu unterschiedlichen Ergebnissen kommen können, obwohl sie dieselbe Ausgangssituation besitzen, vgl. hierzu ADAM, D. (1996), S. 15.
73
Vgl. MÜLLER-MERBACH, H. (1992), S. 14f.
74
Von MÜLLER-MERBACH werden die Begriffe synonym verwendet. Vgl. MÜLLER-MERBACH, H. (1992), S. 24.
75
HANSEN, H. R.; NEUMANN, G. (2005), S. 782.
76
Vgl. HANSEN, H. R.; NEUMANN, G. (2005), S. 782.
22
Grundlagen logistischer Systeme und Prozesse
gen Methoden gelegt werden, die im Rahmen dieser Arbeit für die Optimierung von CTProzessen implementiert wurden und zum Einsatz kommen.
2.2.2 Klassifizierung relevanter Methoden des Operations Research In diesem Abschnitt sollen die Verfahren der Unternehmensforschung klassifiziert werden. In der Literatur sind sehr unterschiedliche Ansätze zur Klassifizierung verfügbar. Es sollen hier die Zielsetzung des Modells, die Informationsgrundlage und deren Verfügbarkeit, die zeitliche Struktur sowie die zur Lösung erforderlichen mathematischen Methoden untersucht werden. Es lassen sich deterministische von nicht deterministischen Modellen abgrenzen. Nicht deterministische Modelle weisen nicht für alle Modellparameter vollständige und/oder sichere Informationen auf. Im Gegensatz dazu wird von deterministischen Modellen gesprochen, wenn alle notwendigen Daten und Parameter gegeben sind und keine zufallsabhängigen Elemente vorliegen.77 Modelle können weiterhin bezüglich ihrer Funktionsstruktur unterschieden werden. In linearen Modellen liegen ausschließlich lineare Strukturen sowohl in der Zielfunktion als auch in den Nebenbedingungen vor. In diesen Modellen lassen sich Verfahren der linearen Programmierung einsetzen.78 Weiterhin ist der Typ der Entscheidungsvariablen zu betrachten. In diskreten Modellen, in denen einige oder alle Variablen des Modells nur ganzzahlige Werte annehmen dürfen, eignen sich beispielsweise Branch and Bound-Verfahren. Für kontinuierliche Variablen lässt sich beispielsweise die Simplexmethode einsetzen, die sehr weit verbreitet ist.79 Im Gegensatz zu deterministisch linearen Modellen gibt es für nichtlineare Modelle kaum allgemein einsetzbare Methoden, weil sich die Funktionsstrukturen sehr stark unterschei-
77
Vgl. BIETHAHN, J.; MUCKSCH, H.; RUF, W. (2004), S. 167ff.
78
Vgl. BIETHAHN, J.; MUCKSCH, H.; RUF, W. (2004), S. 167.
79
Die bewusste Veränderung eines Variablentyps, z.B. die Verwendung eines kontinuierlichen statt diskreten Typs, stellt eine Relaxationstechnik dar, vgl. DOMSCHKE, W. (1997), S. 8- 12. Diese Technik kann zur Entwicklung von Untergrenzen in Branch and Bound-Verfahren eingesetzt werden. Vgl. auch Kapitel 2.2.3.4.
Grundlagen logistischer Systeme und Prozesse
23
den können. Zu nennen sind hier bspw. die Lagrange’sche Multiplikatormethode sowie die Differentialrechnung.80 Entscheidungsmodelle mit Ungewissheit treten auf, wenn nicht alle Daten und Parameter des Modells gegeben sind, bspw., wenn das Verhalten eines konkurrierenden Unternehmens nicht bekannt, für die Entscheidung der eigenen Unternehmung aber relevant ist. Es ist deshalb zwischen Modellen mit Risiko oder Unsicherheit zu unterscheiden. Risiko tritt auf, wenn Entscheidungsmodelle Stochastizitäten in den Zielfunktionen und/oder den Nebenbedingungen aufweisen. Hier liegt im besten Fall eine gute Approximation für die Verteilung der stochastischen Variablen vor. Unsicherheit ist bei nicht beeinflussbaren Umwelteinflüssen auf die eigenen Alternativen gegeben.81 Mit Hilfe von Fuzzy-Methoden kann vages Wissen mathematisch abgebildet werden. Im Gegensatz zu klassischen Zuordnungsfunktionen von Mengen, bei denen ein Element einer Menge angehören oder nicht angehören kann, bieten Fuzzy Sets die Möglichkeit, Elemente mit einem gewissen Grad einer Menge angehören zu lassen.82 Diese Methoden finden breiten Einsatz in der wissenschaftlichen Literatur, beispielsweise im Rahmen der Weiterführung einer Balanced Scorecard83, oder auch in der Projektarbeit von Unternehmensberatungen84. Heuristiken lassen sich nach ihrer Art, Lösungen zu entwickeln, klassifizieren. So unterscheiden DORIGO und STÜTZLE konstruktive und auf lokaler Suche basierende Verfahren.85 Zu den Heuristiken können zudem optimierende, exakte Verfahren hinzukommen, die vor Erreichen des Optimums abgebrochen werden.86 Während konstruktive Verfahren Lösungen von Grund auf iterativ entwickeln, starten lokal suchende Verfahren mit einer Ausgangslösung und versuchen diese durch gezielte (lokale) Veränderungen sukzessiv zu
80
Vgl. BIETHAHN, J.; MUCKSCH, H.; RUF, W. (2004), S. 167f.
81
Vgl. BIETHAHN, J.; MUCKSCH, H.; RUF, W. (2004), S. 169.
82
Vgl. BIETHAHN, J.; MUCKSCH, H.; RUF, W. (2004), S. 170ff.
83
Vgl. POCHERT, B. (2005) und auch SCHUBERT, A. (2002).
84
Vgl. NISSEN, V. (2002).
85
Vgl. DORIGO, M.; STÜTZLE, T. (2004), S. 29ff.
86
Im Rahmen dieser Arbeit kommen exakte, vorzeitig abbrechende Verfahren nicht zum Einsatz und sollen deshalb nicht weiter diskutiert werden.
24
Grundlagen logistischer Systeme und Prozesse
verbessern.87 Dabei spielt vor allem die Überwindungsfähigkeit lokaler Optima eine entscheidende Rolle. Für lokale Verfahren ist es notwendig, eine Nachbarschaft zu definieren, zu der, ausgehend von einer bestehenden Lösung, gewechselt werden kann. Es existieren schwarm- und nicht-schwarmbasierte Ansätze. Zu den auf Schwärmen basierenden Verfahren zählen u.a. evolutionäre Algorithmen, Ameisenalgorithmen und Partikelschwarmoptimierung, während mit Tabu Search und Simulated Annealing Beispiele für nicht auf Schwärmen basierende Verfahren gegeben sind. Heuristische Methoden beziehen Regeln und Erfahrungswerte in den Lösungsprozess ein. Sie zielen in der Regel nicht auf die optimale Lösung des Problems ab, sondern suchen nach einer guten und zulässigen Lösung.88 Heuristiken können beispielsweise im Rahmen von Eröffnungsverfahren zur Bestimmung einer ersten gültigen Lösung eingesetzt werden, die dann mit weiteren Verfahren zu verbessern ist.89 Die Grundprinzipien heuristischer Verfahren werden u.a. ausführlich von DOMSCHKE und DREXL diskutiert. Ein Rahmen zur Analyse der Leistungsfähigkeit von Heuristiken wird von SONDERGELD gegeben.90 Auf weitere, sehr spezielle Bereiche des OR, z.B. Warteschlangenmodelle, Markovketten u.a. ist hier nicht näher einzugehen.91 Nach der allgemeinen Klassifizierung von Methoden
87
Vgl. hierzu die ausführliche Darstellung konstruktiver Verfahren und der lokalen Suche im Anhang.
88
Vgl. BIETHAHN, J.; MUCKSCH, H.; RUF, W. (2004), S. 168f und auch MÜLLER-MERBACH, H. (1992), S. 290ff. Heuristische Verfahren und auch Näherungsverfahren werden angewendet, wenn der für die exakte Lösung eines Problems erforderliche Rechenaufwand nicht vertretbar ist. Dies kann insbesondere für Problemstellungen der kombinatorischen Optimierung der Fall sein. Es kann zweckmäßig sein, die Zielfunktion und auch die Restriktionsfunktionen zunächst auf Konvexität, bzw. Konkavität zu prüfen und Wissen über die Problemstruktur für die Lösungsmethode zu verwenden. Für wenige Variable im Modell existieren Bedingungen, die bzgl. dieser Eigenschaft zu prüfen sind, vgl. u.a. SCHUMANN, M.; DIEKMANN, T.; DOBRINDT, M. (2007), S. 114ff.
89
Ein Beispiel ist das klassische Transportproblem, bei dem mit Hilfe einer einfachen Heuristik eine gültige Ausgangslösung bestimmt wird, die daran folgend mit speziellen Methoden in endlich vielen Schritten optimiert werden kann. Für das klassische Transportproblem kann die Simplexmethode eingesetzt werden. Aufgrund der speziellen Problemstruktur existieren Verfahren, die das Problem schneller lösen. Hierzu zählen die Modified Distribution (MODI-)Methode und Stepping Stone, vgl. hierzu BLOECH, J. (2003), S. 6177 und auch CHARNES, A.; COOPER, W. (1954), S. 49- 69. Das Transportproblem ist Teil der in Kapitel 3.2.4.2 vorgestellten Problemstellung.
90
Vgl. DOMSCHKE, W.; DREXL, A. (2007), S. 129ff. und auch SONDERGELD, L. (2001). Vgl. auch die dort angegebene weiterführende Literatur.
91
Vgl. hierzu die ausführlichen Darstellungen in der Literatur, u.a. DOMSCHKE, W.; DREXL, A. (2007).
Grundlagen logistischer Systeme und Prozesse
25
des Operations Research sollen im folgenden Abschnitt die in dieser Arbeit eingesetzten Verfahren vorgestellt werden.
2.2.3 Optimierung Ein (kombinatorisches) Optimierungsproblem 3 lässt sich als Tripel ( S , f , : ) darstellen. S stellt dabei die Menge möglicher Lösungen dar, f beschreibt die Zielfunktion, die je-
dem Element s S einen Fitnesswert f (s ) zuordnet. : kennzeichnet die Menge der Re~ striktionen, die Menge S S beschreibt die Menge gültiger Lösungen. Für das Optimie~ rungsproblem wird das Element s * S gesucht, das die Problemstellung minimiert, bzw. ~ maximiert: f ( s * ) d f ( s ) , bzw. f ( s * ) t f ( s) , s S .92 Kombinatorische Optimierungsprobleme zeichnen sich häufig durch den hohen Lösungsaufwand aus. Aus diesem Grund gewinnen Heuristiken zur Lösung dieser Problemklassen an Bedeutung. Die folgenden Unterabschnitte beschreiben die in dieser Arbeit zum Einsatz kommenden Optimierungsverfahren. 2.2.3.1 Prioritätsregeln
Mit Prioritätsregeln wird eine Problemlösung unter Einsatz einer Regel konstruiert. Ein einfaches Beispiel stellt die First Come-First Served-Regel dar, die aus der Produktionsplanung bekannt ist.93
92
Vgl. DORIGO, M.; STÜTZLE, T. (2004), S. 26. Jedes Optimierungsproblem besitzt ein Entscheidungsproblem, das wie folgt definiert ist: Sei 3 ein Optimierungsproblem mit den dargestellten Eigenschaften und ein Parameter, dann lautet das Entscheidungsproblem: Gibt es ein s S , so dass f (s) d V ? Es ist somit deutlich, dass mit der Lösung des Optimierungsproblems auch eine Antwort auf das Entscheidungsproblem gegeben werden kann. Der entgegengesetzte Schluss ist jedoch im Allgemeinen nicht möglich. Auf diesem Entscheidungsproblem baut die Komplexitätstheorie auf, vgl. hierzu u.a. CORMEN, T. H. (2005), S. 967ff. Die Komplexität wird im Allgemeinen mit Hilfe der Groß-O-Notation angegeben, die den Lösungsaufwand einer Methode im worst case angibt. Kritiker kennzeichnen diese Darstellung als irreführend. So wird die Komplexität zur Sortierung von n Zahlen mit Hilfe des Quicksort-Verfahrens mit O ( n 2 ) angegeben, obwohl der Großteil der Fälle in O ( n log n ) sortiert werden kann, vgl. hierzu u.a. SONDERGELD, L. (2001), S. 20 und auch CORMEN, T. H. (2005), S. 149- 164.
93
Vgl. BLOECH, J. et al. (2008), S. 306f.
26
Grundlagen logistischer Systeme und Prozesse
Mit Hilfe dieser Regeln lassen sich gute und in besonderen Fällen optimale Lösungen finden, wenn analytische Lösungen aufgrund der Problemstellung versagen. Es lassen sich statische von dynamischen Prioritätsregeln abgrenzen. Im Gegensatz zu den dynamischen Prioritätsregeln verändern sich die statischen Regeln nicht im Zeitablauf. Zudem können lokale und globale Regeln klassifiziert werden. Während lokale Regeln nur eine einzige Maschine berücksichtigen, ziehen globale Regeln auch andere Kriterien hinzu. Die Funktionsweise der Regel ist zumeist mit ihrer Bezeichnung vollständig determiniert. Die folgenden Beispiele für Prioritätsregeln gehen auf BLOECH ET AL. zurück.94 Die First Come-First Served-Regel beschreibt eine statische und lokale Prioritätsregel und besagt, dass Aufträge in der Reihenfolge ihrer Ankunft zu behandeln sind. Die kürzeste Operationszeit-Regel besagt, dass zuerst diejenigen Aufträge zu behandeln sind, deren Operationszeit die geringste Zeit auf der betrachteten Maschine beansprucht. Es handelt sich deshalb ebenfalls um eine statisch lokale Prioritätsregel, die sich jedoch zu einer globalen Regel erweitern lässt, indem die Summe aller noch zu bearbeitenden Aufträge in die Berechnung einbezogen wird. Ein Beispiel für eine dynamische und globale Prioritätsregel gibt die Critical Ratio-Regel. Bei ihr wird für jeden Auftrag der festliegende Liefertermin ins Verhältnis zu der (zu diesem Zeitpunkt noch) notwendigen Restbearbeitungszeit gesetzt. Auch in Anwendungen der Containerlogistik lassen sich Beispiele für den Einsatz von Prioritätsregeln finden, u.a. First Come-First Served (FIFS)95 sowie High Earnings First und Shortest Job First96 in der Liegeplatzplanung. In diesen Fällen wird der Liegeplatz als Maschine abgebildet, die verschiedene Aufträge (Containerschiffe) zu bearbeiten hat.
94
Vgl. BLOECH, J. et al. (2008), S. 307.
95
Vgl. MEIER, L. et al. (2005), S. 2274.
96
Vgl. HENESEY, L. (2004), S. 153. Die genannten Regeln definieren, in welcher Reihenfolge ein Schiff zuzuordnen ist.
Grundlagen logistischer Systeme und Prozesse
27
2.2.3.2 Greedy-Verfahren
Greedy-Verfahren97 basieren auf der Idee, jeweils die lokal beste Möglichkeit zu wählen, in der Hoffnung, so das Gesamtoptimum zu finden. Diese Verfahren sind damit sehr einfach zu implementieren, können aber nur in Ausnahmefällen, d.h. bei sehr speziellen Problemstrukturen, ein Optimum erreichen. Sie gehören zu den konstruktiven Verfahren, da sie sich, ausgehend von einem Startpunkt, mit lokal minimalen Kosten gierig ausbreiten. Aus diesem Grund werden sie auch als myopische98 Verfahren bezeichnet. Den Gegensatz zu gierigen und kurzsichtigen Verfahren bilden vorausschauende Verfahren, die in jedem Schritt der Lösungskonstruktion die Wirkung ihrer Maßnahmen abschätzen.99 Dieses Vorgehen ist im Folgenden aufgezeigt: procedure GreedyConstructionHeuristic
s p Å ChooseFirstComponent while ( s p is not a complete solution) do c Å GreedyComponent( s p ) sp Å sp
c end while s Å sp return s end procedure
Abbildung 2-3: Greedy-Heuristik100
Eingesetzt werden Greedy-Verfahren, z.B. in konstruktiven Heuristiken zur Erstellung von Ausgangslösungen.101 Auch für die Containerbrückenzuordnung in einem Container-Terminal lassen sich Greedy-Verfahren einsetzen. Ein Beispiel aus der Tourenplanung ist im Anhang dargestellt und
97
Aus dem Englischen: greedy = gierig.
98
Aus dem Englischen: myopic = kurzsichtig, myopisch.
99
Vgl. DOMSCHKE, W.; DREXL, A. (2007), S. 129.
100
DORIGO, M.; STÜTZLE, T. (2004), S. 30.
101
Vgl. DORIGO, M.; STÜTZLE, T. (2004), S. 29ff.
28
Grundlagen logistischer Systeme und Prozesse
verdeutlicht, warum eine optimale Lösung mit diesen Verfahren in der Regel nicht zu erreichen ist. 2.2.3.3 Metaheuristiken
In diesem Abschnitt werden die in den implementierten Modellen eingesetzten Metaheuristiken zusammen mit ihren Eigenschaften vorgestellt. Dann wird kurz auf weitere, in der Literatur relevante Metaheuristiken eingegangen.102 2.2.3.3.1 Allgemeine Kennzeichen
Als Definition für Metaheuristiken, die Gegenstand des folgenden Abschnitts sein sollen, führen DORIGO und STÜTZLE folgende Beschreibung an: „A metaheuristic is a set of algorithmic concepts that can be used to define heuristic methods applicable to a wide set of different problems. […] A metaheuristic is therefore a general algorithmic framework which can be applied to different optimization problems with relatively few modifications to make them adapted to a specific problem.”103 Metaheuristiken stellen einen allgemeinen Rahmen für den Einsatz von Heuristiken bereit. Die folgende Abbildung zeigt die Heuristiken und Metaheuristiken hinsichtlich ihres Spezifikationslevels zur konzeptionellen Unterscheidung.104
Metaheuristik
Heuristik
Abbildung 2-4: Spezifikationslevel von Heuristiken105
Über die Spezifizierung ihrer Parameter lassen sich Metaheuristiken für unterschiedliche Problemstellungen anpassen. Sie enthalten Elemente, mit denen es möglich ist, sich von
102
Anwendungsbeispiele werden in den folgenden Kapiteln gegeben.
103
DORIGO, M.; STÜTZLE, T. (2004), S. 33.
104
Vgl. SONDERGELD, L. (2001), S. 6.
105
Leicht verändert übernommen aus SONDERGELD, L. (2001), S. 6.
Grundlagen logistischer Systeme und Prozesse
29
lokalen Optima zu lösen. Auch für sie existiert aber keine Garantie für das Auffinden des globalen Optimums. In dieser Arbeit kommen verschiedene Metaheuristiken zum Einsatz. Aus diesem Grund sollen deren Abläufe und Eigenschaften im folgenden Abschnitt näher und umfassend vorgestellt werden. Aufgrund der Probleme, die sich aus der Komplexität der Lösungsfindung ergeben, sind Heuristiken insbesondere für Problemstellungen der Realität geeignet, wenn sie in der Lage sind, in relativ kurzer Zeit eine möglichst gute (und gültige) Lösung zu finden.106 2.2.3.3.2 Genetische Algorithmen
Genetische Algorithmen (GA) sind Teil evolutionärer Algorithmen und bilden den Evolutionsprozess künstlich nach. Obwohl es sehr viele unterschiedliche Varianten von GA gibt, lassen sich in allen Varianten dieselben Kernelemente wiederfinden. Im Allgemeinen handelt es sich bei dem GA um ein populationsbasiertes Modell, das mit Selektions- und Rekombinationsoperatoren arbeitet.107 Insbesondere NISSEN hat die Anwendung von evolutionären Algorithmen für betriebswirtschaftliche Problemstellungen untersucht108 und zeigt - zusammen mit BIETHAHN - ausführliche Anwendungen in der Praxis auf.109 LACKNER untersucht den Einsatz von GA für kapazitätsrestriktive und dynamische Tourenplanungsprobleme mit Zeitfenstern.110 In jeder Iteration eines GA werden Nachfolger aus einer Population erzeugt, die in die nächste Generation eingehen und mit Hilfe einer Fitnessfunktion zu bewerten sind. Wie in einem Evolutionsprozess haben bessere Lösungen eine größere Wahrscheinlichkeit für die Weitergabe ihrer Merkmale an Nachfolger als schlechte Lösungen.111 Die Population enthält eine Menge von Lösungen für das Optimierungsproblem. Um eine Lösung mit geneti-
106
Diese Aussage deckt sich auch mit der Forderung der Angemessenheit der Problemlösung. Der Aufwand und der Nutzen der Planung müssen in einem angemessenen Verhältnis stehen, vgl. hierzu MÜLLERMERBACH, H. (1992), S. 14f.
107
Vgl. GHANEA-HERCOCK, R. (2003), S. 27.
108
Vgl. NISSEN, V. (1994), S. 291- 432.
109
Vgl. NISSEN, V.; BIETHAHN, J. (1995). Es werden Anwendungen der Industrie, des Handels, der Finanzwirtschaft, der Verkehrswirtschaft und der Ausbildung aufgezeigt.
110 111
Vgl. LACKNER, A. (2004).
Dieses Selektionsprinzip basiert auf DARWINS Prinzipien zur Evolutionstheorie: Survival of the fittest, vgl. DARWIN, C. (1860).
30
Grundlagen logistischer Systeme und Prozesse
schen Algorithmen abbilden zu können, ist der Phänotyp einer Lösung mit Hilfe einer Kodierfunktion in den Genotyp umzuwandeln. Eine Dekodierfunktion transformiert später die genotypisch vorliegende Information zurück in ihre phänotypische Form.112 Die folgende Sequenz geht auf HOLLAND zurück und bildet die gemeinsame Grundlage für den allgemeinen GA:113 1. Erzeugen einer zufällig generierten Population mit N Chromosomen der Länge m. 2. Testen jedes Chromosoms, d.h. einer möglichen Problemlösung x im Rahmen des Lösungsraums und Zuweisung eines Fitnesswertes f (x ) . 3. Selektion von Chromosom-Paaren aus der Population mit einer auf dem Fitnesswert basierenden Wahrscheinlichkeit. 4. Anwendung genetischer Operatoren. Mit der Wahrscheinlichkeit pc wird für zwei Eltern ein Crossover-Operator an einem zufällig ausgewählten Punkt jedes Chromosoms durchgeführt. 5. Anwendung genetischer Operatoren. Mit der Wahrscheinlichkeit pm wird jedes neue Chromosom mutiert. 6. Setzen der neuen Chromosome in die neue Population und Ersetzen der alten Population durch die Neue. 7. Stopp, falls das Zielkriterium erreicht ist, z.B. ein vorgegebener Fitnesswert. Sonst weiter mit Schritt 2. Die folgende Abbildung zeigt den Ablauf evolutionärer Algorithmen im Überblick.
112 113
Vgl. BIETHAHN, J. et al. (2004), S. 55.
Vgl. GHANEA-HERCOCK, R. (2003), S. 28. Es ist darauf hinzuweisen, dass sich der von HOLLAND vorgestellte GA bis heute stark weiterentwickelt hat, vgl. hierzu HOLLAND, J. (1998).
Grundlagen logistischer Systeme und Prozesse
31
procedure EvolutionaryComputationAlgorithm pop Å InitializePopulation EvaluatePopulation(pop) sbest Å BestOfPopulation(pop) while (termination condition not met) do pop' Å Recombination(pop) pop' ' Å Mutation( pop' ) EvaluatePopulation( pop' ' ) s Å BestOfPopulation( pop' ' ) if (f(s)T) auf ein Containerschiff geladen werden, 1 d t d T ,1 d i d B
E it , die erwartete Anzahl an VSDS-Containern, die in Periode t den Terminal erreichen, Block i zugeordnet sind und deren Auslieferungszeitpunkt unbekannt bzw. außerhalb des Planungszeitraums liegt, 1 d t d T ,1 d i d B
J it , die erwartete Anzahl an Transshipment-Containern, die den Terminal in Periode t wasserseitig erreichen und Block i zugeordnet sind, mit einem unbekannten bzw. außerhalb des Planungszeitraums liegenden (wasserseitigen) Aufnahmezeitpunkt, 1 d t d T ,1 d i d B
120
Planung in Container-Terminals
Mit Hilfe dieser Modellparameter wird die Verknüpfung zur Liegeplatzplanung hergestellt, deren Lösung in die erforderliche Form zu bringen ist. Hinzu kommen die folgenden Entscheidungsvariablen:
Gitk , die Anzahl von CYGD-Containern mit vollen Informationen, die in Block i
gelagert werden und den Terminal in Periode t erreichen und in t k wasserseitig wieder verlassen, 1 d i d B,1 d t d T ,0 d k d T t
Git , die Anzahl von CYGD-Containern, die in Block i gelagert werden und den
Terminal in Periode t erreichen, 1 d t d T ,1 d i d B
Ditk , die Anzahl der VSDS-Container mit vollen Informationen, die in Block i ge-
lagert werden, in Periode t wasserseitig den Terminal erreichen und diesen in t k landseitig wieder verlassen, 1 d i d B,1 d t d T ,0 d k d T t
Dit , die Anzahl aller VSDS-Container, einschließlich Transshipment-Containern,
die in Block i gelagert werden und in Periode t wasserseitig den Terminal erreichen, 1 d t d T ,1 d i d B
Ritk , die Anzahl an Transshipment-Containern mit vollen Informationen, die in
Block i gelagert werden, den Terminal in Periode t erreichen und diesen nach k Zeiteinheiten ebenfalls wasserseitig verlassen, 1 d i d B,1 d t d T ,0 d k d T t
Lit , die Anzahl von VSLD-Containern, Transshipment-Container eingeschlossen,
die in Block i gelagert und in Periode t auf ein Schiff verladen werden,
1 d t d T ,1 d i d B
Pit , die Anzahl von CYPI-Containern, die in Block i gelagert werden und in Perio-
de t landseitig den Terminal verlassen, 1 d t d T ,1 d i d B
Vit , die Anzahl der Container in Block i am Ende der Periode t, 1 d t d T ,1 d i d B
Modellformulierung nach ZHANG ET AL. w ªmax( D L ) min ( D L )º ½ it it it it »¼ {i} °° 1 «¬ {i} °° Zielfunktion: Minimiere o ¦ ® ¾ t 1 ° w2 ªmax( Dit Lit Git Pit ) min ( Dit Lit Git Pit )º ° »¼ ¿° {i} ¯° «¬ {i} T
Planung in Container-Terminals
121
Unter den Nebenbedingungen: a) Containerfluss-Restriktionen ~ (1) Dit
B
¦D
itk
,
t
1,2,..., T ; k
0,1,...., T t
itk
,
t
1,2,..., T ; k
0,1,...., T t
itk
,
t
1,2,..., T ; k
0,1,...., T t
i 1
~ (2) Git
B
¦G i 1
B
~ (3) Rit
¦R i 1
Die Bedingungen (1), (2) und (3) stellen sicher, dass VSDS-, CYGD- und TransshipmentContainer vollständig auf die vorhandenen (B) Blöcke aufgeteilt werden. T t
(4) Dit
¦ (D
itk
Ritk ) E it J it ,
i 1,2,..., B; t
1,2,...., T
i 1,2,..., B; t
1,2,...., T
k 0
T t
(5) Git
¦G
itk
D it ,
k 0
Die Restriktionen (4) und (5) stellen sicher, dass die Anzahl der Container in Block i zum Zeitpunkt t gleich der Summe der Container mit vollen Informationen und Containern mit unbekannter bzw. hinter dem Planungszeitraum liegender Abfahrtszeit ist. b) CYPI- und VSLD-Restriktionen t 1
(6) Lit
L0it ¦ (Gi ( t k ) k Ri ( t k ) k ),
i 1,2,..., B; t
1,2,...., T
i 1,2,..., B; t
1,2,...., T
k 0
t 1
(7) Pit
Pit0 ¦ Di ( t k ) k , k 0
Die Anzahl der Container, die den Yard in Periode t wasser- oder landseitig [(6) bzw. (7)] von Block i verlassen, setzt sich zusammen aus der Summe der initial vorhandenen Container für diese Periode und den während der Zeit hinzugekommenen Containern. c) Yard-Block-Restriktionen (8) Vit
Vi ( t 1) [(Git Dit ) ( Pit Lit )],
(9) Vit d KC i ,
i 1,2,..., B; t
1,2,...., T
i 1,2,..., B; t
1,2,...., T
122
Planung in Container-Terminals
Yard-Block-Restriktionen (8) und (9) definieren die Aktualisierung des Block-Bestands, der sich aus dem alten Bestand in Block i zuzüglich den Zugängen und abzüglich den Abgängen zusammensetzt. Zudem soll die Block-Dichte K nicht überschritten werden. d) Ganzzahligkeits-Bedingungen Alle Variablen dürfen nur ganzzahlige, nicht-negative Werte annehmen. Es ist zu bestimmen, wie die Containermengen einzelner Perioden zu verteilen sind. In dem ersten Teil des SLP erfolgt noch keine Zuordnung von Containern zwischen Schiff und Yard, es ist lediglich für jeden Block die Menge der Container, die in der betrachteten Periode zu lagern sind, zu bestimmen. Die konkrete Zuordnung von Im- bzw. Exportcontainern des Schiffes zu einem bestimmten Block erfolgt erst im zweiten Teil des SLP, modelliert als klassisches Transportproblem. Dieses Modell erlaubt die gemeinsame Lagerung von Im- und Exportcontainern in einem Block und die Aufteilung von Containern eines Jobs auf unterschiedliche Blöcke.494 Zur Lösung dieser Problemstellung stellen MURTY
ET AL.
einen Ansatz vor.495 Der Lö-
sungsansatz basiert auf der Idee, Behinderungen im Prozessablauf durch mehrfachen und kurzfristig hintereinander erfolgenden Zugriff von Transportern auf einen Block zu verhindern. Es ist deshalb das Transportaufkommen an den Blöcken des Yards auszugleichen. Die Zielfunktion minimiert das Zuordnungsungleichgewicht der Lagerung von Containern im Yard.496 Die vorgestellte Methode dient der Bestimmung einer Lösung für die erste Stufe des Storage Location Problems. In Abhängigkeit von dem erwarteten Containeraufkommen wird für jeden Block in jeder Periode der Fill-Ratio (FR) berechnet. Der Fill-Ratio für Block i zu Beginn der Periode p+1 (= Fi ( p 1) ) berechnet sich wie folgt:
494
Diese Annahme ist in der Praxis durchaus üblich und gewinnt aufgrund der Zunahme von Containern an Bedeutung, um Kapazitäten weiter auszulasten.
495 496
Vgl. MURTY, K. G. et al. (2005), S. 321- 323.
Diese Zielsetzung wird auch von ZHANG ET AL. angenommen, vgl. die Zielfunktion in diesem Abschnitt. Dieser Ansatz ist insbesondere deshalb zu unterstützen, weil die Zielsetzung die Probleme der Transportplanung mit aufgreift. Im Rahmen einer übergreifenden Untersuchung erscheint die Berücksichtigung abhängiger Entscheidungsbereiche wertvoll.
Planung in Container-Terminals Fi ( p 1)
123
( Fi ( p )k i ESi ( p ) IS i ( p ) xi ( p )) ki
Es ist unglücklich, dass mit der Darstellung von MURTY ET AL. wieder neue Symbole eingeführt werden.497 Zur Erläuterung der Symbole wird die entsprechende und in diesem Abschnitt eingeführte Bezeichnung nach ZHANG ET AL. mit angegeben:
ESi ( p ) beschreibt die Container, die Block i in Periode p wasserseitig verlassen
(= Lip im Modell nach ZHANG ET AL.).
ISi ( p ) beschreibt die Container, die Block i in Periode p landseitig verlassen
(= Pip ).
xi ( p ) stellt die (zu bestimmenden) Zugänge für diesen Block in dieser Periode dar
(= Dip Gip ).
k i beschreibt die Kapazität des Blocks (= Ci ).
Der Fill-Ratio beschreibt das Verhältnis der Anzahl im Block lagernder Container zu seiner Gesamtkapazität. Weil sich alle Elemente im Modell von ZHANG ET AL. wiederfinden lassen, kann der Ansatz zur Lösung dieser Problemstellung zum Einsatz kommen. Das Verfahren strebt den Ausgleich aller Fill-Ratios an und wird deshalb als Fill-RatioEqualization-Ansatz (FRE) für die erste Stufe der Lagerplanung gekennzeichnet. Von
MURTY
ET AL.
wird eine einfache Rechnung zur Bestimmung der Containermengen für
jeden Block aufgezeigt, so dass der Fill-Ratio ausgeglichen wird.498 Im Folgenden soll der zweite Teil des SLP vorgestellt werden. Stufe II des Storage Location Problems als klassisches Transportproblem Nachdem die Verteilung der in den einzelnen Perioden ankommenden Container auf die Blöcke mit Teil I festgelegt wird, entsteht in Teil II ein klassisches Transportplanungsprob-
497
Vgl. MURTY, K. G. et al. (2005), S. 322. Die unterschiedlichen Symbole sind auch insofern unglücklich, weil ein Großteil der Autoren an beiden Artikeln mitgearbeitet hat.
498
Vgl. MURTY, K. G. et al. (2005), S. 321ff. Das FRE-Verfahren kommt im Rahmen der Untersuchung des SLP in Kapitel 6.1.1.5 zum Einsatz.
124
Planung in Container-Terminals
lem, bei dem zu definieren ist, welche Container welchen Schiffes den freigeräumten Blockkapazitäten zuzuordnen sind. Das klassische Transportproblem ist wie folgt aufgebaut:499 Zielfunktion: Minimiere o F ( x)
m
n
¦¦ c
ij
xij
i 1 j 1
Unter den Nebenbedingungen: n
(1)
¦x
ij
ai
, für i=1, 2, …, m
ij
bj
, für j=1, 2, …, n
j 1
m
(2)
¦x i 1
Nichtnegativitätsbedingungen: (3) xij t 0
, für alle i und j
Aus der Lösung des ersten Teils des SLP lassen sich die Parameter für das klassische Transportproblem bestimmen: Der b-Vektor ist das Ergebnis der zugeordneten Blockkapazitäten, während a die wasserseitigen Containerströme zum Zeitpunkt t angibt. Mit n ist demnach die Anzahl der Yard-Blöcke angegeben, m beschreibt die Anzahl der Containerschiffe mit Anlegezeitpunkt t. Es gilt, die Distanz zwischen den Yard-Blöcken und Anlegeorten der Schiffe500 zu minimieren. Zur Bestimmung der Distanz in dem CT-Modell lassen sich Metriken einsetzen:501
499
Vgl. DOMSCHKE, W.; DREXL, A. (2007), S. 81ff.
500
Diese Größe ergibt sich aus der in der Liegeplatzplanung definierten Position v, vgl. Kapitel 3.2.2.2.
501
Vgl. TEAM, R. D. C. (2007). Die R-Funktion dist() gibt unterschiedliche Ansatzpunkte zur Bestimmung der Distanz zwischen zwei Punkten.
Planung in Container-Terminals
125
Buffer- Position: (0,0) (50, 0)
(100, 0)
(150, 0)
(200, 0)
(50, 20)
(100, 20)
(150, 20)
(200, 20)
(50, 40)
(100, 40)
(150, 40)
(200, 40)
(50, 60)
(100, 60)
(150, 60)
(200, 60)
Zur Bestimmung der Distanz d zwischen Buffer p1 und Block p2: Manhattan- Metrik = d ( p1 , p2 ) = (|0-200|+ |0-40|) = 240
¦| ( p
i 1
p2i ) |
Euklidische Distanz =
i
d ( p1 , p2 )
¦( p
1
p2 ) 2
i
(0 200) (0 40) 2 | 204 2
Abbildung 3-20: Auswahl einer Metrik zur Bestimmung der Distanz im CT-Modell
Eingesetzt wird die Manhattan-Metrik, weil diese Metrik den Weg der VC im Terminal am besten abbildet. Zum Vergleich ist in der Abbildung die euklidische Distanz zwischen den beiden Containerpositionen dargestellt. Es wird deutlich, dass die euklidische Distanz nicht für die Abbildung der VC-Fahrwege auf dem Terminal einsetzbar ist. Es ist zu beachten, dass der Wert der euklidischen Distanz („direkter Weg“) geringer ist, als der der Manhattan-Distanz („Umfahren des Blocks“). Das klassische Transportproblem ist ein lineares Optimierungsproblem, weist jedoch aufgrund seiner Nebenbedingungen eine spezielle Struktur auf, für dessen Lösung spezielle Verfahren entwickelt worden sind.502 Zur Lösung des Transportproblems im Rahmen des SLP wurde deshalb die MODIMethode implementiert, um eine optimale Zuordnung der Container auf die im ersten Teil des SLP definierten Yard-Blöcke zu erreichen. Aufgrund der im ersten Teil fixierten Anzahl zu lagernder Container in einem bestimmten Block für eine bestimmte Periode lässt sich der zweite Teil des Problems als Transportproblem abbilden. Es ist in diesem Schritt die konkrete Zuordnung von zu im- bzw. zu exportierenden Containern eines Schiffes zu einem Yard-Block zu bestimmen. Die Anzahl
502
Vgl. DOMSCHKE, W.; DREXL, A. (2007), S. 81ff.
126
Planung in Container-Terminals
der Container der Schiffe lässt sich im Rahmen des KTP als Angebotsmenge betrachten. Die fixierten Kapazitäten im Yard stellen die Nachfragemenge dar, so dass sich diese Container nun kostenminimal503 zuordnen lassen. Der Vorteil von diesem Ansatz ist, dass das KTP in der Literatur weitreichend untersucht worden ist und optimale Lösungsansätze existieren.504 Dieses Vorgehen ist in der folgenden Abbildung zusammengefasst. Storage Location Problem SLP 1:
1
2
…
B
Block-Kap. für t=1
1
2
…
B
Block-Kap. für t=2
1
2
…
B
Block-Kap. für t=T
Yard
Zoom
B2
BB
In t anlegende Schiffe (aus BAP)
Block 1
SLP 2: Klassisches Transport1 2 problem 1
Blockkapazitäten in t (aus SLP 1)
…
B
d(v,b)
2 . . .
Distanzmatrix Distanz (Schiffposition, Blockposition) Schiffposition ist mit BAP-Lösung gegeben Blockposition ist aus Parametern gegeben
Vt
Abbildung 3-21: Darstellung des SLP
In der Abbildung repräsentieren die grau hinterlegten Felder den ersten Teil des SLP, in dem die Kapazitäten jedes Blocks für jede Periode zu bestimmen sind. Diese Zuordnung geht dann in den zweiten Teil des SLP, als Nachfrage des KTP, ein. Die BAP-Zuordnung bestimmt das KTP-Angebot.
503
hier: distanzminimal.
504
Vgl. DOMSCHKE, W.; DREXL, A. (2007), S. 81ff.
Planung in Container-Terminals
127
3.2.4.3 Annahmen und Kritik
Das Modell von ZHANG
ET AL.
behandelt lediglich Container einer Größe. Spezifische
Merkmale von Containern, u.a. Kühlgut, Gefahrgut etc. finden in dem Modell keine Berücksichtigung. Der Arbeitsaufwand wird über die Anzahl zu bearbeitender Container bestimmt. Es wird angenommen, dass genügend Ressourcen zur Behandlung der Container vorhanden sind. Stochastizität wird in dem Modell nicht behandelt. Dies kann jedoch notwendig sein, wenn es aufgrund von Verzögerungen im Ablauf zu einer Veränderung der Nachfrage und des Angebots von Yard-Ressourcen kommt. Das vorgestellte Modell setzt direkt im Rahmen der in Abbildung 3-4 vorgestellten Hierarchie von CT-Entscheidungen an. Es berücksichtigt die Behandlung von Import-, Exportund Transshipment-Containern in einem gemeinsamen Lager. Dieser Fall ist insbesondere für Terminals interessant, die mit einer begrenzten Yardkapazität umgehen müssen. Die Positionen der Schiffe und der Lagerplätze im Yard finden Berücksichtigung, um so die Transportdistanz zwischen Kai und Yard zu minimieren. Die Zielsetzung versucht die Container unter Berücksichtigung der Anforderungen für die Yard-Transporte zu verteilen und setzt damit einen zielgesteuerten Ansatz zur Koordination mit anderen Entscheidungen ein. Die Dekomposition in zwei Teilprobleme zerschneidet erneut Abhängigkeiten. Der Artikel von ZHANG
ET AL.
zeigt keinen Lösungsansatz für die Problemstellung auf.
Erst MURTY ET AL. zeigen einen Fill-Ratio-Equalization-Ansatz, an dem zu kritisieren ist, dass keine Rücksicht auf die Verweildauer der Container im Yard genommen wird.
3.2.5 Transportplanung (Vehicle Dispatching Problem)
In dem Vehicle Dispatching Problem (VDP) werden die einzelnen Containertransporte betrachtet. Das VDP führt die Bereiche der Containerbrücken- und der Yardplanung (SLP) zusammen, weil sich durch diese Bereiche die Distanzen für die durchzuführenden Containertransporte ergeben. 3.2.5.1 Ansätze in der Literatur
Wie für die Yardplanung, existieren auch für Modelle der CT-Transportplanung weitreichende Abstraktionsunterschiede. Dies ist der Fall, weil in Abhängigkeit vom Betriebssys-
128
Planung in Container-Terminals
tem sowohl Eigenschaften von Transportern und Flurfördergeräten zu beachten sind, als auch das detaillierte Layout des Terminals zu berücksichtigen ist. Es sind somit im Rahmen von operativen Modellen weitaus präziser definierte Informationen zu verwenden, als dies in strategischen oder taktischen Modellen notwendig ist. Eingangsdaten für die Transportplanung können in zwei Gruppen klassifiziert werden. Aus der hierarchischen Struktur und dem sequenziellen Ansatz von ZHANG ET AL. erwächst die erste Gruppe der erforderlichen Eingangsdaten für diese Problemstellung.505 Die zweite Gruppe ergibt sich aus den terminalspezifischen Parametern.506 Aufgrund der vorangestellten Probleme finden sich Literaturmodelle der Transportplanung auf unterschiedlichen Abstraktionsstufen wieder und lassen sich darüber klassifizieren. BÖSE ET AL. untersuchen das Vehicle Dispatching Problem mit Hilfe von GA für drei unterschiedliche Zuordnungsstrategien.507 Die von ihnen modellierte Problemstellung maximiert die QC-Produktivität unter dem Aspekt der Minimierung seiner Wartezeiten.508 Die beschriebenen Strategien zur Zuordnung von Van Carriern und Containerbrücken werden von MEIER im Rahmen von terminalpolitischen Entscheidungen aufgeführt.509 BISH ET AL. stellen unterschiedliche und leicht implementierbare Greedy-Algorithmen für das Vehicle Dispatching Problem vor. Der Modellansatz ist mit dem von BÖSE ET AL. vergleichbar. Jeder Container wird als ein Job betrachtet. Für eine gegebene Jobsequenz werden die Algorithmen zunächst für eine Single-Vessel-Single-Crane-Instanz betrachtet und daraufhin für den Multiple-Crane-Fall erweitert. Die Leistungsfähigkeit der Algorithmen wird analysiert. Der Fokus der Autoren liegt auf der Einsatzfähigkeit der entwickelten Verfahren, auch für große Instanzen.510
505
Vgl. Abbildung 3-4.
506
Zu den terminalspezifischen Parametern gehören u.a. die Positionen der Yard-Blöcke und deren Kapazität sowie die Anzahl der Yard-Transporter und deren Operationsgeschwindigkeit.
507
Vgl. BÖSE, J. et al. (2000).
508
Vgl. BÖSE, J. et al. (2000), S. 4f.
509
Vgl. MEIER, L. (2006), S. 218- 220.
510
Vgl. BISH, E. K. et al. (2005), S. 491- 506.
Planung in Container-Terminals
129
Weitere Ansätze für dieses Problem werden ausführlich von STAHLBOCK und VOß vorgestellt. Unterschiedliche Modellierungsperspektiven erschweren ihre Vergleichbarkeit. In der Literatur wird im Wesentlichen die Zuordnung von AGVs behandelt. Das Modell von BÖSE
ET AL.
soll im Folgenden dargestellt werden, weil es Van Carrier
einsetzt und auf der für diese Arbeit relevanten Abstraktionsebene ansetzt. 3.2.5.2 Vehicle Dispatching Problem nach BÖSE ET AL.
In dem Modell sind G Containerbrücken vorhanden, die Container mit einer einheitlichen und konstanten Bearbeitungszeit umschlagen: t g , g {1,2,..., G} Jede Containerbrücke erledigt im Rahmen der Bearbeitung einer Bay n Containerjobs. Dabei wird jeder einzelne Job der Bay mit einer individuellen Bearbeitungszeit determiniert, die sich in Abhängigkeit von der Distanz zwischen der Yard-Ressource und der Kaiposition ergibt. Unter der Annahme einer konstanten VC-Geschwindigkeit ergibt sich die Zeit für die Bearbeitung dieses Jobs j aus der Distanz zwischen Kai und Yard. Diese Zeit lässt sich wie folgt berechnen: t j [ ZE ]
s j [ SE ] . [ SE ] vVC [ ZE ]
Jeder Container-Transport erhält somit eine individuelle Bearbeitungszeit, die von den vorangegangenen Entscheidungen aus SLP sowie BAP und CSP abhängig ist.511 Jede Containerbrücke verfügt über einen kleinen Puffer mit wenigen Containerstellplätzen auf der Kaistellfläche, auf der eine bestimmte Anzahl von Containern gelagert werden kann. Ist dieser Puffer belegt, muss der QC seine Arbeit einstellen und warten, bis ein Transportfahrzeug einen Container aus dem Puffer entfernt. Ziel des Modells von BÖSE ET AL.
511
ist die Minimierung dieser Verzögerungen. Alle t g Zeiteinheiten kann der QC einen
Vgl. hierzu Kapitel 3.2.
130
Planung in Container-Terminals
neuen Container in diesen Puffer platzieren, während ein Transporter für die Durchführung von Job j exakt 2 * t j Zeiteinheiten für den Hin- und Rücktransport beschäftigt ist.512 Unterschiedliche Zuordnungsstrategien schränken die Zuordnung von VC zu den Containerbrücken ein. So stehen die VC bei Verwendung von statischen Strategien513 lediglich für die Transporte an genau einer im Vorfeld definierten Containerbrücke zur Verfügung. In semi-dynamischen Strategien514 stehen die VC lediglich für die Containerbrücken eines bestimmten Schiffes zur Verfügung, währen in dynamischen Strategien515 diese Restriktionen in der Zuordnung aufgehoben werden und die VC für alle Jobs auf dem gesamten Terminal eingesetzt werden können. BÖSE ET AL. zeigen im Rahmen der von ihnen durchgeführten Experimente, dass sich mit Hilfe eines GA und der Umstellung auf eine dynamische Strategie sehr gute Ergebnisse erzielen lassen.516 Für einen Job an einer Bay bearbeitet ein QC zunächst sämtliche Löschcontainer, bevor er mit dem Laden der Container für diese Bay beginnt. Der Entstehungszeitpunkt tibirth des i ,g ten (Container-)Jobs eines QC g kann in Abhängigkeit von seinem Typ wie folgt berechnet werden, mit tibirth ,g
½ (1) t ginitial i * t g , ® initial trans ¾ t ( i 1 ) * t t g g ,i ¿ ( 2) ¯g
wobei (1) den Löschvorgang und (2) den Ladevorgang auf das Schiff kennzeichnet. Mit i ist der i-te Job des QC g dargestellt. t ginitial gibt den Zeitpunkt für den Beginn der Operatiobeschreibt die Zeit, die für die Durchführung dieses Transports nen für QC g an. t gtrans ,i durch den VC benötigt wird.
512
Im Allgemeinen stehen jeder Containerbrücke eine Anzahl (>1) unterstützender Transporter zur Verfügung. Die Zeit, die ein Yardfahrzeug für den Transport eines Containers in den Yard und zurück benötigt ( 2 * t j ) ist in der Regel größer, als die Zeit für den Umschlag des QC eines Containers zwischen Kai und
Schiff ( t g ), d.h. 2 * t j ! t g . 513
Diese Strategie wird auch als Crane-Pooling bezeichnet.
514
Diese Strategie wird auch als Vessel-Pooling bezeichnet.
515
Diese Strategie wird auch als Terminal-Pooling bezeichnet.
516
Vgl. BÖSE, J. et al. (2000), S. 7- 9. Auch MEIER, L. et al. (2005) zeigen für einen kleinen Terminal in Rio Grande, Brasilien, dass sich durch die Reorganisationsmaßnahme eine gesteigerte Produktivität erzielen lässt. Für die Umsetzung ist ein geeignetes Informationssystem erforderlich.
Planung in Container-Terminals
131
Beim Löschen der Container stellt der QC alle t g Zeiteinheiten einen neuen Container in den Puffer auf dem Kai zur Verfügung. Der letzte zu importierende Container cim kann demnach frühestens zum Zeitpunkt t ginitial cim * t g (
t gbirth , cim ) zur Verfügung stehen.
Das Laden der Container beginnt erst nachdem alle Container gelöscht worden sind, die für den Hafen bestimmt sind. Damit der QC ohne Unterbrechung arbeiten kann, muss der erste zu exportierende Container cex ( cim 1) bereits zum Zeitpunkt t ginitial cim * t g t gtrans ,cex initial ( t gbirth cim * t g im Puf,cex ) vom VC aus dem Yard genommen werden, damit dieser in t g
fer des QC von diesem aufgenommen und auf das Schiff geladen werden kann. Der Fertigstellungszeitpunkt des k-ten Jobs des Van Carriers c wird über eine rekursive Funktion berechnet, weil der Zeitpunkt der Fertigstellung des vorangehenden Jobs k-1 bekannt sein muss: t cdeath ,k
t cdeath t cempty t ktrans t cwait ,k 1 ,k ,k ,
rekursive Komponente
Der Fertigstellungszeitpunkt eines Jobs k berechnet sich somit aus dem Zeitpunkt der Fertigstellung des vorangegangenen Jobs, der Zeit für die Leerfahrt bis zu dem Job, der Transempty ! tcbirth portzeit und der Wartezeit auf den Container. Wartezeit tritt auf, wenn tcdeath ,k 1 t c ,k ,k ,
also falls der Transporter vor Bereitstellung des neuen Jobs an dem Startpunkt eingetroffen ist. Die von BÖSE ET AL. betrachtete Zielfunktion berechnet sich wie folgt: G
Minimiere
Jg
¦¦ Max((t
death c ,k 1
t cempty ) t gbirth ,k ,i ,0) , wobei
g 1 i 1
J g der Anzahl der Jobs des QC g entspricht und sich c aus der Zuordnung ergibt. Minimiert wird die Summe der Verspätungen aller VC bei der Ankunft am Entstehungsort eines Jobs. Es soll so die Produktivität der Containerbrücken maximiert werden. Zudem sind weitere Ziele denkbar, die sich berechnen lassen, z.B. die Minimierung der Transportdistanzen der VC, die Minimierung der VC-Wartezeiten oder auch eine (gewichtete) Kombination aus allen Zielen. Das Modell besteht aus einem einfachen Zuordnungsproblem, wie es in der OR-Literatur zu finden ist.
132
Planung in Container-Terminals
Die einzelnen Strategien zur Zuordnung wirken zusätzlich restriktiv auf den Lösungsbereich. So ist im Rahmen der statischen Crane-Pooling-Strategie die Zuordnung eines VC auf einen bestimmten QC fixiert, während andere QC verboten sind. Die folgende Abbildung verdeutlicht die Restriktionen für die Zuordnung von VC und QC unter den genannten Strategien:
QC
Vessel QC
QC
Terminal
Terminal QC
QC Vessel
Vessel QC
QC QC
QC Vessel
VC Restriktionen im Rahmen einer statischen Strategie nach Böse et al.
QC VC
QC
Vessel QC Terminal
QC
Restriktionen im Rahmen einer dynamischen Strategie nach Böse et al.
VC
QC Vessel
QC
Restriktionen im Rahmen einer semi-dynamischen Strategie nach Böse et al.
Abbildung 3-22: Restriktionen für das VDP unter verschiedenen Zuordnungsstrategien
Die Abbildung verdeutlicht, wie unter den gegebenen Strategien die Menge für die Zuordnung zugelassener Elemente variiert. Im Rahmen der dynamischen Strategie ist das größte Einsparpotenzial gegeben, da durch intelligente Zuweisung von Jobs unterschiedlicher Schiffe die Möglichkeit entsteht, Leerfahrten von VC zu reduzieren und durch Transportfahrten zu ersetzen. Es fallen in der statischen Strategie zwangsläufig Leerfahrten an. Die Berechnung ist jedoch sehr einfach. In der Regel werden von einem Terminal zwischen drei und vier VC pro QC eingesetzt. Die VC übernehmen nacheinander einen Job des QC, bis alle Jobs erledigt sind. Fallen keine Warte- und Transportzeiten an, dann würde die Bearbeitung einer Bay mit n Jobs genau (n-1) * t g Zeiteinheiten dauern, weil der QC genau einmal auf dem Rückweg seiner Tour einen Container mitnehmen kann. Diese Begründung veranschaulicht die folgende Abbildung am Beispiel von jeweils drei zu im- bzw. zu exportierenden Containern.
Planung in Container-Terminals
133 tg
Schiff
2 tg
tg
Beispiel: Kai
1
tg
2 tg 3 2 tg 4 2
2
tg tg
5
6
Mit n=6 ergibt sich
4 * tg 2 *
tg 2
(6 1) * t g
Abbildung 3-23: Optimale QC-Auslastung
Aus einem optimalen QC-Durchlauf517 für das in Abbildung 3-23 gezeigte Beispiel ergibt sich ohne Wartezeiten für den QC eine minimale Durchlaufzeit von 5 * t g Zeiteinheiten. Mit der Kenntnis der (theoretisch) optimalen Lösung lässt sich die Qualität der VDPZuordnung beurteilen. 3.2.5.3 Annahmen und Kritik
Für die Transportplanung ist, wie auch für das CSP, eine Restriktion hinzuzufügen, um den Anforderungen in dieser Arbeit gerecht zu werden. In dem Transportmodell von BÖSE ET AL.
wird angenommen, dass alle Container mit Beginn der Planung in t=0 zur Verfügung
stehen. Tatsächlich kann jedoch der Fall auftreten, dass Schiffe in dem betrachteten Zeitraum nacheinander ankommen und somit auch ihre Container nacheinander zu behandeln sind. Konkret muss dieselbe Bedingung, die für das CSP hinzugefügt wurde, geprüft werden.518
517
Als optimal wird der QC-Durchlauf in diesem Fall betrachtet, wenn sich keine Wartezeiten ergeben, d.h., jeder umzuschlagende Container zum geforderten (frühest)möglichen Zeitpunkt bereitsteht.
518
Für ein Beispiel kann auf Abbildung 3-12 verwiesen werden. Die Restriktion ist in Kapitel 3.2.3.2 beschrieben.
134
Planung in Container-Terminals
Die Personalplanung findet - wie für das CSP - keine Berücksichtigung. Es wird angenommen, dass für jeden in Betrieb zu nehmenden VC auch ein Fahrer zur Verfügung steht.519 In dem Modell von BÖSE ET AL. werden konstante QC-Zeiten für eine Containerbewegung gesetzt. Es wird angenommen, dass jeder VC jeden Job durchführen kann. Alle VC verfügen über eine konstante Transportgeschwindigkeit. Für das Modell ist kritisch festzustellen, dass keine stochastischen Fragestellungen zum Einsatz kommen. Gerade aber in diesem operativen Modell spielen stochastische Einflüsse eine sehr große Rolle.520 Behinderungen durch die Transporter selbst werden ebenfalls nicht berücksichtigt. Die Autoren setzen eine realitätsnahe Zielfunktion ein und zeigen unterschiedliche Zuordnungspolitiken für VC auf. Zusammen mit genetischen Algorithmen sind sie in der Lage, sehr gute Ergebnisse zu erzielen. Für jeden Job können individuelle Bearbeitungszeiten bestimmt werden. Das Modell ist so in der Lage, die Ergebnisse von SLP und CSP aufzugreifen. Es lässt sich das Terminalergebnis in einem zusammenhängenden Modell berechnen.
3.2.6 Weitere Planungssysteme und -ansätze
Bereits in der Kritik des vorangegangenen Abschnitts wurde die Personalplanung angesprochen, die für den Terminal von Bedeutung ist, von der jedoch in dieser Arbeit abstrahiert werden soll. Mit den in den vorangegangenen Kapiteln vorgestellten Planungssystemen konnten zwar die wesentlichen, keinesfalls jedoch alle Problemstellungen von Container-Terminals angesprochen und aufgezeigt werden. In der Literatur lassen sich andere
519
Mit der Personalplanung für alle nicht-automatischen Fahrzeuge des Terminals beschäftigen sich unterschiedliche Artikel in der Literatur, u.a. LEGATO, P.; MONACO, M. F. (2004), LIM, A.; RODRIGUES, B.; SONG, L. (2004) und auch HARTMANN, S. (2004) sowie den Überblick von VIS, vgl. VIS, I. (2008). Weil von dieser Problemstellung in dieser Arbeit abstrahiert wird, soll hier nur die verfügbare Literatur aufgezeigt werden.
520
Von BIETHAHN, J.; MEIER, L.; KLETTNER, N. (2006), S. 146- 148, werden stochastische Einflüsse auf diesen Entscheidungsbereich systematisiert. Diese Kritik wird auch im Ausblick von BÖSE ET AL. angesprochen, vgl. BÖSE, J. et al. (2000), S. 9f.
Planung in Container-Terminals
135
Planungssysteme finden, u.a. Probleme der Personalplanung, auf die hier nicht näher eingegangen werden soll.521 Auch auf die Stauplanung wird in dieser Arbeit keine Rücksicht genommen. Dies liegt darin begründet, dass für die Planung der Ladung auf dem Schiff die Eigenschaften der Container und von Schiffen im Detail zu betrachten sind, weil jedes Schiff unterschiedliche Restriktionen bzgl. seiner Beladung aufweist.522 Ebenfalls wurde die Vernachlässigung der exakten Positionierung von Containern innerhalb eines Blocks im Rahmen des Location Assignment Problems als Teil der Yardplanung angesprochen. Auch Reihenfolgeprobleme werden nicht mehr auf der Ebene einzelner Container, sondern lediglich für Containergruppen behandelt. Zudem wird von der landseitigen An- und Auslieferung von Containern abstrahiert. Die Vielzahl vorhandener Modelle und Lösungsansätze lässt es nicht zu, dass in dieser Arbeit ein vollständiger Überblick gegeben werden kann. Zur Lösung integrierender Modelle soll im Weiteren - aufgrund ihrer Bedeutung für diese Arbeit - auf zwei unabhängig voneinander entwickelte Ansätze von REBOLLO
ET AL.
und
auch HENESEY näher eingegangen werden, weil diese Autoren multiagentenbasierte Modelle für die übergreifende Behandlung von CT-Problemstellungen einsetzen. REBOLLO ET AL. zeigen, dass der Einsatz multiagentenbasierter Technologien aufgrund der Prozesskomplexität gerechtfertigt und geeignet ist. Die Autoren schlagen den Einsatz von insgesamt fünf verschiedenen Agentenklassen vor. Hierzu gehören SHIP-AGENTS, STEVEDORE-AGENTS,
SERVICE-AGENTS, TRANSTAINER-AGENTS und GATE-AGENTS. Für jedes an-
kommende Schiff werden SHIP-AGENTS erzeugt. Für jeden QC des CT existiert ein STEVEDORE-AGENT,
der die Zielsetzung verfolgt, die Aufgaben ankommender Schiffe so schnell
wie möglich zu bearbeiten. Insgesamt enthält das Modell somit eine Vielzahl interagierender Agenten.523
521
Für eine Diskussion weiterer Planungssysteme der CT-Logistik ist auf den ausführlichen Überblick in STEENKEN, D.; VOß, S.; STAHLBOCK, R. (2004) und STAHLBOCK, R.; VOß, S. (2007) sowie die dort angegebene Literatur zu verweisen.
522
Vgl. SCHOTT, R. (1989), S. 12- 41.
523
Vgl. REBOLLO, M. et al. (2000).
136
Planung in Container-Terminals
HENESEY beschäftigt sich mit der multiagentenbasierten Technologie um die Leistungsfähigkeit von CT-Systemen zu steigern.524 Neben dem Einsatz für ein Stakeholder Relationship Management (SRM) System,525 untersucht HENESEY zusammen mit WERNSTEDT und DAVIDSSON das Verhalten marktbasierter Verfahren in der CT-Anwendung. Die Autoren gliedern den CT in vier Subsysteme. Es sind darin die maritime und landseitige Schnittstelle526 enthalten, zusätzlich werden das Transfersystem (transfer system) und das Lagersystem (storage system) abgebildet.527 Eingeleitet durch die Arbeit von VICKREY von 1961 hat die markbasierte Kontrolle zusammen mit der Auktionstheorie an Bedeutung gewonnen.528 Marktbasierte Verfahren haben sich seitdem als geeignetes Instrument zur Beherrschung komplexer Systeme bewiesen.529 In der Arbeit von HENESEY werden vier unterschiedliche Agententypen eingesetzt. Hierzu gehören SHIP-AGENTS, BERTH-AGENTS, YARD-AGENTS und GATE-AGENTS, die in einer gemeinsamen Umgebung miteinander kommunizieren und (marktbasiert) verhandeln. Beispielsweise wird mit jeder Ankunft eines Schiffes ein SHIP-AGENT erzeugt, der gemeinsam mit einem BERTH-AGENT um den kostenminimalen Liegeplatz verhandelt.530
3.3 Interdependenzen Weil Beziehungen zwischen den CT-Teilbereichen existieren sind koordinierende Maßnahmen für ihre Integration erforderlich. Es entwickelt sich daraus der folgende Konflikt: Zum einen sollen bestehende Interdependenzen bei der Planung möglichst vollständig berücksichtigt werden, zum anderen steigen damit auch die Kosten der Planung.531 In diesem
524
Vgl. HENESEY, L. (2004).
525
Vgl. hierzu auch die Darstellung im Rahmen von Kapitel 3.1.1.
526
Diese Systeme werden von den Autoren als Ship-to-Shore-System und Delivery and Recipt-System bezeichnet.
527
Vgl. HENESEY, L. (2004), S. 131- 133. Die Subsysteme sind aus dem Ansatz von HOLGUÍN-VERAS und JARA-DÍAZ entnommen, vgl. HOLGUÍN-VERAS, J.; JARA-DÍAZ, S. (1999), S. 83.
528
Vgl. KRISHNA, V. (2002), S. 171ff.
529
Vgl. hierzu u.a. HENESEY, L. (2004), S. 127- 145.
530
Vgl. HENESEY, L. (2004), S. 127- 145.
531
Vgl. LAUX, H.; LIERMANN, F. (2005), S. 194.
Planung in Container-Terminals
137
Abschnitt sollen Interdependenzen, die zwischen Teilproblemen von CT-Prozessen vorliegen, aufgedeckt und als Grundlage für das zu entwickelnde Modell genutzt werden, mit dem sich der Einfluss von Wirkungen dieser Teilbereiche untereinander quantifizieren lässt. Die Integration von BAP und CSP wird u.a. von MEISEL und BIERWIRTH aufgezeigt.532 Die Autoren entwerfen eine übergreifende und ressourcenorientierte Zielfunktion, über die die beiden Entscheidungsbereiche koordiniert werden. Dieser Koordinationsansatz entspricht der von ADAM
ET AL.
beschriebenen Koordination über Führungsgrundsätze mit
impliziten Normen.533 Mit den untersuchten Verfahren zeigen die Autoren sehr gute Ergebnisse für die Problemstellung auf. Sie weisen auf die Bedeutung der Koordination zwischen BAP und CSP hin und zeigen wechselseitige Abhängigkeiten auf. Dennoch bietet diese Methode der Modellintegration einen Nachteil. Das Modell ist, wie auch ein Modell von PARK und KIM534, speziell für diese zusammenhängende Problemstellung aufgestellt worden. Auch deshalb zeigen die darauf abgestimmten Methoden gute Ergebnisse. Es darf trotzdem nicht außer Acht gelassen werden, dass nun zwar eine wichtige Interdependenz Berücksichtigung findet, noch immer bestehen jedoch Abhängigkeiten zwischen Problemstellungen des Terminals, die keine Berücksichtigung finden. Eine erneute Modellerweiterung ist unter keinen Umständen trivial. Genau dies ist aber erforderlich, wenn Schwachstellen bestehender Modelle entfernt werden sollen. Die Liegeplatzplanung beeinflusst die Containerbrückenplanung, weil sich die Brücken535 zum geplanten Zeitpunkt an dem geplanten Ort und in der richtigen Anzahl befinden müssen, um das Schiff so schnell wie möglich abzufertigen. Genau umgekehrt wirkt die Containerbrückenplanung auf den Liegeplatzplan, weil erst hier die tatsächlich benötigte Zeit für die Bearbeitung der Schiffe determiniert wird. Weicht die Bearbeitungszeit von der in der Liegeplatzplanung angenommenen Größe ab, dann basiert diese Planung auf einer falschen Grundlage.
532
Vgl. MEISEL, F.; BIERWIRTH, C. (2005).
533
Vgl. Kapitel 2.3.3.5.
534
Vgl. PARK, Y.; KIM, K. H. (2003).
535
Verkürzt wird teilweise von einer Brücke statt von Containerbrücken gesprochen.
138 Im Fall sequenzieller Koordination, wie von ZHANG
Planung in Container-Terminals ET AL.
aufgezeigt, findet dieser Ein-
fluss keine Berücksichtigung, weil kein Rücklauf der Informationen vorgesehen ist. Es existieren weitere Interdependenzen im CT. In Kapitel 3.2.2.1 wurde das Modell zur Liegeplatzplanung von MOORTHY und CHUNG-PIAW angesprochen, das einen Bezug zur Yardplanung herstellt.536 Die Operationszeit der Containerschiffe ist nicht allein abhängig von der Anzahl der Containerbrücken, die an den Schiffen operieren, sondern auch von der Entfernung, die die Yard-Transporter in das Containerlager zurücklegen müssen. Bei schlechter Organisation muss die Containerbrücke ihre Arbeit unterbrechen, weil kein Transportfahrzeug für den Container zur Verfügung steht. Wartezeiten an den Containerbrücken behindern den Prozessablauf und wirken auf die in der Liegeplatzplanung eingesetzten Operationszeiten. Während die Wartezeit eine Qualität der Leistung des Terminals beschreibt, handelt es sich bei der Distanz, die die Transporter zurücklegen müssen, um eine Kennzahl, die auf die Kosten des Terminals wirkt. BIETHAHN, MEIER und KLETTNER führen im Rahmen der Analyse von Interdependenzen zwischen Entscheidungsproblemen von CTs an, dass der Terminal einen Prozess beschleunigen kann, indem Container auf den kurzfristig günstigsten Positionen in dem Yard gelagert werden.537 Im Anschluss daran werden jedoch aufwändige Reorganisationsmaßnahmen notwendig. BAP und SLP beeinflussen sich gegenseitig, weil sich gemeinsam aus den Ergebnissen ihrer Planung die Transportdistanz ergibt, die auf die Operationszeit wirkt. Wie auch für den Zusammenhang zwischen BAP und CSP findet diese Interdependenz in einem sequenziellen Modell keine Berücksichtigung. Weiterhin sind wechselseitige Abhängigkeiten zwischen VDP und CSP sowie VDP und SLP zu nennen. Zusammen mit der Positionierung der Container im Yard bilden die Entscheidungen der Liegeplatz- und Containerbrückenplanung die Datengrundlage für die Transportplanung.
536
Vgl. MOORTY, R.; CHUNG-PIAW, T. (2006).
537
Vgl. BIETHAHN, J.; MEIER, L.; KLETTNER, N. (2006), S. 148- 151.
Planung in Container-Terminals
139
Mit diesen Ergebnissen werden die Start- und Zielpunkte der Containertransporte festgelegt.538 Das Crane Scheduling Problem determiniert, wann und wo eine Containerbrücke eingesetzt wird. Daraus ergibt sich der konkrete Bedarf für den Containertransport und beeinflusst so die Transportplanung. Für die Bearbeitung einer Bay werden in der Containerbrückenplanung konstante Zeiten angenommen. Konkret werden diese jedoch von der Bearbeitungszeit der Transporter determiniert. Dieser Zusammenhang wird von BÖSE ET AL. im Rahmen der Transportplanung untersucht.539 Die Transportplanung bestimmt die Zeitpunkte, wann ein Container im Yard zu platzieren bzw. aus diesem zu holen ist. Somit besteht auch zwischen CSP und SLP eine wechselseitige Abhängigkeit, die in sequenziellen Modellen keine Berücksichtigung findet. Nachdem in Kapitel 2.1.3 systemtheoretische Grundlagen gelegt wurden und in Kapitel 3.2 Modelle der CT-Planung im Detail vorgestellt werden konnten, kann nun in diesem Abschnitt darauf aufbauend die für diese Arbeit relevante Definition eines Planungssystems gegeben werden. Unter einem Planungssystem ist ein strukturiertes Gefüge einzelner Elemente der Planung zu verstehen. Das Planungssystem umfasst das Zielsystem und das Restriktionssystem sowie Methoden, um das Entscheidungsmodell zu lösen. Mit Hilfe eines Instanzsystems werden die Instanz, bzw. die Instanzen der konkreten Problemstellung bereitgehalten. Das folgende Kapitel greift die vorgestellten Ausführungen auf. Es werden zunächst relevante Trends beleuchtet, die zukünftige Anforderungen für den Terminal kennzeichnen. Es ist dann ein Blick auf die Modellbildung zu werfen, um die Leistungen und auch die Grenzen bestehender Ansätze herausstellen zu können. Dieser Untersuchung folgt die Darstellung resultierender Implikationen, die Ansatzpunkte für die Gestaltung eines Modells aufzeigen soll, das die Stärken bestehender Modelle aufgreifen kann und mit dem sich Schwachstellen reduzieren lassen.
538
Dem VDP kommt deshalb eine integrierende Funktion im übergreifenden Modell zu.
539
Vgl. BÖSE, J. et al. (2000).
Leistung und Grenzen bestehender CT-Modelle
141
4 Leistung und Grenzen bestehender CT-Modelle Nachdem in den vorangegangenen beiden Kapiteln die Grundlagen logistischer Systeme und Prozesse umfassend vorgestellt und im Rahmen der Einordnung von Container Terminals der aktuelle Stand der Entwicklung in diesem Forschungsbereich aufgezeigt werden konnte, sollen in diesem Kapitel die damit verbundenen Grenzen bestehender Ansätze herausgearbeitet werden. Dafür ist es erforderlich, den Blick auf die wesentlichen Trends zu werfen, um zukünftigen Anforderungen mit den richtigen Methoden begegnen zu können. Im Anschluss daran sollen die besondere Leistung und die Grenzen bestehender Modelle herausgearbeitet sowie resultierende Implikationen vorgestellt werden. So wird ein Weg für die sich anschließenden Kapitel gelegt, in denen die notwendigen Ansätze entwickelt, implementiert (Kapitel 5) und getestet werden (Kapitel 6).
4.1 Zusammenfassung wesentlicher Trends Bereits in den Kapiteln 1 und 3 wurden das starke Wachstum des containerisierten Verkehrs und dessen Bedeutung für die gesamte Volkswirtschaft angesprochen. Politik und Wirtschaft sind gemeinsam für die Sicherstellung der Standortqualität verantwortlich. In diesem Abschnitt sollen Trends zusammengefasst werden, die die Grundlage für diese Arbeit bilden. Das stark anhaltende Nachfragewachstum nach logistischen Leistungen zwingt die CTBetreiber zur Verbesserung ihrer Prozesse, um die wachsende Nachfrage befriedigen und um zusätzliche Gewinne realisieren zu können. Es wurde bereits festgestellt, dass zukünftige Verbesserungen maßgeblich von der Optimierung der Prozesse abhängig sind, weil sich die Kapazitäten des Terminals nur begrenzt erweitern lassen.540 Auch die zunehmende Konkurrenz zwischen den CT-Betreiberunternehmen fördert das Streben nach einer Optimierung der Prozesse im Hafen.541
540
Dieses Problem führt auch zu höheren Anforderungen bzgl. der Lagerung der Container.
541
Vgl. SAANEN, Y. A. (2004), S. 6- 15 und STEENKEN, D.; VOß, S.; STAHLBOCK, R. (2004), S. 5.
142
Leistung und Grenzen bestehender CT-Modelle
Insbesondere der Einsatz und die Weiterentwicklung von Informationssystemen haben die Durchsetzung neuer Technologien erst ermöglicht. Änderungen am Status eines Containers können innerhalb kurzer Zeit zwischen den Parteien kommuniziert werden. Als Beispiel sind die Informationen über den Stauplan eines Schiffes zu nennen, die für die effiziente Gestaltung der Operationen am CT von wesentlicher Bedeutung sind.542 Auch die für diese Arbeit einzusetzenden Optimierungsmethoden umfassen insbesondere rechenintensive Verfahren, die ohne den Einsatz moderner Informationssysteme nicht zum Einsatz kommen könnten. SAANEN behandelt insbesondere die Fragestellung zur Gestaltung (voll-)automatisierter Terminals mit dem Ziel, weiteres Potential für die Prozessoptimierung zu eröffnen. Er führt an, dass bisher lediglich in Rotterdam und Hamburg wesentliche Schritte hinsichtlich der Automatisierung durchgeführt worden sind, obwohl hohe Personalkosten auch in anderen Städten und Ländern Druck auf die CT-Betreiber ausüben.543 Mit Blick auf den in Kapitel 3.2 gegebenen Überblick zur Optimierung von CT-Prozessen werden zwei unterschiedliche Forschungsstränge deutlich, die in der wissenschaftlichen Literatur diskutiert werden: 1. Die Ausgestaltung und Entwicklung isolierter Modelle im Zusammenhang mit der Suche nach immer besseren und schnelleren Verfahren. 2. Die Forschung nach koordinierenden Ansätzen, nach der der CT als Gesamtprozess zu begreifen und auch als solcher zu optimieren ist. Obwohl die Notwendigkeit koordinierender Strukturen klar erkannt ist, befindet sich der Forschungsschwerpunkt noch immer in der Entwicklung isolierter Modelle.544
542
Die (elektronische) Kommunikation basiert auf internationalen Standards, z.B. EDIFACT. Vgl. STEEND.; VOß, S.; STAHLBOCK, R. (2004), S. 10f.
KEN, 543
Vgl. SAANEN, Y. A. (2004). Im Vergleich dazu ist der Schwerpunkt dieser Arbeit nicht auf die Automatisierung von Terminals gerichtet, sondern auf das Potential, das sich aus der Koordination interdependenter Planungssysteme eröffnet.
544
Diese Aussage verdeutlicht sich mit Hilfe des in Kapitel 3.2 gegebenen Literaturüberblicks; ein Blick auf Quellen, die die wissenschaftliche Literatur in diesem Bereich zusammenfassen, bestätigt ebenfalls diese Aussage, vgl. hierzu STEENKEN, D.; VOß, S.; STAHLBOCK, R. (2004) und die aktualisierte Fassung, insb. mit Blick auf die Aussagen zur Modellintegration in STAHLBOCK, R.; VOß, S. (2007), S. 33- 40. Allgemein für die Logistik bestätigt PFOHL die Notwendigkeit einer koordinierenden Struktur für vorrangig isoliert betrachtete Teilprobleme. Vgl. PFOHL, H. C. (2004), S. 16ff sowie Kapitel 2.1.2.
Leistung und Grenzen bestehender CT-Modelle
143
Diese Arbeit findet sich im zweiten Forschungsstrang wieder. Gerade aktuelle wissenschaftliche Literatur erkennt und formuliert die Notwendigkeit einer koordinierenden Struktur. Ansätze hierfür unterscheiden sich jedoch noch immer maßgeblich. STAHLBOCK und STEENKEN zeigen im Rahmen ihres Überblicks die Entwicklung integrierender und koordinierender Modelle auf. Dabei finden sich hier vor allem drei unterschiedliche Ansätze wieder: 1. Analytische Methoden 2. Simulationsbasierte Methoden 3. (Multi-)Agentenbasierte Methoden In dieser Arbeit wird das Potential agentenbasierter Methoden untersucht. Der Vergleich mit verfügbaren Ansätzen zeigt dabei Unterschiede mit dem in dieser Arbeit entwickelten Modell.545
4.2 Leistung und Grenzen isolierter Modelle In diesem Abschnitt sollen die in dem vorangegangenen Kapitel vorgestellten Modelle übergreifend untersucht werden. Es ist auf die Leistung bestehender Modelle einzugehen, und gleichzeitig sind Grenzen dieser Modelle aufzuzeigen, um so einen Ansatz entwickeln zu können, der existierende Stärken unterstreicht und Schwächen zu mindern in der Lage ist. Hierfür ist zunächst der Planungsprozess zu untersuchen, wie er derzeit in der Praxis durchlaufen wird.546 Die folgenden Zitate belegen die bislang in der Praxis dominierende Vorgehensweise für die Behandlung von CT-Entscheidungen. Bereits 1989 zeigt DAGANZO auf:
545 546
Vgl. insbesondere die in Kapitel 3.2.6 vorgestellten multiagentenbasierten Modelle.
Es ist darauf hinzuweisen, dass hier nur der abstrakte Rahmen vorgestellt werden kann, wie er in der Literatur zu finden ist. Die konkreten Abläufe innerhalb eines Terminals können von diesem Prozess abweichen, vor allem weil menschliche Experten die Entwicklung konsistenter Pläne überwachen.
144
Leistung und Grenzen bestehender CT-Modelle „These [CSP-] decisions are based on the cumulative experience of the decision maker, complemented perhaps with various rules of thumb that prevail in the industry.”547
Unter Berücksichtigung der Vielzahl aufgezeigter Modelle und ihrer Entwicklungen im vorangegangenen Kapitel könnte vermutet werden, dass dieses Vorgehen mit dem Einsatz moderner IT-Systeme heute keine beherrschende Stellung mehr einnimmt. Das Gegenteil deuten KIM und MOON in einem Artikel von 2003 an. Die Autoren führen für das Berth Allocation Problem an: „Port managers usually schedule the usage of berths by an intuitive trial-and-error method supported by a schedule board or a graphic-user-interface in a computer system.”548 Mit der Aussage zeigen die Autoren, dass menschliche Entscheidungsträger automatisierten Entscheidungen von IT-Systemen noch immer skeptisch gegenüberstehen. IT-Systeme kommen lediglich unterstützend, nicht aber zur Entscheidung zum Einsatz. Weiterhin beherrschen intuitive Methoden die Entscheidungsfindung. Die Begründung dafür liegt in der Komplexität der Entscheidungen. In den vorangegangenen Kapiteln konnte gezeigt werden, dass die Modellbildung keinesfalls trivial ist und noch immer nicht alle relevanten Aspekte abgebildet werden können. Um überhaupt Ansatzpunkte für die Strukturierung zu finden, liegt der bisherige Forschungsschwerpunkt auf isolierten Modellen. LIU, WAN und WANG zeigen, wie diese Teilprobleme in der Praxis zusammengesetzt werden: „Such hard problems motivate practitioners to formulate the problems hierarchically and solve them sequentially”.549 Die Dekomposition stellt ein Instrument zur Komplexitätsreduktion dar, die sich hierarchisch gestalten lässt.550 Die hierarchische Planung stellt einen Kompromiss aus zentraler
547
DAGANZO, C. F. (1989), S. 160.
548
KIM, K. H.; MOON, K. C. (2003), S. 541.
549
LIU, J.; WAN, Y.; WANG, L. (2006), S. 60. Es ist dabei anzumerken, dass dieser Prozess von einem menschlichen Experten überwacht wird, der bei einem Problem korrigierend eingreifen kann.
550
Vgl. SAANEN, Y. A. (2004), S. 83f.
Leistung und Grenzen bestehender CT-Modelle
145
und dezentraler Planungsphilosophie dar. Von BLOECH ET AL. wird angegeben, dass in der Praxis eine weitgehend rückkopplungsfreie Sukzessivplanung vorherrscht.551 Diese Aussage bestätigt sich mit der Darstellung von LIU, WAN und WANG für die konkrete Planung von CT-Prozessen.552 Die Modellbildung für Teilbereiche durch Abstraktion und Vereinfachung realer Merkmale und Zusammenhänge einer Planungssituation führt jedoch vorsätzlich zu „Fehlern“.553 Wie im Rahmen von Kapitel 2.3.3 aufgezeigt werden konnte, umfasst die Sukzessivplanung Nachteile, die die Qualität der Lösung insgesamt beeinflussen.554 Aus diesem Grund erscheint es sinnvoll, neben einer rein sequenziellen Synthese der Teilprobleme, auch andere Koordinationsinstrumente für diese Problemstellung zu untersuchen. Auch SAANEN bestätigt, dass die nicht ganzheitliche Gestaltung von CT-Prozessen die Existenz von Systemkomponenten hervorruft, die nicht zusammenpassen und so suboptimale Lösungen stärken.555 Unter Berücksichtigung der Phasen der Planung nach BEA, FRIEDL und SCHWEITZER (Kriterien 1-5), ergänzt durch die von MÜLLER-MERBACH im Rahmen der schematischen Vorgehensweise für die Planung mit mathematischen Methoden genannten Kriterien (Kriterien 6-8)556, sollen die in Kapitel 3.2 vorgestellten und implementierten Entscheidungsmodelle untersucht werden.557 Hinzu kommt das Kriterium DATEN, das beschreibt, auf welcher Datengrundlage die Problemstellung getestet wurde.
551
Vgl. BLOECH, J. et al. (2008), S. 119.
552
Vgl. Kapitel 4.2. Diese Aussage wird weiterhin von VACCA, I.; BIERLAIRE, M.; SALANI, M. (2007), S. 18 für das Management von CT-Prozessen unterstützt.
553
Vgl. ADAM, D. et al. (2004), S. 6. Konkret zeigt die Behandlung einheitlicher Container ein Beispiel für die Vereinfachung von Merkmalen auf. Die Vernachlässigung von Interdependenzen zeigt die Vereinfachung von Zusammenhängen in einer Planungssituation. Ausführlich werden diese Punkte in Kapitel 3.2 diskutiert. Ein allgemeines Beispiel stellt die funktionale Zerlegung des Unternehmens in die Teilprobleme Beschaffungs-, Produktions- und Absatzplanung u.a. dar, die für sich isoliert optimiert werden.
554
Die Sukzessivplanung wird in dieser Arbeit synonym mit sequenzieller Planung verwendet, weil das sukzessive Durchlaufen mehrerer Planungssysteme eine Sequenz darstellt.
555
Vgl. SAANEN, Y. A. (2004), S. 89.
556
Vgl. Kapitel 2.2.1.
557
Stellvertretend für ihre Problemstellung werden die implementierten Modelle untersucht: Für das Berth Allocation Problem, vgl. Kapitel 3.2.2.2, für das Crane Scheduling Problem, vgl. Kapitel 3.2.3.2, für das Storage Location Problem, vgl. Kapitel 3.2.4.2 sowie für das Vehicle Dispatching Problem, vgl. Kapitel 3.2.5.2.
146
Leistung und Grenzen bestehender CT-Modelle
Die folgende Tabelle deckt die besondere Leistung der Modelle, aber auch deren Grenzen im Rahmen ihrer Entwicklung auf.
1) Problemfeststellung 2) Zielbildung 3) Alternativensuche 4) Prognose 5) Bewertung und
BAP
CSP
SLP
VDP
ja
ja
ja
ja
eingeschränkt
eingeschränkt
ja
ja
ja
ja
ja
ja
entfällt
entfällt
entfällt
entfällt
ja
ja
ja
ja
nein
nein
nein
nein
ja
ja
nein
ja
nein
nein
eingeschränkt
nein
realistisch
realistisch
zufällig
zufällig
generiert
generiert
(Hong Kong)
(ohne Angabe)
Entscheidung 6) Berücksichtigung von Beziehungen im Modellierungsprozess 7) Konstruktion einer Lösungsmethode 8) Übertragung und Kontrolle
9) Daten
Tabelle 4-1: Untersuchung bestehender Modelle
In allen vier untersuchten Bereichen wurde das jeweilige Problem herausgearbeitet und als mathematisches Programm exakt formuliert. Die Zielbildung wird für BAP und CSP als eingeschränkt beurteilt, weil die gezeigten Ansätze Schwächen aufzeigen.558 Alternativen werden analysiert, und es können in allen Systemen eine Bewertung und Entscheidung
558
Vgl. hierzu die in den Kapiteln 3.2.2.3 und 3.2.3.3 aufgeführten Kritikpunkte zu den Modellen.
Leistung und Grenzen bestehender CT-Modelle
147
vorgenommen werden.559 Die Prognose entfällt, weil in keinem der betrachteten Probleme Stochastizitäten berücksichtigt werden.560 Im Rahmen der Modellierung werden Beziehungen zu anderen Modellen lediglich angesprochen, finden jedoch keine Berücksichtigung. Die daran folgende Modellkonstruktion basiert demnach auf dieser vereinfachten Grundlage. Für jede der eingesetzten Problemstellungen können Lösungsmethoden in der Literatur gefunden werden.561 Die nachfolgenden Schritte der Übertragung der Ergebnisse und deren Kontrolle sind zumindest in den untersuchten Artikeln und der nachfolgenden Literatur nicht dokumentiert. Von allen Autoren werden vor Übertragung weitere notwendige Untersuchungen angekündigt. Allein ZHANG
ET AL.
geben an, dass, aufbauend auf den gezeigten Ergebnissen dieses Modells,
nun die Betrachtung der Zuordnung der Container innerhalb des Blocks erfolgen soll.562 Die untersuchte Datengrundlage zeigt, dass die untersuchten Modelle bislang vorrangig in theoretischer Umgebung zum Einsatz kommen. Der Begriff PLANUNGSPROZESS ist für diese Arbeit von besonderer Bedeutung. Dieser Prozess lässt sich in die in Kapitel 2.2.1 angesprochenen und in Tabelle 4-1 untersuchten Phasen nach BEA, FRIEDL und SCHWEITZER zerlegen. Zugleich bietet es sich an, im Rahmen der Planung von CT-Prozessen von einem Planungsprozess zu sprechen. Dabei sind die isoliert vorgestellten Planungssysteme für die
559
Vgl. Kapitel 2.2.1 und die Stellung der Planung im Führungsprozess des Unternehmens, BEA, F. X.; FRIEDL, B.; SCHWEITZER, M. (2005), S. 51.
560
Aus dieser Perspektive zeigt sich, dass die Nicht-Berücksichtigung von Stochastizitäten für alle Modelle als Instrument zur Komplexitätsreduktion eingesetzt wird. Die Vernachlässigung stellt eine Annahme dar, die als Kritikpunkt in allen vier untersuchten Problemstellungen zu nennen ist. Vgl. die entsprechenden Abschnitte in Kapitel 3.2.
561
Von ZHANG ET AL. wird keine Lösungsmethode für das SLP entwickelt. Die Autoren setzen zur Lösung das kommerzielle Tool CPLEX ein, vgl. ZHANG, C. et al. (2003), S. 898ff und auch ILOG (2007). Für die Zuordnung der Container im ersten Teil des SLP lässt sich von MURTY ET AL. eine Methode finden, vgl. MURTY, K. G. et al. (2005), S. 321- 323. Zur Lösung des klassischen Transportproblems sind in der Literatur hinreichend Methoden bekannt.
562
Aus diesem Grund ist das Kriterium ÜBERTRAGUNG in der Tabelle als eingeschränkt gekennzeichnet.
148
Leistung und Grenzen bestehender CT-Modelle
Konstruktion eines gültigen Planes, der alle Tätigkeiten der am CT beteiligten Entities umfasst, in einem Prozess zu durchlaufen.563 Um den Begriff nicht mehrdeutig zu belegen, sind deshalb beide Perspektiven näher zu betrachten. Die zweite prozessorientierte Definition des Planungsprozesses behandelt lediglich die Alternativensuche als Phase der Planung in der umfassenden Perspektive nach BEA, FRIEDL und SCHWEITZER. Implizit wird für diese Definition unterstellt, dass die übergreifende Problemstellung bekannt und ein übergreifendes Zielsystem existent ist. Die Phasen des Planungsprozesses in der Betrachtung von BEA, FRIEDL und SCHWEITZER finden sowohl im Rahmen der Planung der isoliert betrachteten Subsysteme Anwendung,564 als auch im Rahmen der Synthese dieser Subsysteme zu einer übergreifenden Lösung. Beide Darstellungen des Planungsprozesses stellen keinen Widerspruch dar.565 Im Folgenden ist unter dem Planungsprozess der Prozess der Wiederherstellung der Teilprobleme zu einer Gesamtlösung zu betrachten, dem implizit die Existenz notwendiger Elemente der Planung nach der umfassenden Definition unterstellt wird. Das CT-Management muss u.a. diesen Planungsprozess definieren und überwachen. Für die isoliert optimierten Teilprobleme muss gewährleistet werden, dass im Rahmen ihrer Synthese ein gültiger und möglichst gut abgestimmter Gesamtplan für alle am CT ablaufenden logistischen Prozesse entstehen kann. Bislang kann für das (übergreifende) Management von CT-Prozessen jedoch keinesfalls von einer gut strukturierten Problemstellung gesprochen werden. Aus diesem Grund sollen
563
Diese Definition eines Planungsprozesses orientiert sich an der Definition für einen Geschäftsprozess nach HANSEN und NEUMANN: „Ein Geschäftsprozess besteht aus einer Menge miteinander verknüpfter Aktivitäten, welche in einer bestimmten Reihenfolge ausgeführt werden, um ein festgelegtes Ziel zu erreichen.“ Die verschiedenen Aktivitäten können sequenziell und/oder parallel gestartet und ausgeführt werden. Vgl. HANSEN, H. R.; NEUMANN, G. (2005), S. 233. Die Planung von CT-Prozessen kann als Menge miteinander verknüpfter Planungssysteme begriffen werden, die sequenziell zu durchlaufen sind. Die angegebene Definition soll deshalb als prozessorientiert bezeichnet werden.
564 565
In Tabelle 4-1 werden diese Phasen für die isolierten Teilprobleme untersucht.
Die beiden Definitionen des Planungsprozesses resultieren aus unterschiedlichen Ansatzpunkten: BEA, FRIEDL und SCHWEITZER identifizieren die Elemente der Planung (hier: Zielbildung, Problemfeststellung, …), während die zweite Definition bei den Elementen (hier: Planungssysteme [BAP, CSP, SLP und VDP]) des untersuchten Prozesses ansetzt.
Leistung und Grenzen bestehender CT-Modelle die in Kapitel 2.3.1 von ADAM
ET AL.
149
genannten Kriterien herangezogen werden, um zu
beurteilen, ob wenigstens die Teilprobleme strukturiert vorliegen. BAP
CSP
SLP
VDP
Wirkungsdefekte
behoben
behoben
behoben
behoben
Bewertungsdefekte
behoben
behoben
behoben
behoben
Zielsetzungsdefekte
behoben
behoben
behoben
behoben
Lösungsdefekte
behoben
behoben
behoben
behoben
Tabelle 4-2: Defektanalyse in CT-Modellen
Für jedes der untersuchten Teilprobleme konnte jede der untersuchten Defektarten behoben werden. Es kann deshalb - für den isolierten Fall - von einer gut strukturierten Problemstellung gesprochen werden. Von ADAM wird festgestellt, dass Planung in strukturierten Problemen zu einer reinen Rechenaufgabe degeneriert.566 Die Vielzahl unterschiedlich formulierter Modelle deutet aber auf strukturdefekte Situationen hin.567 Der Auswahl der richtigen Problemstellung für den Planungsprozess kommt deshalb eine wichtige Rolle zu.568 Es ist somit festzuhalten, dass die wissenschaftliche Leistung der untersuchten CTEntscheidungsprobleme bislang vor allem in der Strukturierung strukturdefekter Probleme liegt.569 Zudem konnten für diese Modelle gute Lösungsmethoden vorgestellt werden. PFOHL stellt allgemein für die Logistik heraus, dass für isoliert betrachtete Teilprobleme gute Lösungsverfahren existieren und nennt als Beispiel u.a. die Touren- und auch die Lagerplanung.570 Diese Aussage kann nun für CT-spezifische Teilprobleme bestätigt werden. Weiterhin hebt PFOHL allgemein für die Logistik hervor, dass der Koordinationsfunktion
566
Vgl. ADAM, D. (1996), S. 9.
567
Vgl. Kapitel 2.3.1. Dies wird deutlich, weil unterschiedliche Planer zu unterschiedlichen Ergebnissen im Strukturierungsprozess kommen. Die Literaturuntersuchung zeigt aber, dass die Modelle der einzelnen Teilbereiche und insbesondere die verwendeten Modelle bereits gut entwickelt sind, vgl. Kapitel 3.2.
568
Es ist eine wesentliche Aufgabe des CT-Managements zu klären, welches die richtigen Aufgaben in der Prozessgestaltung sind.
569
Diese Strukturierung gehört zu den schwierigsten Problemen des OR, vgl. hierzu die Ausführungen in Kapitel 2.3.1.
570
Vgl. PFOHL, H. C. (2004), S. 16ff sowie die Ausführungen hierzu in Kapitel 2.1.2.
150
Leistung und Grenzen bestehender CT-Modelle
eine wachsende Bedeutung zukommt. Konkret nennen STEENKEN, VOß und STAHLBOCK u.a. diese Anforderung auch für den CT-Bereich.571 Genau hier zeigen die vorgestellten Modelle bislang jedoch eine Schwachstelle. Im Wesentlichen werden isolierte Entscheidungsprobleme des Terminals behandelt und Beziehungen zu anderen Bereichen vernachlässigt. Zur Planung gehört die Berücksichtigung komplexer Zusammenhänge im Unternehmen. Nach ADAM muss die Planung alle Bereiche des Unternehmens und deren Beziehungen zueinander abbilden und koordinieren.572 MEIER und FISCHER weisen für den konkreten Fall eines fiktiven CT nach, dass die sequenzielle Koordination unerwünschte Effekte im Gesamtergebnis des Terminals zeigen kann.573 Aus diesem Grund ist es erforderlich, Methoden zu untersuchen, mit denen es möglich ist, die Teilbereiche des Terminals zu koordinieren. Nach der Diskussion der Leistung und der Grenzen bestehender CT-Modelle sollen in dem folgenden Abschnitt die Implikationen für die Gestaltung eines umfassenden Modells erarbeitet werden, mit denen es möglich ist, bestehende Schwächen zu mindern und Stärken bestehender Ansätze auszubilden.
4.3 Implikationen In der Literatur wird gehäuft der Bedarf an intelligenten Methoden zur Prozesskoordination angesprochen.574 Kenntnisse über die Strukturen zu lösender Probleme lassen sich bei der Entwicklung intelligenter Methoden nutzen. Die steigende Forschung nach geeigneten Methoden und Modellen in der (CT-)Logistik hat zu einem besseren Verständnis der Probleme und ihrer Eigenschaften geführt. Auch die wesentlichen Beziehungen der Problemstellungen untereinander sowie die zu verfolgenden Zielsetzungen und ihre Konflikte sind bekannt.575
571
Vgl. STEENKEN, D.; VOß, S.; STAHLBOCK, R. (2004), S. 36. Diese Forderung wird in dem später aktualisierten Überblick nochmals unterstrichen, vgl. STAHLBOCK, R.; VOß, S. (2007).
572
Vgl. ADAM, D. (1996), S. 3.
573
Vgl. MEIER, L.; FISCHER, H. (2006).
574
Vgl. STAHLBOCK, R.; VOß, S. (2007), S. 40- 42. Zudem PFOHL, H. C. (2004), S. 16ff, SAANEN, Y. A. (2004), S. 80f und auch HENESEY, L. (2004), S. 78ff.
575
Vgl. hierzu die Ausführungen in Kapitel 4.2.
Leistung und Grenzen bestehender CT-Modelle
151
Auf diesem Stand der Forschung können neue und intelligente Methoden ansetzen. Intelligente Methoden müssen in der Lage sein, robuste Lösungen zu generieren, die einer Veränderung der Umwelt standhalten. Umwelteinflüsse können beispielsweise der Ausfall einer Containerbrücke, aber auch veränderte gesetzliche Rahmenbedingungen darstellen, auf die der CT flexibel reagieren muss.576 Jede Planungsebene kann von diesen Einflüssen betroffen sein. Eine zentrale Schwäche, die im vorangegangenen Abschnitt identifiziert werden konnte, ist die Vernachlässigung von Beziehungen zwischen den isolierten Modellen. SAANEN führt an, dass insbesondere für (hoch-)effiziente Logistikprozesse die Kooperation von Hard- und Software des Terminals optimal abgestimmt sein muss. Diese Kooperation muss in einer hoch dynamischen und nicht bzw. schwer prognostizierbaren Umgebung erfolgen.577 Mit Kapitel 3.2 konnte zudem erheblicher Koordinationsbedarf für die isoliert betrachteten Planungssysteme des CT nachgewiesen werden. In genau dieser Domäne scheint der Einsatz multiagentenbasierter Systeme sehr gut geeignet. Das Potential für den Einsatz von MAS in der Transportlogistik wird in der Literatur als hoch eingestuft. Dennoch existieren bislang nur wenige einsatzfähige Anwendungen.578 Multiagentensysteme bieten die Möglichkeit, mehrere sich gegenseitig beeinflussende und autonom agierende Systeme in einer gemeinsamen Umgebung zu untersuchen. Insbesondere ist es für diese Systeme nicht erforderlich, bereits im Rahmen ihrer Entwicklung auf andere Systeme einzugehen. Die isoliert entworfenen und gut strukturierten Entscheidungsmodelle der Literatur lassen sich demnach als Teil des Planungssystems eines Agenten in die Umgebung des Multiagentensystems einsetzen. Die in einem Planungssystem erzielten Ergebnisse beeinflussen die in der Umgebung situierten Agenten. Die Organisationsstruktur des CT kann erhalten
576
Beispielsweise haben die Anschläge vom 11. September 2001 zu einer massiven Veränderung der Sicherheitspolitik auf Seiten der USA geführt.
577
Vgl. SAANEN, Y. A. (2004), S. 21ff.
578
Vgl. DAVIDSSON, P. et al. (2005), S. 5ff und auch die Kriterien für den Einsatz von MAS in WOOLDRIDM. J. (2005), S. 225f. Auch konkret für integrierte Ansätze in der CT-Logistik wurden mit den Ansätzen von HENESEY und REBOLLO ET AL. gute Ergebnisse erzielt, vgl. Kapitel 3.2.6. Diese Ansicht wird auch von STAHLBOCK und VOß geteilt. Vgl. STAHLBOCK, R.; VOß, S. (2007), S. 39f. GE,
152
Leistung und Grenzen bestehender CT-Modelle
bleiben und in ihrer bestehenden Form auf das Modell übertragen werden. Die Interpretation der Ergebnisse wird dadurch erleichtert. Vorteil ist, dass sich mit den vorhandenen Modellen und Methoden weiterarbeiten lässt. Diese müssen nicht verworfen, bzw. aufgrund mangelnder Schnittstellen umständlich restrukturiert werden. Zur Lösung von CT-Problemstellungen sind Methoden bekannt, mit denen sich gute bzw. sogar optimale Lösungen erzielen lassen.579 Für die Kooperation von Agenten in einem Multiagentensystem ist die BenevolenceAnnahme nicht erforderlich.580 Die unabhängig voneinander entworfenen Agenten können durchaus unterschiedliche und konfliktäre Ziele verfolgen.581 Es sind damit alle Voraussetzungen für ein Modell zur Koordination interdependenter Planungssysteme in der CT-Logistik gegeben. Im Folgenden ist deshalb aufzuzeigen, welche Elemente die Gestaltung eines Koordinationsmodells umfassen muss. Ein Koordinationsmodell beschreibt in dieser Arbeit den Ablauf des Planungsprozesses in seiner prozessorientierten Definition. Die Definition des Ablaufs beeinflusst deshalb maßgeblich den Entscheidungsbaum im Rahmen der Alternativensuche. In Abhängigkeit von dem Koordinationsmodell könnten bereits mit der Aufstellung eines Entscheidungsbaumes gültige Alternativen von der Lösungsmenge ausgeschlossen worden sein. Im Fall einer sequenziellen Synthese der Ergebnisse der Planungssysteme ist der Ausschluss von Alternativen durchaus beabsichtigt, um die Komplexität der Synthese zu reduzieren.582 Aufgrund der Unterschiede bzgl. Komplexität und Struktur eines Lösungsraumes sind Methoden unterschiedlich für den Einsatz in bestimmten Problemstellungen geeignet.583 Diese
579
Vgl. Kapitel 3.2.
580
Vgl. Kapitel 2.4.2.
581
Dies ist insbesondere aufgrund der unabhängig und von verschiedenen Autoren entworfenen Modelle der Fall.
582 583
Vgl. hierzu die Aussage von LIU, WAN und WANG in Kapitel 4.2.
Beispielsweise zeigt sich, dass die Simplexmethode zur Lösung des Transportproblems zwar geeignet ist, aufgrund der speziellen Problemstruktur existieren aber Methoden, die das Problem deutlich schneller und ebenfalls optimal lösen können.
Leistung und Grenzen bestehender CT-Modelle
153
Suche nach geeigneten Methoden für Probleme der CT-Logistik ist ein Schwerpunkt bisheriger Forschung in diesem Bereich, wie die Darstellungen in Kapitel 3.2 belegen. Intelligente Methoden setzen bei der Analyse (und gezielten Filterung) hochkomplexer Entscheidungsbäume an, um eine gute Lösung zu finden.584 Im Rahmen des Multiagentensystems lässt sich das Verhalten unterschiedlicher Koordinationsmodelle simulieren. Die Ergebnisse dieser Simulation erlauben Rückschlüsse auf die Gestaltung des Planungsprozesses in Container-Terminals. Die folgende Tabelle zeigt die Planungsebenen der mit diesem System durchführbaren Experimente auf. Experiment
Planungsebene Methoden
taktisch
Parameter
strategisch
Methoden
taktisch
Parameter
strategisch
Methoden
operativ
Parameter
strategisch
Methoden
operativ
Parameter
taktisch
BAP
SLP
CSP
VDP
Koordination interdependenter Planungssysteme
strategisch-taktisch
Tabelle 4-3: Experimente des MAS und Planungsebene
Die Tabelle zeigt, dass die als Agenten in das Multiagentensystem eingesetzten Planungssysteme auf unterschiedlichen Planungsebenen ansetzen. Während es sich bei der Planung von Liegeplätzen und der Planung von Lagerplätzen in dem Yard für die Containergruppen um taktische Problemstellungen handelt, stellen die Containerbrückenzuordnung und die Transportplanung operative Entscheidungsprobleme dar. Die Analyse von Parametern dieser Modelle spielt sich im Wesentlichen auf der strategischen Planungsebene ab: Die Veränderung der Kailänge, die Erweiterung oder veränderte
584
Vgl. Kapitel 2.4. Ein Beispiel stellt die Suche nach einem geeigneten Zug in dem Entscheidungsbaum eines Schachspiels dar.
154
Leistung und Grenzen bestehender CT-Modelle
Anordnung des Yards und die Variation der Containerbrückenanzahl greifen massiv in die Potentiale des CT ein. Lediglich Entscheidungen bzgl. der Anzahl der Transportfahrzeuge sind auf taktischer Ebene zu betrachten, weil sich diese Anzahl auch mittelfristig und - im Vergleich zu den vorangegangenen Entscheidungen - mit erheblich geringerem Aufwand verändern lässt. Die Vorgabe eines Koordinationsmodells definiert den taktischen Rahmen für die Entscheidungsfindung. Unter der Annahme, dass dieser Rahmen die Leistungsfähigkeit und damit die Potentiale des CT maßgeblich beeinflusst und dass sich die hier getroffenen organisatorischen Entscheidungen nicht ohne erheblichen Aufwand rückgängig machen lassen, kann diese Entscheidung auch auf strategischer Ebene getroffen werden. Mit Hilfe der multiagentenbasierten Simulation lässt sich das Verhalten unterschiedlicher Koordinationsmodelle für den CT-Prozess simulieren. Klassische Koordinationsmethoden der Betriebswirtschaftslehre werden unterstützt und lassen sich modellgestützt validieren. Dieser Ansatz entspricht den Anforderungen, die aus der Untersuchung wissenschaftlicher Probleme in diesem Bereich aufgezeigt werden konnten. Gleichwohl wird der Bedarf zur Koordination interdependenter Planungssysteme nicht nur speziell für den CT-Bereich aufgezeigt, sondern auch allgemein für die Logistik erkannt. Somit bietet es sich an, auch andere Problemstellungen mit Hilfe eines Multiagentensystems zu untersuchen. Die unabhängig voneinander entworfenen Systeme können in dem MAS auch weiterhin unabhängig voneinander und mit individuellem Zielsystem optimiert werden. Es lassen sich neue Methoden einsetzen, wenn bekannt ist, dass diese zu besseren Lösungen führen. Entscheidungsmodelle lassen sich ersetzen, wenn bekannt ist, dass sich eine bestimmte Problemstellung dadurch besser abbilden lässt. Selbst Agenten werden austauschbar, wenn die ihnen zugewiesene Aufgabe nicht mehr in den Rahmen der Organisationsstruktur des CT passt. Das MAS bildet einen Rahmen um die sonst isolierten Systeme, so dass sich die Entscheidungen der in dieser Umgebung situierten Agenten wechselseitig beeinflussen.
Leistung und Grenzen bestehender CT-Modelle
155
Zur Implementierung von Multiagentensystemen kann auf vielfältige Ansätze zurückgegriffen werden.585 Der Einsatz eines verfügbaren MAS-Frameworks bietet den Vorteil, dass die technischen Aufgaben bereits weitgehend gelöst sind. So ist es bspw. möglich, Agenten in Rechnernetzen zu verteilen und über standardisierte Schnittstellen kommunizieren zu lassen. Das folgende Kapitel greift diese Anforderungen auf und stellt vor, wie sich ein multiagentenbasiertes Modell zur Prozesskoordination in Container-Terminals entwickeln lässt.
585
Diese Ansätze werden im Rahmen der Implementierung eines Multiagentensystems mit JADE in Kapitel 5.2 vorgestellt.
Entwicklung eines multiagentenbasierten Modells zur CT-Prozesskoordination
157
5 Entwicklung eines multiagentenbasierten Modells zur CTProzesskoordination In diesem Kapitel sollen die in den vorangegangenen Kapiteln erarbeiteten Anforderungen in einem Modell abgebildet und mit Hilfe der Programmiersprache Java implementiert werden. Hierfür soll in Kapitel 5.1 das Container-Terminal Management Problem umfassend vorgestellt werden, bevor in Kapitel 5.2 auf die technische Realisierung der Problemstellung einzugehen ist. Der Einsatz des Modells erfolgt schließlich in Kapitel 6.
5.1 Das Container-Terminal Management Problem (CTMP) Um ein den aufgezeigten Anforderungen gerechtes Modell zu entwickeln, wurden aus der Vielzahl vorhandener isolierter Modelle diejenigen ausgewählt, die aufgrund ihrer Formulierung als besonders geeignet erscheinen und zudem die gefundenen Schnittstellen zu anderen Entscheidungsbereichen direkt enthalten. Im Folgenden wird ein Container-Terminal betrachtet, der Van Carrier für den Transport der Container einsetzt.
5.1.1 Modellbeschreibung und -architektur
Die Bezeichnung Container-Terminal Management Problem wird bereits von REBOLLO ET AL.
verwendet und bezeichnet dort, wie auch in dieser Arbeit, die komplexen Entschei-
dungsbereiche und deren Zusammenwirken im CT.586 Für den Begriff Softwarearchitektur führen HANSEN und NEUMANN an: Die Softwarearchitektur beschreibt die Struktur und die Interaktionsbeziehungen zwischen den verschiedenen Hauptkomponenten eines Informationssystems auf einem relativ grobgranularen („grobkörnigen“) Niveau. Die Softwarearchitektur bildet somit das Grobdesign eines Informationssystems.587 Die folgende Abbildung zeigt die Hauptkomponenten dieses Modells.
586
Vgl. REBOLLO, M. et al. (2000), S. 1.
587
HANSEN, H. R.; NEUMANN, G. (2005), S. 223.
158
Entwicklung eines multiagentenbasierten Modells zur CT-Prozesskoordination
CSP
BAP VDP
Agent wrappt Planungssystem vereinfachte sequentielle Koordination
SLP
Abbildung komplexer Zyklen
Abbildung 5-1: Komponenten des CTMP-Modells588
Das Ineinandergreifen von Bewegungs- und Lagerprozessen ist charakteristisch für Logistiksysteme, so dass sich dieses Zusammenspiel sehr gut als Netzwerk darstellen lässt.589 Das hier entwickelte Modell lässt sich als ein Logistiksystem begreifen, dessen Darstellung als Graph erfolgt. Ein Graph G besteht aus Knoten V und Kanten E. Jeder Knoten steht für ein Planungssystem, das von einem Agenten umhüllt wird. Kanten deuten auf eine Beziehung zwischen den Planungssystemen hin. In der vereinfachten Darstellung von ZHANG
ET AL.
werden
Kanten zur Reduktion der Komplexität aus dem Graphen entfernt. Aufgrund der Interdependenzen zwischen den Planungssystemen des Terminals erscheint diese starke Vereinfachung jedoch nicht angemessen. Das in Abbildung 5-1 dargestellte Modell berücksichtigt Beziehungen zwischen den Knoten, die in vorherigen Modellen keine oder nur unzureichende Beachtung gefunden haben.590 Je nachdem, über welche Knoten der Graph durchlaufen wird, sind den Agenten unterschiedliche Informationen bekannt, die für ihre Planung von Bedeutung sind. Das Durch-
588
Die in der Abbildung dargestellte, vereinfachte sequenzielle Koordination richtet sich nach der Struktur von ZHANG ET AL, vgl. hierzu Abbildung 3-4. Diese Abbildung des Informationsflusses ist fragwürdig, weil mit der Zuordnung von Containerbrücken (CSP) zunächst eine operative Fragestellung behandelt wird, bevor mit der Yardplanung (SLP) wieder eine taktische Problemstellung aufgegriffen wird. Weil sich CSP und SLP in dem Modell jedoch nicht direkt beeinflussen, ist die Reihenfolge ihrer Bearbeitung nicht von Bedeutung.
589
Vgl. PFOHL, H. C. (2004a), S. 5.
590
Die Interdependenzen zwischen den behandelten Planungssystemen werden in Kapitel 3.3 vorgestellt.
Entwicklung eines multiagentenbasierten Modells zur CT-Prozesskoordination
159
laufen des Graphen bildet den Planungsprozess für das Container-Terminal Management Problem ab. Es lassen sich unterschiedliche Koordinationsmethoden simulieren. Dabei kommen grundsätzlich alle Kombinationen aus iterativem und sequenziellem Vorgehen aller Teilmengen des Graphen in Betracht.591 Die Agenten bleiben autonom agierende Spezialisten für ihre individuelle Problemstellung. In Kapitel 4.2 wurde festgestellt, dass die Gestaltung des Ablaufs der Planung im Rahmen der Alternativensuche allein nicht ausreichend sein kann. Es ist ein übergreifendes Zielsystem zu definieren, mit dem sich Konflikte sowohl zwischen Planungssystemen als auch innerhalb eines Planungssystems bewerten lassen. Die Gestaltung des Zielsystems ist Teil des folgenden Abschnitts. Die von WOOLDRIDGE aufgezeigten Instrumente zur Zusammenarbeit von Agenten finden sich in dieser Betrachtung wieder.592 Das CTMP behandelt die Synthese der in den vorangegangen Schritten des Cooperative Distributed Problem Solving zerlegten und isoliert behandelten Teilprobleme.593 Jeder Knoten in G verfügt über die Fähigkeit zur Lösung einer komplexen Problemstellung, die sich unabhängig von anderen Problemstellungen abbilden lässt. Dennoch verfügt keiner der Knoten über diejenigen Fähigkeiten, Ressourcen und Kenntnisse, die notwendig wären, um die gesamte Problemstellung allein lösen zu können.594 Das Container-Terminal Management Problem (CTMP) setzt sich als übergreifende Problemstellung aus den betrachteten Teilproblemen zusammen. In einer Black Box lässt sich das Problem wie folgt abbilden:
591
In der Abbildung ist ersichtlich, dass diese Möglichkeit für das vereinfachte Modell nicht in Betracht kommen kann, weil der Informationsfluss nur in eine einzige Richtung möglich ist.
592
Vgl. WOOLDRIDGE, M. (2008), S. 189ff sowie die Ausführungen in Kapitel 2.4.2.
593
Vgl. Abbildung 2-14.
594
Diese Darstellung konkretisiert die Definition des CDPS nach DURFEE, E.; LESSER, V.; CORKILL, D. (1989) in Kapitel 2.4.2. Auch zur Koordination von Teillösungen im Rahmen ihrer Synthese nennt WOOLDRIDGE verschiedene Ansätze.
160
Entwicklung eines multiagentenbasierten Modells zur CT-Prozesskoordination
Input
Output
CTMP
Abbildung 5-2: Black Box-Betrachtung
Mit den vorangegangenen Ausführungen ist nun ersichtlich, wie sich das CTMP im Einzelnen zusammensetzt: CSP
Input
Output BAP
VDP SLP
Abbildung 5-3: CTMP-Struktur
In Abbildung 5-3 sind die Definition und die Struktur des CTMP ersichtlich.595 Es wird deutlich, dass sich das Ergebnis des CTMP aus dem Zusammenspiel der einzelnen Subprobleme ergibt. Im einfach koordinierten System werden die Probleme sequenziell durchlaufen und ihre Ergebnisse sukzessiv weitergereicht.596 Die dezentralen Teilplanungsbereiche eines CT konnten aufgezeigt werden. Auch Ansatzpunkte unterschiedlicher Planungsphilosophien wurden erörtert.597 Von der - vorrangig in der Praxis eingesetzten - hierarchischen Planung sind Nachteile bekannt. Im Rahmen eines Multiagentensystems lassen sich Koordinationsmodelle untersuchen und so neue Ansatzpunkte für die Zusammenführung der interdependenten Teilbereiche aufzeigen. Konkret läuft der Planungsprozess wie folgt ab:
595
Die vom Management des CT zu definierende Organisationsstruktur ist hiermit auf die Teilbereiche Liegeplatzplanung (BAP), Containerbrückeneinsatzplanung (CSP), Yardplanung (SLP) und Transportplanung (VDP) fixiert. Durch den Austausch oder das Hinzufügen neuer Agenten ist auch die Untersuchung weiterer Organisationsstrukturen möglich. Die Untersuchung unterschiedlicher Organisationsstrukturen des CTMP ist nicht Teil dieser Arbeit.
596
Das Ergebnis dieser sequenziellen Koordination ist Teil der modellübergreifenden Untersuchung in Kapitel 6.1.2.2.1. Die sequenzielle Koordination entspricht im Wesentlichen dem Ansatz von ZHANG ET AL., vgl. hierzu auch Abbildung 3-4.
597
Vgl. Kapitel 2.3.3.
161
Größe
Entwicklung eines multiagentenbasierten Modells zur CT-Prozesskoordination
Größe
CSP: Betrachtung des Schiffes mit Bays
Größe
Aufenthaltszeit
Aufenthaltszeit Aufenthaltszeit
VDP: Betrachtung des Schiffes mit Bays und Containern
BAP: Betrachtung des Schiffes
SLP: Zuweisung von Lagerplätzen in Yard- Blöcken
Abbildung 5-4: Konkretisierung der Planung
Im Rahmen des Berth Allocation Problems sind die Schiffe als Elemente auf einer Fläche (time-space) zu ordnen. Im Crane Scheduling Problem werden die Bays jedes einzelnen Schiffes betrachtet und einer Containerbrücke zugeordnet. Das Vehicle Dispatching Problem integriert die Ergebnisse des Storage Location- und des Crane Scheduling Problems: Es nimmt die Ergebnisse beider Problemstellungen auf und bestimmt die Transportwege der Van Carrier. Der Plan wird in jedem Schritt konkretisiert. Dabei besteht die Gefahr, dass sich die angenommenen Daten in vorangestellten Problemen ändern. In diesem Fall basieren die Ergebnisse der Vorgängermodelle auf falschen Eingangsdaten und können zu suboptimalen Entscheidungen führen. Die beschriebenen Probleme werden von Agenten gelöst. In der folgenden Abbildung wird auf den Aufbau dieser Agenten eingegangen.
162
Entwicklung eines multiagentenbasierten Modells zur CT-Prozesskoordination
Parametersystem
Agent
Planungssystem
Wissenssystem
Instanzsystem Methodensystem
Perzeptorsystem
Entscheidungsmodell
Kooperationssystem
Rezeptorsystem
Zielsystem
Input
Output
Restriktionssystem
Abbildung 5-5: Architektur der Agenten im Modell
Die Abbildung zeigt die Architektur von Agenten in dem verwendeten Modell. Ein Agent verfügt über Rezeptoren und Perzeptoren zur Wahrnehmung und Abgabe von Reizen. Agenten umhüllen neben dem Planungssystem zusätzlich ein Wissenssystem, in dem der Agent Erfahrungen und Wissen hinterlegen kann, auf das bei der Suche nach Lösungen von Problemen zugegriffen werden kann. Das Kooperationssystem steuert die Weitergabe von erzeugten Lösungen.598 Das Planungssystem des Agenten baut auf dem Entscheidungsmodell bestehender Ansätze auf.599 Das Entscheidungsmodell enthält das Zielsystem600 und das Restriktionssystem. Zusätzlich müssen dem Planungssystem das Instanzsystem und auch das Methodensystem zur Verfügung stehen. Nachrichten, die der Agent erhält, werden mit Hilfe des Instanzsystems zu gültigen Instanzen für das Entscheidungsmo-
598
Über das Kooperationssystem wird gesteuert, an welche oder welchen Agenten die erzeugte Lösung weitergeleitet werden soll.
599
Vgl. hierzu die ausführliche Darstellung dieser Entscheidungsmodelle in den Kapiteln 3.2.2.2, 3.2.3.2, 3.2.4.2 und 3.2.5.2.
600
Das Zielsystem wird in den einzelnen Entscheidungsmodellen teilweise erweitert, um den Anforderungen, die sich durch das übergreifende Modell ergeben, gerecht zu werden. Vgl. hierzu Kapitel 5.1.2.
Entwicklung eines multiagentenbasierten Modells zur CT-Prozesskoordination
163
dell überführt.601 Zur Lösung dieser Entscheidungsprobleme steht das Methodensystem zur Verfügung.602 Neben Nachrichten können über die Rezeptoren des Agenten auch Parameter des Terminals abgefragt werden. Eingesetzt in die Terminal-Umgebung ergibt sich für die Agenten die folgende Struktur: Terminal-Umgebung des Modells
CSP Agent
VDP Agent
BAP Agent
SLP Agent
Abbildung 5-6: In die Terminal-Umgebung eingesetzte Agenten603
Agenten informieren beteiligte Entscheidungsträger über ihre Planung. Bei sequenzieller Koordination erfolgt keine Rückmeldung nachfolgender Agenten zu ihren Vorgängern. Dieser Verlauf ist in der Abbildung durch die verstärkt gekennzeichneten Verbindungen angezeigt. Im Fall der iterativen Koordination erfolgt die n-fache Iteration zwischen zwei oder mehr Planungssystemen, bevor Ergebnisse weitergereicht werden. Innerhalb der Modelle werden die folgenden Entities eingesetzt, deren Beziehungen mit Hilfe eines Entity Relationship Modells (ERM) dargestellt werden können. Unter einem Entity versteht man reale oder abstrakte Objekte mit eigenständiger Bedeutung.604 Die En-
601
Beispielsweise werden aus einer Nachricht des CSP-Agenten an den Liegeplatzverantwortlichen die sich ergebenden Operationszeiten für die Containerschiffe berechnet und für das BAP-Modell gesetzt, vgl. hierzu auch die Kapitel 3.2.2 und 3.2.3.
602
Die Methoden werden in Kapitel 3.2 ausführlich vorgestellt.
603
Es wird die in Abbildung 5-1 aufgezeigte Struktur in das Modell übertragen.
604
Vgl. MERTENS, P. et al. (2005), S. 62- 64. Mit dem ERM lassen sich Objekte und ihre Beziehungen beschreiben. Entitytypen sind als Rechtecke und Beziehungstypen als Raute dargestellt. Ungerichtete Kanten verknüpfen Beziehungs- und Entitytypen. Die Komplexität des Beziehungstyps wird an der Kante angegeben.
164
Entwicklung eines multiagentenbasierten Modells zur CT-Prozesskoordination
tities des beschriebenen CT-Modells können durch das folgende ERM abgebildet werden. Attribute, die die Entities näher beschreiben, sind nicht in der Abbildung dargestellt.
Containerschiff
Yard 1
1
Job enthält
n
n
definiert
n
enthält ist zugeordnet
1
n
gruppiert
Bay
1
1
Block
n n
n n
Container
ist zugeordnet
1
lädt/ löscht
ist zugeordnet
n
1
transportiert
m
ist zugeordnet
1
1
m 1
lagert
n
Containerbrücke
n
Van Carrier m
besitzt
greift zu
Buffer 1
n
Abbildung 5-7: CT-Entity Relationship Modell (ohne Attribute)
Die Abbildung zeigt die im Modell verwendeten Entities und ihre Beziehungen mit Kardinalitäten. Der Beziehungstyp „ist zugeordnet“ ist Gegenstand der in den Planungssystemen behandelten Problemstellung. Jedes Containerschiff605 enthält mehrere Bays, die es im Rahmen des CSP zuzuordnen gilt. Eine Bay definiert n (hier: n=2) Jobs, um den Typ des Containers (hier: Import- und Exportcontainer) zu differenzieren. Jeder Job umfasst den Umschlag mehrerer Container. Im SLP werden diese Jobs einzelnen Blöcken zugeordnet, wobei ein Block mehrere Jobs aufnehmen kann, ein Job aber genau einem Block zuzuordnen ist. Der Yard umfasst mehrere Blöcke. Van Carrier transportieren einzelne Container zwischen den Blocks im Yard und den Buffern der Containerbrücke am Kai. Diese Zuordnung erfolgt im Rahmen des VDP. Eine Containerbrücke löscht und lädt die Container einer zugeordneten Bay zwischen Buffer und Containerschiff. Die Containerbrücke kann mehrere Reihen (nacheinander) bearbeiten.
605
Ein Containerschiff ist mindestens einer Kai-Ressource zugeordnet, deren Zuordnung mit der Liegeplatzplanung erfolgt. Der Kai wird nicht als Entity in das Modell aufgenommen, weil dieser in dem Modell nicht als komplexes Objekt abgebildet ist. Vgl. hierzu die Modelformulierung nach GUAN, Y.; CHEUNG, R. K. (2004) in Kapitel 3.2.2.2.
Entwicklung eines multiagentenbasierten Modells zur CT-Prozesskoordination
165
Zusammenfassend gibt Abbildung 5-8 einen Überblick über die hier behandelten Entscheidungsbereiche des Terminals. Kai QC
Vehicle Dispatching Problem (VDP)
space
Block
Schiff
Storage Location Problem time
Berth Allocation Problem
Crane Scheduling Problem
Yard
Abbildung 5-8: Überblick behandelter Entscheidungsbereiche im Modell
Im folgenden Abschnitt ist auf das Zielsystem des CT im Modell einzugehen, das aus den allgemeinen Zielsetzungen der Logistik abzuleiten ist.
5.1.2 Definition eines Zielsystems im CT-Modell
In den in Kapitel 3.2 vorgestellten Modellen wird zumeist eine konkrete Zielfunktion für die betrachtete Problemstellung angegeben. In einem Überblick stellen STEENKEN, STAHLBOCK und VOß606, SAANEN607 und auch MEIER608 allgemeine Bezugspunkte für das Zielsystem in unterschiedlichen Entscheidungsbereichen zusammen. In diesem Abschnitt werden die Ziele des Terminals vorgestellt, wie sie in dem implementierten Modell eingesetzt werden. Das Zielsystem ist wiederum in seine Entscheidungsbereiche unterteilt sowie in gemeinsame, bereichsübergreifende Ziele. 5.1.2.1 Klassifizierung von Zielen
Zwischen den Entscheidungsbereichen bestehen Interdependenzen, wie in Kapitel 3.3 aufgezeigt wurde. Aus diesem Grund sind auch die systemübergreifenden Zielsetzungen des
606
Vgl. STEENKEN, D.; VOß, S.; STAHLBOCK, R. (2004).
607
Vgl. SAANEN, Y. A. (2004).
608
Vgl. MEIER, L. (2006).
166
Entwicklung eines multiagentenbasierten Modells zur CT-Prozesskoordination
Terminals zu betrachten. In Abhängigkeit von den verwendeten Koordinationsinstrumenten spielen die übergreifenden Ziele des CT eine wesentliche Rolle im Planungsprozess. SAANEN zeigt eine umfassende Klassifizierung von CT-Kennzahlen auf. Hierzu werden genannt:609
Design-Indikatoren, um CT-Typen zu klassifizieren
Performance-Indikatoren aus Kundenperspektive
Performance-Indikatoren aus Terminalperspektive, insb. Infrastruktur-Auslastung und Produktivität
Performance-Indikatoren aus Terminalperspektive, insb. des Equipments
Performance-Indikatoren aus Terminalperspektive, insb. Auslastung des Lagers
Indikatoren zur Kostenanalyse
Die Klassifizierung von SAANEN umfasst alle Kennzahlen, die den CT und seine Umgebung betrachten. In die erste Gruppe fallen Indikatoren, die den CT selbst klassifizieren. Hierzu gehören Kennzahlen, die die Größe des Terminals und seine relevanten Dienstleistungen charakterisieren, z.B. der Containerumschlag in einem bestimmten Zeitraum und die durchschnittliche Lagernachfrage in TEU.610 Eine zweite Gruppe ist durch Kennzahlen gegeben, die die Leistungsfähigkeit des CT beschreiben. Diese Kennzahlen werden von SAANEN in unterschiedlichen Perspektiven klassifiziert. Aus der Sicht des Kunden interessieren z.B. die maximale Schiffsgröße oder die durchschnittliche Operationsgeschwindigkeit in TEU/ZE. Aus CT-Sicht ist die Leistungsfähigkeit der vorhandenen Ressourcen relevant, die von SAANEN weiterhin in die Gruppen Infrastruktur, Equipment und Lager differenziert werden. Hierzu gehören beispielsweise die abgefertigten Container pro Kaimeter in TEU/m, die Produktivität der QC in TEU/(QC/h) sowie die durchschnittliche Anzahl von Containerbewegungen, die notwendig ist, um auf einen bestimmten Container im Yard zuzugreifen.611
609
Vgl. SAANEN, Y. A. (2004), S. 34- 50.
610
SAANEN, Y. A. (2004), S. 36- 40.
611
SAANEN, Y. A. (2004), S. 40- 48.
Entwicklung eines multiagentenbasierten Modells zur CT-Prozesskoordination
167
Zusätzlich werden von SAANEN Indikatoren zur Kostenanalyse genannt.612 Die Klassifizierung der Kennzahlen von STEENKEN, STAHLBOCK und VOß ist funktional gegliedert und orientiert sich an den in der Literatur publizierten Modellen und deren Zielsetzung für die betrachteten Bereiche.613 Für das Berth Allocation Problem werden von den Autoren die Minimierung der Transportdistanzen zur Maximierung der Produktivität sowie die Minimierung der Wartezeiten für Containerschiffe genannt.614 Weiterhin werden in der Literatur die Minimierung von Unzufriedenheiten und die Maximierung der Anzahl der Berth On Arrivals erwähnt.615 Diese Zielsetzungen decken sich mit den in den Entscheidungsmodellen konkret eingesetzten Zielsetzungen, angesprochen in Kapitel 3.2.2. Die Ziele des Crane Scheduling Problems setzen zur Maximierung der Leistungsfähigkeit des Terminals bei der Minimierung der Verzögerungen an den Containerbrücken an. Von ZHU und LIM wird der Fertigstellungszeitpunkt des letzten QC-Jobs minimiert.616 Diese Zielsetzung ist nur in dem isoliert betrachteten Modell sinnvoll, unter der Annahme, dass alle Schiffe und deren Jobs mit Beginn des Planungszeitraumes zur Verfügung stehen. STEENKEN, STAHLBOCK und VOß nennen zudem den ökonomischen Einsatz von Containerbrücken. Diesen Ansatz berücksichtigen u.a. MEISEL und BIERWIRTH in der Zielfunktion.617 Das Storage Location Problem orientiert sich an der effizienten Auslastung des Yards. Aus diesem Grund werden von den Autoren im Bereich der Yardplanung die Maximierung der Auslastung, die Minimierung der Transportdistanzen zwischen Kai und Yard sowie die Minimierung unnötiger Containerbewegungen genannt. Insbesondere im Rahmen der Zu-
612
Vgl. SAANEN, Y. A. (2004), S. 48- 50.
613
Vgl. STEENKEN, D.; VOß, S.; STAHLBOCK, R. (2004).
614
Vgl. STEENKEN, D.; VOß, S.; STAHLBOCK, R. (2004), S. 17.
615
Der Begriff UNZUFRIEDENHEIT ist von dem Entscheidungsträger zu definieren. Unzufriedenheit kann beim Kunden des CT entstehen, wenn die Ankunftsreihenfolge von Containerschiffen nicht der Abfertigungsreihenfolge entspricht. Die Kennzahl Berth On Arrivals gibt an, wie vielen Containerschiffen mit ihrer Ankunft ein Liegeplatz zugewiesen werden kann, d.h. die Wartezeit des Containerschiffs ist gleich Null, vgl. hierzu Abbildung 5-9.
616 617
Vgl. Kapitel 3.2.3.2.
Vgl. STEENKEN, D.; VOß, S.; STAHLBOCK, R. (2004), S. 21 und als Beispiel für den konkreten Einsatz dieser Zielsetzung, vgl. MEISEL, F.; BIERWIRTH, C. (2005), S. 106- 108.
168
Entwicklung eines multiagentenbasierten Modells zur CT-Prozesskoordination
ordnung zu bestimmten Blöcken wird die Notwendigkeit einer ausgeglichenen Lagerung aufgezeigt, weil es sonst zu Blockaden von Transportern an diesen Blöcken kommt, die den Prozess verzögern.618 Das Vehicle Dispatching Problem greift als operatives Planungssystem auf die Entscheidungen der vorangestellten Bereiche zurück. In diesem Rahmen kommt diesem Bereich eine koordinierende Funktion zu. Die Zielsetzungen orientieren sich an der Minimierung von Kosten in logistischen Systemen. Kosten entstehen für Elemente in einem logistischen System aufgrund von Bewegung, z.B. durch zu überbrückende Distanz, und durch Stillstand, z.B. durch zu überbrückende Zeit.619 Zu einem Stillstand kommt es u.a., wenn mehrere Transporter gleichzeitig auf Container aus demselben Yard-Block zugreifen möchten. Aus diesem Grund kommt auch der Yardplanung eine besondere Rolle zur Minimierung der Kosten in dem logistischen System zu. Das in Kapitel 3.2.5.2 diskutierte Modell von BÖSE
ET AL.
nutzt die Minimierung der
Transporter-Wartezeiten zur Maximierung der QC-Produktivität. STEENKEN, STAHLBOCK und VOß nennen zudem die Transport-Synchronisation mit den QC-Abläufen als wichtige Aufgabe der Transportplanung.620 Der folgende Abschnitt definiert die übergreifenden Ziele des Modells. 5.1.2.2 Übergreifende Ziele des Modells
Zu den übergreifenden Zielsetzungen sollen diejenigen Ziele gezählt werden, die von jedem isoliert betrachteten Ziel(sub-)system vorrangig zu behandeln sind. Übergreifend sind vor allem die Aufenthaltszeit im Hafen und die Transportdistanz zu berücksichtigen. Diese beiden Größen des Zielsystems enthalten Aussagen zur Konkurrenzfähigkeit des Terminals und auch zur Wirtschaftlichkeit des CT. Die Aufenthaltszeit setzt
618
Vgl. STEENKEN, D.; VOß, S.; STAHLBOCK, R. (2004), S. 23f. Die ausgeglichene Verteilung der Lagerung der Container im Yard wird von MURTY ET AL. in der Zielsetzung aufgegriffen, vgl. hierzu MURTY, K. G. et al. (2005), S. 321f.
619
Vgl. DAGANZO, C. F. (1999), S. 17ff.
620
Vgl. STEENKEN, D.; VOß, S.; STAHLBOCK, R. (2004), S. 25f.
Entwicklung eines multiagentenbasierten Modells zur CT-Prozesskoordination
169
sich aus der Operationszeit im Hafen und der Wartezeit des Containerschiffs vor dem Hafen zusammen. Deshalb müssen auch diese Größen betrachtet werden. Die folgende Abbildung verdeutlicht die Berechnung der Zielsetzungen Aufenthaltszeit (TIP), Operationszeit ( top ) und Wartezeit ( t wait ) im Rahmen des in Kapitel 3.2.2 eingeführten time-spaceDiagramms.
Aufenthaltszeit im Hafen (Time in Port, TIP),
Wartezeit: twait
TIP twait top
(c a )
Operationszeit: top
Containerschiff
Zeit
Anlegezeitpunkt: u Ankunftszeit: a
Fertigstellungszeitpunkt: c
Abbildung 5-9: Zieldefinition
Die Abbildung verdeutlicht die Zusammensetzung der Zielgrößen. Die Aufenthaltszeit im Hafen (TIP) berechnet sich aus der Summe der Wartezeit des Containerschiffs vor dem Hafen und der Operationszeit im Hafen. Es ist die Minimierung der Aufenthaltszeit anzustreben. Für V ankommende Schiffe in dem Planungshorizont T ergibt sich folgende zu minimierende Zielgröße: TIP
1 V
V
¦ w (c v
v
a v ) , mit v d V und a v d T .
v 1
Mit Hilfe von wv lässt sich jedem Schiff ein Gewicht zuordnen, das dessen relative Bedeutung ausdrückt. Die durchschnittliche Warte- und Operationszeit ergeben sich wie folgt: t wait
top
1 V ¦ wv (uv a v ) sowie V v1 1 V
V
¦ w (c v
v 1
v
uv ) , mit v d V und a v d T .
170
Entwicklung eines multiagentenbasierten Modells zur CT-Prozesskoordination
Diese Zielsetzungen sind für alle implementierten Entscheidungsbereiche relevant. In der Liegeplatzplanung wird jedoch von einer konstanten Operationszeit für jedes Schiff ausgegangen, so dass diese Größe in diesem Planungssystem nicht variiert wird. Hier wird mit der Bestimmung des Anlegezeitpunktes und der Schiffsposition Einfluss auf die durchschnittliche Wartezeit der Containerschiffe genommen. In der Containerbrückenzuordnung werden für jedes Schiff mehrere Containerreihen betrachtet, unter Berücksichtigung der in der Liegpeplatzplanung gesetzten Schiffsposition ( posc ,w ). Auch für jede Bay des Schiffs werden konstante Bearbeitungszeiten durch einen QC angenommen. Je nach QC-Zuordnung können sich nun aber die Operationszeit der Schiffe (und dadurch die Wartezeit nachfolgender Schiffe) ändern. Gemeinsam mit der in der Yardplanung bestimmten Positionierung der Container im Yard ( posc ,l ) steht die Transportdistanz jedes einzelnen Containers einer Bay fest. Mit Hilfe der gegebenen Geschwindigkeit der Transporter auf dem Yard lassen sich die Container als individuelle Jobs bearbeiten. Dieser Transport beeinflusst die im CSP angenommene JobBearbeitungszeit und damit wiederum die durchschnittliche Operations- und Wartezeit der Containerschiffe. Die Transportdistanz kann wie folgt berechnet werden: C
D
¦ | pos
c ,w
posc ,l | , mit a v ( c ) d T
c 1
Die Bedingung a v ( c ) d T drückt aus, dass die Ankunft des Schiffes, dem der Container c zugeordnet ist, innerhalb des betrachteten Planungszeitraumes liegt. In dem Planungszeitraum T sind C Container umzuschlagen. In diesem Zusammenspiel beeinflussen die implementierten Teilbereiche des CT gemeinsam die durchschnittliche Aufenthaltszeit von Containerschiffen. Die isoliert gewonnenen Entscheidungen sind mit Hilfe geeigneter Koordinationsinstrumente so abzustimmen, dass diese Zielgröße minimiert werden kann. Eine differenzierte Gewichtung der Schiffe ist sinnvoll, weil ihre Bearbeitung zu unterschiedlichen Konsequenzen für den CT führen kann. Beispielsweise kann eine bestimmte Produktivität vertraglich zugesichert sein und deren Nichteinhaltung eine Vertragsstrafe bedingen.
Entwicklung eines multiagentenbasierten Modells zur CT-Prozesskoordination
171
Das Ergebnis des CTMP soll als Quadrupel dieser vier übergreifenden Kennzahlen angegeben werden: CTMP ( TIP , twait , top , D).621 Die Entscheidungen in den Planungssystemen beeinflussen gemeinsam das Ergebnis des CTMP. Der folgende Abschnitt zeigt konkurrierende Zielsetzungen im Rahmen der Planung von CT-Prozessen auf. 5.1.2.3 Konkurrierende Zielsetzungen
Das im vorangegangen Abschnitt vorgestellte Zielsystem ist von allen Agenten des MAS zu berücksichtigen. Innerhalb und zwischen den Planungssystemen kann es dennoch zu Zielkonflikten kommen. Dies ist der Fall, wenn mit der Verbesserung des Zielerreichungsgrades eines Zieles sich derjenige des anderen Zieles verschlechtert. Zwei Ziele können zueinander komplementär, konkurrierend (konträr) oder neutral sein. Zur Lösung von Zielkonflikten führen DOMSCHKE und DREXL die lexikographische Ordnung von Zielen, die Zieldominanz, die Zielgewichtung sowie die Berücksichtigung von Abstandsfunktionen an.622 In dieser Arbeit wird dieses Problem mit einer Gewichtung des Zielsystems gelöst. Am Beispiel von Transportdistanz und Wartezeit der Containerschiffe soll ein erster Zielkonflikt aufgezeigt werden. Die folgende Abbildung zeigt jeweils einen Ausschnitt aus dem Berth Allocation Problem, vor und nach der Abstimmung mit der Yardplanung.
Abbildung 5-10: Zielkonflikt zwischen Transportdistanz und Wartezeit
621
Ein Quadrupel bildet eine Zusammenfassung von vier geordneten Elementen.
622
Vgl. DOMSCHKE, W.; DREXL, A. (2007), S. 55- 59.
172
Entwicklung eines multiagentenbasierten Modells zur CT-Prozesskoordination
Durch Verschieben des Elements (10)623 lässt sich, für die gegebene Zuordnung von YardLagerplätzen, die Transportdistanz verringern. Für dieses Schiff muss dafür jedoch eine höhere Wartezeit in Kauf genommen werden. Dieses Beispiel verdeutlicht die Bedeutung der Gestaltung des Zielsystems. Es stellt sich die Frage, um wie viele Einheiten sich die Transportdistanz verringern muss, um die um eine Zeiteinheit erhöhte Wartezeit zu rechtfertigen. In Abhängigkeit von der Gewichtung beider Größen im Zielsystem ergeben sich unterschiedliche Empfehlungen für die Zuordnung.624 Die in Kauf genommene zusätzliche Wartezeit stellt eine Investition dar, zur Eröffnung des Potentials, um geringere Operationszeiten erreichen zu können. Die verlängerte Wartezeit lässt sich rechtfertigen, wenn die Operationszeit aufgrund der geringeren Transportdistanz ausreichend reduziert werden kann.625 Mit einer Sensitivitätsanalyse lässt sich eine Lösung des Optimierungsmodells auf Reaktionen gegenüber Veränderungen der Ausgangssituation testen. Von einer robusten Lösung kann gesprochen werden, wenn die Lösung auch bei Veränderung mehrerer Daten noch zulässig und hinsichtlich ihrer Güte „akzeptabel“ ist.626 Es ist interessant, das Verhältnis zwischen beiden Gewichten des Zielsystems zu untersuchen und zu analysieren, wie stark die Änderung der Zielkoeffizienten ausfallen muss, damit sich eine andere Entscheidung ergibt. Dieses Vorgehen unterstützt die Interpretationsfähigkeit einer Lösung. Das optimale Verhältnis beider Ziele kann zumeist nicht als exakter Wert, sondern lediglich in einem gewissen Bereich angegeben werden. Ein weiteres Beispiel für eine konkurrierende Zielsetzung zeigt sich in der Betrachtung der Kosten zur Bereitstellung zusätzlicher Ressourcen für den Umschlag von Containern des CT. Stellt der CT zusätzliche Containerbrücken und Transportfahrzeuge für den Contai-
623
Die Elemente der Abbildung stellen Containerschiffe dar. Vgl. hierzu Kapitel 3.2.2 und insbesondere die allgemeine Darstellung eines Liegeplatzplanes in Abbildung 3-5.
624
In der Gewichtung des Zielsystems ist bei Berücksichtigung von Transportdistanz in km und Aufenthaltszeit in h anzugeben, wie viele Einheiten der Zielsetzung I mit wie vielen Einheiten der Zielsetzung II äquivalent sind. Die Gewichtung drückt das Verhältnis zwischen einer Transporteinheit (in km) und einer Zeiteinheit (in Stunden) aus.
625
Dieser Aspekt ist Teil der Untersuchung in Kapitel 6.1.2.1.2.
626
Vgl. DOMSCHKE, W.; DREXL, A. (2007), S. 42ff.
Entwicklung eines multiagentenbasierten Modells zur CT-Prozesskoordination
173
nerumschlag bereit, dann ist zu erwarten, dass sich die durchschnittliche Aufenthaltszeit für Containerschiffe im Hafen senken lässt. Gleichzeitig steigen jedoch die Kosten für die Durchführung der Operationen. In Abhängigkeit von den Kosten ist die optimale Zusammenstellung der CT-Ressourcen auszuwählen.627 Je mehr die Details von CT-Prozessen in dem Modell abgebildet werden, umso mehr lassen sich konkurrierende Ziele und auch Zielkonflikte aufzeigen. Insbesondere im Zusammenhang mit der Yardplanung ergeben sich Konflikte, weil sich durch Missachtung der Planung in diesem Bereich eine kurzfristige Beschleunigung der Prozessabläufe erzielen lässt.628 Die Analyse unterschiedlich gewichteter Zielfunktionen wird in dieser Arbeit nicht durchgeführt.
5.1.3 Modellkritik
Als Vorteil dieser Modellumsetzung wurde aufgezeigt, dass sich die Organisationsstruktur eines CT und auch dessen Koordinationsmethoden sehr gut übertragen lassen. Es ist dennoch nicht auszuschließen, dass die sequenzielle Zusammenführung dieser Teilergebnisse zunächst zu schlechteren Ergebnissen als in der Realität führt, weil
die Möglichkeit für den Eingriff eines menschlichen Experten in diesem Prozess nicht vorgesehen ist und
die in die MAS-Umgebung eingesetzten Modelle der Literatur zwar die geforderten Problemstellungen abbilden, dennoch bislang nicht auf ihre Koordinationsfähigkeit überprüft werden konnten.629
627
Dieser Aspekt ist Teil der Untersuchung in Kapitel 6.1.1.2 im Rahmen der Erweiterung der Kailänge und in Kapitel 6.1.1.4 im Rahmen der Bereitstellung neuer Containerbrücken für den Containerumschlag.
628
Mit detaillierter Modellierung des Yards fällt dieser Aspekt stärker ins Gewicht, weil dann auch Umstauer zu behandeln sind, die den Prozess verlängern. Diese treten auf, wenn nicht direkt auf einen Container zugegriffen werden kann, weil der Container unterhalb von anderen Containern platziert ist. Umstauer werden in dem implementierten Yardmodell nicht behandelt.
629
Dies ist auch der Fall, weil bislang kein geeigneter Ansatz existiert, um diese Fähigkeit zu untersuchen. Auch aus der Übertragung der Ergebnisse in die Praxis sind bislang keine Resultate bekannt, aus denen sich Ansatzpunkte hierfür ergeben könnten. Vgl. Tabelle 4-1.
174
Entwicklung eines multiagentenbasierten Modells zur CT-Prozesskoordination
Der CT ist in der Lage, auf zahlreiche Erfahrungen im Rahmen der Synthese zurückzugreifen, insbesondere auch im Voraus bei der Auswahl geeigneter Modelle. Es wurde bereits angesprochen, dass die Auswahl der richtigen Modelle im Rahmen des Planungsprozesses eine wichtige Aufgabe des Managements ist. Die gesamte Planung hängt von dieser Auswahl ab. Hier steht die Forschung noch in ihren Anfängen. Gleichzeitig eröffnet sich mit diesem Modell das Potential, die isolierten Modelle der Literatur hinsichtlich dieser Fähigkeiten zu überprüfen. Isoliert gefundene Ergebnisse können im übergreifenden Fall eine unterschiedliche Wirkung aufweisen. Als Ursachen für die Abweichung zwischen Ist- und Plan-Ergebnis identifiziert SAANEN u.a. die unterschätzte Anzahl menschlicher Interventionen in den Planungsprozess sowie eine unerwartet hohe Anzahl von Systemfehlern, etwa den Ausfall von Containerbrücken (Hardware) oder auch Softwarefehler.630 Das Informationssystem, das die Hard- und Software des CT koordinieren muss, stellt eine zentrale Ressource für den Container-Terminal dar.631 Die Kosten für Computer-Hardware und Software gibt SAANEN mit 4.000.000 € bis 20.000.000 € an.632 Diese Kosten belegen die hohe Bedeutung dieser Ressource und gleichzeitig die Notwendigkeit für die Untersuchung von Ansätzen zur Systemverbesserung. Es erscheint deshalb durchaus gerechtfertigt, die Leistung der in das Multiagentensystem eingesetzten Agenten ohne menschliche Intervention zu untersuchen. So lässt sich aufzeigen, inwieweit sich die vorhandenen Systeme ohne externe Unterstützung behaupten können.633 Diese Situation stellt sich als Benchmark für neue intelligente Lösungen dar.
630
Vgl. SAANEN, Y. A. (2004), S. 60ff.
631
Vgl. SAANEN, Y. A. (2004), S. 34.
Folgendes Beispiel soll die Bedeutung des Informationssystems verdeutlichen: In der Untersuchung von MEIER ET AL. konnte eine Prozessverbesserung über den Einsatz einer dynamischen VC-Zuordnung identifiziert werden, vgl. MEIER, L. et al. (2005), S. 2280f. Die Diskussion mit dem CT-Management bestätigte die erwartete Wirkung dieser Maßnahmen. Das zu diesem Zeitpunkt eingesetzte Informationssystem war jedoch nicht in der Lage, die vorgeschlagenen Maßnahmen abzubilden. 632 633
Vgl. SAANEN, Y. A. (2004), S. 49.
SAANEN weist darauf hin, dass Interventionsmöglichkeiten in automatisierten Terminals nochmals geringer ausfallen. Vgl. SAANEN, Y. A. (2004), S. 126.
Entwicklung eines multiagentenbasierten Modells zur CT-Prozesskoordination
175
Es ist zudem auf die Kritik der isolierten Modelle hinzuweisen, die auch für das umfassende Modell gilt. Festzuhalten bleibt, dass der Vorteil dieses Ansatzes die Austauschbarkeit erlaubt, weil die isolierten Modelle über die definierten Schnittstellen als Modul integriert worden sind. Der folgende Abschnitt beschreibt die technische Realisierung dieses Modells.
5.2 Technische Realisierung Der Fokus dieser Arbeit soll auf der Analyse komplexer Logistiksysteme am Beispiel von Container-Terminal-Prozessen liegen. Um Experimente durchführen zu können, wurden verschiedene Entscheidungsprobleme implementiert und innerhalb eines Multiagentensystems miteinander verknüpft. Dadurch sollen Erkenntnisse über das Zusammenwirken von Entscheidungen gewonnen werden. Die folgenden Abschnitte geben einen Überblick über die technische Umsetzung der beschriebenen Modelle in Java und diejenigen Tools, die während der Anwendung zum Einsatz kommen.
5.2.1 Java
Java ist eine objektorientierte, plattformunabhängige und frei verfügbare Programmiersprache. Die Sprache basiert auf einer Vereinfachung übermäßig komplexer Merkmale, die andere objektorientierte Programmiersprachen belasten.634 Es existieren umfangreiche Klassen und Programmierschnittstellen (API) für Java, auf die während der Entwicklung zurückgegriffen werden kann. Zudem kann die Programmierung durch den Einsatz leistungsstarker Entwicklungsumgebungen zusätzlich erleichtert werden. Beispiele stellen das eingesetzte MAS-Framework JADE dar, auf das im folgenden Abschnitt eingegangen werden soll sowie die Programmierschnittstelle JDOM, mit deren Hilfe XML-Dateien innerhalb der Java-Umgebung manipuliert werden können. Zudem wurde
634
Auf die besondere Architektur der Programmiersprache Java, der Java Virtual Machine und der Plattform Java geht FLANAGAN ein. Vgl. FLANAGAN, D. (2006), S. 3- 9. Auf die Architektur der Sprache soll hier nicht näher eingegangen werden. Der Autor gibt einen umfassenden Überblick zu Java. Es werden auch die Unterschiede zwischen Java und C herausgestellt. Vgl. hierzu insbesondere die Seiten 88- 90.
176
Entwicklung eines multiagentenbasierten Modells zur CT-Prozesskoordination
bereits im Rahmen der Darstellung der Optimierungsmethoden auf APIs für Metaheuristiken eingegangen. Mit der Arbeit von PAGE und KREUTZER wurde die Einsatzfähigkeit von Java auch als Simulationssprache bestätigt.635 Insbesondere die Plattformunabhängigkeit ist für diese Arbeit von besonderer Bedeutung. So lassen sich Agenten oder deren Module von unabhängigen Herstellern entwickeln und in die (Modell-)Umgebung des Terminals einsetzen.
5.2.2 JADE und Ontologien
Das aufgezeigte Modell soll mit Hilfe von JADE (Java Agent Development Environment) in Java realisiert werden. JADE ist ein freies Framework zur Entwicklung von Multiagentensystemen in Java unter Einhaltung der FIPA-Spezifikationen636.637 Unter einem Framework verstehen HANSEN und NEUMANN ein „halbfertiges“ Softwaresystem. Aufgrund der darin enthaltenen und aufeinander abgestimmten Softwarekomponenten kann mit relativ geringem Aufwand ein (einer spezifischen Problemstellung) angepasstes Softwaresystem erstellt werden.638 Mit dem Agenten-Framework JADE ist somit die Grundlage für den Einsatz der multiagentenbasierten Technologie gegeben. Der Programmieraufwand kann stärker am Modell erfolgen, weil die technischen Probleme bereits weitgehend gelöst sind.639 LEHNER nennt Ontologien im Rahmen von Methoden zur Repräsentation von Wissen. Ontologien geben ein Vokabular an die Hand, mit dem sichergestellt werden kann, dass mit demselben Begriff auch dasselbe Konzept gemeint ist. So werden Uneinigkeiten über Be-
635
Vgl. Kapitel 2.2.4.3.
636
Die Foundation for Intelligent Physical Agents (FIPA) ist als IEEE Computer Society für die Standardisierung von agentenbasierten Technologien und deren Interoperabilität mit den Standards anderer Technologien betraut, vgl. FIPA (2008).
637
Vgl. o.A. (2008a). Eine umfassende Übersicht von Tools zur Modellierung agentenbasierter Systeme gibt die folgende Internetquelle: o.A. (2008b).
638 639
Vgl. HANSEN, H. R.; NEUMANN, G. (2005), S. 229.
Zu technischen Problemen für die Realisierung von Agentensystemen zählen u.a. die Realisierung der Kommunikation und der Autonomie. Vgl. hierzu Kapitel 2.4.1 sowie WOOLDRIDGE, M. J. (2005), S. 15- 42 und S. 163- 183.
Entwicklung eines multiagentenbasierten Modells zur CT-Prozesskoordination
177
griffe vermieden. In dieser Bedeutung helfen Ontologien bei Problemen der Kommunikation zwischen Personen, zwischen Personen und Maschinen sowie zwischen Maschinen.640 Der Austausch von Nachrichten zwischen den Knoten in einem Netzwerk ist Gegenstand der Informatik. Beispiele stellen u.a. CORBA, SOAP oder auch RMI dar. JADE-Agenten kommunizieren mit Hilfe der FIPA Semantic Language (FIPA-SL). Das JADE-Framework stellt alle notwendigen Klassen zur (Agenten-)Kommunikation und Validierung zur Verfügung. Ontologien helfen dem Agenten zur Beschreibung von Fakten, Annahmen, Hypothesen und Prädikaten im Rahmen einer definierten Domäne. Content Languages, u.a. FIPASL, sind domänenunabhängig.641 In dieser Arbeit kommunizieren Agenten unter Verwendung der mit Protégé definierten PortOntology642 mit Hilfe der FIPA-SL, die im Rahmen einer ACL-Message übertragen wird.643 Für die Realisierung der Agentenkommunikation in JADE werden Ontologien verwendet, die die folgenden Elemente berücksichtigen:644
Concept: Ausdruck, der Entities mit komplexer Struktur abbildet, z.B.: (person :name Leif :age 28)
Dieser Ausdruck beschreibt eine Person mit dem Namen Leif und dem Alter 28. Es sind weitere, auch komplexe Attribute denkbar, z.B. eine Adresse, die gemeinsam durch Angabe der Straße, Hausnummer, Postleitzahl und Ort gegeben ist.
Predicate: Ausdruck, der einen Zustand beschreibt und wahr oder falsch sein kann, z.B.: (isSolution (Vessel :id 1 :start 10h :position 5))
640
Vgl. LEHNER, F. (2006), S. 195- 197. Ein Beispiel ist mit dem Kinderspiel Teekesselchen gegeben: Ein Teekesselchen ist ein Begriff, der mehr als nur eine Bedeutung besitzt (homonym), z.B. ein Jaguar. Ein Jaguar kann neben der Raubkatze in seiner Bedeutung auch als Fahrzeug verstanden werden. Ontologien stellen im Rahmen der Kommunikation sicher, dass es nicht zu diesem Problem kommen kann.
641
Vgl. VAN AART, C. et al. (2002), S. 1ff.
642
Ein Auszug dieser Definition mit Protégé ist im Anhang dargestellt.
643
Vgl. WOOLDRIDGE, M. (2008), S. 175- 180.
644
Vgl. VAN AART, C. et al. (2002), S. 3f.
178
Entwicklung eines multiagentenbasierten Modells zur CT-Prozesskoordination Das Beispiel Predicate zeigt eine Lösung, in der das Schiff mit der Identifikationsnummer 10 zum Startpunkt 10 auf der Position 5 anlegt. Ein Agent ist in der Lage auszuwerten, ob diese Lösung gültig ist oder nicht.
AgentAction: Concept, das eine Aktion abbildet, die von einem Agenten durchgeführt werden kann, z.B.: (assign (QC :id 1)(Bay :id 1))
Mit Hilfe des folgenden Konzepts kann ein Agent einen anderen bitten, die folgende Aktion durchzuführen: Weise Containerbrücke (QC) 1 der Bay (Jobreihe) 1 zu. Es ist wichtig festzuhalten, dass es sich hierbei lediglich um eine Bitte handeln kann, da ein Agent autonom entscheiden kann, ob und wann eine Handlung durchgeführt werden soll. Dies stellt einen entscheidenden Unterschied zur objektorientierten Programmierung dar, da ein Methodenaufruf dem Zwang zur Durchführung entspricht. Mit Hilfe von Protégé lassen sich komplexe Ontologien modellieren. Ein verfügbares Plug-In unterstützt die automatisierte Übertragung in die für JADE erforderliche Struktur.645 Die genannten Elemente der Ontologie sind im Rahmen der Kommunikation zwischen den Agenten notwendig für die semantische Prüfung der Nachricht. Sie werden konkret wie folgt verwendet: Die im Entity Relationship Modell abgebildeten Entities sind als Concept in Protégé realisiert.646 Die (Teil-)Lösungen einer Problemstellung werden zwischen den Agenten mit Hilfe von Predicates kommuniziert. Es werden Predicates für jedes Teilproblem erzeugt, mit denen der verantwortliche Agent seine Lösung kommunizieren kann. Andere Agenten können diese empfangen und prüfen, ob es sich um eine gültige Lösung handelt. Als Beispiel für eine Aktion (AgentAction) könnte der Liegeplatzplaner den Verantwortlichen der Containerbrückenplanung bitten, einen bestimmten Teil des Schiffes mit einer
645
Vgl. CAIRE, G.; CABANILLAS, D. (2004), S. 26. Das mit Hilfe von Protégé abgebildete Modell ist im Anhang dargestellt.
646
Vgl. Abbildung 5-7.
Entwicklung eines multiagentenbasierten Modells zur CT-Prozesskoordination
179
bestimmten Brücke abzufertigen. Der QC-Planer wird dies jedoch nur dann durchführen, wenn ihm diese Aktion nützlich erscheint.647 Agenten kommunizieren mit Hilfe der Agent Communication Language (ACL). ACLNachrichten können zwischen allen Agenten ausgetauscht werden, die diesen Standard verstehen. Eingebettet in das Agentenframework lassen sich dessen Vorteile nutzen und erhöhen die Flexibilität des hier realisierten Modells. Ein Beispiel für die mögliche Erweiterung stellen verteilte Anwendungen dar, die gerade für die durchgeführten Berechnungen vorteilhaft sein können. JADE bietet mit speziellen Klassen die Möglichkeit, die Berechnungen auf mehrere Rechner in einem Netzwerk zu verteilen. Zudem unterstützt JADE ein GUI, das zur Prozessverifikation eingesetzt werden kann.648 Hinsichtlich der Architektur des Softwaresystems bietet JADE Vorteile, weil sich die implementierten Softwarekomponenten an wohldefinierte Schnittstellen zu halten haben. Der Einsatz von Softwarekomponenten erlaubt somit Wiederverwendbarkeit und Austauschbarkeit.649
5.2.3 Protégé
Für die technische Umsetzung und Einsatzfähigkeit im Rahmen des JADEAgentenframeworks ist das vorgestellte Modell des Container-Terminals an unterschiedliche Konventionen gebunden. Zur Unterstützung dieser Aufgaben dient das Tool Protégé650, das von der STANFORD UNIVERSITY entwickelt wurde.651
647
Dieses Element kommt in dieser Arbeit nicht zum Einsatz.
648
Die Überwachung der Kommunikation mit Hilfe des GUI ist im Anhang abgebildet.
649
Vgl. HANSEN, H. R.; NEUMANN, G. (2005), S. 224. Gerade die Austauschbarkeit erlaubt es in dieser Modellformulierung, dass sich auch neue Modellierungsansätze und Lösungsmethoden im Rahmen dieser Architektur untersuchen lassen.
650
Protégé wird für diese Arbeit in der Version 3.3.1 verwendet.
651
Vgl. o.A. (2008c). Protégé ist ein frei verfügbares und auf Java basierendes Tool zur Modellierung wissensbasierter Applikationen mit Ontologien. Zur automatisierten Generierung von Ontologien in Java in der für JADE-Agenten erforderlichen Struktur ist ein Bean Generator für Protégé erforderlich, der von o.A. (2008d) bereitgestellt wird und in Protégé eingesetzt werden kann. Die angegebene Quelle beschreibt diesen Prozess ausführlich.
180
Entwicklung eines multiagentenbasierten Modells zur CT-Prozesskoordination
Mit Hilfe von Protégé lässt sich das in der Konzeption in Kapitel 5.1.1 entwickelte Modell abbilden. Zur Integration in das JADE-Framework ist es erforderlich, die Entities den Klassen Concept, AgentAction oder Predicate zuzuordnen.652 Mit Hilfe des Class- und Slot-Editors lässt sich das Modell technisch realisieren. Das in Abbildung 5-7 gezeigte ERM wird in Protégé abgebildet. Der Ontology Bean Generator erzeugt dann automatisiert die entsprechenden Klassen.653 Es lässt sich eine HTML-basierte Übersicht generieren, die das technisch realisierte Modell aufzeigt.654
5.2.4 Extensible Markup Language (XML)
Um Daten und Parameter des Modells einzulesen, wird die eXtensible Markup Language (XML) verwendet. XML ist eine Meta-Auszeichnungssprache zur Definition anderer domänenspezifischer, semantischer und strukturierter Auszeichnungssprachen. XML umfasst einen Satz von Regeln zur Definition semantischer Tags, die ein Dokument zerteilen und die Bedeutung dieser Teile des Dokuments beschreiben. Im Gegensatz dazu werden mit der Hypertext Markup Language (HTML) die Formatierung und die Auszeichnung von Struktur und Semantik beschrieben.655 Aufgabe von XML ist nicht die Definition von Inhalten auf Präsentationsebene, sondern die Strukturierung von Inhalten.656 Mit Hilfe von Document Type Definitions (DTD) oder XML-Schemata lässt sich die eingesetzte XML-Struktur automatisiert validieren. Der Datenaustausch zwischen zwei Systemen wird dadurch erleichtert. Dies ist insbesondere für die interorganisatorische Kommunikation von Bedeutung und wird als Alternative zum herkömmlichen EDIFACT-Format genannt.657 Die CT-spezifischen Daten können mit Hilfe von XML strukturiert werden. Für die Zusammenarbeit mit Java wird die Programmierschnittstelle JDOM verwendet, die Klassen
652
Vgl. o.A. (2008a).
653
Vgl. VAN AART, C. et al. (2002), S. 4.
654
Ein Ausschnitt des in Protégé abgebildeten Modells ist im Anhang dargestellt.
655
Vgl. HAROLD, E. R. (2004), S. 31ff.
656
Vgl. BIETHAHN, J.; NOMIKOS, M. (2002), S. 57.
657
Vgl. BIETHAHN, J.; NOMIKOS, M. (2002), S. 156- 158.
Entwicklung eines multiagentenbasierten Modells zur CT-Prozesskoordination
181
für die Arbeit mit XML-Dateien zur Verfügung stellt.658 Mit Hilfe von JDOM werden die in XML strukturierten Daten in Java als Baumstruktur abgebildet. Es kann gezielt auf einzelne Elemente zugegriffen werden. Eine XML-Datei ist rein textbasiert und kann - wie Java - plattformunabhängig von jedem Texteditor bearbeitet werden. Der Datensatz und die Parameter der Terminalstruktur werden XML-basiert in das System eingelesen. Durch Austausch der XML-Datei kann die Struktur des CT in dem Modell verändert werden. Hierzu gehören bspw. die Position und Kapazität von Yard-Blöcken, die Kailänge, die Anzahl der Terminal-Ressourcen, deren Eigenschaften usw. Diese Modellparameter lassen sich von den Agenten jederzeit abfragen. Der im Anhang aufgezeigte und verwendete Datensatz kann ersetzt werden, ohne dass Änderungen an dem Programm und seinem Quellcode vorgenommen werden müssen. So lassen sich die in Kapitel 6 durchgeführten Simulationen für unterschiedliche Parameter und Datensätze an die Situation in anderen Häfen flexibel anpassen.659 Die verwendete XML-Struktur zum Einlesen von Daten und Parametern des Terminals ist im Anhang vorgestellt.
5.2.5 Unterstützende Tools
Es existieren unterschiedliche Tools, die die Arbeit mit Java unterstützen und vereinfachen. Eclipse ist eine frei verfügbare Software-Entwicklungsumgebung.660 Zusätzlich kommt die frei verfügbare Statistiksoftware R661 zum Einsatz, mit der die Auswertung der Ergebnisse in Kapitel 6 erfolgt. Alle in Kapitel 6 entwickelten Darstellungen der Untersuchungsergebnisse wurden mit Hilfe von R erzeugt. Ergebnisse, die im Rahmen der Simulation in Java erzeugt werden, können u.a. als CSV-Datei von R gelesen und verarbeitet werden. Nach Darstellung der Anforderungen an ein Modell für die Koordination interdependenter Planungssysteme, der konkreten Modellarchitektur und seiner technischen Realisierung,
658
Vgl. HUNTER, J. (2008). Es werden alle Klassen zur Manipulation von XML-Dokumenten mit Java bereitgestellt.
659
Beispielsweise lässt sich der Einfluss der Kailänge auf die Wartezeit der Containerschiffe vor dem Hafen testen. Unter Einsatz unterschiedlicher XML-Dateien werden jeweils unterschiedliche Werte für den Parameter KAILÄNGE gesetzt. Dieses Experiment wird in Kapitel 6.1.1.2 durchgeführt.
660
Vgl. The Eclipse Foundation (2008). Die angegebene Quelle beschreibt ausführlich die Systemfunktionen und stellt die Entwicklungsumgebung zur Verfügung.
661
Vgl. TEAM, R. D. C. (2007).
182
Entwicklung eines multiagentenbasierten Modells zur CT-Prozesskoordination
soll dieses Modell Gegenstand der Untersuchung im folgenden Kapitel sein. Untersuchungen werden sowohl isoliert als auch übergreifend durchgeführt. Zusammenfassend basiert das hier zu entwickelnde Modell auf den folgenden Grundsteinen:
Es werden bestehende CT-spezifische Modelle und Methoden verwendet, die bereits gute Ergebnisse für ihren jeweiligen Teilbereich gezeigt haben.
Zur technischen Implementierung des Multiagentensystems wird auf das bestehende Framework JADE zurückgegriffen. So sind bereits technische Problemstellungen, u.a. zur Kommunikation von Agenten basierend auf dem FIPA Standard, gelöst.
Das folgende Kapitel setzt das hier entwickelte Modell ein. Es werden Experimente zur Koordination interdependenter Planungssysteme im Rahmen des CTMP aufgezeigt.
Koordination des Planungsprozesses in Container-Terminals
183
6 Koordination des Planungsprozesses in Container-Terminals In diesem Kapitel sollen die Ausführungen der vorangegangenen Kapitel unter Einsatz des in Kapitel 5 entwickelten Modells empirisch getestet werden. Hierfür kommt ein in Abstimmung mit dem Institut für Seeverkehrswirtschaft und Logistik (ISL) in Bremerhaven generierter, auf realistischen Parametern basierender Datensatz zum Einsatz.662 Die vorgestellten Modelle sind sowohl in isolierter als auch in übergreifender Form zu analysieren.663 Das Kapitel gliedert sich wie folgt: Zunächst werden der experimentelle Aufbau und die Durchführung der Experimente vorgestellt. Im Anschluss daran folgt eine zusammenfassende Interpretation der Ergebnisse, in der auch kritisch auf deren Übertragbarkeit einzugehen ist. Den Abschluss bildet die Betrachtung von Erweiterungsmöglichkeiten des Modells.
6.1 Experimenteller Aufbau und Durchführung Die folgende Untersuchung erfolgt empirisch-induktiv und setzt die Ceteris-paribusMethode ein. Es wird der Einfluss einer Größe (Ursache) auf eine andere Größe (Wirkung) untersucht, indem alle anderen Größen konstant gehalten werden. Eine Veränderung des Ergebnisses ist dann auf Veränderungen an diesem Systemelement zurückzuführen.664 Aus vielen gleich verlaufenden Experimenten soll induktiv ein gesetzmäßiger Zusammenhang gefolgert werden. Die untersuchten Größen werden in den nachfolgenden Kapiteln konkret aufgezeigt. Mit dem Einsatz von Metaheuristiken in der Optimierung der Teilprobleme wird dem Planungssystem eine stochastische Komponente hinzugefügt, die in dem Entscheidungsmodell selbst noch nicht vorhanden ist. Es sind für die Experimente mehrfache Replikationen durchzuführen, um die Wirkung einer Maßnahme beurteilen zu können. Für alle nachfol-
662
Vgl. ISL (2008). Dieser Datensatz ist im Anhang abgebildet.
663
In dieser Arbeit ist von einem übergreifenden bzw. zusammenhängenden Modell zu sprechen, wenn die isoliert entworfenen Subsysteme des CT gemeinsam in der Umgebung des Multiagentensystems untersucht werden, in der sie sich gegenseitig beeinflussen.
664
Vgl. WÖHE, G.; DÖRING, U. (2002), S. 34f.
184
Koordination des Planungsprozesses in Container-Terminals
genden Experimente werden jeweils 31 Replikationen durchgeführt. Die Darstellung der Ergebnisse erfolgt mit Hilfe von Boxplots, weil sich so die Verteilung der Ergebnisse der einzelnen Replikationen eines Experimentes aufzeigen lässt.
6.1.1 Methoden- und Parameteranalyse in isolierter Umgebung
In den vorangegangenen Kapiteln konnte aufgezeigt werden, dass die isolierten Modelle bereits gut erforscht sind.665 Die Folge ist, dass die Wirkungen von Modellparametern (für den isolierten Fall!) im Wesentlichen bekannt sind. Aus diesem Grund dient die isolierte Untersuchung der Parameter auch ihrer Validierung. Die Untersuchung in isolierter Umgebung ist wie folgt aufgebaut: Für die implementierten Modelle werden jeweils Methoden zur Lösung des Problems untersucht. Darauf aufbauend werden unter Einsatz der besten gefundenen Methode die Parameter des Modells variiert und ihre Wirkung festgestellt. Dem Vehicle Dispatching Problem kommt eine besondere Rolle zu. Es dient der Integration der Ergebnisse der vorangestellten Entscheidungen. Aus diesem Grund werden relevante Methoden und Parameter erst in Kapitel 6.1.2 angesprochen, in dem das übergreifende MAS-Modell behandelt wird. 6.1.1.1 Analyse von Methoden zur Lösung des BAP
Als Eingangsdaten für das Berth Allocation Problem werden die vom ISL bereitgestellten Daten verwendet.666 Der Planungszeitraum beträgt acht Tage. Insgesamt sind in diesem Zeitraum 62 Schiffe zuzuordnen. Der Typ der Schiffe wird in den Kategorien FEEDER (A), MEDIUM (B) und JUMBO (C) angegeben. Es wird angenommen, dass eine Containerbrücke 20 TEU/ h bearbeiten kann.667 Aus der Anzahl umzuschlagender Container und in Abhängigkeit von dem Typ eines Schiffes wird die Operationszeit geschätzt, die für das BAP konstant bleibt.
665
Vgl. Kapitel 3.2 und auch Kapitel 4.
666
Die Daten werden XML-basiert in das Modell eingelesen. Die Struktur ist im Anhang dargestellt.
667
Moderne Containerbrücken sind in der Lage, deutlich mehr TEU/h umzuschlagen. Vgl. hierzu die Ausführungen in Kapitel 3.1.4. Die Leistungsfähigkeit der Containerbrücken wird in diesem Abschnitt bewusst gering angesetzt, weil so die Auslastung des untersuchten Systems höher liegt.
Koordination des Planungsprozesses in Container-Terminals
185
Abhängig von dem Typ des Schiffs wird angenommen, dass eine unterschiedliche QCAnzahl für die Bearbeitung bereitsteht: Typ des Schiffs Anzahl
A
B
C
2
3
4
operierender QC
Tabelle 6-1: Anzahl operierender QC für Schiffstyp (Annahme)
Beispielsweise ist die Operationszeit für ein Schiff des Typs A, dass 400 TEU umschlagen lassen möchte, wie folgt zu bestimmen: Ein Feederschiff wird von zwei QC bearbeitet. Jede Containerbrücke ist in der Lage, 20 TEU pro Stunde umzuschlagen. Für dieses Schiff v wird die Operationszeit mit 10 Stunden geschätzt: top ,v
400TEU TEU 2 * 20 h
10h .668
Die Kailänge (S) wird in dem Modell auf S=170 Einheiten à 10m gesetzt.669 Zur Lösung des Berth Allocation Problems sollen insgesamt die folgenden vier Verfahren zum Einsatz kommen. Zu diesen gehören zwei Metaheuristiken:
Genetische Algorithmen sowie
Particle Swarm Optimization
Für die Problemstellung werden Genetische Algorithmen eingesetzt, weil sich dieses Verfahren als äußerst flexibel erwiesen hat. Zudem wurde das Verfahren von NISHIMURA, IMAI und PAPADIMITRIOU bereits erfolgreich in der Liegeplatzplanung mit anderer Problemformulierung eingesetzt.670 Die Particle Swarm Optimization ist eine bislang wenig erforschte Metaheuristik, die von BRODERSEN und SCHUMANN speziell für den Einsatz in
668
Es wird dabei angenommen, dass genau zwei Containerbrücken ohne Verzögerungen mit einer Umschlagsleistung von jeweils 20 TEU/h an dem Schiff operieren.
669 670
Die Parameter des Modells sind in Kapitel 3.2.2.2 ausführlich beschrieben.
Vgl. Kapitel 2.2.3.3.2 für die Darstellung genetischer Algorithmen und Kapitel 3.2.2.1 für die Anwendung genetischer Algorithmen in der Liegeplatzplanung.
186
Koordination des Planungsprozesses in Container-Terminals
kombinatorischen Problemstellungen modifiziert wurde.671 Diese Problemstellung soll einen Ansatz geben, die Metaheuristik in einer komplexen Anwendung zu testen. Eine Lösung des Berth Allocation Problems wird in einem Vektor der Länge V (=Anzahl der Schiffe im Planungszeitraum) abgebildet. Jedes Element des Vektors beschreibt die zugewiesene Kaiposition des Schiffes. Die Schiffe werden anschließend in der Reihenfolge ihrer Ankunft - unter Berücksichtigung der zugewiesenen Position - auf den frühest möglichen Anlegezeitpunkt geschoben. Die Ergebnisse der Metaheuristiken sollen mit einer Heuristik verglichen werden, die speziell für das BAP entwickelt und von GUAN und CHEUNG vorgestellt worden ist:
Composite Heuristic672
Neben diesen Methoden kommt ein randomisiertes Verfahren zum Einsatz, bei dem die Schiffspositionen zufällig bestimmt werden. Es ist zu erwarten, dass diese Methode die schlechtesten Ergebnisse liefert, weil eine rein zufallsbasierte Vorgehensweise nicht in der Lage ist, aus vergangenen Lösungen zu „lernen“. Es ist dennoch sinnvoll, dieses Verfahren einzusetzen, weil sich durch einen Vergleich die Qualität der anderen Verfahren zur Lösung des BAP abschätzen lässt:
Randomisiertes Verfahren
Die Parametereinstellungen für GA und PSO sind in den folgenden Tabellen abgebildet.673
671
Vgl. Kapitel 2.2.3.3.3.
672
Vgl. Kapitel 3.2.2.2.
673
An diesen Parametereinstellungen für die verwendeten Metaheuristiken lässt sich ein wesentlicher Kritikpunkt dieser Vorgehensweise anbringen. Die Auswahl der Parameter erfolgt quasi willkürlich. Die Einstellung von Parametern einer Metaheuristik an eine bestimmte Problemstellung kann als Optimierungsproblem betrachtet werden. Hier werden nur wenige mögliche Parametereinstellungen untersucht. Eine methodische Vorgehensweise zur systematischen Konfiguration von Metaheuristiken zeigt MONETT DÍAZ mit Hilfe eines agentenbasierten Ansatzes, vgl. MONETT DÍAZ, D. (2005). Die Agenten übernehmen die Konfiguration der Verfahren für den menschlichen Experten.
Koordination des Planungsprozesses in Container-Terminals Experiment
187
Mutationsrate
Crossoverrate
Selektionsrate
Populationsgröße
Iterationen
1 (GA #1)
20
20
60
100
500
2 (GA #2)
40
40
60
100
500
3 (GA #3)
60
60
60
100
500
Nr.
4 (GA #4)
80
80
60
100
500
5 (GA #5)
100
100
60
100
500
6 (GA #6)
20
20
80
100
500
7 (GA #7)
40
40
80
100
500
8 (GA #8)
60
60
80
100
500
9 (GA #9)
80
80
80
100
500
10 (GA #10)
100
100
80
100
500
Tabelle 6-2: BAP-Parametereinstellungen für GA Experiment
Schwarmgröße
Iterationen
Mutationsrate
1 (PSO #1)
20
2500
0
2 (PSO #2)
20
2500
50
3 (PSO #3)
20
2500
100
4 (PSO #4)
60
834
0
5 (PSO #5)
60
834
50
6 (PSO #6)
60
834
100
7 (PSO #7)
100
500
0
8 (PSO #8)
100
500
50
9 (PSO #9)
100
500
100
Nr.
Tabelle 6-3: BAP-Parametereinstellungen für PSO
Minimiert wird die Summe der gewichteten Aufenthaltszeit aller Schiffe im Hafen in Stunden. Die Ergebnisse werden mit der in Kapitel 3.2.2.2 angegebenen Zielfunktion bewertet. Abbildung 6-1 zeigt die Ergebnisse der beiden Metaheuristiken unter Einsatz der in den Tabellen genannten Parametereinstellungen als Boxplots.
188
Koordination des Planungsprozesses in Container-Terminals
2600 2500 2400 2300
Summe der gewichteten Aufenthaltszeit in h
2700
BAP Genetische Algorithmen
GA #1
GA #2
GA #3
GA #4
GA #5
GA #6
GA #7
GA #8
GA #9
GA #10
2250 2240 2230 2220 2210 2200
Summe der gewichteten Aufenthaltszeit in h
2260
BAP Particle Swarm Optimization
PSO #1
PSO #2
PSO #3
PSO #4
PSO #5
PSO #6
PSO #7
PSO #8
PSO #9
Abbildung 6-1: BAP-Ergebnisse für GA und PSO (Boxplots)
Zu beachten ist die unterschiedliche Skalierung der Ordinate für genetische Algorithmen und die Particle Swarm Optimization. Die gefundenen Aufenthaltszeiten der Particle Swarm Optimization weisen eine deutlich geringere Varianz auf und liegen im Durchschnitt deutlich unter denen des Genetischen Algorithmus.674 Die folgende Tabelle zeigt zusammenfassend den Mittelwert, Median und die Standardabweichung der Summe der gewichteten Aufenthaltszeit aller Schiffe in Stunden.
674
Vgl. hierzu auch Tabelle 6-4.
Koordination des Planungsprozesses in Container-Terminals Experiment
GA
PSO
189
Nr.
1
2
3
4
5
6
7
8
9
10
mean
2358
2370
2329
2484
2524
2368
2403
2421
2450
2482
median
2350
2356
2313
2476
2520
2370
2394
2425
2449
2492
sd
45.22
53.05
56.11
82.52
78.16
39.34
57.36
62.18
65.88
69.96
mean
2224
2230
2238
2225
2230
2232
2225
2232
2233
-
median
2227
2232
2237
2226
2232
2233
2228
2234
2233
-
sd
12.66
12.00
6.89
10.96
11.34
13.47
10.03
10.79
11.21
-
Tabelle 6-4: BAP-Ergebnisse für GA und PSO
In der Tabelle ist jeweils der minimale Wert aller Einstellungen gekennzeichnet. Die Aufenthaltszeiten der Schiffe liegen bei Einsatz der Particle Swarm Optimization unter den von dem GA gefundenen Ergebnissen. Auch die Standardabweichung fällt geringer aus. Bisher wurden lediglich die eingesetzten Metaheuristiken verglichen. Abbildung 6-2 zeigt den Vergleich mit der Composite Heuristic und dem randomisierten Verfahren. Die Heuristik von GUAN und CHEUNG enthält keine stochastische Komponente. Es werden deshalb keine Replikationen durchgeführt.
2700 2600 2500 2400 2300
CH
2200
Summe der gewichteten Aufenthaltszeit in h
BAP- Methoden
PSO
GA
Random
Abbildung 6-2: Vergleich eingesetzter BAP-Methoden
Die Abbildung zeigt, dass der Einsatz der Particle Swarm Optimization zu der minimalen Aufenthaltszeit führt.675 Die Ergebnisse der PSO liegen dabei immer unterhalb der als
675
Für GA sind die Ergebnisse von Parametereinstellung #3 angegeben, für die PSO wird Einstellung #1 verwendet, weil hier die minimale Zielgröße erzielt worden ist. Vgl. Tabelle 6-2 und Tabelle 6-3 für die Parametereinstellungen der Metaheuristiken und Tabelle 6-4 für die Darstellung der Ergebnisse.
190
Koordination des Planungsprozesses in Container-Terminals
Benchmark eingesetzten Composite Heuristic nach GUAN und CHEUNG. Die Aufenthaltszeiten des GA liegen über denen der PSO und im Durchschnitt auch über den Ergebnissen der CH. Die Leistung von GA, PSO und CH zeigt sich auch durch den Vergleich mit dem randomisierten Verfahren. Die Heuristiken weisen deutlich geringere Aufenthaltszeiten für die Schiffe auf. Für den GA wird das Java-API JGAP verwendet, das Klassen für den Einsatz von Genetischen Algorithmen in Java zur Verfügung stellt und von MEFFERT veröffentlicht worden ist.676 Für die PSO wird eine vom Institut für Wirtschaftsinformatik der Universität Göttingen bereitgestellte Methode verwendet. 6.1.1.2 Analyse von BAP-Parametern
Die Kailänge (S) stellt einen Parameter der Liegeplatzplanung dar.677 Um die Wirkung dieses Parameters auf die Zielgröße beobachten zu können, soll S im Intervall [1000, 2200] variiert werden. Alle anderen Größen werden konstant gehalten. Zur Lösung des Problems wird die Particle Swarm Optimization mit der Parametereinstellung #1 eingesetzt, weil diese Methode in Kapitel 6.1.1.1 zu den besten Ergebnissen geführt hat. Zu erwarten ist, dass die Wartezeit der Schiffe mit zunehmender Kailänge sinkt, weil für die Bearbeitung der Schiffe mehr Ressourcen zur Verfügung stehen. Die folgende Tabelle zeigt die Ergebnisse für variierende Kailängen. Die Tabelle zeigt die Summe der gewichteten Aufenthaltszeit im Hafen in Stunden. Die Operationszeit ist für das Berth Allocation Problem konstant.
676 677
Vgl. MEFFERT, K. (2008).
In der Modellformulierung von GUAN und CHEUNG entspricht die Kailänge dem Parameter S. Vgl. Kapitel 3.2.2.2.
Koordination des Planungsprozesses in Container-Terminals
191
Kailänge in m
1000
1100
1200
1300
1400
1500
1600
1700
1800
1900
2000
2100
2200
4402
3568
3031
2808
2576
2430
2315
2222
2191
2163
2145
2139
2137
w
2266
1432
894.5
672.5
440.5
293.6
179.2
86.45
55.42
27.19
9.26
2.90
0.78
op
2136
2136
2136
2136
2136
2136
2136
2136
2136
2136
2136
2136
2136
'TIP
-
834
537
223
230
146
115
93
31
28
18
6
2
sd
81.38
99.90
40.58
33.29
25.84
27.17
17.40
9.19
3.62
6.27
2.87
0.54
1.26
und Zielgröße in h
¦ TIP ¦t
¦t
Tabelle 6-5: BAP-Ergebnisse unter Variation der Kailänge
Die Modellergebnisse bestätigen die Vermutung, dass die Wartezeit für Containerschiffe mit zunehmender Kaifläche und unter sonst gleichen Umständen im isoliert betrachteten Modell sinkt. Zudem lässt sich der abnehmende Grenznutzen zusätzlicher Kaieinheiten feststellen: Unter Einsatz einer geringen Anzahl von Kai-Ressourcen, z.B. einer Kailänge von 1000 m, bewirkt die Hinzunahme eine erhebliche Reduktion der Zielgröße, während dieser Effekt mit Verlängerung des Kais abnehmend ist. Die Verlängerung von S erfolgt sukzessiv um jeweils 100 m. Die folgende Abbildung stellt die Ergebnisse grafisch dar.
3500 3000 2500
Fitnesswert in h
4000
4500
BAP - Variation der Kailänge
1000
1100
1200
1300
1400
1500
1600
1700
1800
1900
2000
2100
2200
Kailänge in m
Abbildung 6-3: Variation der Kailänge
Die Abbildung zeigt die Summe der gewichteten Aufenthaltszeit der Containerschiffe im Hafen in Abhängigkeit von der Kailänge. Die Ausprägung der Zielgröße entspricht der
192
Koordination des Planungsprozesses in Container-Terminals
erwarteten Entwicklung. Dieser Effekt ist jedoch insbesondere auf das isolierte Modell zurückzuführen. Für das zusammenhängende Modell darf dieser Effekt nicht ohne weiteres angenommen werden, weil die Aufenthaltszeit der Schiffe nicht allein durch die Verlängerung der Kailänge sinken kann.678 Die simulierten Werte lassen sich im Rahmen einer einfachen Investitionsrechnung untersuchen, um für gegebene Kostensätze die optimale Kailänge in diesem betrachteten Modell zu bestimmen. Hierfür sind die folgenden Zahlen näher zu betrachten: Kailänge in m und
1100
1200
1300
1400
1500
1600
1700
1800
1900
2000
2100
2200
834
537
223
230
146
115
93
31
28
18
6
2
834
1371
1594
1824
1970
2085
2178
2209
2237
2255
2261
2263
k
k
k
k
k
k
k
k
k
k
k
k
k
2k
3k
4k
5k
6k
7k
8k
9k
10k
11k
12k
834 -
1371 -
1594 -
1824 -
1970 -
2085 -
2178 -
2209 -
2237 -
2255 -
2261 -
2263 -
k
2k
3k
4k
5k
6k
7k
8k
9k
10k
11k
12k
Zielgröße in h
Reduktion in h Reduktion in h (kumuliert) K K (kumuliert)
Differenz
Tabelle 6-6: Nutzen und Kosten der verlängerten Kailänge
Die Verlängerung der Kailänge verursacht Kosten, die durch die Reduktion der Wartezeit amortisiert werden sollen. Die entstehenden Kosten sind mit den Nutzeneinheiten, gemessen in der kumulierten Reduktion, zu vergleichen. Um beurteilen zu können, ob der Ausbau des Kais lohnend ist, sind die Kosten, gemessen in GE, auf ein vergleichbares Maß umzurechnen. Dies kann wie folgt durchgeführt werden: Beispielsweise verursacht die Verlängerung des Kais auf 1100 Meter k Kosten. Mit diesem eingesetzten Betrag ist eine Reduktion der Zielgröße um mindestens h Stunden zu erreichen.
678
Hier wirkt die Modellannahme, dass Schiffe mit einer konstanten Operationszeit bearbeitet werden und mit der Abfertigung begonnen wird, sobald eine Kairessource zur Verfügung steht. Durch die Integration in das zusammenhängende Modell entfällt diese Annahme. Auch übergreifend wird mit der Verlängerung des Kais eine Reduktion der Aufenthaltszeit angestrebt. Ob sich dieser Effekt einstellt, ist aber von weiteren Faktoren abhängig.
Koordination des Planungsprozesses in Container-Terminals
193
Zur Beurteilung der optimalen Kailänge (S*) [für dieses Ergebnis] sind zwei verschiedene Zielfunktionen (Z) denkbar: a) Die Minimierung der Aufenthaltszeit unter Berücksichtigung eines angemessenen Gewinns, mindestens jedoch Null, oder b) die Maximierung des Gewinns unter Berücksichtigung einer angemessenen Aufenthaltszeit. Der Gewinn ist definiert als die Differenz zwischen Nutzen und Kosten der Kailängenerhöhung. Die Quantifizierung des Begriffs „angemessen“ ist von dem CT-Betreiber zu beurteilen. Beide Zielsetzungen sind im Rahmen der Entscheidungsfindung für den CT von hoher Bedeutung: Um die Konkurrenzfähigkeit zu erhalten, ist der CT auf eine geringe durchschnittliche Aufenthaltszeit angewiesen. Gleichzeitig sind die Gewinne des Terminals zu maximieren, um das Überleben des Unternehmens zu sichern. Nur wenn der Betreiber beide Zielsetzungen vereinbaren kann, kann langfristig das Überleben des CT gesichert werden. Fänden die Kosten in dem Modell zur Beurteilung der optimalen Kailänge keine Berücksichtigung, dann würde sich für S* [für beide Zielsetzungen] die maximal untersuchte Größe (S*=2200m) ergeben, weil mit jeder Verlängerung der Kailänge eine Reduktion der durchschnittlichen Aufenthaltszeit einhergeht. 679 In Abhängigkeit von k und Z existieren unterschiedliche Handlungsempfehlungen: Ist k groß, dann muss die Reduktion der Aufenthaltszeit sehr stark ausfallen, um die Erweiterung der Kailänge zu begründen. Ist k klein, dann reicht eine geringe Aufenthaltszeitreduktion für die Empfehlung der Erweiterung. Unter Berücksichtigung der Kosten ergeben sich die folgenden Ergebnisse für die beiden betrachteten Ziele. Die Tabelle gibt an, für welchen Kostensatz die jeweilige Kailänge für die Zielsetzungen optimal ist.
679
Dies entspricht k=0. Vgl. Tabelle 6-7.
194 Kailänge in m
Z a)
Z b)
Koordination des Planungsprozesses in Container-Terminals 1100
1200
1300
1400
1500
1600
1700
1800
1900
2000
2100 205.55
834
685.5
531.33
456
394
347.5
311.14
276.13
248.56
225.5
= k
1.06 >= k
1.06
19
-
-
Tabelle 6-13: Optimale Containerbrückenanzahl (m*) in Abhängigkeit von Z und k
Der Nutzen zusätzlicher Containerbrücken wird in Höhe der Reduktion der durchschnittlichen Aufenthaltszeit in Stunden angegeben. Um diese Größe mit den Kosten vergleichen zu können, sind die Kosten für die Bereitstellung einer zusätzlichen Containerbrücke in Höhe der minimal geforderten Reduktionszeit (ebenfalls in Stunden) anzugeben. Die Tabelle zeigt die optimale Anzahl einzusetzender Containerbrücken in Abhängigkeit von k und der gewählten Zielsetzung. Die folgende Abbildung stellt dieses Ergebnis grafisch dar.
k
0
2
4
6
8
10
12
Kostensatz k für m*
9
10
11
12
13
14
15
16
17
18
m*
Abbildung 6-10: Optimale Containerbrückenanzahl (m*) in Abhängigkeit von Z und k
Die durchgezogene Linie stellt die Aufenthaltszeitminimierung und die gestrichelte Linie die Gewinnmaximierung dar. Auch hier lässt sich ein Widerspruch in der Empfehlung der optimalen Anzahl einzusetzender Containerbrücken für unterschiedliche Kostensätze auf-
Koordination des Planungsprozesses in Container-Terminals
205
zeigen. Daraus ergibt sich, dass auch in diesem Entscheidungsbereich die Auswahl der einzusetzenden Ressourcen von mehr Kriterien abhängig ist, als in diesem Modell berücksichtigt werden. Das Modell kann deshalb nur einen ersten Ansatz für die Entscheidung aufzeigen. 6.1.1.5 Analyse von Methoden zur Lösung des SLP
Die Eingangsdaten des Storage Location Problems basieren - wie im Crane Scheduling Problem - auf den Ergebnissen der Liegeplatzplanung. Dies liegt darin begründet, dass mit dem Liegeplatzplan feststeht, wann und wo ein Containerschiff anlegen wird. Erst wenn diese Daten bekannt sind, lassen sich die Lagerstandorte für die Container im Yard transportdistanzminimal zuordnen. Gleichzeitig deckt dieses Vorgehen ein Problem auf: Auch die Liegeplatzplanung benötigt die Daten der Containerstandorte im Yard, weil die Schiffe dann transportdistanzminimal den Liegeplätzen am Kai zugeordnet werden können.692 Die Minimierung der Transportdistanz reduziert direkt die Kosten des CT-Betreibers und kann die Reduktion der Operationszeit bewirken, wenn die Entscheidungen des Terminals optimal abgestimmt sind. Das Layout des Lagers ist im Anhang dargestellt. Für jeden Block wird einheitlich eine Kapazität von 720 TEU angenommen. Insgesamt stehen dem CT in diesem Modell 30 Blöcke zur Verfügung. Folgende SLP-Methoden kommen für den ersten Teil der Problemstellung zum Einsatz:
Regelbasiertes Verfahren nach MURTY, Fill Ratio Equalization (FRE)
Genetische Algorithmen
Die Einstellungen des GA sind mit der folgenden Tabelle gegeben.
692
Zu den Abhängigkeiten der isolierten Planungssysteme vgl. Kapitel 3.3.
206
Koordination des Planungsprozesses in Container-Terminals Experiment
Mutationsrate
Crossoverrate
Selektionsrate
Populationsgröße
Iterationen
1 (GA #1)
20
20
60
50
50
2 (GA #2)
40
40
60
50
50
3 (GA #3)
60
60
60
50
50
Nr.
4 (GA #4)
80
80
60
50
50
5 (GA #5)
dynamisch
dynamisch
60
50
50
6 (GA #6)
20
20
80
50
50
7 (GA #7)
40
40
80
50
50
8 (GA #8)
60
60
80
50
50
9 (GA #9)
80
80
80
50
50
10 (GA #10)
dynamisch
dynamisch
80
50
50
Tabelle 6-14: SLP-Einstellungen für GA
Zur Lösung des klassischen Transportproblems als zweiten Teil des SLP kommen die folgenden Methoden zum Einsatz:
Nordwesteckenregel (NWE)
Vogel´sche Approximationsmethode (VAM)
NWE und VAM stellen Eröffnungsheuristiken des klassischen Transportproblems dar. Ihre Anwendung führt in der Regel nicht zu einer optimalen Lösung. Die optimale Lösung lässt sich mit Hilfe der Simplex-Methode erzielen. Aufgrund der besonderen Struktur des Transportproblems wurde die folgende Methode entwickelt, die ebenfalls das Auffinden des Optimums garantiert und hier zum Einsatz kommen soll:
Modified-Distribution-Methode (MODI)
Die folgende Abbildung zeigt die Ergebnisse, die mit Hilfe von FRE nach MURTY und unter Einsatz genetischer Algorithmen gefunden wurden. Die Transportzuordnung erfolgt
Koordination des Planungsprozesses in Container-Terminals
207
mit der Modified-Distribution-Methode unter Einsatz einer der genannten Eröffnungsheuristiken.693 Die Zielsetzung minimiert das Zuordnungsungleichgewicht im Yard in TEU.694
3000
4000
5000
6000
7000
Zuordnungsungleichgewicht (wasserseitig) in TEU
SLP - GA und FRE
GA #1
GA #2
GA #3
GA #4
GA #5
GA #6
GA #7
GA #8
GA #9
GA #10
Murty
Abbildung 6-11: SLP-Ergebnisse mit GA und FRE nach MURTY
Mit Hilfe des GA lässt sich das Zuordnungsungleichgewicht im Yard in Abhängigkeit von der Parametereinstellung senken. Der Fill-Ratio-Equalization-Ansatz nach MURTY
ET AL.
berücksichtigt weder die Verweilzeit von Exportcontainern im Yard vor der Ankunft des Containerschiffs, noch die Verweildauer von Importcontainern bis zum Weitertransport ins Hinterland.695 Der GA ist in der Lage, diesen Aspekt zu berücksichtigen und kann deshalb das Zuordnungsungleichgewicht weiter reduzieren. Im folgenden Abschnitt ist wiederum auf die Parameter des Modells einzugehen. 6.1.1.6 Analyse von SLP-Parametern
Für die Analyse von Parametern des Storage Location Problems sollen die folgenden Ansatzpunkte untersucht werden:
Verschieben der Positionen der Lagerplätze (Yard-Blöcke)
693
Für den Rechenaufwand der MODI-Methode ist bei dieser Problemstellung kaum relevant, welche der beiden Eröffnungsmethoden zum Einsatz kommen.
694
Vgl. Kapitel 3.2.4.2.
695
Vgl. Kapitel 3.2.4.2.
208
Koordination des Planungsprozesses in Container-Terminals Veränderung der Kapazitäten der Lagerplätze
Im Gegensatz zu Parameteruntersuchungen der vorangegangenen Modelle wirken sich diese Einstellungen in isolierter Betrachtung nicht auf die Aufenthaltszeit der Schiffe aus.696 Mit Betrachtung des SLP kommt jedoch die Transportdistanz als Element des Zielsystems des CTMP hinzu. Insgesamt werden fünf unterschiedliche Experimente durchgeführt, wie in Abbildung 6-12 dargestellt ist. Versuch #1: Schieben des Lagers nach oben (leicht) Lager mit Blöcken
Versuch #3: Schieben des Lagers nach rechts (stark)
Versuch #4: Erhöhung der Lagerkapazität (++) Kai
Versuch #5: Reduzierung der Lagerkapazität (--)
Versuch #2: Schieben des Lagers nach unten (stark)
Abbildung 6-12: Versuchsaufbau SLP-Parameter
Es werden drei unterschiedliche Positionen des Lagers untersucht. Hinzu kommt die Veränderung der Lagerkapazität. Die folgende Abbildung zeigt den Einfluss dieser Parameter auf die Transportdistanz. Alle Experimente werden im Anschluss an die BAP-Zuordnung durchgeführt.
696
Erst im übergreifenden Modell in Kapitel 6.1.2 wirken die im SLP bestimmten Standorte für Container im Yard auf die Aufenthaltszeit, weil die Operationszeit der Schiffe durch die Transportdistanz der VC beeinflusst wird. Die Auswahl der Zielfunktion nach MURTY ET AL. ist sinnvoll, weil sie die modellübergreifende Wirkung der SLP-Entscheidung berücksichtigt.
209
800
900
1000
1100
1200
SLP Parameter
700
Durchschnittliche Transportdistanz zwischen Kai und Yard in m
Koordination des Planungsprozesses in Container-Terminals
Exp #1
Exp #2
Exp #3
Exp #4
Exp #5
Abbildung 6-13: Variation der SLP-Parameter
Die Variation von SLP-Parametern dient als Test, um die Wirkungsweise des Modells zu verstehen und die Implementierung zu validieren. Betrachtet wird die durchschnittliche Transportdistanz für die VC zwischen Kaiposition und Yard in m.697 Für die gesetzten Parametereinstellungen zeigt sich das erwartete Bild. Die Verlegung der Lagerplätze in entfernte Bereiche führt erwartungsgemäß zu einer Erhöhung der durchschnittlichen Transportdistanz. Die Experimente #4 und #5 untersuchen eine Veränderung der Block-Kapazitäten. Steigt die Block-Kapazität, dann steigt damit der Spielraum für die Zuordnung von Lagerplätzen. Dies führt in der durchgeführten Untersuchung zu einer Reduzierung der durchschnittlichen Transportdistanz, während die Kapazitätssenkung in Experiment #5 zu einer Verlängerung führt. Die Ergebnisse kommen unter Berücksichtigung einer für die Yardplanung akzeptablen Verteilung zustande.698 Nachdem die Teilprobleme des CTMP in ihrer isolierten Form betrachtet worden sind,699 erfolgt in dem folgenden Abschnitt die Untersuchung der Problemstellungen in dem übergreifenden Modell der MAS-Umgebung.
697
Die Eigenschaften von Van Carriern werden in Kapitel 3.1.4 ausführlich vorgestellt.
698
Für die Optimierung wird der GA mit der Parametereinstellung #5 verwendet, vgl. Kapitel 6.1.1.5.
699
Das Vehicle Dispatching Problem ist aufgrund seiner übergreifenden Bedeutung bislang davon ausgenommen.
210
Koordination des Planungsprozesses in Container-Terminals
6.1.2 Analyse von Koordinationsinstrumenten in MAS-Umgebung
Die in die MAS-Umgebung eingesetzten Teilprobleme bilden gemeinsam die übergreifende Problemstellung, die als Container-Terminal Management Problem bezeichnet werden soll.700 Das Problem lässt sich durch seinen Entscheidungsbaum veranschaulichen, der sich bei (sequenziellem) Durchlauf der einzelnen Planungssysteme des CTMP ergibt.
BAP gute BAP Lösungen
CSP …
…
gute CSP Lösungen
SLP …
…
gute SLP Lösungen
VDP …
gute VDP Lösungen
CTMP- Lösung
Abbildung 6-14: Entscheidungsbaum des CTMP
Abbildung 6-14 zeigt den Entscheidungsbaum im übergreifenden Modell, das die isolierten Modelle integriert. Wie in der vorangegangenen Untersuchung aufgezeigt werden konnte, ergeben sich für jedes Einzelproblem mehrere gute Lösungen. Das VDP-Ergebnis der letzten Stufe entspricht dem Ergebnis des CTMP. Die sequenzielle Koordination entspricht dem unidirektionalen Durchlaufen des Entscheidungsbaums. Der Einsatz dieser Koordinationsform lässt eine hohe Varianz erwarten, weil sich die Anzahl möglicher Lösungen mit jeder Stufe vervielfacht. In anspruchsvolleren Koordinationsinstrumenten müssen Rücksprünge auf vorangegangene Stufen, auch in andere Knoten als die Wurzel, möglich sein.701
700 701
Vgl. hierzu die Modellentwicklung der Architektur in Kapitel 5.
Diese Forderung steht im Einklang mit der Beschreibung von Koordinationsinstrumenten in Kapitel 2.3.3. In einem iterativen Ansatz soll mit jeder Iteration ein besseres Ergebnis erzielt werden. Hierfür ist es notwendig, jeden Schritt in einem zuvor noch nicht durchlaufenen Knoten zu beginnen.
Koordination des Planungsprozesses in Container-Terminals
211
Es soll untersucht werden, wie sich die CTMP-Lösung unter sequenzieller Koordination der Teilprobleme verhält. Anschließend ist die Frage zu stellen, welche Möglichkeiten zur Verbesserung der Qualität der Lösung existieren. Die folgenden Experimente werden im Rahmen der MAS-Umgebung durchgeführt, die die isolierten Modelle integriert. Die Untersuchung gliedert sich wie folgt: Zunächst sind mit Kapitel 6.1.2.1 Teilmengen des CTMP zu betrachten, weil sie in der Literatur von besonderer Bedeutung sind:702
BAP und CSP
BAP und SLP
Im Anschluss daran folgt in Kapitel 6.1.2.2 die übergreifende Untersuchung, in der alle Elemente des CTMP zu berücksichtigen sind:
BAP, CSP, SLP und VDP
6.1.2.1 Untersuchung von Teilmengen des CTMP
In diesem Abschnitt sollen zunächst zusammenhängende Teilmengen des CTMP untersucht werden. Dieses betrifft die Koordination von BAP und CSP sowie von BAP und SLP. 6.1.2.1.1 Koordination von BAP und CSP
Von ADAM
ET AL.
werden Instrumente zur Koordination interdependenter Planungssyste-
me beschrieben. In komplexen Systemen ist die Simultanplanung nicht durchführbar. Die sequenzielle Planung zeigt Probleme auf, die nicht akzeptiert werden können. Aus diesem Grund soll in diesem Abschnitt die Wirkung eines iterativen Ansatzes getestet werden. ADAM
ET AL.
sehen das iterative Vorgehen als Gegenentwurf zur Simultanplanung.703
PARUNAK führt aber an, dass sich iterative Systeme auch chaotisch verhalten können.704
702
Vgl. u.a. MEISEL, F.; BIERWIRTH, C. (2005) für die Untersuchung von BAP und CSP sowie MOORTY, R.; CHUNG-PIAW, T. (2006) für die Untersuchung von BAP und SLP. Auf diese Probleme wird auch in Kapitel 3.3 eingegangen.
703
Vgl. ADAM, D. et al. (2004), S. 82.
704
Vgl. PARUNAK, H. (1991), S. 241- 259.
212
Koordination des Planungsprozesses in Container-Terminals
Unter Einsatz der in den vorangegangenen Abschnitten bestimmten Methoden und deren Einstellungen werden beide Problembereiche iterativ durchlaufen und passen jeweils ihre Eingangsdaten an die Situation des abhängigen Bereichs an. Diese Iterationen werden für 31 Replikationen fünfmal durchgeführt. Es ist zu untersuchen, ob sich durch einfache Iteration ein im Durchschnitt besser koordiniertes Ergebnis finden lässt.705 Die folgende Abbildung zeigt die Ergebnisse, die in diesem Versuch beobachtet wurden.
30 25 20
Durchschnittliche Aufenthaltszeit in h
BAP und CSP - Verlauf (iterativ)
Iteration 1 (=Sequenz)
Iteration 2
Iteration 3
Iteration 4
Iteration 5
Abbildung 6-15: Iterativer Verlauf für BAP und CSP
Die Abbildung zeigt, dass der unkontrollierte iterative Verlauf für BAP und CSP nicht zu der gewünschten Verbesserung im Laufe fortschreitender Iterationen führt.706 Die Ergebnisse der Iterationen in der Abbildung zeigen die durchschnittliche Aufenthaltszeit der Containerschiffe in Stunden, nachdem die CSP Planung erfolgt ist. Die erste Iteration entspricht dem Ergebnis der sequenziellen Planung. In den folgenden Iterationen werden mit Hilfe der Ergebnisse des CSP die Operationszeiten für das BAP angepasst und erneut durchlaufen.
705
Der iterative Ansatz zur Koordination interdependenter Planungssysteme wird ebenfalls von MEIER und SCHUMANN für BAP und CSP für insgesamt 12 Iterationen durchgeführt. Vgl. MEIER, L.; SCHUMANN, R. (2007).
706
Der Verlauf wird als unkontrolliert charakterisiert, weil es im Rahmen der Iteration zwischen BAP und CPS zu keiner Anpassung von Modellparametern kommt. Denkbar wäre bspw. die Anpassung einer Gewichtung der Zielfunktion, um auf bestimmte Eigenschaften des Ergebnisses des anderen Planungssystems zu reagieren.
Koordination des Planungsprozesses in Container-Terminals
213
Für die genaue Untersuchung der iterativen Ergebnisse sind in der folgenden Tabelle der Mittelwert, der Median und die Standardabweichung für jede Iteration angegeben. Sequenz
Iteration 2
Iteration 3
Iteration 4
Iteration 5
mean
23.47
23.29
23.17
22.69
23.99
median
23.18
22.32
21.95
22.69
23.04
sd
3.49
2.92
4.15
2.93
3.81
Tabelle 6-15: Ergebnisse der iterativen Untersuchung für BAP und CSP
Die beobachtete durchschnittliche Aufenthaltszeit im Hafen liegt weiterhin im Rahmen der sequenziell festgestellten Zeit. Es ist keine signifikante Verbesserung durch diese einfache Koordinationsform festzustellen.707 Dennoch lässt sich beobachten, dass der Median bis zur dritten Iteration deutlich sinkt und für alle Iterationen unter dem sequenziellen Niveau verbleibt. Insgesamt kann das Ergebnis der iterativen Koordination jedoch nicht befriedigend sein. Im Folgenden ist deshalb ein weiterer Ansatz für die Koordination dieser Teilbereiche zu untersuchen. Die Lösung des BAP erfolgt im Weiteren mit dem GA, weil gezielt die Variabilität in der Population dieses Verfahrens genutzt werden soll. Aus der isolierten Modellbetrachtung können zusammenfassend die folgenden Erkenntnisse für die Gestaltung des MAS-basierten Ansatzes gewonnen werden:
Das CSP-Ergebnis ist maßgeblich von der Ausgangslösung der Eröffnungsheuristik abhängig.
Das absolut beste BAP-Ergebnis führt nicht immer zu der für das CSP optimalen Ausgangslösung.
Mit Hilfe der CSP-Eröffnungsheuristiken lässt sich relativ schnell, d.h. ohne mehrfache Iterationen, eine Lösung bestimmen.
707
Zu einem ähnlichen Ergebnis gelangen auch MEIER und SCHUMANN, vgl. MEIER, L.; SCHUMANN, R. (2007).
214
Koordination des Planungsprozesses in Container-Terminals
Aus diesen Erkenntnissen lässt sich der folgende MAS-unterstützte Ansatz entwickeln, der insbesondere die Unabhängigkeit der Agenten unterstreicht und gleichzeitig die Kommunikationsfähigkeit von Agenten nutzt, um die Qualität der CTMP-Lösung zu verbessern. Mit Blick auf die genannten Aspekte der isolierten Optimierung erscheint es sinnvoll, nicht nur die beste gefundene Lösung weiter zu verfolgen, sondern einen mehrere gute Lösungen umfassenden Pool zu untersuchen. Schwarmbasierte Verfahren - wie sie die für das Berth Allocation Problem verwendeten Metaheuristiken darstellen - bieten hierfür einen geeigneten Ansatzpunkt. Die in der Population des GA, bzw. dem Schwarm der PSO enthaltenen Lösungen, entwickeln sich im Laufe fortlaufender Iterationen zunehmend zu guten Lösungen.708 Es sollen demnach die Elemente des Pools genutzt und durch den CSP-Agenten in einem schnellen Prüfverfahren auf ihre Erfolgsaussicht (für das CSP) untersucht werden. Mit dem daraus gewonnenen besten Element kann dann mit Hilfe einer CSP-Metaheuristik die Ausgangslösung wie gehabt optimiert werden. Dieses Vorgehen wird in Abbildung 6-16 vorgestellt: BAP- Pool
BAP
CSP
CSP
BAP- Optimierung
CSP- Auswahl
CSP- Optimierung
Ergebnis
Abbildung 6-16: MAS-basiertes Vorgehen für BAP und CSP
Dieser Ansatz bietet zwei wesentliche Vorteile:709
Der BAP-Agent kann seine Problemstellung unabhängig von anderen Einflüssen optimieren und wird durch die vom Management vorgegebene Zielsetzung motiviert, ein möglichst gutes Ergebnis zu erzielen. Die Optimierung bleibt somit vollständig in der Hand des Liegeplatzplaners, der Experte für diese Aufgabenstellung ist.
708 709
Vgl. hierfür die Kapitel 2.2.3.3.2 sowie 2.2.3.3.3.
Das aufgezeigte Koordinationsmodell wird MAS-BASIERT bezeichnet, weil verschiedene Elemente agentenbasierter Koordination in diesem Ansatz auftreten, u.a. die Kommunikationsfähigkeit der Agenten. Vgl. hierzu auch 2.4.2. Die Berechnung wird in der MAS-UMGEBUNG durchgeführt.
Koordination des Planungsprozesses in Container-Terminals
215
Der CSP-Agent beurteilt nun die Lösungen der zuletzt erzeugten Generation des GA (respektive des Schwarms der PSO), weil dieser - basierend auf dieser Entscheidung - mit dem Ergebnis weiterarbeiten muss. Es wird dabei angenommen, dass der BAP-Agent den Lösungen dieses Pools indifferent gegenübersteht. Der BAP-Agent bleibt weiterhin in der Lage, die Akzeptanzgrenze für eine gute Lösung autonom festzulegen.
Das folgende Beispiel zeigt die Lösungsvielfalt der Population des GA nach 50 Iterationen.
1.0
Lösungsvielfalt GA- Population
0.6 0.4
relative Häufigkeit
0.8
gute Lösungen in GA Population
0.0
0.2
Beste Lösung in GA Population
13
14
15
Akzeptanzgrenze
16
17
18
Durchschnittliche Aufenthaltszeit in h
Abbildung 6-17: Lösungsvielfalt in der Population des GA710
Die Abbildung zeigt, dass Ergebnisse bis zu einem (vom BAP-Agenten) definierten Fitnesswert als gute Lösungen akzeptiert und in den Pool aufgenommen werden.711 Alle in diesem Pool enthaltenen Lösungen werden von dem CSP-Agenten mit Hilfe einer Eröffnungsheuristik auf ihr Potential überprüft. Die Berechnung mit dieser Heuristik kann sehr schnell erfolgen. Die Ergebnisse dieses Vorgehens sind mit Tabelle 6-16 gegeben. Zum Vergleich werden die Ergebnisse des sequenziellen und iterativen Vorgehens ebenfalls mit aufgezeigt.
710
Die Abbildung wurde mit Hilfe der R-Funktion density() erzeugt, unter Einsatz der in Kapitel 6.1.1.1 gefundenen Parametereinstellung für den GA. Es ist gut zu erkennen, dass in der (fortgeschrittenen) Population des GA noch immer ein (bewusst) breites Spektrum unterschiedlicher Chromosome vorgehalten wird.
711
In der Abbildung entspricht der Threshold dem Fitnesswert von 14.4 h.
216
Koordination des Planungsprozesses in Container-Terminals CSP Eröffnungsheuristik
Durchschnittliche Zielgröße in h
BAP EH 1 (*)
Aufenthaltszeit
14.01
Wartezeit
0.32
Operationszeit
13.68
28.83 (23.12) 14.04 (9.52) 14.78 (13.60)
CSP Metaheuristik sequen-
Greedy
33.52
31.88
23.46
23.17712
22.00
12.87
19.99
10.43
10.11
8.68
20.64
11.89
13.03
13.06
13.33
ziell
iterativ
MAS-
EH 2
basiert
Tabelle 6-16: Vergleich von Koordinationsmethoden zwischen BAP und CSP
Während die sequenzielle und die iterative Koordination zu ähnlichen Ergebnissen führen, zeigt sich mit der MAS-basierten Koordination, dass sich die durchschnittliche Aufenthaltszeit der Containerschiffe im Hafen durch die gezielte Auswahl von Elementen für die Optimierung erheblich senken lässt. Festzuhalten bleibt, dass die Ergebnisse des BAP nach Durchlaufen des CSP nicht mehr zu halten sind. Insbesondere die BAP-Annahme, dass Containerschiffe mit dem Anlegezeitpunkt am Kai sofort bearbeitet werden, kann im zusammenhängenden (Teil-)Modell nicht aufrecht erhalten werden. Dies führt insbesondere zu einer massiven Erhöhung der Wartezeiten, wenn das CSP mit einbezogen wird. Interessant ist das Verhalten der drei eingesetzten Eröffnungsheuristiken:713 Die Aufenthaltszeit setzt sich aus der Wartezeit und der Operationszeit zusammen. Das GreedyVerfahren zeigt eine sehr geringe Operationszeit bei hoher durchschnittlicher Wartezeit. EH 2 weist eine geringe Wartezeit, dafür jedoch eine hohe Operationszeit auf. Der Erfolg von EH 1 scheint in der ausgeglichenen Gestaltung beider Größen zu liegen. Der Stern (*) kennzeichnet die durch den Pool erhaltenen Ergebnisse mit EH 1.
712
Angegeben ist die während der Iterationen gefundene, minimale durchschnittliche Aufenthaltszeit in h, vgl. Tabelle 6-15.
713
Die Bestimmung einer Ausgangslösung mit EH1 und EH2 ist detailliert im Anhang beschrieben. Vgl. auch Kapitel 6.1.1.3.
Koordination des Planungsprozesses in Container-Terminals
217
Die folgende Abbildung zeigt die Verteilung der Ergebnisse in allen fünf Iterationen und für das MAS-basierte Vorgehen. BAP und CSP
0.05
0.10
Sequenz Iteration 2 Iteration 3 Iteration 4 Iteration 5 MAS- Pool
0.00
relative Häufigkeit
0.15
BAP und CSP
10
15
20
25
30
35
40
Durchschnittliche Aufenthaltszeit in h
Abbildung 6-18: Vergleich sequenzieller, iterativer und MAS-basierter Koordination
Die Abbildung bestätigt die Vorteilhaftigkeit der MAS-basierten Koordination für BAP und CSP gegenüber den anderen Verfahren. Aufgrund des Erfolgs dieses Vorgehens soll dieses Koordinationsmodell auch Teil der in Kapitel 6.1.2.2.2 zu untersuchenden, alle Teilprobleme des CTMP umfassenden Problemstellung werden.714 6.1.2.1.2 Koordination von BAP und SLP
Für die Koordination von BAP und SLP werden zwei verschiedene Koordinationsmodelle untersucht. Zum einen kommt die als Benchmark eingesetzte sequenzielle Koordination zum Einsatz. Zum anderen soll ein iterativer Ansatz untersucht werden. Es ist zu erwarten, dass dieser Ansatz für die Koordination von BAP und SLP besser geeignet ist, als für die Abstimmung der im vorangegangenen Abschnitt vorgestellten Teilprobleme, weil der Liegeplatzplaner das Ergebnis der Yardplanung direkt in die Zielfunktion aufnehmen kann.
714
Es soll von einem Koordinationsmodell gesprochen werden, wenn definiert wird, wie die Koordination der interdependenten Planungssysteme des CTMP ablaufen soll.
218
Koordination des Planungsprozesses in Container-Terminals
Das iterative und MAS-basierte Koordinationsmodell für BAP und SLP kann wie folgt beschrieben werden:715 1. Der BAP-Agent beginnt mit der Zuordnung der Liegeplätze. 2. Auf diesen Ergebnissen basierend legt der SLP-Agent die Lagerplätze für die Container im Yard fest. Das sequenzielle Koordinationsmodell ist an dieser Stelle beendet. 3. Der BAP-Agent beginnt wieder mit der Neuordnung der Schiffsliegeplätze unter Berücksichtigung der Lagerplätze für die Container. In die Zielfunktion wird nun zusätzlich die Transportentfernung aufgenommen.716 Die Schiffe werden durch die erneute Zuordnung verschoben, und es kann zu einer Verlängerung von Wartezeiten kommen, wenn dadurch die Transportdistanz gesenkt werden kann. 4. Der Einfluss der neu angeordneten Liegeplätze auf die Yardplanung wird durch den SLP-Agenten geprüft, weil die Modifikation der Liegeplätze zu veränderten Zugriffszeitpunkten im Yard führt. Nur wenn das Zuordnungsungleichgewicht nicht unverhältnismäßig durch die Neuordnung der Schiffe aus dem Gleichgewicht kommt, ist der SLP-Agent bereit, diese neue Lösung zu akzeptieren.717 5. Wird die Lösung vom SLP-Agenten akzeptiert, dann wird die Transportdistanz zwischen Kai und Yard optimiert, basierend auf der bestehenden Yard-Zuordnung und den neuen Liegeplätzen.718 Kann die neue Liegeplatzzuordnung hingegen nicht
715
Das aufgezeigte Vorgehen enthält aufgrund der Rückkopplung des Informationsflusses Elemente von MOORTHY und CHUNG-PIAW, vgl. Kapitel 3.2.2.1.
716
Es ist eine auf die spezifischen Anforderungen des CT auszurichtende Gewichtung der Zielfunktion zu entwickeln. Darin muss definiert werden, wie hoch die Reduktion der Transportdistanz ausfallen muss, um eine Verlängerung der Wartezeit zu rechtfertigen. In dieser Untersuchung wird das Verhältnis (willkürlich) mit 1:1000 festgelegt, d.h., eine Stunde Wartezeit entspricht der Reduktion der Transportdistanz um 1000m. Aus der Literatur sind keine Ansätze zur Bestimmung eines optimalen Verhältnisses beider Ziele bekannt.
717 718
Vgl. hierzu die Zielfunktion des SLP in Kapitel 3.2.4.2.
Dies ist der Fall, wenn sich die Zielgröße des SLP nach Umstellung der BAP-Lösung um nicht mehr als t% verändert.
Koordination des Planungsprozesses in Container-Terminals
219
vom SLP-Agenten akzeptiert werden, dann ist dieser gezwungen, erneut mit der Lagerplanung zu beginnen, basierend auf der neuen Liegeplatzzuordnung.719 Die folgende Abbildung zeigt zusammenfassend das eingesetzte Vorgehen.
Start
BAP
Liegeplatzzuordnung
SLP
Lagerplatzzuordnung
BAP
Anpassung der Liegeplatzzuordnung an die Lagerplatzzuordnung
Nein
Ja SLP
SLP ?
Ist die Anpassung der Liegeplätze für das SLP akzeptabel?
Stopp
Optimierung der Transportdistanz
Abbildung 6-19: Ablauf iterativer/ MAS-basierter Koordination für BAP und SLP
Die Ergebnisse dieses Vorgehens für das Zusammenspiel von BAP und SLP sind mit der folgenden Tabelle gegeben. Durchschnittliche Zielgröße in h und m
SLP BAP sequenziell
iterativ/ MAS
Aufenthaltszeit
14.01
14.01
14.69
Wartezeit
0.32
0.32
1.01
Operationszeit
13.68
13.68
13.68
Distanz
-
71055 (769.5 m)
67847 (734.5 m)
Tabelle 6-17: Vergleich von Koordinationsmethoden zwischen BAP und SLP
719
An dieser Stelle wird die MAS-basierte Komponente dieses Verfahrens hervorgehoben: Der SLP-Agent bleibt autonom und ist allein für die Yardplanung verantwortlich. Ohne seine Akzeptanz kann keine Lösung zustande kommen.
220
Koordination des Planungsprozesses in Container-Terminals
Auf den ersten Blick scheint das iterative Vorgehen nachteilig, weil die Aufenthaltszeit im Vergleich zur sequenziellen Koordination steigt. Insbesondere die Koordination von BAP und SLP erfordert jedoch die Behandlung von Zielkonflikten:720 In speziellen Situationen kann die Transportdistanz für den Containertransport zwischen Kai und Yard reduziert werden, wenn die Schiffe dafür auf einen geeigneten Liegeplatz warten. Tatsächlich sinkt die Transportdistanz im Vergleich zur sequenziellen Koordination, während die Wartezeit und bei konstanter Operationszeit auch die Aufenthaltszeit der Containerschiffe steigt. Ziel dieses Vorgehens ist die Reduktion der Operationszeit, die über die Verringerung der Transportdistanz gesenkt werden soll. Die Operationszeit ist für das Zusammenspiel von BAP und SLP jedoch konstant. Aus diesem Grund ist es erforderlich, nicht allein Teilmengen des CTMP zu betrachten, sondern alle relevanten Planungssysteme in der MAS-Umgebung zu untersuchen. 6.1.2.2 Untersuchung des CTMP
In diesem Abschnitt werden alle Teilprobleme in der gemeinsamen MAS-Umgebung betrachtet. Die Ergebnisse des sequenziellen Vorgehens werden dabei als Benchmark für das daran folgende Koordinationsmodell genommen. Im Rahmen des VDP werden jeweils drei Van Carrier für eine Containerbrücke eingesetzt, die mit einer konstanten Geschwindigkeit von 36 km/h fahren. 6.1.2.2.1 Sequenzielle Koordination als Benchmark
Das sequenzielle Koordinationsmodell stellt das in der Praxis übliche Vorgehen dar. Die Ergebnisse einer vorangestellten Stufe werden an das nachfolgende Planungssystem weitergereicht. Dieses Vorgehen ist in Abbildung 3-4 aufgezeigt. Die sequenzielle Aneinanderreihung von Ergebnissen führt - unter den hier gesetzten Einstellungen - zu folgendem CTMP-Ergebnis. Dargestellt sind die durchschnittliche Zeit in h sowie die durchschnittliche Transportdistanz zwischen Kai und Yard in m.
720
Vgl. hierzu Kapitel 3.3, in dem die Interdependenzen vorgestellt werden und zudem Kapitel 5.1.2.3 für ein Beispiel konfliktärer Zielsetzungen im Rahmen des CTMP.
221
5
10
740
15
760
20
780
25
800
Koordination des Planungsprozesses in Container-Terminals
Aufenthaltszeit =
Wartezeit +
Operationszeit
Durchschnittliche Transportdistanz in m
Abbildung 6-20: Sequenzielles CTMP-Ergebnis (Boxplot)
Die grafische Darstellung als Boxplot deckt auf, dass die Ergebnisse des CTMP bei sequenzieller Aneinanderreihung der isoliert modellierten Subsysteme - wie vermutet - zu einer relativ hohen Varianz führen.721 Durch das Zusammenwirken der Teilprobleme in der MAS-Umgebung ist es möglich zu untersuchen, wie sich Koordinationsinstrumente und Zielvorgaben in den Teilbereichen auf das Gesamtproblem auswirken. Grundsätzlich existieren zwei Möglichkeiten, ein Koordinationsproblem zu lösen.722 Den ersten Ansatz gibt die Simultanplanung, mit der sich Probleme als Ganzes lösen lassen. In der Praxis ist dieser Ansatz jedoch häufig unbrauchbar, da die resultierende Modellkomplexität zu hoch ist.723 Dieses Problem wurde im Speziellen auch für das CTMP erkannt. Obwohl es Ansätze für die Synthese von Planungssystemen gibt,724 ist nicht zu erwarten, dass sich ein solcher Ansatz für das CTMP durchsetzen kann. Um Pläne zu koordinieren, bleibt deshalb nur ein iteratives Verfahren, in dessen Rahmen die Koordination über rückgekoppelte Planungsschritte erfolgt. Um Pläne für das CTMP koordinieren zu können, sind Rückkopplungen erforderlich. Die im Modell eingesetzten Beziehungen stellen die Grundlage bereit, überhaupt nach koordinierten Lösungen suchen zu können.
721
Vgl. Kapitel 6.1.2.
722
Vgl. die ausführliche Darstellung zur Koordination betrieblicher Entscheidungen in Kapitel 2.3.
723
Vgl. ADAM, D. et al. (2004), S. 82.
724
Vgl. MEISEL, F.; BIERWIRTH, C. (2005), PARK, Y.; KIM, K. H. (2003) und auch MOORTY, R.; CHUNGPIAW, T. (2006).
222
Koordination des Planungsprozesses in Container-Terminals
Es gibt keine allgemeingültigen Vorgaben, wie die Iteration zur Koordination von Teilproblemen auszusehen hat. Aus diesem Grund sollen die aus den Experimenten gewonnenen Erkenntnisse genutzt werden, um ein Modell für die Koordination des CTPlanungsprozesses zu entwickeln und in der Umgebung des Multiagentensystems zu untersuchen. 6.1.2.2.2 Multiagentenbasierte Koordination
Das eingesetzte multiagentenbasierte Koordinationsmodell setzt sich aus den in den vorangegangenen Abschnitten bestimmten Ansätzen zusammen. Für das CTMP wird ein MAS-basiertes Verfahren eingesetzt, das sich aus der gezeigten Vorgehensweise zur Koordination von BAP und CSP in Kapitel 6.1.2.1.1 sowie zur Koordination von BAP und SLP in Kapitel 6.1.2.1.2 zusammensetzt. In der folgenden Abbildung ist das Vorgehen dargestellt. Start Berücksichtigung der Yardposition BAP
SLP
SLP: Akzeptanz? BAP CSP Pool Nein! Ja!
Neustart!
VDP:= CTMP-Lösung (Stopp)
Abbildung 6-21: MAS-basierte Koordination im CTMP
Zur Koordination von BAP und SLP kommt der iterative/ MAS-gestützte Ansatz zum Einsatz.725 In diese Vorgehensweise wird das Vorgehen zur Koordination von BAP und CSP integriert.726 Es ist darauf hinzuweisen, dass eine Vielzahl weiterer Ansätze für diese Untersuchung in Frage kommt. Die Untersuchung einer Kombination der besten beobachteten Ansätze erscheint zunächst sinnvoll.
725 726
Dieses Vorgehen wird in Kapitel 6.1.2.1.2 vorgestellt.
Vgl. Kapitel 6.1.2.1.1. Nach der Berücksichtigung der Transportdistanz in der Zielfunktion durch den BAP-Agenten wird das Ergebnis der Liegeplatzplanung (als Pool guter Lösungen) zunächst an die Containerbrückenplanung weitergereicht. Erst danach erfolgt die Prüfung dieses Ergebnisses durch den SLPAgenten.
Koordination des Planungsprozesses in Container-Terminals
223
Die folgende Tabelle zeigt die Ergebnisse der MAS-basierten Koordination im Vergleich zum sequenziellen Ansatz für den Planungsprozess. Das Ergebnis des VDP entspricht - als letzte Stufe in diesem Prozess - dem für das CTMP gefundenen Ergebnis und ist deshalb hervorgehoben. BAP
CSP
SLP
VDP (CTMP)
Zielgröße
Aufenthaltszeit
Wartezeit
Operationszeit
Distanz
seq.
MAS
seq.
MAS
seq.
MAS
seq.
MAS
mean
14.02
14.25
23.39
22.32
14.02
14.25
25.19
24.86
median
14.00
14.14
23.31
22.16
14.00
14.14
25.05
24.42
min
13.80
13.94
18.69
19.78
13.80
13.94
20.23
21.15
max
14.33
14.94
26.90
26.26
14.33
14.94
28.68
29.13
sd
0.12
0.31
1.92
1.84
0.12
0.31
2.04
2.12
mean
0.33
0.57
9.99
9.15
0.33
0.57
10.79
10.49
median
0.32
0.46
9.77
8.81
0.32
0.46
10.39
10.29
min
0.11
0.25
6.35
6.72
0.11
0.25
6.85
7.08
max
0.65
1.25
14.40
14.04
0.65
1.25
14.79
14.58
sd
0.12
0.31
2.06
1.90
0.12
0.31
2.10
1.95
mean
13.68
13.68
13.40
13.17
13.68
13.68
14.40
14.37
median
13.68
13.68
13.45
13.23
13.68
13.68
14.48
14.39
min
13.68
13.68
12.28
11.76
13.68
13.68
12.68
12.68
max
13.68
13.68
14.65
14.09
13.68
13.68
15.96
16.13
sd
0
0
0.68
0.64
0
0
0.81
0.99
mean
-
-
-
-
771.70
737.60
771.70
737.60
median
-
-
-
-
774.90
735.10
774.90
735.10
min
-
-
-
-
729.70
716.20
729.70
716.20
max
-
-
-
-
808.70
760.30
808.70
760.30
sd
-
-
-
-
16.74
12.36
16.74
12.36
Tabelle 6-18: Vergleich sequenzieller und MAS-basierter Koordination
224
Koordination des Planungsprozesses in Container-Terminals
Der Vergleich beider Koordinationsmethoden zeigt den gewünschten Effekt: Die MASbasierte Koordination reduziert im Durchschnitt alle vier für das CTMP betrachteten Zielgrößen. Zur besseren Übersicht zeigt die folgende Abbildung die Entwicklung der Zielgrößen im Planungsprozess.727
Wartezeit
Operationszeit
Zielgröße in h 11
5
15
12
Zielgröße in h
Zielgröße in h
13
20
10
14
Aufenthaltszeit
15
15
25
Entwicklung der Zielgröße im Planungsprozess
BAP
SLP
CSP
VDP
MAS Sequenz
10
0
10
Planungsprozess
BAP
SLP
CSP
VDP
BAP
SLP
CSP
VDP
Abbildung 6-22: Entwicklung der Zielgrößen des CTMP im Planungsprozess
Es ist möglich, die Entwicklung der Zielgrößen im Planungsprozess zu betrachten und zu analysieren. Dabei ist zu beachten, dass die Aufenthaltszeit nach Durchführung der Liegeplatzplanung für die MAS-basierte Koordinationsform höher liegt als in der sequenziellen Planung. Dies ist durchaus gewollt und liegt darin begründet, dass bereits im Rahmen der Liegeplatzplanung auf die Position zu lagernder Container eingegangen wird. Die Berücksichtigung bereits zu Beginn des Planungsprozesses gilt als Ursache für ein besseres Ergebnis am Ende dieses Prozesses. Die Abbildung zeigt die Entwicklung der Zielgrößen für den Lauf durch die beteiligten Planungssysteme. Am Ende des Planungsprozesses ist das Gesamtergebnis für den CT in Form des Zielsystems ersichtlich.728 Der MAS-Ansatz ist in der Lage, die durchschnittliche Aufenthaltszeit von Containerschiffen um 33 Minuten zu
727
Der Planungsprozess lässt sich über die Entwicklung des Zielsystems in allen vier implementierten Planungssystemen darstellen.
728
Vgl. hierzu die Definition des Zielsystems in Kapitel 5.1.2.2.
Koordination des Planungsprozesses in Container-Terminals
225
reduzieren.729 Unter Berücksichtigung der in Kapitel 1.1 einleitend angesprochenen Operationskosten von bis zu 65.000 € für ein Containerschiff am Tag zeigt sich der Wert dieser Koordinationsmethode. Die beobachteten guten Ergebnisse mit Hilfe der multiagentenbasierten Koordination sind im folgenden Abschnitt kritisch auf ihre Übertragbarkeit in die Realität zu überprüfen, und es ist auf die Interpretation der Ergebnisse insgesamt einzugehen.
6.2 Übertragbarkeit und Interpretation der Ergebnisse Im Vergleich zu ihrer isolierten Variante liefern bisherige Ansätze relativ schlechte Lösungen im Prozesszusammenhang. Dies lässt sich vor allem durch das sequenzielle Aneinanderreihen suboptimaler Lösungen im Rahmen ihrer Synthese erklären. Es konnte gezeigt werden, dass die sequenzielle Koordinationsform zu ungenügenden Ergebnissen führt. In der Realität des CT kann dieser Nachteil durch das Eingreifen von Experten ausgeglichen werden, die aus Erfahrung wissen, wie auf bestimmte Probleme reagiert werden muss. Wünschenswert ist ein IT-gestützter Weg, der bereits im Voraus gute Ansätze liefert, die wiederum von Experten begutachtet und verbessert werden können. Bereits im Rahmen der ersten Untersuchungen mit Multiagentensystemen konnten verbesserte Ergebnisse aufgezeigt werden. Dies lässt erwarten, dass mit weitergehenden Untersuchungen zusätzliches Potential für die Prozessoptimierung erschlossen werden kann. Unter Berücksichtigung der gezeigten Zuwachsraten für den Containerverkehr erscheint dies unbedingt notwendig. Es ist klar, dass sich die eingesetzten Modelle nicht ohne weiteren Aufwand in die Realität übertragen lassen, weil dort zusätzliche Restriktionen zu beachten sind. Dies zeigen auch die ausführlich diskutierten Annahmen und die Modellkritik in Kapitel 3.2. Dennoch lassen sich im Rahmen des MAS nun die Auswirkungen von zuvor isoliert betrachteten Modellen in ihrem Prozesszusammenhang untersuchen. Es lassen sich so Erkenntnisse für die zukünftige Modellgestaltung gewinnen. Die intensive Forschung im Bereich der Logistik im Allgemeinen und im Bereich von CTProblemstellungen im Speziellen hat zu einem Verständnisgewinn über die Wirkung von
729
Vgl. Tabelle 6-18.
226
Koordination des Planungsprozesses in Container-Terminals
Entscheidungen geführt. Auch lassen sich nun Probleme präzise beschreiben und darstellen. Der hier untersuchte MAS-basierte Koordinationsansatz ist durch die Erkenntnisse vorangestellter Experimente beeinflusst.730 Ein Problem des induktiv-empiristischen Erkenntnisweges ist, dass die durch die Beobachtungen formulierten besonderen Sätze kein Beweis für ihre Gültigkeit darstellen. Ihr Einsatz kann sich als falsch erweisen, auch wenn sehr viele Beobachtungen die Wirkung zu bestätigen scheinen.731 Konkret wurden folgende Erkenntnisse in Rahmen von Kapitel 6.1 auf induktivempirischem Erkenntnisweg gewonnen:
Die Beurteilung der eingesetzten Optimierungsmethoden
Die Wirkung der Modellparameter
Im Rahmen der Untersuchung von Teilmengen des CTMP wurden Erkenntnisse gewonnen, die in die implementierte Methode zur Prozesskoordination einspielen:
Im Zusammenspiel von BAP und CSP konnte beobachtet werden, dass die Aufenthaltszeit über die Iteration des Informationsflusses zwischen den Planungssystemen weniger reduziert wurde, als bei einer abschließenden CSP-Beurteilung mehrerer guter BAP-Lösungen.
Im Zusammenspiel von BAP und SLP konnte beobachtet werden, dass die Transportdistanz über die Iteration des Informationsflusses zwischen den Planungssystemen reduziert werden konnte.
Basierend auf diesen Erkenntnissen wurde ein Koordinationsprotokoll entwickelt, das sich durch die folgenden Punkte auszeichnet:
Koordination durch verstärkte Kommunikation (BAP und CSP)
Koordination durch zielgerichtete Iteration (BAP und SLP)
730
Vgl. die Gestaltung MAS-basierter Koordination in Kapitel 6.1.2.
731
Vgl. BORCHERT, J.; GOOS, P.; STRAHLER, B. (2004), S. 10f.
Koordination des Planungsprozesses in Container-Terminals
227
Es ist festzuhalten, dass bereits die Implementierung eines einfachen Ansatzes zur Prozesskoordination zu einer Verbesserung der Zielgrößen des CTMP geführt hat. Dieser Ansatz konnte aus den vorangegangenen Experimenten abgeleitet werden. Es zeigt sich, dass die Durchführung von Experimenten mit dem entwickelten System zu Erkenntnissen führt, die sich anschließend im Rahmen des Modells untersuchen lassen.
6.3 Erweiterbarkeit und Modellkritik Neben den hier vorgestellten Methoden lassen sich weitere Koordinationsformen untersuchen. In dieser Arbeit konnte nur ein kleiner Ausschnitt möglicher Instrumente simuliert werden. Auch multikriterielle Zielsysteme wurden bislang nicht umfassend berücksichtigt, erscheinen jedoch vielversprechend, weil in dem umfassenden CT-Modell eine Vielzahl konfliktärer Ziele zusammen kommt. Kritisch an dem vorgestellten Modell lässt sich anmerken, dass die Anzahl verwendeter Datensätze noch ausgedehnt werden kann. Beispielsweise lassen sich mit Daten weiterer Häfen die Experimente erneut durchführen, was zu veränderten Ergebnissen führen kann. Diese Kritik lässt sich für empirische Modelle kaum vollständig ausschließen. Ansätze der Literatur, die Teilmengen des CTMP behandeln und sehr gute Ergebnisse liefern, weil sie speziell auf die Koordination der Teilmenge ausgerichtet sind, müssen keinesfalls als Konkurrenz zu diesem Ansatz betrachtet werden. Kernelement dieser Arbeit ist die Untersuchung bestehender Modelle in einer gemeinsamen Umgebung. So ist es möglich, auf dem Know-how existierender Modelle aufzubauen und diese im Rahmen einer neuen Perspektive zu beleuchten. Die Schnittstellen sind idealtypisch formuliert und finden sich in den betroffenen Modellen der Literatur wieder. Beispielsweise ist es möglich, die isolierten Modelle BAP und CSP durch ein gemeinsames Modell (BAPCSP) zu ersetzen.732 Eine solche Maßnahme lässt sich als Veränderung der Organisationsstruktur des Container-Terminals interpretieren. Es lassen sich dann neue Koordinationsformen untersuchen.
732
Beispiele hierfür lassen sich in der Literatur finden. Vgl. Kapitel 3.3. Die Schnittstellen werden dadurch nicht verändert.
228
Koordination des Planungsprozesses in Container-Terminals
Die Analyse weiterer Untersuchungsschwerpunkte für dieses Modell zeigt aber auch, wie vielseitig diese Rahmenstruktur einsetzbar ist.
Schlussbetrachtung
229
7 Schlussbetrachtung Für die Koordination interdependenter Planungssysteme in der Logistik existierten bislang kaum einsatzfähige Methoden. Im Gegensatz dazu konnte in der Literatur auf eine Vielzahl isolierter Modelle, die Teilprobleme von Container-Terminals aufgreifen und gute Ansätze für die Lösung dieser Problemstellungen aufzeigen, zurückgegriffen werden. Schwachstelle dieser Modelle bleibt die Vernachlässigung von Beziehungen zu abhängigen Planungssystemen. Nachdem in Kapitel 2 die Grundlagen logistischer Systeme und Prozesse vorgestellt wurden, konnten in Kapitel 3 bestehende Entscheidungsmodelle der CT-Logistik klassifiziert und deren Stärken und Schwächen abgewogen werden. Wesentliche Interdependenzen zwischen Entscheidungsbereichen des CT, die in isolierten Modellen keine Berücksichtigung finden, wurden identifiziert. Kapitel 4 widmete sich Leistung und Grenzen dieser Modelle, unter Berücksichtigung zukünftiger Anforderungen sowie zuvor identifizierter wechselseitiger Abhängigkeiten. Den Bedarf insbesondere an intelligenten Methoden zur Prozesskoordination stellt die Literatur heraus. Implikationen wurden aufgezeigt, die sich auf dieser Grundlage ergeben. Kapitel 5 zeigte deshalb die Entwicklung eines multiagentenbasierten Modells zur CTProzesskoordination auf, deren Eignung für den Einsatz in dieser Domäne bestätigt werden konnte. Bestehende Modellansätze können in einer gemeinsamen und sich wechselseitig beeinflussenden Umgebung weitergehend untersucht werden. Dieser Rahmen und die gewählte Architektur der Agenten begünstigen den Einsatz intelligenter Methoden zur Koordination interdependenter Planungssysteme. Mit diesem entwickelten Modell wurden in Kapitel 6 umfangreiche Untersuchungen durchgeführt. Die hierfür verwendete Datengrundlage hatte das Institut für Seeverkehrswirtschaft und Logistik in Bremerhaven zur Verfügung gestellt. Nach Tests von Methoden und Parameterwirkungen in isolierter Umgebung wurden mit den daraus gewonnenen Einstellungen übergreifende Untersuchungen durchgeführt. Mit jedem Entwicklungsschritt fand eine kritische Überprüfung statt. Diese führte, basierend auf den Untersuchungen mit dem MAS-Modell, zur Entwicklung eines Koordinationsansatzes. Bereits mit einem relativ einfachen implementierten Koordinationsmodell konnte eine Prozessverbesserung im Vergleich zu der in der Praxis üblichen Vorgehensweise zur
230
Schlussbetrachtung
Synthese isolierter Teilprobleme festgestellt werden. Dies lässt auf ein hohes Potential für die Optimierung der CT-Prozesse mit diesem Ansatz schließen. Zahlreiche weitergehende Ansatzpunkte lassen sich aufzeigen. Die Fähigkeiten, die sich durch das Multiagentensystem ergeben, wurden in der bisherigen Form noch nicht ausgeschöpft. Planungssysteme und Lösungsmethoden sind aufgrund der Modellierung austauschbar und erweiterbar. Kapitel 6.2 zeigte kritisch Möglichkeiten einer Modellerweiterung. Für die Zukunft bietet es sich an, zusätzliche Planungssysteme in die MAS-Umgebung zu integrieren. Hierzu gehört die Stauplanung, die für jedes Containerschiff, stark von den Interessen des Reeders beeinflusst, durchzuführen ist. Daneben ist die Yardplanung zu nennen, die hier auf das Storage Location Problem reduziert wurde. Mit Berücksichtigung detaillierter Containerinformationen lassen sich die Containerflüsse noch genauer untersuchen. Dazu gehören auch Fragestellungen der Reihenfolgeplanung und Stapelhöhe von Containern. Nicht zuletzt sollte die Personalplanung zukünftig in das Modell eingesetzt werden. Ausgeklammert wurde bisher der landseitige Weitertransport in dieser Betrachtung. Wenn sich das Containeraufkommen jedoch, wie in der Studie des BUNDESMINISTERIUMS
FÜR
VERKEHR, BAU UND STADTENTWICKLUNG angegeben, bis zum Jahr 2025 in Deutschland vervierfachen soll, dann kann es nicht genügen, nur die Prozesse im Container-Terminal zu optimieren.733 Um diese erhebliche Steigerung der logistischen Leistung bewältigen zu können, müssen Verkehrsträger ausgebaut, modernisiert und optimal koordiniert sein. Hier sind zahlreiche Forschungsfragen unbeantwortet. Der verstärkte Güterverkehr über Wasser führt zu einer Verringerung des Verkehrsaufkommens auf der Straße. Aus diesem Grund wachsen Anforderungen an ContainerTerminals, weil in dem optimierten Containerverkehr auch die Chance für die Reduktion des Kohlenstoffdioxidausstoßes (CO2) gesehen wird. Interessant erscheint ferner die Berücksichtigung von Interessen der Hafenbehörde und anderer Stakeholder. Ihre Vorgaben beeinflussen den Handlungsrahmen des CT. Inspiriert
733
Vgl. Bundesministerium für Verkehr, Bau und Stadtentwicklung (BMVBS) (2007).
Schlussbetrachtung
231
wäre diese Maßnahme durch den Beitrag von HENESEY, NOTTEBOOM und DAVIDSSON, die bereits ein Stakeholder Relationship Management System untersuchen.734 Hier könnten die Wirkungen von Regelungen der Behörde und Interessensvertretern bis auf die Ebene einzelner Bereiche untersucht werden. Selbst der Einsatz veränderter Organisationsstrukturen, beispielsweise die angesprochene Integration von BAP und CSP, lässt sich in dieses Modell einsetzen und im Zusammenhang mit der Terminal-Umgebung untersuchen. So ist es möglich, die Liegeplatz- und Containerbrückenplanung durch einen gemeinsamen Entscheidungsbereich zu ersetzen. Die Zusammenlegung dieser Bereiche erscheint sinnvoll, weil es an dieser Schnittstelle zu einer erheblichen Steigerung der Aufenthaltszeit kommt. In der Literatur vorhandene Modelle wurden in dieser Arbeit diskutiert. Organisatorische Veränderungen lassen sich keinesfalls nur für die Liegeplatz- und Containerbrückenplanung simulieren. Modelle für die Koordination von Liegeplatz- und Yardplanung sowie andere Bereiche wurden bereits angesprochen. Hier bieten sich zahlreiche Ansatzpunkte für weitere Forschungsarbeiten, die sich mit den zurzeit vorherrschenden und beschriebenen Anforderungen decken. Auch ist es denkbar, die aufgezeigte Vorgehensweise der Konstruktion eines multiagentenbasierten Ansatzes zur Koordination interdependenter Planungssysteme, auf andere Bereiche in der Logistik zu übertragen. Die Anforderungen sind nach Ansicht von PFOHL gegeben.735 Die Radio Frequency Identification (RFID)-Technologie kann für die Identifikation von Containern und unterstützend im Prozessablauf in Container-Terminals eingesetzt werden. Diese Technologie stellt ebenfalls einen Gegenstand aktueller Forschung dar. Es fehlt jedoch an weltweiten Standards. Hinzu kommen technische Aspekte, die das Multiagenten-Framework bietet und die bislang nur in einfacher Form ausgenutzt worden sind. Verteilte Agenten können die Rechengeschwindigkeit steigern und lassen so weiter verbesserte Ergebnisse erhoffen. Noch lange sind die Möglichkeiten zur (technischen) Prozessbeschleunigung und Reduzierung des
734
Vgl. HENESEY, L. (2004), S. 99- 125.
735
Vgl. PFOHL, H. C. (2004b), S. 16ff.
232
Schlussbetrachtung
Speicheraufwands nicht ausgeschöpft. Auch aus Sicht der (reinen) Informatik entstehen deshalb zahlreiche Anforderungen. Das Framework JADE bietet die Möglichkeit den Koordinationsprozess grafisch darzustellen und zu überwachen. Die Transparenz des Planungsprozesses für den Anwender wird dadurch erhöht, die Akzeptanz von Ergebnissen dieser Simulation gesteigert. Ohne verständliche Präsentation der Resultate ist die Übertragung auf reale Fälle und damit die Akzeptanz bei Praktikern kaum denkbar. Wissensbasierte Komponenten und weitergehende Konzepte der KI bieten im Rahmen des MAS weitere Ansatzpunkte. Auch hier ergeben sich für zukünftige Forschungsarbeiten breite Einsatzmöglichkeiten. Ein Wissenssystem ist deshalb in der Architektur der Agenten berücksichtigt.
Anhang
233
Anhang A1: Konstruktive Verfahren und lokale Suche Konstruktive Verfahren
Konstruktive Verfahren erzeugen Lösungen für kombinatorische Optimierungsprobleme, indem sukzessive und ohne Backtracking neue Komponenten zu einer Partiallösung736 hinzugefügt werden, bis eine vollständige Lösung existiert. Um Komponenten hinzuzufügen, können unterschiedliche Verfahren zum Einsatz kommen, z.B. zufällige Verfahren, Greedy-Verfahren oder einfache Regeln. Greedy-Verfahren werden häufig zur Bestimmung einer gültigen Ausgangslösung eingesetzt, nur in Ausnahmefällen lässt sich auf diese Weise eine optimale Lösung bestimmen.737 DORIGO gibt ein Beispiel für die Greedy-Konstruktion einer Lösung für das TravellingSalesman-Problem.738 Es ist in der Abbildung leicht zu erkennen, dass diese Lösung nicht optimal ist. f
b
a
e
c
d
Abbildung A-1: Greedy-Konstruktion einer TSP-Lösung (suboptimal)739
Das Problem der gierigen Bestimmung einer Lösung liegt, wie in Abbildung A-1 erkennbar ist, in der Vernachlässigung globaler Zusammenhänge zwischen den einzelnen Knoten.
736
Es wird im Rahmen dieser Arbeit zwischen Lösungen und Teil- (bzw. Partial-)Lösungen differenziert. Ist von einer Lösung die Rede, so ist damit grundsätzlich eine Lösung als Ganzes zu sehen, ist nur ein Teil der Lösung gemeint, wird explizit von einer Partiallösung gesprochen.
737
Vgl. CORMEN, T. H. (2005), S. 370.
738
Das Traveling-Salesman-Problem wird in der Literatur ausführlich diskutiert. Die ursprüngliche Formulierung ist in FLOOD, M. M. (1956), S. 61-75 zu finden.
739
DORIGO, M.; STÜTZLE, T. (2004), S. 30.
234
Anhang
In jedem Knoten wird lediglich der individuelle Nutzen optimiert. Zwar lässt sich mit Beginn des Verfahrens jeweils die kürzeste Verbindung zwischen zwei Elemente realisieren, der Einsatz dieser Verbindungen führt aber zu einer Verringerung des Spielraums für nachfolgende Knoten, so dass zuletzt die ungünstige Verbindung von f nach a in die Lösung aufgenommen werden muss. Lokale Suche
Die lokale Suche basiert auf der iterativen Erforschung der Nachbarschaft einer Lösung. Es wird versucht, bestehende Lösungen durch lokale Änderungen zu verbessern. Hierfür ist es erforderlich zu definieren, welche Elemente Teil der Nachbarschaft sein sollen. DORIGO gibt folgende Definition für die Nachbarschaftsstruktur: S „A neighborhood structure is a function N : S 2 that assigns a set of neighbors
N ( s ) S to every s S . N (s ) is also called the neighborhood of s.”740 Es ist demnach nicht implizit gegeben, welche Elemente zu der Nachbarschaft eines Elements gehören: Erst mit der Definition der Nachbarschaftsfunktion wird die Umgebung festgelegt. Zudem ist zu definieren, auf welche Weise die Nachbarschaft zu durchsuchen ist. Hier kommen z.B. die best-improvement- oder auch first-improvement-Regel zum Einsatz.741
A2: CSP-Eröffnungsheuristiken Für das CSP werden zur Bestimmung einer gültigen Ausgangslösung zwei einfache Heuristiken eingesetzt.
740
DORIGO, M.; STÜTZLE, T. (2004), S. 31.
741
Vgl. DORIGO, M.; STÜTZLE, T. (2004), S. 31.
Anhang
235 procedure Einfache_Eröffnungsheuristik (EH2) Bestimme Arbeitsbereich AB für jeden QC Für jeden Job Bestimme Earliest Assignment Time (EAT) für jeden QC für jeden Job j Wenn Job position in AB von QC q liegt, dann Weise zu (QC q, Bay b, EAT)
end procedure
Abbildung A-2: CSP-Eröffnungsheuristik (Pseudocode)
Die einfache Eröffnungsheuristik basiert auf dem Ansatz, für jede Containerbrücke einen bestimmten Arbeitsbereich zu definieren. Die Abbildung zeigt den Pseudocode des Verfahrens. Alle Jobs, die in den Arbeitsbereich fallen, werden diesem QC zugeordnet. Der Vorteil dieser Heuristik liegt in der einfachen Berechenbarkeit und dem Erreichen einer gültigen Lösung, weil sich die Containerbrücken aufgrund fixierter Arbeitsbereiche nicht schneiden können. Zu kritisieren ist u.a. die Fixierung eines Arbeitsbereichs für alle Containerbrücken.742 Mit der Festlegung auf einen bestimmten Arbeitsbereich verliert das Verfahren an Flexibilität. Eine Abschwächung der aufgeführten Nachteile soll mit der folgenden Heuristik erreicht werden.743
742
Der Arbeitsbereich eines QC ergibt sich in dieser Eröffnungsheuristik aus dem Quotienten der gesamten Kailänge dividiert durch die Anzahl zur Verfügung stehender Containerbrücken. Der Arbeitsbereich ist somit für jeden QC gleich groß.
743
Entgegen der Darstellungsreihenfolge beider Eröffnungsheuristiken in diesem Abschnitt soll die erweiterte Methode als EH1 bezeichnet werden, weil sie primär zur Entwicklung einer Ausgangslösung für das CSP zum Einsatz kommt. Vgl. hierzu Kapitel 6.1.1.3.
236
Anhang procedure Einfache_Eröffnungsheuristik (EH1)
Bestimme Arbeitsbereich AB für jeden QC Für jeden Job Bestimme Earliest Assignment Time (EAT) für jeden QC für jeden Job j Wenn Schiff v keinen Nachfolger v´ hat, dann Weise zu (QC q, Bay b, EAT) // wie in EH2 sonst
Wenn AB von v und AB von v‘ überlappen, dann Weise zu (QC q, Bay b, EAT), so dass sich AB von v und AB von v´ nicht überlappen sonst Weise zu (QC q, Bay b, EAT) // wie in EH2 end procedure
Abbildung A-3: Erweiterte CSP-Eröffnungsheuristik (Pseudocode)
Im Gegensatz zu der eben vorgestellten, sehr einfachen Eröffnungsheuristik werden hier die Nachfolger der Schiffe berücksichtigt, so dass, nicht direkt aufeinander folgend, dieselbe Containerbrücke eingesetzt wird. Sollten zwei aufeinander folgende Schiffe in denselben Arbeitsbereich einer Containerbrücke fallen, dann kann dieser Bereich verlassen werden, um die schnellere Bearbeitung der Schiffe gewährleisten zu können. Mit dem Einsatz dieser Ausnahmeregelung in EH2 wird versucht, die starre Zuordnungsform von EH1 zu lösen, um so ein besseres Eröffnungsergebnis für das CSP zu erreichen. Der Ergebnisvergleich dieser Heuristiken wird in Kapitel 6.1.1.3 vorgestellt.
A3: CSP-Nachbarschaft (SA) Für das Crane Scheduling Problem wird von dem Simulated Annealing auf zwei unterschiedliche Definitionen einer Nachbarschaft zurückgegriffen, die für die Entwicklung einer Lösung von Bedeutung sind. In der untersuchten Instanz werden J=176 Jobs und C=15 QC betrachtet. Die CSP-Lösung lässt sich als Vektor der Länge J darstellen. Jedem Element des Vektors wird eine ganze Zahl i, i ^0,1,..., C 1` zugewiesen. Das Element beschreibt den Index desjenigen QC, der für die Bearbeitung des Jobs zuständig ist.
Anhang
237
Die folgenden Abbildungen zeigen die eingesetzten Nachbarschaften für die CSPMetaheuristik. procedure Erzeuge_Nachbarn (NB1) Bestimme zufälliges Element der Lösung (Bay b) Bestimme Zufallselement (u
^0,1` )
Wenn (u