Einsatzplanung von Automated Guided Vehicles in Seehafen

Seminar Sommersemester 2010:
Automobile Systeme in der Automatisierung
Prof. Dr. Dieter Zöbel, Universität Koblenz-Landau, FB Informatik
Einsatzplanung von Automated Guided Vehicles in
Seehafen-Containerterminals
Seminar: Automobile Systeme in der Automatisierung
Urs Buchholz
the date of receipt and acceptance should be inserted later
Zusammenfassung Im Einsatz von fahrerlosen Transportsystemen (AGV) in SeehafenContainerterminals werden besondere Anforderungen an deren Einsatzplanung gestellt. Seehafen Containerterminals lassen sich in verschiedene Bereiche, mit unterschiedlichen, voneinander abhängigen Planungsproblemen, aufteilen. Einsatzplanung
von AGVs schließt die Zuordnung von AGVs zu Transportaufträgen mit ein. Dieses,
stark von weiteren Planungsproblemen abhängige, Problem und Lösungsverfahren werden durch bestimmte Eigenschaften charakterisiert und von Problemen aus flexiblen
Fertigungssystemen abgegrenzt.
Schlüsselwörter Automated Guided Vehicles · Einsatzplanung · Containerterminal
1 Einleitung
Die prägnante Entwicklung des Güterverkehrs in den letzten Jahrzehnten, bedingt
durch den steigenden Welthandel, macht es notwendig, die Transportkette des Güterumschlags zu optimieren. Containerterminals bilden als Umschlagplatz zwischen See
und Land ein wichtiges Glied in der Transportkette. Kurze Liegezeiten der Schiffe
sind ein Konkurrenzkriterium für Terminalbetreiber. Im Seehafen in Singapur werden
beispielsweise täglich ca. 70000 Standardcontainer abgefertigt [5]. Um diese enorme
Menge effizient umschlagen und Schiffe möglichst schnell abfertigen zu können, bietet
sich der Einsatz von automatischen Transportfahrzeugen innerhalb eines SeehafenContainerterminals an. Automated Guided Vehicles (AGV) sind Fahrerlose Transportsysteme, welche hier die Aufgabe des Horizontaltransports übernehmen.
In flexiblen Fertigungssystemen sind Fahrerlose Transportsysteme bereits seit längerer
Zeit im Einsatz. Lösungen und Algorithmen zur Einsatzplanung aus diesem verwandten Teilgebiet lassen sich nicht ohne weiteres auf Containerterminals übertragen, da
andere Planungsaufgaben die Einsatzplanung von AGVs beeinflussen. Alternative Lösungsansätze, zugeschnitten auf die Umgebung eines Containerterminals, sind somit
Urs Buchholz
Universität Koblenz-Landau
E-Mail: [email protected]
2
erforderlich. Diese Arbeit beschäftigt sich mit der Einsatzplanung in Containerterminals, genauer dem Teilproblem der Zuordnung von Transportaufträgen zu AGVs.
Kapitel 2 beschreibt den Aufbau von Containerterminals mit den dort stattfindenden
Abläufen. Weiterhin werden die dort auftretenden Planungsprobleme näher erläutert,
da diesen für die Einsatzplanung von AGVs Beachtung geschenkt werden muss. In Kapitel 3 werden Problemstellung und Eigenschaften der Einsatzplanung behandelt und
die Abgrenzung zu bekannten Problemen vorgenommen. Ein einfaches Verfahren zur
Einsatzplanung wird in Kapitel 4 vorgestellt. Ein Fazit und ein Ausblick finden sich
im letzten Kapitel.
2 Einsatz von Automated Guided Vehicles in Containerterminals
Containerterminals sind Ort des Umschlags und der Lagerung im weltweiten Handel.
Hier werden Container importiert und exportiert, wobei der An- und Abtransport über
den See- oder Landweg erfolgen kann. Als Umschlagplätze sind sie darauf ausgerichtet,
möglichst viele Container in kurzer Zeit abzufertigen. Die Transportkette innerhalb des
Terminals ist auf die Anforderungen der Beförderung von Standardcontainern ausgelegt. Was ein Standardcontainer ist und welche Eigenschaften er besitzt, beschreibt der
nächste Abschnitt.
2.1 Standardcontainer
Ein Standardcontainer ist eine Metallbox mit genormten Maßen. Meist handelt es sich
um Container mit einer Länge von 20 ft oder 40 ft, einer Breite von 8 ft und einer
variablen Höhe (gewöhnlich 8 ft). 20 ft lange Container werden auch als twenty-foot
equivalent unit (TEU) bezeichnet und bilden somit eine Einheit zur Zählung von Containern verschiedener Größe. Transportgüter aller Art können in einem Standardcontainer untergebracht werden. Güter, welche besondere Anforderungen an den Transport
stellen, können oftmals in speziellen Container befördert werden. Ein Beispiel hierfür
sind Lebensmittel, für die es Kühlcontainer gibt. Vorteile von Containern sind, dass
diese sehr stabil sind, sich gut stapeln lassen und von verschiedenen Transportmitteln
wie Containerschiffen, Lastkraftwagen oder Güterzügen transportiert werden können.
2.2 Automated Guided Vehicle
Ein Automated Guided Vehicle (AGV) oder auch Fahrerloses Transportsystem ist ein
automatisch gesteuertes Fördersystem für den Materialtransport. Die Fahrzeuge werden oftmals dieselhydraulisch angetrieben. Anwendungsgebiete sind unter anderem die
Fertigung, Krankenhäuser oder auch Containerterminals.
Im Rahmen der Containerterminals existieren zwei Varianten der AGVs. Single
Load Carrier (SLC) sind in der Lage einen Standardcontainer, Multi Load Carrier
(MLC) mehrere Standardcontainer zu befördern. Dual Load Carrier (DLC) sind MLC,
welche genau zwei Container transportieren können.
3
Abb. 1 Containerterminal Altenwerder des Hamburger Hafens1
2.3 Aufbau und Abläufe eines Containerterminals
Der Aufbau eines Terminals kann grob in drei Bereiche eingeteilt werden: Die Landseite, den Lagerplatz sowie die Kaiseite (siehe Abbildung 1). Verschiedene Abläufe finden
jeweils in den drei Bereichen statt und sind wichtig für die Einsatzplanung von AGV.
Containerschiffe legen an der Kaimauer an und transportieren Container an oder ab.
Die Schiffe werden dazu durch Kaikräne be- und entladen. Im Horizontaltransport
werden Fahrzeuge zu Beförderung der Container zwischen Lager und Kaimauer eingesetzt. Lagerkräne setzen die Container an die vorhergesehenen Positionen im Lager.
Vom Lager erfolgt die Hinterlandanbindung durch Verladung auf Lastkraftwagen oder
Güterzüge. Die in CTs eingesetzten Geräte zur Abfertigung der Container variieren
von Terminal zu Terminal und bestimmen auch den Ablauf der Abfertigung, was in
den nächsten Abschnitten detaillierter erklärt wird.
An- und Abtransport der Container durch Schiffe: Große Containerschiffe, welche heutzutage im Einsatz sind, haben eine maximale Ladekapazität von über
10000 TEU und somit große Ausmaße und hohen Tiefgang. Die mit der Größe der
Hochseeschiffe einhergehenden Anforderungen, wie zum Beispiel die Tiefe der Liegeplätze an der Kaimauer, müssen von den Terminals erfüllt werden, um eine direkte
Abfertigung durchzuführen. Andernfalls muss die Umladung auf kleinere Feederschiffe
in anderen Terminals erfolgen, um die Container an den Zielhafen zu bringen. Binnenschiffe werden im Terminal beladen, um die Fracht über Binnengewässer ins Hinterland
zu befördern.
Be- und Entladen der Schiffe: An der Kaimauer eines Terminals befinden sich
Kräne um die Container zu be- oder entladen. An den Kränen befestigte Containergeschirre, sogenannte Spreader, greifen die Container von oben und lösen die Verbindung
wieder, sobald das Absetzen erfolgt ist. Das Absetzen von Importcontainern kann auf
einem Fahrzeug des Horizontaltransports geschehen oder auf einem dafür vorgesehenen
Ort entlang der Kaimauer. Der aktuelle Stand der Technik sind die Containerbrücken
(quay cranes). Mit Hilfe eines Schienensystems sind diese entlang der Kaimauer verfahrbar, um an allen Positionen des Schiffes Ladebewegungen durchführen zu können.
Als Laufkatze wird das fahrbare Element am Ausleger des Krans bezeichnet. Die An1
http://www.hhla.de/Technische-Daten.655.0.html, besucht am 26.08.2010
4
zahl der Laufkatzen eines Krans entscheidet über die Produktivität, so sind ca. 25-35
Containerbewegungen pro Stunde mit einer Katze erreichbar und ca. 45 durch teilweise Automatisierung mit 2-Katz-Brücken. Das Auf- und Abladen erfolgt durch einen
Kranführer aus einer Kabine am Kran. 2-Katz-Brücken ermöglichen teilweise Automatisierung durch eine Plattform am unteren Teil der Brücke, auf der die Container vom
Kranfahrer abgeladen werden. Der Weitertransport auf das Fahrzeug oder den Boden
erfolgt dann vollautomatisch durch die Portalkatze.
Horizontaltransport: Als Horizontaltransport wird die Beförderung der Container zwischen Kaimauer und Lager durch Fahrzeuge bezeichnet. Man kann die Fahrzeuge hinsichtlich der Fähigkeit zur Auf- und Abladung von Containern und ihrem
Automatisierungsgrad unterscheiden. Aktive Fahrzeuge sind in der Lage durch Hebevorrichtungen einen Container selbstständig auf ihre Ladefläche aufzunehmen oder
abzuladen, wohingegen passive Fahrzeuge ein weiteres Gerät, zum Beispiel einen Kran,
benötigen. Bei passiven Fahrzeugen ist eine Synchronisierung von Gerät und Fahrzeug
notwendig, um zu bestimmen, ob der Ladevorgang beendet ist. Den Automatisierungsgrad betreffend werden bemannte Fahrzeuge durch einen Fahrer gesteuert, unbemannte automatisch durch ein Steuerungssystem. Automated Guided Vehicles (AGV) lassen
sich somit in die Kategorie der unbemannten passiven Fahrzeuge einteilen. Der Einsatz
von AGVs im Horizontaltransport hat in den letzten Jahren an Beliebtheit gewonnen
und sich verbreitet. Andere Fahrzeuge wie passiv bemannte Flurfördergeräte LKWChassis, Zugmaschinen oder Trailerzüge sind ebenso im Einsatz wie aktiv bemannte,
beispielsweise Straddle-Carrier, Shuttle-Carrier, Containerstapler oder Reach-Stacker.
Auf diese wird hier nicht weiter eingegangen. Weitere Informationen finden sich in [10].
Eine noch neue Entwicklung stellen die aktiv unbemannten Automated Lifting Vehicles (ALV) dar. Diese sind in der Lage Container automatisch auf- und abzuladen
sowie zu transportieren.
Lagerung der Container: Container aus dem Hinterland oder dem Horizontaltransport werden im Lager untergebracht und bis zum Weitertransport deponiert.
Durchschnittliche Verweildauern von drei bis vier Tagen sind üblich [1]. In Containerterminals werden, oft abhängig vom verfügbaren Platz, hauptsächlich drei verschiedene
Lagerarten eingesetzt.
Abb. 2 Rail Mounted Gantry Crane2
2
3
Lehmann 2006, S.17
http://www.siemens.nl/energynew/persinfo.asp?id=1382, besucht am 26.08.2010
5
Abb. 3 Rubber-Tired Gantry Crane3
Die erste Möglichkeit bildet das Blocklager in welchem Container in Reihen angeordnet und in fünf oder mehr Ebenen aufeinander gestapelt werden. Vorteil des
Blocklagers ist die gute Flächenausnutzung, wobei sich dies zu Lasten der Zugriffszeit
auf Container in den unteren Ebenen auswirkt, da Umstapeloperationen erforderlich
sind. Die Einlagerung und der Zugriff auf die Container erfolgt durch schienengebundene (Rail Mounted Gantry Cranes, Abb. 2) oder bereifte (Rubber Tired Gantry Cranes,
Abb. 3) Portalkräne. Rail Mounted Gantry Cranes können automatisiert betrieben
werden, wie zum Beispiel am Burchardkai im Hamburger Hafen [8].
Als zweite Möglichkeit bietet das Flächenlager leichteren Zugriff auf Container, da
die maximale Stapelhöhe auf ca. vier Ebenen beschränkt ist, mit der Folge, dass eine
größere Fläche benötigt wird. Ein- und Auslagerung der Container erfolgt meist durch
aktive Flurfördergeräte des Horizontaltransports.
Als dritte Möglichkeit der Einlagerung gibt es das Regallager in dem Container
durch Horizontal- und Vertikalförderer untergebracht werden. Aufgrund der Nutzung
von über 10 Ebenen wird wenig Fläche beansprucht [1].
Hinterlandanbindung: Der An- und Abtransport der Container vom oder in das
Hinterland erfolgt über die Infrastruktur von Straßen- und Schienennetz. Das Be- und
Entladen der Container auf Chassis, LKW oder Güterzüge erfolgt durch die Lagerkräne
oder aktive Flurfördergeräte [8].
2.4 Planungsprobleme im Containerterminal
Wie in Kapitel 2.3 beschrieben finden in Containerterminals viele sich gegenseitig beeinflussende Prozesse statt. Um kurze Liegezeiten der Schiffe und einen hohen Umschlag zu erreichen, ist es erforderlich die Planungsprobleme eines Terminals zu betrachten, um dafür Lösungen zu entwickeln. Eine simultane Lösung der Probleme ist
nicht einfach möglich, weil Containerterminals sehr komplexe Systeme darstellen. Die
Lösung der einzelnen Probleme erfolgt deshalb meist hierarchisch, wobei die Lösung
eines übergeordneten Problems Input für die Lösung der untergeordneten Probleme
ist. Da insbesondere der Einsatz von AGVs von anderen Planungsproblemen abhängig
ist, soll im weiteren der nähere Zusammenhang betrachtet werden.
Abbildung 4 zeigt auftretende Probleme im CT. Eine grobe Einteilung der Probleme in zwei Klassen unterscheidet zwischen Terminaldesign und Terminallogistik [1].
4
Lehmann 2006, S.19
6
Abb. 4 Übersicht über die wichtigsten Planungsprobleme im Containerterminal4
Hinsichtlich der Zeitskala lässt sich der Entscheidungsprozess zwischen drei Ebenen,
der strategischen, der taktischen und der operativen differenzieren. Die strategische
Ebene hat einen langen Planungshorizont (über Jahre hinweg) mit der Absicht, Ziele,
Grundsätze oder Richtungen zu definieren. Hierbei lassen sich falsche Entscheidungen
nur schwer und mit viel Kapital korrigieren. Entscheidungen auf taktischer Ebene haben einen mittleren Planungshorizont (über Monate-Wochen hinweg) und zielen auf
die Unterstützung der strategischen Entscheidungen ab. Falsche Entscheidungen sind
einfacher zu korrigieren als solche auf strategischer Ebene. Ein kurzer Planungshorizont
(über Tage-Stunden) charakterisiert Entscheidungen auf der operativen Ebene. Ziele
sind detaillierte Entscheidungen und Überwachung sowie Ausführung. Sofort durchführbar und mit wenig Kosten verbunden sind hier Änderungen der Entscheidung [3].
Das Terminaldesign ist im Entscheidungsprozess mit Problemen auf strategischer
und taktischer Ebene verbunden, Terminallogistik hingegen auf operativer. Im näheren
soll auf die beiden Klassen und ihre Planungsprobleme in den folgenden Abschnitten
eingegangen werden.
Terminaldesign: Die im Terminaldesign auftretenden Probleme beziehen sich auf
die langfristige Auswahl von Ressourcen und Konfigurationen. Zuerst ist es notwendig,
das strategische Problem der Standortauswahl zu lösen. Strukturelle Standortfaktoren
beeinflussen hier die Entscheidung. Infrastrukturelle Anbindungen, politische Rahmenbedingungen oder technische Möglichkeiten sind hier beispielhaft als Faktoren zu nennen. Nach getroffener Standortwahl wird nach Gegebenheiten vor Ort die Aufgabe der
Layoutplanung, mit dem Ziel die geplante Umschlagmenge zu erreichen, vorgenommen.
Entscheidende Faktoren sind hier die Länge der Kaimauern oder Lagerkapazitäten. Die
Geräteauswahl beschäftigt sich damit, welche Geräte im Terminal eingesetzt werden
und wie groß die Flottengröße ist. Im Containerterminal Altenwerder werden zum Beispiel 15 Containerbrücken sowie 84 AGVs eingesetzt [6]. Das Fahrkurslayout muss beim
7
Einsatz von AGVs strukturiert werden, was durch ein Gitter aus Transpondern im Boden oder durch GPS und Radar erfolgen kann. Die Punkte des Gitters werden dann
zu einem logischen Fahrkurs zusammengeschaltet [1].
Terminallogistik: Die Planungsprobleme der Terminallogistik sind von operativer
Natur und beschäftigen sich mit dem konkreten Einsatz der Ressourcen in kurzfristigem
Planungszeitraum. Die Stauplanung gibt Auskunft über die Positionen der Container,
die im Schiff verstaut werden sollen. Durch die Angabe von Bay, Tier (Ebene) und
Row (Reihe) erhält jeder Container eine exakte Position. Die Bestimmung des Stauplans erfolgt vor Be- und Entladung in zwei Phasen. Erstens einer groben Planung
bei der jede Staupositionen eine Containerkategorie, zum Beispiel aufgrund Größe,
Typ, Gewicht oder Zielhafen, zugeordnet wird. Und zweitens einer genauen Planung
in der die Container eine genaue Position erhalten. Diese Planung geschieht im voraus
durch den Terminalplaner des Hafens. Die Liegeplatzzuordnung weist jedem Schiff ein
Liegeplatz im Terminal zu. Aspekte wie die Nähe zu den Lagerblöcken in denen Container zur Aufladung auf das Schiff liegen, technische Beschränkungen oder Konflikte
mit anderen Schiffen sind hier wichtig. Erst nach der Liegeplatzzuordnung kann die
Kranzuordnung erfolgen bei der jedem Schiff Containerbrücken zur Be- und Entladung
zugewiesen werden [3].
Beim Quay-Crane-Scheduling (QC-Scheduling) muss geplant werden, in welcher
Reihenfolge die Be- und Entladeoperationen durchgeführt werden. Möglich sind hier
die Vorgehensweisen horizontale oder vertikale sowie seeseitige oder landseitige Aufund Abladung. Der Kranfahrer der Containerbrücke kann kurzfristige Änderungen in
der Planung vornehmen, etwa durch Änderung der Abladereihenfolge aufgrund eines
verkanteten Containers. Die Einsatzplanung der Horizontalfahrzeuge muss in der Lage
sein solche kurzfristigen Abweichungen zu berücksichtigen und angemessen zu reagieren.
In der Lagerblockauswahl wird bestimmt, in welchem Block Container eingelagert
werden. Wie auch im QC-Scheduling beeinflusst die Lagerblockauswahl die Einsatzplanung des Horizontaltransports, da sie festlegt, an welchen Lagerblock die Container
von den Fahrzeugen befördert werden müssen. Eine Verfeinerung der Lagerungsposition
nimmt die Stellplatzzuweisung durch Festlegung der genauen Stellplätze im Lagerblock
vor. Aus diesen kann dann die Reihenfolge der Ladeoperationen für die Lagerkräne bestimmt werden. Erst nach diesen Planungsschritten kann die Einsatzplanung für den
Horizontaltransport vorgenommen werden. Es muss also konkret festgelegt werden,
welches Fahrzeug welchen Container transportiert, wann die Aufladung und Abladung
stattfindet und welche Route das Fahrzeug wählt. Weitere Details hierzu finden sich
in Kapitel 3. Die Verkehrsregelung kann eher als ein Steuerungsproblem angesehen
werden, da es Echtzeitanforderungen stellt und auf nicht planbare Ereignisse reagieren
muss. Planungsprobleme im Hinterland sind denen der Abfertigung der Schiffe an der
Kaimauer sehr ähnlich und sollen hier nicht weiter erläutert werden.
3 Einsatzplanung von Automated Guided Vehicles in Containerterminals
3.1 Problemstellung Einsatzplanung von AGVs in Containerterminals
Der Begriff Einsatzplanung von AGVs beschreibt hauptsächlich drei zu lösende Planungsprobleme. Diese sind das Scheduling das Routing sowie die Überwachung des
Verkehrs der AGVs [2].
8
Abb. 5 Problemstellung der Einsatzplanung5
Unter Scheduling versteht man die Zuweisung von AGVs zu Transportaufträgen
und die Erstellung der Einsatzpläne der AGVs.
Als Routing bezeichnet man das Bestimmen der Route im Fahrkurs vom Ausgangsort zum Ziel des AGVs basierend auf der aktuellen Verkehrssituation. Hierfür gilt es
zwei Probleme zu lösen. Erstens ist die Entscheidung zu treffen, ob eine Route existiert,
und zweitens, ob die gefundene Route konflikt-, stauungs- und deadlockfrei ist [4].
Insbesondere das Auftreten von Deadlocks stellt in Containerterminals ein Problem
dar, welches hier nicht näher betrachtet wird. Wann Deadlocks auftreten und Strategien zur Behandlung finden sich in [1]. Da Routing und Verkehrsregelung meist in der
Steuerungssoftware der Hersteller von AGVs integriert ist, wird hier Einsatzplanung
hier als Scheduling verstanden und Routing sowie Überwachung nicht weiter behandelt.
Abbildung 5 zeigt die Problemstellung Einsatzplanung von AGVs formal. Die Eingangsdaten sind Standort im Fahrkurs, Beladung sowie die maximale Kapazität zum
Planungszeitpunkt aller AGVs. Die Transportaufträge (TA) bestehen aus der Größe des
Containers in TEU, die Auf- und Abladeorte, geplante Zeitpunkte sowie die voraussichtliche Dauer der Ladeoperationen. Die dritte Eingangsgröße beschreibt das Fahrkurslayout in Form einer Zeitmatrix, welche die kürzesten Transportzeiten zwischen
den für die AGVs wichtigen Orten angibt. Bei der Planung müssen einige Nebenbedingungen beachtet werden. Eine Zuordnung von AGV und TA muss vorgenommen
werden, wobei die Beladung des AGVs mit einem Container vor der Abladung stattfinden muss und die maximale Kapazität des Fahrzeugs nicht überschritten werden
darf. Die Fahr- und Beladungszeiten müssen berücksichtigt werden und dürfen die
Mindestabstände nicht unterschreiten. Aus den Eingangsgrößen wird unter Berücksichtigung der Nebenbedingungen ein detaillierter Plan für die AGVs erstellt, um ein
angestrebte Zielstellung zu erreichen. Die angestrebte Zielstellung ist meist die Minimierung des Makespans (Liegezeit des Schiffs an der Kaimauer). Möglich ist hier aber
auch die Minimierung der Verspätung oder Leerfahrzeiten. Ein detaillierter Plan setzt
sich aus der Zuordnung von AGV und TA, der Reihenfolge der auszuführenden Operationen sowie den dazugehörigen Startzeiten zusammen. Das Problem der Zuordnung
ist NP-vollständig und somit nicht in polynomieller Laufzeit lösbar [1].
5
Lehmann 2006, S.34
9
3.2 Abgrenzung zu verwandten Problemen
Klassische Scheduling- und Routing Probleme wie das allgemeine General Pickup and
Delivery Problem (GPDP) und Spezialisierungen davon sind bekannt und wurden charakterisiert [9]. Im Folgenden soll näher auf das GPDP mit seinen drei bekanntesten
Spezialisierungen eingegangen werden, um zu zeigen, warum diese Probleme sich nicht
direkt auf AGVs in CTs übertragen lassen. Beim GPDP ist das Ziel eine Menge von
Routen zu bestimmen, um eine Transportaufgabe zu lösen. Mit Hilfe einer Flotte von
Fahrzeugen, die eine gegebene Kapazität, einen Start- sowie Zielort haben, soll eine
Menge von Transportaufträgen, bestehend aus einer Ladung und verschiedenen Aufund Abladeorten, transportiert werden. Dabei muss die Ladung jedes Transportauftrags von einem Fahrzeug übernommen werden, sodass die Ladung vom Auf- zum
Abladeort ohne Umladung gebracht wird. Darüber hinaus muss die Aufladung vor der
Abladung erfolgen, die Kapazität der Fahrzeuge darf nicht überschritten werden und
jeder Ort nur einmal besucht werden [9].
Der erste Spezialfall ist das Vehicle Routing Problem (VRP) bei dem Start- und
Zielorte der Fahrzeuge ein Depot ist in dem die Fahrt startet und auch endet. Anders
als beim GPDP besteht ein Transportauftrag aus nur einem Besuch eines Ortes [1].
Das Pickup and Delivery Problem (PDP) geht ebenfalls von einem Depot aus. Von
hier starten die Fahrzeuge zur Abholung der Ladung und kehren nach Lieferung wieder
dorthin zurück [9].
Falls zeitliche Restriktionen eine Rolle spielen, fasst man das Problem unter dem
Begriff Pickup and Delivery Problem with Time Windows (PDPTW) zusammen. Hier
können Zeitfenster für Abholung und Lieferung, feste Abhol- und Lieferzeiten oder
auch maximale Fahrzeiten festgelegt sein [1].
Das Dial-a-Ride Problem (DARP) ist prinzipiell ein PDP, wobei die Transportaufträge nur aus einer Einheit bestehen, und ist motiviert durch den Transport von
Personen. Auch hier können die gleichen zeitlichen Beschränkungen wie beim PDP eine Rolle spielen, was man als Dial-a-Ride Problem with Time Windows (DARPTW)
bezeichnet [9, 1].
Betrachtet man die Umgebung der Containerterminals, so werden Gemeinsamkeiten und Unterschiede zu den oben aufgeführten Problembeschreibungen deutlich. Am
ähnlichsten ist die Einsatzplanung von AGVs zum DARPTW (Einsatz von SLC) und
PDPTW (Einsatz von MLC), jedoch ergeben sich einige Abweichungen: AGVs haben
kein Depot von dem sie starten, sondern können über den Fahrkurs verteilt sein. Auch
der Beladungszustand kann variieren. Es existiert eine endliche Anzahl an Orten, die
von verschiedenen Fahrzeugen wiederholt angefahren werden können bzw. angefahren
werden müssen, als Beispiel sind hier die Containerbrücken oder Lagerblöcke zur Aufoder Abladung der Container genannt. Aufgrund zeitlicher Verzögerungen in der Planung werden Abhol- und Lieferzeiten weniger strikt gehandhabt, da nur der früheste
Startzeitpunkt einer Operation gegeben ist. Das Auftreten von Verspätungen in der
Planung ist zulässig. Die Notwendigkeit der Synchronisation zwischen AGVs und Kränen ist ein charakteristisches Merkmal für den Einsatz in CTs, da AGVs als passive
Fahrzeuge keine selbstständige Auf- und Abladung vornehmen können und somit keine
Puffer an den Kränen entstehen können. Dies unterscheidet den Einsatz von AGVs
in CTs von dem in Flexiblen Fertigungssystemen in denen Puffer an den Maschinen
vorhanden sind. Weiterhin ist die Reihenfolge der Ladeoperationen der Kräne wichtig
und sollte nach Möglichkeit nicht geändert werden [1].
10
3.3 Eigenschaften der Einsatzplanung
Einsatzplanung von AGVs in Containerterminals wird gekennzeichnet durch Charakteristiken des Problems und der Einsatzplanung. Aus der Problemstellung ergeben sich
besondere Erfordernisse der Planung.
In Bezug auf die Verfügbarkeit von Informationen können Probleme statisch oder
dynamisch sein. Statische Probleme haben die Eigenschaft, dass alle Informationen im
voraus bekannt sind. Im Gegensatz dazu sind bei dynamischen Problemen die Informationen nicht vorher bekannt und der Informationsstand ändert sich im Zeitverlauf.
Lösungen für dynamische Planungsprobleme werden oftmals durch das Lösen einer Sequenz von statischen Problem erreicht. Einsatzplanung von AGVs in CTs stellen ein
dynamisches Problem dar, was dazu führt, dass Pläne nur bis zu einer Neuplanung
gültig sind und dann durch neue ersetzt werden.
Die Sicherheit der verfügbaren Informationen in einer Anwendungsumgebung ist
ein weiteres Kriterium. Hier wird unterschieden zwischen stochastischen und deterministischen Anwendungsumgebungen. In deterministischen Umgebungen treten die
Ereignisse so ein, wie sie vorhergesagt wurden. Anders in stochastischen Umgebungen
wie CTs in denen aufgrund externer und interner Einflüsse, zum Beispiel Witterungsbedingungen, welche die Ladezeiten beeinflussen, starke Schwankungen auftreten. Die
Schwankungen können durch Wahrscheinlichkeitsverteilungen abgebildet werden.
Die Problemstellung kann integriert oder separat betrachtet werden, was sich auf
Wechselwirkungen mit anderen Planungsproblemen bezieht. Eine integrierte Betrachtung liegt vor, wenn alle Planungsprobleme simultan betrachtet werden, was im komplexen System Containerterminal bisher noch nicht erreicht wurde. Vielmehr wird die
Einsatzplanung von AGVs separat betrachtet und die Wechselwirkungen durch Schnittstellen zu den Kränen berücksichtigt.
Hinsichtlich der Qualität von Lösungsverfahren kann eine Einteilung in optimierende und heuristische Verfahren vorgenommen werden. “Optimierende Verfahren zeichnen
sich dadurch aus, dass die beste Lösung eines Problems - also die mit dem maximalen
bzw. minimalen Zielfunktionswert - bestimmt wird” [1]. Optimalen Lösung sind häufig
mit einem hohen Rechenaufwand verbunden. Heuristische Verfahren sind meist weniger
rechenintensiv liefern aber auch nur eine hinreichend gute Lösung [1].
Verfahren können eine Online- oder Offline-Einsatzplanung vornehmen. Online Einsatzplanung betrachtet einen kurzfristigen Vorausschauhorizont von einer oder wenigen
Operationen, und Entscheidungen werden erst dann getroffen, wenn sie benötigt werden. Online Einsatzplanung eignet sich besonders bei Schwankungen durch interne oder
externe Einflüsse, da diese zur Laufzeit mit einbezogen werden können. Offline Verfahren planen über einen längeren Zeitraum und Entscheidungen werden für mehrere
Operationen simultan getroffen. Auftretende Abweichungen in der Planung erfordern
oft eine Neuplanung oder Veränderung des Plans.
Im laufenden Betrieb der Einsatzplanung ist es notwendig, neue Planungen aufgrund auftretender Ereignisse, zum Beispiel neue Transportaufträge, durchzuführen.
Eine Neuplanung kann ergänzend oder revidierend sein. Bei ergänzender Neuplanung
wird der letzte Plan, als unveränderliche Basis, um neu bekannt gewordene Transportaufträge lediglich ergänzt. Revidierende Neuplanung dagegen verändert die Struktur
des bestehenden Plans. Neuplanung kann durch verschiedene Faktoren ausgelöst werden, was üblicherweise nach drei Strategien passieren kann. Die periodische Neuplanung
wird in konstanten Intervallen vorgenommen, wobei neue Ereignisse innerhalb der Zeitintervalle in die nächste Planung aufgenommen werden. Ereignisorientierte Neuplanung
11
wird angestossen, wenn signifikante Abweichungen zwischen Plan und Umsetzung auftreten. Auch die Freigabe eines Transportauftrags oder ein wieder verfügbares AGV
können Auslöser sein. Die hybride Neuplanung kombiniert die zwei genannten Strategien [7].
4 Verfahren zur Einsatzplanung von Automated Guided Vehicles
Die Entwicklung von Verfahren zur Einsatzplanung von AGVs in CTs hat in den letzten Jahren mehr Aufmerksamkeit bekommen. Insbesondere die Flottengröße und Echtzeitanforderungen stellen Herausforderungen dar [4].
Lösungsverfahren zum Scheduling lassen sich in die Kategorien Konstruktionsverfahren oder Verbesserungsverfahren einteilen. Konstruktionsverfahren haben das Ziel
eine zulässige nicht zwingend optimale Lösung zu finden. In Bezug auf Einsatzplanung
von AGVs bedeutet dies, die Pläne für AGVs zu bestimmen, ohne dabei Restriktionen,
wie Reihenfolgebedingungen, zu verletzen [1]. Die Berechnung von nicht optimalen aber
zulässigen Lösungen geht oftmals schneller als das Finden einer optimalen Lösung und
reicht meist aus. Solche nicht optimalen Lösungen können mit Hilfe von Verbesserungsverfahren in ihrer Lösungsgüte erhöht werden. Hierbei werden Modifikationen an der
Lösung vorgenommen [1].
4.1 Einfaches Auswahlverfahren
Hier soll nun ein einfaches Online-Auswahlverfahren vorgestellt werden. Dieses OnlineKonstruktionsverfahren liefert eine zulässige Lösung der Zuordnung von AGV und
Transportauftrag (TA) für Single Load Carrier und wendet die Strategie des wiederholten Lösen statischer Teilprobleme an. Das Auswahlverfahren wird durch zwei
verschiedene planungsauslösende Ereignisse angestossen. Erstens durch die Freigabe
eines neuen Transportauftrags (TA-initiierte Einsatzplanung) oder zweitens durch ein
verfügbares AGV nach Beendigung einer Abladung (AGV-initiierte Einsatzplanung).
Wird die Planung durch ein solches Ereignis ausgelöst, so muss statt einer m:n nur eine 1:n oder eine m:1 Zuordnung gelöst werden. Bei TA-initiierter Einsatzplanung wird
also einem neuen Transportauftrag eines von m verfügbaren AGVs zugeordnet. Analog
wird bei AGV-initiierte Planung ein neuer Auftrag aus n neuen Transportaufträgen
zugewiesen.
Abbildung 6 zeigt den Ablauf des Verfahrens. Nach Eintritt eines planungsauslösenden Ereignisses wird je nach Art unterschiedlich vorgegangen. Wird ein AGV verfügbar,
muss, falls offene TA vorhanden sind, ein TA ausgewählt und ein neuer Plan zurückgegeben werden. Sind keine TA offen, so wird das AGV geparkt und bleibt weiterhin
verfügbar. Ist das auslösende Ereignis ein neuer TA muss aus den verfügbaren AGVs
eines ausgewählt werden, um den Auftrag zu übernehmen. Gibt es jedoch keine verfügbaren AGVs, so wird der TA in die Menge der offenen TAs aufgenommen. Weitere
Aspekte sind wichtig für das Verfahren und werden im Folgenden beschrieben.
Zum einen ist der Vorausschauhorizont bei diesem Verfahren nur ein Transportauftrag je Kran. Das heißt ein TA wird freigegeben sobald die Bearbeitung des vorherigen
Auftrags beginnt und ein danach ausgewähltes AGV hat noch Vorlaufzeit zur Anfahrt
6
Lehmann 2006, S.60
0#1A->+##-(#-E=(),+$21-(0%-'()*E&=+)(#-?C;-=.<F-(0%(%-5**(%(%-6?-&0=1A->0(-.$&(5)>%(1<()>(%-G"%%(%-H>F,F-8I:-=.<F-%I:JF-?%#5%#1(%-=3(0=1->0(-D3+%$%&-()*53&35#A-$%>-(0%(K$5)>%$%&-G+%%-()#1-&(*$%>(%-<()>(%A-<(%%-#0B,->0(-;()*E&=+)G(01->()-?C;#-=.<F->0(L(%&(- >()- 5**(%(%- 6?#- M%>()1F- N()- ?=3+$*- >()- (0%*+B,(%- ?$#<+,3'()*+,)(%- 0#1- 0%?==03>$%&-O@P->+)&(#1(331F-12
D3+%$%&#+$#3"#(%>(#-/)(0&%0#
?)1->(#
23+%$%&#+$#3"#(%>(%
/)(0&%0##(#
?C;
2+)G(%
%(0%
?C;-=((%>(1-3(1.1(
Q2()+105%-08-D3+%
R($()-6?-<0)>-=(G+%%1
C0=1-(#
5**(%(-6?#S
C0=1-(#
'()*E&=+)(
?C;#S
T+
T+
U$B,(-=(#1(%-6?-$%>
5)>%(-0,%->(8-?C;-.$
U$B,(-=(#1(#-?C;-$%>
5)>%(->0(#(8->(%-6?-.$
R($(%-D3+%-.$)EBG&(=(%
R($(%-D3+%-.$)EBG&(=(%
%(0%
6?->(8-D553
5**(%()-6?#
,0%.$*E&(%
?==03>$%&-O@PV-;5)&(,(%->()-(0%*+B,(%-?$#<+,3'()*+,)(%-.$)-?C;@/0%#+1.23+%$%&Abb. 6 Vorgehen des einfachen Auswahlverfahrens6
N0(-&(%+$(-N$)B,*E,)$%&->0(#()-?)1-'5%-;()*+,)(%-,M%&1->+=(0-'5%->)(0-4)+&(%-+=Vdes Krans. Ist die Freigabe erfolgt, so gilt es ein verfügbares AGV zu finden. Somit kann
auf
Änderungen,
zum Beispiel bei der
Abladereihenfolge
an den
Kränen, +=Ax! kurzfristige
W0(- &)5X- <0)>>()- ;5)+$##B,+$,5)0.5%1&(<M,31H>+'5%- ,M%&18+X&(=30B,reagiert werden.
<0(-'0(3(-6?#-5**(%-#0%>JS-H?=#B,%011-OFYFYFYJ-
Die Frage nach der Verfügbarkeit eines AGV hängt mit dem Beladungszustand
zusammen.
Hier kann zwischen physischem und logischem Beladungszustand unterx! W(3B,(-?C;#-<()>(%-+3#-'()*E&=+)-=(1)+B,1(1S-H?=#B,%011-OFYFYFPJschieden werden. Der physische Zustand bezieht sich auf die physische Beladung zum
aktuellen Zeitpunkt. Der logische Zustand eines AGVs bezieht Informationen aus seix! R+B,-<(3B,(%-Z)01()0(%-<0)>->0(-?$#<+,3->()-6?#-=.<F->()-?C;#-'5)&(%58@
nem aktuellen Plan mit ein. Er ergibt sich aus dem physischen Zustand nach der aktuell
8(%S-H?=#B,%011-OFYFYF[Jausgeführten
Auf- oder Abladeoperation. Ein AGV (SLC) auf der Fahrt zur Abladung
eines Containers am Lagerblock wird somit als verfügbar angesehen [1].
Als dritter Aspekt muss entschieden werden, nach welchen Kriterien AGVs oder
TA zur Zuordnung
ausgewählt werden. Hier kann auf Strategien aus dem Einsatz von
!"#"#"#!
$%&'())*+'(+%&,-%./0
AGVs in Flexiblen Fertigungssystemen zugegriffen werden. Im Falle einer TA-initiierten
Planung bieten sich zwei bekannte Strategien an. Bei der nearest-vehicle-Regel (NV)
/#-30(&1-0%->()-R+1$)-'5%-Q%30%(@;()*+,)(%A->+##->()-;5)+$##B,+$,5)0.5%1-(\1)(8-G3(0%wird das AGV mit der geringsten Entfernung (kürzeste Fahrzeit) zum Aufladeort des
&(<M,31<0)>A- Fahrzeuge,
$8- %$)- #(,)#0B,()(0%- >0(- D3+%$%&.$-die
3+##(%TA gewählt.
welche
weit ]%*5)8+105%(%weg von allen Aufladeorten
sind, (0%*30(X(%werden durch
NV-Regel
benachteiligt
gar nicht eingesetzt.
Um eine gleichmäßige
Nutzung
H'&3F?=#B,%011[FPJF- 4E)-oder
>+#- '5)30(&(%>(D3+%$%&#2)5=3(8=(>($1(1- >0(#A>+##-aller
T(<(03#AGVs zu erreichen, kann die least-utilized-vehicle-Regel (LUV) angewendet werden.
Die LUV-Regel bestimmt die Nutzung eines Fahrzeugs durch Zählen der bereits abgeschlossenen TAs und der dem AGV bereits zugewiesenen Aufträge. Die Zuordnung eines
Transportauftrags zu einem Fahrzeug bei der AGV-initiierten Planung kann mit Hilfe
der first-come-first-serve-Regel (FCFS) oder der shortest-travel-time-Regel (STT) erfolgen. Der TA mit der frühesten Startoperation wird bei der FCFS-Regel ausgewählt,
13
um die Wartezeit jedes Auftrags zu begrenzen. Die STT-Regel weist dem Fahrzeug
den Transportauftrag mit der kürzesten Distanz zum Aufladeort zu, um die Fahrzeit
minimal zu halten [7].
Für das einfache Auswahlverfahren hat sich in Bezug auf die Minimierung der Liegezeiten der Schiffe eine auf Auslastung der Kräne abzielende Verwendung der NV-Regel
für TA-initiierte Einsatzplanung und der FCFS-Regel für AGV-initiierte Einsatzplanung bewährt [1].
4.2 Weitere Verfahren
Das einfache Auswahlverfahren aus Kapitel 4.1 ist ein grundlegendes und einfaches
Verfahren zur Einsatzplanung von AGVs und zeigt ein Beispiel für ein Verfahren zur
Einsatzplanung auf. Die detaillierte Vorstellung weiterer Verfahren kann aufgrund des
Umfangs dieser Arbeit leider nicht vorgenommen werden. Im Folgenden wird auf weitere, umfangreichere Verfahren verwiesen. Das iterative Zuordnungsverfahren Pattern
von Günther et al. [7] ist dem einfachen Auswahlverfahren ähnlich, aber es stößt die
Planung auch an, wenn eine Abweichung einer Startzeit um einen Schwellenwert vorliegt. Die angestoßene Planung unterscheidet nicht zwischen den planungsauslösenden
Ereignissen und erlaubt eine revidierende Neuplanung. Zuweisungsmuster (Pattern)
dienen der Beschreibung möglicher Sequenzen einzelner Operationen von zwei Transportaufträgen. Dieses Offline-Verfahren ist ausgelegt für den Betrieb von Dual Load
Carriern und in der Lage, pro AGV zwei Container gleichzeitig zu transportieren [1].
Weitere Details und Konstruktionsverfahren, wie ein gemischt-ganzzahliges lineares
Optimierungsmodelles für MLC von Lehmann [1], finden sich neben Verbesserungsverfahren in [1, 7].
5 Fazit und Ausblick
Das steigende Transportaufkommen sowie die Reedereien fordern geringe Liegezeiten
der Schiffe und ein hohen Umschlag im Containerterminal. AGVs sind in Containerterminals in aller Welt im Einsatz und bilden ein wichtiges automatisiertes Glied in
der Transportkette. Insbesondere in Ländern mit hohen Personalkosten bietet sich
der Einsatz von AGVs an, um den Umschlag der Terminals zu erhöhen. Diese Arbeit
gibt einen Überblick über den Einsatz von AGVs in der komplexen Umgebung Containerterminal, in der sich Planungsprobleme gegenseitig beeinflussen. Das Problem
Einsatzplanung von AGVs stellt eine Herausforderung dar, da Lösungsverfahren von
verwandten Scheduling- und Routingproblemen nicht auf die komplexe Umgebung der
CTs übertragbar sind und das Scheduling als NP-vollständiges Problem keine triviale
Aufgabe darstellt. Wie der Betrieb von AGVs in Terminals, wie Hamburg Altenwerder,
Singapur, etc., zeigt sind verwendbare Verfahren entwickelt worden.
Um dem zukünftige Transportaufkommen ebenfalls gerecht zu werden, ist es sinnvoll, weitere Forschung zu AGVs in CTs zu betreiben. Die Hardware von AGVs erlaubt,
durch den Einsatz von Multi-Load-Carriern, den Transport von mehreren Containern
gleichzeitig. Hier kann eventuell noch weiteres Potenzial ausgeschöpft werden, indem
weitere Verfahren entwickelt werden, welche die Möglichkeit zum Transport von zwei
oder mehr Container miteinbeziehen. Aktive automatisierte Fahrzeuge (Automated Lifting Vehicles) könnten den Umschlag in Terminals ebenfalls erhöhen, da Puffer an den
14
Containerbrücken und Lagerkränen gebildet werden könnten. Ob die Verfahren zur
Einsatzplanung von AGVs auf ALVs übertragen werden können, ist offen und muss
weiter erforscht werden. Eventuell sind neue Verfahren notwendig.
Die Einsatzumgebung Containerterminal wird eher separat betrachtet. Eine integrierte Betrachtung ist sehr schwierig und bietet weiteren Anlass zur Forschung.
Eventuell ist eine Umschlagssteigerung durch eine integrierte Lösung der operativen
Planungsaufgaben möglich.
Literatur
1. Lehmann, M. (2006): Einsatzplanung von Fahrerlosen Transportsystemen in SeehafenContainerterminals. Dissertation, Technische Universität Berlin.
2. Cheng Y-L.; Sen H-C. (2005): Dispatching Automated Guided Vehicles in Container Terminal.
3. Nang Laik, M. (2008): Optimal Planning of Container Terminal Operations. Dissertation,
Imperial College London
4. Qiu L.; Hsu W-J.; Huang S-Y.; Wang H. (2002): Scheduling and routing algorithms for
AGVs: a survey. International Journal of Production Research, Volume 40, Issue 3 February
2002 , pages 745 - 760
5. Internetseite der Zeitschrift stern besucht am 23.08.2010, http://www.stern.de/wissen/
technik/high-tech-hafen-singapur-alles-bewegt-sich-wie-von-geisterhand-609980.
html
6. Internetseite der Hamburger Hafen und Logistik AG, http://www.hhla.de/
Technische-Daten.655.0.html, besucht am 23.08.2010
7. Günther, H-O; Grunow, M., Lehmann, M. (2006): AGV Dispatching Strategies at Automated Seaport Container Terminals. in Container Terminals and Cargo Systems, SpringerVerlag, Berlin Heidelberg.
8. Koppe B.; Brinkmann B. (2008): State of the art of handling and storage systems on container terminals. Chinese-German Joint Symposium on Hydraulic and Coastal Engineering.
9. Savelsbergh, M.W.P; Sol, M. (1995): The General Pickup and Delivery Problem. Transportation Science, Volume 29, pages 17-29.
10. Brinkmann, B. (2005): Seehäfen. Planung und Entwurf. Springer-Verlag, Berlin und Heidelberg