Konzeption eines autonomen Gepäckbeförderungssystems für Flughäfen


Diplomarbeit, 2002

125 Seiten, Note: 1,0


Leseprobe


Inhaltsverzeichnis

Danksagung

Abstract

1 Einleitung
1.1 Motivation
1.2 Gliederung

2 Gepacktransport in Flughafen
2.1 Merkmale bestehender Gepackbeforderungssysteme
2.2 Anforderungen an neue Gepackbeforderungssysteme

3 Auftragsvergabe und Routenplanung in verschiedenen Anwendungsbereichen
3.1 Routing in Datennetzen
3.2 Produktionsplanung
3.3 Routenplanung in der Robotik
3.4 Routenplanung im Strafien- und Schienenverkehr

4 Dezentrale Koordination und Steuerung der DCVs’ eines Gepackbeforderungssystems
4.1 Management der leeren DCVs’
4.1.1 Einfache Steuerungsalgorithmen
4.1.2 Potentialverfahren
4.1.3 Marktbasiertes Verfahren
4.2 Routenwahl
4.2.1 Hop-by-hop routing ohne Anmeldung
4.2.2 Source routing mit grober Anmeldung
4.2.3 Source routing mit verbindlichen Zeitfenstern
4.3 Zusammenfassung

5 Detaillierte Ausfuhrung des dezentralen Steuerungskonzepts
5.1 Streckenkosten
5.2 Prioritat: die Entscheidung uber den Vorrang an Weichen
5.3 Wegsuche beladener DCVs’
5.4 Management der leeren DCVs’
5.5 Erkennung und Auflosung von Deadlocks
5.6 Kommunikation
5.7 Erweiterungen
5.7.1 eine Spur - zwei Richtungen
5.7.2 Richtungsumkehr von Streckenelementen
5.7.3 Uberwachung

6 Simulationsmodelle
6.1 DCV Klasse
6.1.1 Fahrzeugdynamik
6.1.2 Konvoifahrten / Prioritaten
6.1.3 Bestimmung der Fahrtroute
6.1.4 Umplanung
6.2 Rail Klasse
6.3 Klassen fur Streckenknoten
6.3.1 Weichenklassen switch12 und switch21
6.3.2 Beladestationsklassen LoadingSide und LoadingSideSec
6.3.3 Entladestationsklassen UnloadSide und UnloadSideSec
6.4 Momentaufnahmen wahrend der Simulation

7 Simulationsdurchfuhrung und -ergebnisse
7.1 Simulationsdurchfuhrung
7.2 Simulationsergebnisse
7.2.1 Simulation des Terminalbetriebs
7.2.2 Simulation mit drei sternformig verbundenen Terminals

8 Zusammenfassung und Ausblick

Anhang
A1 Quellcode far die Simulation
Methode AnfrageNeueBeladestation
Methode AnfrageNeueSicherheitsstation
Methode CalcCost
Methode CalcReward
Methode CalcRewardSec
Methode CalcRewardWithoutDCV
Methode CalcRideTimeldeal
Methode CalcRideTimePart
Methode CalculateRoutes
Methode LoadDCV
Methode StartLoading
Methode UnloadDCV
MethodeUnlock
Methode UpdateRouteTimes
Methode VControl
A2 Flugplan als Grundlage fur die Gepackdaten

Literaturverzeichnis

Danksagung

Diese Diplomarbeit entstand am ABB Forschungszentrum in Ladenburg in Zusammenarbeit mit dem Institut fur Industrielle Informationstechnik an der Universitat Karlsruhe (TH).

Herrn Prof. Dr.-Ing Uwe Kiencke danke ich fur die Ermoglichung und Betreuung der Diplomarbeit.

Mein besonderer Dank gilt Herrn Dr.-Ing. Alexander Fay fur die Betreuung der Diplomarbeit vor Ort am ABB Forschungszentrum. Durch bestandiges Interesse, fachliche Diskussionen und Anregungen hat er wesentlich zum Gelingen der Arbeit beigetragen.

Mein Dank gilt in gleicher Weise Herrn Dipl.-Ing. Carsten Thierer fur die Hinweise und Unterstutzung bei der Erstellung der Diplomarbeit.

Herrn Dipl.-Ing. Olof Norlund und D ipl.-Ing. Klaus Lilienthal von de r ABB Airpot Technologies GmbH danke ich fur wertvolle Hinweise uber bestehende Gepackbeforderungssysteme und di e Erstellung eines Simulationstools. Die Zurverfugungstellung und Einweisung in den AirportDataGenerator hat mir die Generierung der Eingangsdaten fur die Simulation erlaubt.

Meiner Familie und m einen Freunden danke ich fur anregende Diskussionen und di e Mithilfe bei der Korrektur der vorliegenden Arbeit.

Concept for an autonomous system for baggage transportation in airports

Master Thesis of Ivo Fischer

Abstract

In this thesis a novel control structure for destination coded vehicles (DCVs) roaming autonomously in a track network without any centralized control entity is proposed and simulated.

The DCVs have the ability of transporting abaggage item between check-in counters and gate positions in an airport. The major tasks of the control concept are routing of DCVs as well as allocation of new transportation tasks to empty vehicles.

One of the major challenges in today’s ever-growing airports is timely baggage handling. Today conventional conveyor and tilt-tray systems used for baggage transport are not fast enough. But DCVs are able to reach the required speeds. Depending on the size of the airport there can be need for several thousand DCVs. The high number of vehicles combined with a steady emergence of new transport tasks is a challenge for today’s centralized control architecture and restricts their utilization.

To overcome problems with current DCVs systems a new approach consisting of DCVs controlled by a decentralized architecture is proposed. The DCVs are coordinated by a market mechanism, where baggage loading stations are bidding for empty DCVs to pick up a baggage item. As soon as a DCV decides to travel to a loading station it notifies the served station and reports its’ the estimated arrival time. This information enables the station to adjust its bids. The bidding strategy can be chosen depending upon the optimization aim, for example by favouring bags that have waited longest. A more complex auction scheme is not required, because all the entities are designed by one organisation that can ensure a honest behaviour of the market’s participants.

The proposed routing strategy resembles the source routing in data networks. Upon choosing a destination a DCV autonomously decides which route it will use. After choosing the route it notifies all track elements it will pass to enable them to predict their load. The tracks’ load prediction allows the DCVs to estimate the transit times. Furthermore the track elements are able to adjust the cost for DCV transit in order to avoid future trafficjams.

With the strategy of routing and empty vehicle allocation described above, the DCVs can be coordinated. In order to reduce the communication bandwidth requirement, strategies used for database search are employed. Instead of collecting all route and bid information by each DCV itself, the idea of mobile agents is applied. Information can be filtered on stationary track computers, thus only the results of the filtering operation have to be transmitted by wireless technology to the DCVs. The DCVs in return need only to pass a small amount of information to the track computers containing the DCVs intentions.

A simulation of the proposed system is conducted. It is based on the event discrete standard simulation tool eM-Plant™. With this tool the DCV system of Singapore’s Changi Airport Terminal 1 is modelled and simulated. The simulation results show that the proposed control concept works properly.

1 Einleitung

Ziel dieser Diplomarbeit ist die Konzeption eines neuartigen, autonomen Gepackbeforderungssystems fur Flughafen. Die bisher eingesetzten Systeme verwenden zentrale Steuerungsansatze. Die Neuartigkeit des vorgeschlagenen Konzeptes liegt in der dezentralen, autonomen Koordination und S teuerung selbstandiger, schienengebundener Fahrzeuge (DCVs), welche zum Transport aller anfallenden Gepackstucke in Flughafen eingesetzt werden. Die Entschiedungen, die von den einzelnen DCVs im Rahmen dieser Steuerung getroffen werden mussen, basieren auf der in diesem Systemansatz gewahlten Verteilung von Wissen und Information. Als Anforderung an das System ist das erforderliche Datenaustauschvolumen zwischen DCVs untereinander undm it Streckenrechnern ist moglichst gering zu halten, da fur diese Kommunikation aufgrund der Anlage der DCVs’ nur ein drahtloses Netzwerk mit relativ geringer Bandbreite zur Verfugung steht.

1.1 Motivation

Der Transport von Gepackstucken ist einer der entscheidenden Erfolgsfaktoren eines modernen Flughafens. ,,Die Zufriedenheit des Passagiers im Flugverkehr wird wesentlich durch ein funktionierendes Gepackhandling am Flughafen bestimmt. Hierbei spielen auf der Abflugseite die Sortiergenauigkeit, auf der Ankunftseite eine schnelle Bereitstellung des Gepacks eine wesentliche Rolle.“[Beu98]. Daruber hinaus ist es vongrofier Bedeutung, dab das Gepack beim Umsteigen genugend schnell in das neue Flugzug eingeladen werden kann. Nicht nur die Passagiere sind an einem reibungsfreien undm oglichst schnellen Gepackhandling interessiert, sondern auch die Airlines, da jede Minute, in der die Flugzeuge am Boden stehen, einen Verdienstausfall zur Folge hat.

Da die international bedeutenden Flughafen heutzutage immer grofier werden, mussen die Gepackstucke uber immer weitere Strecken transportiert werden. Dies fuhrt zu dem Problem, dafi die herkommlichen, auf Forderbandern basierten Losungen die geforderten Transportzeiten nicht mehr garantieren konnen, weil die maximale Transportgeschindigkeit der Forderbander von 6 m/s relativ niedrig ist. Daher wird zunehmend auf destination coded vehicles (DCVs) zum Uberbrucken grofier Distanzen zuruckgegriffen. Die DCVs konnen Maximalgeschwindigkeiten vonube r 10m/s erreichen unds ind somit bestehenden Transportbandern uberlegen.

Da die Anzahl der Freiheitsgrade durch den Einsatz autonomer DCVs sehr stark zunimmt, werden die Steuerungskonzepte bisher unbekannten Leistungsanforderungen unterworfen. Bei dem ersten eingesetzten, flughafenweiten DCV System des Grofifughafens Denver im Jahr 1994 wurde die Steuerungsarchitektur so weit uberfordert, dafi der Flughafen erst mit einer Verspatung von 1 6 Monaten in Betrieb genommen worden konnte. Dazu mufite das DCV System stark vereinfacht werden und ein zusatzliches, herkommliches System parallel installiert wurde [Sch96] [Lan98]. Alle bisherigen Konzepte verwenden eine zentrale Steuerung, die teilweise von dezentralen Einheiten unterstutzt wird.

Um den Anforderungen unterschiedlicher Flughafen gerecht zu werden und eine einfache Erweiterung des Systems zu ermoglichen, durfen keine Einschrankungen der Streckenfuhrung vorgenommen werden.

Schliefilich mufi das Gepackbeforderungssystem sehr zuverlassig arbeiten, da ein Ausfall massive Storungen des gesamten Flughafenbetriebs und damit letzlich imense Folgekosten verursacht.

1.2 Gliederung

In Kapitel 2 findet eine Einfuhrung in das Umfeld der Gepackbeforderung in Flughafen statt. Anschliefiend wird in Kapitel 3 e ine Ubersicht uber verschiedene Planungs- und Wegsuchverfahren aus unterschiedlichen Anwendungsfeldern gegeben. Kapitel 4skizziert grob mogliche Steuerungsansatze welche daraufhin auf ihre Anwendbarkeit in einem Gepackbeforderungssystem hin untersucht werden. Eine Ausarbeitung des praferierten Ansatzes erfolgt detaillierter in Kapitel 5. D arauf aufbauend wird in Kapitel 6 auf die Umsetzung in einer Simulation eingegangen. Kapitel 7 stellt die Resultate der Simulationsdurchfuhrung vor. Diese Arbeit schliefit in Kapitel 8 mit einer Zusammenfassung und einem Ausblick.

2 Gepacktransport in Flughafen

Das zu transportierende Gepack in Flughafen lafit sich in drei Klassen einteilen. Diese Klassen entsprechen den Passagiergruppen, die abfliegen, ankommen und umsteigen.

- Das Gepack der abfliegenden Passagiere mufi von den Check-In Schaltern zunachst zu den Sicherheitskontrollstationen transportiert werden. Die Sicherheitskontrollen werden, abhangig vom jeweiligen Flughafen, in der Regel in mehreren aufeinander folgenden Stationen durchgefuhrt, bis die Gepackstucke schliefilich als sicher klassifiziert werden. Nun mussen sie entweder zu der Verladestation, die fur das Zielflugzeug bestimmt wurde, oder in den Fruhgepackspeicher transportiert werden. Der Fruhgepackspeicher wird benotigt, falls die Verladestation noch nicht fur den entsprechenden Flug freigegeben wurde.
- Fur Gepack vonum steigenden Passagieren entfallen die Sicherheitskontrollen, da sie schon bei dem Abflug vorgenommen wurden. Sonst wird genauso wie bei eincheckenden Fluggasten vorgegangen.
- Das Gepack der ankommenden Reisenden mufi moglichst schnell zur Abholung in der Gepackausgabe bereitgestellt werden.

2.1 Merkmale bestehender Gepackbeforderungssysteme

Die Aufgaben der Gepackbeforderung sind an allen Flughafen weitestgehend gleich. Aufgrund historisch gewachsener Strukturen undba ulicher Beschrankungen werden allerdings in den verschiedenen Flughafen der Welt sehr unterschiedliche technische Systeme zum Transport von G epack verwendet. Uberwiegend von m anueller Arbeit bestimmte Systeme kommen nur in kleineren Flughafen zum Einsatz, daher wird in dieser Arbeit nicht naher auf sie eingegangen.

Fur die automatisierten Systeme der Grofiflughafen lassen sich einheitliche Merkmale bestimmen. Jedem Gepackstuck kann nach der Einlieferung in das System ein Zielort zugeordnet werden, zu dem es transportiert werden mufi, um das Gepackbeforderungssystem wieder verlassen zu konnen. Die Transportsysteme lassen sich nach [Beu98] in zwei Klassen einteilen, die zentral- und die dezentral sortierenden Systeme.

Zentral sortierende Systeme leiten das Gepack von den Check-In Schaltern auf eine zentrale Sortiervorrichtung. Die Sortierer verwenden in der Regel einen Verteilerkreis, welcher von d en Gepackstucken an den entsprechenden Stellen zum Weitertransport verlassen werden kann. Meist werden solche Systeme redundant ausgelegt, das heifit mit zwei Sortierern ausgestattet, um die geforderte Ausfallsicherheit garantieren zu konnen. Diese Sortierverfahren werden haufig in Verbindung mit Bandfordertechniken fur den Gepacktransport realisiert.

,,Dezentrale Sortiersysteme hingegen beinhalten den direkten Transport des Koffers vom Check-in zur Gate-Position des Flughafens, ohne dafi das Gepack gesondert einem zentralen Sortierprozefi unterworfen wird. Zu dieser Art der dezentralen Sortiersysteme gehoren beispielsweise die Behalterfordersysteme und DCV (destination coded vehicle)-Systeme der jungeren Zeit.“[Beu98] Durch eine geeignete Routenwahl wird sichergestellt, dafi die Gepackstucke ihren Zielort erreichen. Diese Systeme lassen sich wiederum, je nach Antriebsform, in zwei Klassen einteilen. Es gibt Realisierungen, die auf schienengebundenen Fahrzeugen basieren und solche mit passiven Behaltern, die auf Rollenbahnen oder Forderbandern bewegt werden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1

Die derzeit eingesetzten schienengebundenen Fahrzeugein dezentralen Sortiersystemen werden von Linearmotoren angetrieben. Ein solches DCV der Firma Beumer ist in Abbildung 2.1 zu sehen. Die Linearmotoren sind in der Strecke integriert und ermoglichen die Ubertragung von Antriebs- und B remskraften auf die Fahrzeuge. Da sich die Antriebseinheiten nicht notwendigerweise in der ganzen Strecke befinden, sind die Fahrzeuge streckenweise nicht beeinflufibar.

Das bisher grofite und komplexeste System, das mit D CVs arbeitet, befindet sich im Grofiflughafen Denver, USA [Swa97][Sch96][AWM+94]. Dort wurde 1994 ein Gepackbeforderungssystem geplant und realisiert, das flughafenweit auf DCVs basiert. Die DCVs wurden dort nicht ausschlieBlich zum Transport zwischen weit entfemten Terminals verwendet, sondern dienen auch der Sortierung.

Bei der Inbetriebnahme stellten sich allerdings erhebliche Mangel heraus, so daB der Flughafen erst mit einer Verspatung von 16M onaten in Betrieb genommen werden konnte [Sch96]. Unter anderem ergaben sich Probleme, weil die Fahrzeuge uber keinen eigenen Antrieb verfugten, sondern nur abschnittsweise per Linearmotoren angetrieben wurden. Daher war uber den Antrieb keine kontinuierliche Steuerbarkeit moglich, so daB die fur die Verfolgung der Fahrzeuge zustandigen Computer diese verwechselten. Dies hat zu ZusammenstoBen und Entgleisungen der Fahrzeuge gefuhrt.

Die Fahrzeuge konnten ihre eigene Geschwindigkeit nicht selbst bestimmen, sondern wurden uber die Uberwachungsrechner der Strecke fremdbestimmt. Zur Steuerung des Systems wurden laut [Sch96] 300,, tracking computers44 verwendet, die die Weicheneinstellungen vornahmen. Dieser Beschreibung zu folge verfugten die Wagen selbst uber keinerlei Autonomie.

Um den Flughafen dennoch betreiben zu konnen, wurde die Komplexitat des Systems stark verringert. „Wie bekannt ist, haben wir in Denver ein By-pass-System (herkommliche Bandfordertechnik) installiert, welches ein halbes Jahr nach Auftragserhalt den groBten Teil des Flughafens zusatzlich bedienen konnte. Dadurch wurde es erst moglich, den Flugbetrieb aufzunehmen. Es ist ein ganz normales, konventionelles System, welches unabhangig vom installierten System lauft.“ [Lan98].

Die Ausfuhrungsform der passiven Behalter zeichnet sich dadurch aus, daB die Gepackstucke in Schalen verladen werden und in ihnen durch das gesamte System befordert werden. Die Schalen werden auf Bandern oder Rollenbahnen transportiert. Da die Schalen einzeln, ahnlich der DCV geleitet werden konnen, ist eine zentrale Sortierung auch hier nicht notig. Das groBte Behaltersystem ist derzeit im Flughafen Frankfurt im Einsatz.

Ein entscheidendes Merkmal von G epackbeforderungsanlagen ist ihre Steuerung. In der Fachliteratur finden sich keine direkten Abhandlungen uber die Steuerung der bestehenden Systeme. Anhand der Systembeschreibungen der Hersteller lassen sich aber dennoch einige Ruckschlusse ziehen. Die derzeit eingesetzten Steuerungsverfahren weisen demnach alle eine zentrale Steuerungskomponente auf. Diese wird in unterschiedlichem MaB vondezentralen Einheiten entlastet. Insbesondere die strategische Planung des Vorhaltens von Leerfahrzeugen wird von der zentralen Einheit vorgenommen [VC98].

2.2 Anforderungen an neue Gepackbeforderungssysteme

Die grofien, intemationalen Flughafen mussen ein zunehmendes Passagieraufkommen bewaltigen. Dies bedeutet, dafi die Zahl der zu transportierenden Gepackstucke steigt. Mit der erhohten Anzahl an Flugbewegungen dehnen sich die Flughafengelande aus, so dafi die Transportwege, insbesondere zwischen den Terminals, zunehmend langer werden. Im Rahmen der Serviceorientierung der Flughafen versuchen diese gleichzeitig kurzere Umsteigezeiten fur Transitpassagiere zu ermoglichen. All diese Bestrebungen und Trends fuhren dazu, dafi die Anforderungen an die Gepackbeforderungssysteme steigen. Wahrend die Transportzeiten der Gepackstucke gesenkt werden sollen, mufi eine gleichbleibend hohe Systemzuverlassigkeit gewahrleistet bleiben. Selbst ein kurzfristiger Ausfall des Gepackbeforderungssystems kann den Flughafenbetrieb sehr weitgehend storen.

Zur Verkurzung der Transportzeiten, konnen DCVs eingesetzt werden, da sie mit uber 10m/s hohere Spitzengeschwindigkeiten als herkommliche Bandfordertechniken erreichen konnen. Fur den Einsatz in Grofiflughafen bedeutet das, dafi die Anzahl der benotigten DCVs in der Grofienordung einiger Tausend liegen kann, um den Transport von mehr als 15.000 Gepackstucken pro Stunde gerecht werden zu konnen.

Die Steuerung eines solchen Systems mufi daher die Aufgabe bewaltigen konnen, mehrere tausend DCVs zu koordinieren. Dabei mussen Beschrankungen der Kommunikationsbandbreite eingehalten werden, da zumindest die Kommunikation von und zu den DCVs drahtlos erfolgen mufi.

Somit scheiden herkommliche zentrale Steuereinheiten zur Bewaltigung dieser Problematik aus, weil einerseit der kommunikationsbandbreite Grenzen gesetzt sind und andererseits der zentralen Neuberechung der Routen vontausenden DCVs’, aufgrund der kombinatorischen Explosion, wahrend des Betreibs Grenzen gesetzt sind. Daher wird in dieser Arbeit ein dezentraler Losungsansatz verfolgt.

3 Auftragsvergabe und Routenplanung in verschiedenen Anwendungsbereichen

In diesem Kapitel werden Auftragsvergabe- und Routenplanungsverfahren aus verschiedenen aktuellen Forschungsgebieten in Hinsicht auf ihre Relevanz fur die Steuerung eines Gepackbeforderungssystems untersucht. Interessante Ideen werden dann in Kapitel 4 aufgegriffen, um ein Verfahren zur Koordination undS teuerung der DCVs des Gepackbeforderungssystems zu entwerfen.

3.1 Routing in Datennetzen

Im Umfeld der weltweit vernetzten Datenverarbeitungssysteme stellt sich die Aufgabe, die Informationen zwischen den einzelnen Rechnern moglichst schnell und kos tengunstig zu ubertragen. Eine Ubersicht uber verschiedene Routingverfahren, also der Wahl der Konten des Netzwerkes, uber die die Informationen weitergeleitet werden, findet sich in den Arbeiten [Mur94] [Tom98] [SchOO].

Neben der leitungsvermittelten Ubertragung, bei der eine Datenleitung exklusiv zur Verfugung steht, gibt es die paketvermittelte Ubertragung. Die paketvermittelte Ubertragung verwendet eine Leitung simultan zum Datentransport fur mehrere Nutzer. Die Gesamtmenge der Daten wird dabei in einzelne Pakete aufgeteilt, die unabhangig voneinander versendet werden. Die einzelnen Netzknoten, Router genannt, leiten die Datenpakete jeweils zu benachbarten Routern weiter, bis das Ziel erreicht ist.

In paketvermittelten Netzen konnen neben statischen Routingverfahren dynamische eingesetzt werden. Die dynamischen lassen sich in zentrale und dezentrale unterscheiden. Bei dem zentralen Ansatz wird die Weginformation in einem zentralen Knoten berechnet, bei dem dezentralen finden die Berechnungen in allen Knoten statt. Die dezentralen Ansatze konnen weiterhin in ,,distance-vector algorithms“(DVA) und,, link-state algorithms“(LSA) unterteilt werden.

Im Falles des DVA Routings kennen die Router jeweils die Verbindungskosten der benachbarten Router zu allen Zielen. Mit diesen Informationen konnen die Router den nachsten Knoten (Hop) fur den Transport eines Datenpaketes zu dem jeweiligen Ziel berechnen. Fur die Bestimmung der optimalen Route wird in der Regel der Bellman/Ford Algorithmus verwendet [Bel57] [FF62]. Anderungen der Verbindungskosten werden zuerst nur dem direkt an die Verbindung angeschlossenen Router bekannt. Die Router geben dann die Aktualisierungen der Routingtabellen immer nur den direkt benachbarten Routern weiter, die diese dann wiederum an ihre Nachbarn weiterleiten. Bei DVA tritt das sogenannte „count-to-infinity“ Problem auf, das eine sehr langsame Propagierung vonne gativen Nachrichten wie beispielsweise einem Verbindungsausfall beschreibt.

Wird der LSA verwendet, senden die Router regelmabig Informationen uber den Zustand der direkt angeschlossenen Datenleitungen an alle Router des Netzes. Dieses Verfahren ist unter dem Begriff „flooding“ bekannt. Die Router berechnen dann einzeln mit Hilfe eines Algorithmus zur Bestimmung des kurzesten Weges, wohin ankommende Datenpakete weiterzuleiten sind. Bei Verwendung des LSA werden Verbindungsausfalle sofort fur alle Router sichtbar, so dab sich das Netz sehr schnell auf die neue Situation einstellen kann, dafur mub allerding ein hoherer Kommunikationsaufwand als beim DVA in Kauf genommen werden.

Neben der Unterscheidung, wie die Routinginformation gewonnen wird, kann auch noch unterschieden werden, ob de n Datenpaketen beim Versenden direkt die komplette Routeninformation bis zum Ziel mitgegeben wird (Source routing), oder ob sie jeweils nur zum nachsten Knoten geschickt werden, wo dann wiederum der nachste Knoten bestimmt wird (Hop-by-hop routing). Bei dem Source routing wird der Weg der Datenpakete schon in der Quelle vollstandig bestimmt. Auf dem Weg mussen daher keinerlei Entscheidungen mehr getroffen werden.

Wird das Source routing in Verbindung mit LSA eingesetzt, so konnen aufwendige Verfahren zur Routenbestimmung (z.B. MPLS) Verwendung finden, um speziellen Anforderungen an die Routenwahl gerecht zu werden. Bei MPLS handelt es sich um ein neues Routingverfahren. Es ermoglicht ein sehr weitgehendes Planung und Beeinflussung der gewahlten Routen. Durch die Bestimmung virtueller Routen kann der Administrator bei Bedarf den Informationsstrom uber die einzelnen Source-Destination Paare gezielt festlegen. Die Einschrankung der moglichen Routen wird beispielsweise zum Schutz vertraulicher Daten verwendet, die ausschlieblich uber das interne Firmennetz geroutet werden durfen. Details zu den einzelnen Algorithmen lassen sich unter anderem in [CDS98] [GSA01] [FTOO] [AMA99] [Moy97] finden.

Es besteht eine Analogie zwischen der Wegsuche fur Datenpakete und Fahrzeuge in einem Schienennetzwerk wie beispielsweise einem Gepackbeforderungssystem mitD CVs.

Parallelen in beiden Systemen finden sich in den begrenzten Ressourcen bar den Transport, also Datenleitungen bzw. Strecken.

Der Vergleich beider Systeme zeigt aber auch deutliche Unterschiede. Im Bereich der Datennetze wird die Ubertragungszeit in der Regel vernachlassigt. Bei einem Transport mit DCVs ist dies aber gerade einer der entscheidenden Qualitatsfaktoren. Damit hangt eng zusammen, dab die Lastwechselzeitkonstanten in einem DCV-System klein gegenuber den Fahrzeiten sind. Die Transportauftage werden erst sehr kurzfristig bekannt, wahrend der eigentliche Transport relativ lange dauert. In Datennetzen sind die Lastwechselzeitkonstanten relativ grofi gegenuber der Datenubertragungszeit. Wahrend das Abhandenkommen von Datenpaketen (packet loss) zur Erkennung von Uberlastung in Datennetzwerken herangezogen wird, konnen unddurfen in Transportsystemen einzelne DCVs mit Gepack nicht einfach verschwinden, so dab fur diese Logistiksysteme andere Indikatoren fur Uberlastung herangezogen werden mussen [QH99].

Im Gegensatz zum Internet ist die Struktur eines Gepackbeforderungssystems fur den Entwickler transparent. Das Internet weist diese Eigenschaft wegen seiner Grobe und der verschiedenen beteiligten Organisationen, die ihre Netztopologien geheimhalten, nicht auf. In der Welt der Datennetze gibt es eine Vielzahl von S ystemen und (inkompatiblen) Protokollen. Probleme durch Inkompatibilitaten konnen bei einem Gepackbeforderungssystem, welches von e iner einzigen Organisation geplant und g ewartet wird, vermieden werden.

Die aus dem Bereich der Datennetze untersuchten Verfahren haben einen mabgeblichen Einflub auf die Algorithmen, die zur Routenwahl der DCVs in den folgenden Kapiteln beschrieben werden. Von besonderem Interesse sind dabei Ideen, welche den dezentralen LSA zugrundeliegen.

Daruber hinaus labt sich zahlreiche Literatur bezuglich der Lastverteilung zwischen alternativen Routen finden. Dies beinhaltet unter anderem die Lastpradiktion, aber vor allem Verfahren zur dynamischen Bestimmung der Routingtabellen auf Basis der aktuellen Lastsituation. Es handelt sich hierbei uberwiegend um ,,Quality of Service“ (QoS) Betrachtungen in bezug auf die Bandbreite. Dabei wird nicht fur einen Zeithorizont optimiert, der geringer als die Ubertragungszeit ist. In dem Bereich des Strabenverkehrsmanagements werden Verfahren vorgestellt, die sich zur Anwendung in der Gepackbeforderung besser eignen (Kapitel 3.4).

Neben den bisher beschriebenen und weit verbreiteten Verfahren, wurde auch ein Verfahren in dem Forschnugsgebiet der kunstlichen Intelligenz entwickelt. Die Bestimmung der Routen erfolgt uber virtuelle Ameisen, die Duftstoffe (Pheromone) auf ihrem Weg verteilen. [FGOOO]. Inspiriert wurde dieser Ansatz durch die Beobachtung des Verhalten realer Ameisen. Der Kerngedanke besteht aus der gleichmabigen Verteilung von Duftstoffen durch Ameisen auf zufallig gewahlten Wegen. Auf kurzeren Wegen werden die Duftstoffe dichter zuruckgelassen. Wahlen die Ameisen nunbevorzugt Wege, die eine hohere Duftstoffmenge aufweisen, konnen sie auf diese Weise ohne jegliche zentrale Kontrolle und ohne Kenntnis des gesamten Systems gute Routen finden.

Das Verhalten der Ameisen ist rein evolutionar bestimmt und l abt sich nur schwer vorhersagen. Die Steuerung des Gepackbeforderungssystems soll im Gegensatz dazu den Transport der Gepackstucke innerhalb bestimmter Fristen gewahrleisten. Wegen der Risiken, die der Verwendung dieses evolutionaren Algorithmus innewohnen, wird daher den klassischen Verfahren zur Routenbestimmung im Gepackbeforderungssystem der Vorzug gegeben.

3.2 Produktionsplanung

Die Produktionsplanung beschaftigt sich mit der Optimierung von Fertigungsprozessen. Konkurrieren verschiedene Fertigungsauftrage um eine begrenzte Anzahl von M aschinen, wird die Reihenfolge der von den Auftragen zu „besuchenden“ Maschinen im Rahmen der Herstellung optimiert. Dabei wird berucksichtigt, dab verschiedene Auftrage verschiedene Bearbeitungsschritte und Bearbeitungszeiten benotigen und eventuell mit unterschiedlichen Prioritaten versehen sind.

Die uberwiegende Anzahl der Ansatze basiert auf zentralen Planungsalgorithmen [BorOO], die sich fur die dezentrale Routenplanung bzw. Auftragsvergabe an leere DCVs nicht einsetzen lassen. Off-line Algorithmen, die einen Belegungsplan im voraus bestimmen, lassen sich ebenfalls nicht verwenden, da Beforderungsauftrage fur Gepackstucke sehr kurzfristig aufkommen.

Die Idee nach [BorOO], die dem dezentralen Vorausplanungsverfahren zum Lastausgleich verschiedener Maschinen zugrunde liegt, labt sich auf das Gepackbeforderungssystem ubertragen. Dazu konnen hier Ausgleichsvorgange zwischen parallelen Stecken oder Beladestationen realisiert werden. Im Gegensatz zu dem Fertigungssystem kann aber keine langfristige Vorausplanung erfolgen, undes gibt kein Analogon zu den Zwischenspeichern

an Bearbeitungsmaschinen, da die DCVs an Weichen oder Be-/Entladestationen die physische Reihenfolge nicht tauschen konnen. Letzteres stellt eine starke Einschrankung an das System dar.

In [BSOO] wird ein dezentrales, auktionsbasiertes MaterialfluBplanungssystem fur die Fertigung vorgestellt. Die Auftragsvergabe wird durch einen einfachen Auktionsmechanismus vorgenommen. Die einzelnen Maschinen und W erkstucke werden durch Agenten, die an den Auktionen teilnehmen, vertreten. Ansatze dieses Verfahrens werden in Kapitel 4.1.3 aufgegriffen, um eine Strategie der Auftragsvergabe an leere DCVs zu entwickeln.

3.3 Routenplanung in der Robotik

Das Forschungsgebiet der Robotik hat zahlreiche Strategien der Wegeplanung sowie der Zusammenarbeit zwischen verschiedenen Robotern hervorgebracht.

Die in dem Bereich der Robotik untersuchten Logistiksysteme zum Transport von Gutern verwenden eine vergleichsweise geringe Anzahl von Robotern. Eine Ubersicht uber Arbeiten zur Routenplanung und Auftragsvergabe finden sich bei Qiu undHsu [QH99]. Die dort vorgestellten Losungsansatze verwenden allerdings zentral arbeitende Strategien. Dort wird als komplexestes Problem das Routing vonAGVs (automated guided vehicles) in einem Hafen zum Containertransport herangezogen. Die Anzahl der dort eingesetzten Fahrzeuge liegt in der Grofienordung von einhundert. Um diese Aufgabe zentral beherrschen zu konnen, wird die Topologie auf ein regelmafiiges quadratisches Gitternetzwerk beschrankt. Dieser Ansatz schiedet desahlb aufgrund der geforderten Flexibilitat bei der Streckenlegung aus.

Im Rahmen des MARTHA Forschungsprojektes wurde das Plan-Merger-Paradigma vorgeschlagen, um eine dezentrale Plankoordinierung zwischen Robotern zu ermoglichen [AFH+98] [AMP97] [RC96]. In [AFH+98] wir der Ansatz wie folgt beschrieben: „The basic ideas of the approach we have chosen and implemented is that whenever a robot produces a plan which makes use of some kind of shared resources ...,it advertises it, and collects from other robots the plans which specify how they plan to use these resources as well as the right ...to perform its plan coordination. It then produces a coordinated plan and informs the other robots of event occurrence ...of which it wants to be informed/4

Auf diese Weise wird die Planung dezentral von den einzelnen Fahrzeugen vorgenommen. Sollten aber Konflikte zwischen den Planen auftreten, so kann es zu einer Eskalation fuhren, die schliefilich in einer de facto zentralisierten Planung endet, in der ein Agent die gesamte Planung ubernimmt. Diese Konfliktsituation tritt immer dann ein, wenn mehrere Fahrzeuge dasselbe Streckenelement zur gleichen Zeit nutzen wollen. Der Ubergang zur zunehmenden Zentralisierung des Verfahrens macht es fur das Gepackbeforderungssystem nicht anwendbar.

Weitere Planungs- beziehungsweise Koordinierungsverfahren aus dem Bereich der Robotik sind vom Rechenaufwand zu komplex, um direkt fur ein Gepackbeforderungssystem mit mehreren tausend DCVs Verwendung zu finden.

Ein haufig verwendeter Ansatz zur Routenplanung frei fahrender Roboter basiert auf Potentialfeldern. Hindernisse wirken dabei abstofiend, wahrend das Ziel eine anziehende Kraft auf den Roboter ausubt [TVH01]. Dieser Ansatz wird in Kapitel 4.1.2 aufgegriffen.

Das Themengebiet der Erkennung und A uflosung von D eadlocks wird im Bereich der Robotik sehr ausfuhrlich behandelt. Als Deadlock wird eine Situation bezeichnet, in der verschiedene Fahrzeuge zyklisch aufeinander warten und so ein Teilsystem oder sogar das Gesamtsystem zum permanenten Stillstand gebracht wird. Da eine solche Situation das Gepackbeforderungssystem zum volligen Erliegen bringt, wenn keine geeigneten Schutzvorkehrungen getroffen werden, ist es wichtig, Deadlocks sicher zu erkennen und eine wirkungsvolle Auflosestrategie in den Systementwurf zu integrieren. Die Methode von [Wan95] [WP95] wird in Kapitel 5.5n aher vorgestellt undka nn fur das Gepackbeforderungssystem verwendet werden.

3.4 Routenplanung im Strafien- und Schienenverkehr

Der Bereich der Verkehrsplanung ist sehr weit gefachert. Er ersteckt sich von der Planung der Verkehrsnetze bis hin zur optimierten Nutzung der bestehenden Infrastruktur.

Um den Verkehr modellieren zu konnen, wurden unter Zuhilfenahme zahlreicher Felddaten Modelle des menschlichen Fahrverhaltens erzeugt [May90]. Mit Hilfe dieser Modelle konnen Kapazitatsberechnungen fur vorgegebene Streckenkonfigurationen vorgenommen werden. Die entwickelten Verfahren zur Bestimmung der Modelle des Fahrverhaltens finden in dieser Arbeit keine direkte Anwendung, da das Fahrverhalten der DCVs’ eines Gepackbeforderungssystems bekannt undwohldefiniert ist. Fur das allgemeine Verstandnis des Zusammenwirkens einer Vielzahl ahnlicher Individuen in einem gemeinsamen Verkehrsystem bieten die Studien aus diesem Bereich wertvolle Erkenntnisse.

In zunehmenden Mafie werden die Moglichkeiten der Verkehrsbeeinflussung und Steuerung durch Routenvorschlage erforscht. Es wird eine optimierte Nutzung der bestehenden Strafien angestrebt, indem den Fahrern aktuelle Informationen zur Verfugung gestellt werden, die insgesamt eine bessere, stauvermeidende Auslastung der Strecken bewirken sollen.

In diesem Zusammenhang werden Strategien fur Ampelschaltungen und Zuflufibegrenzungen, beispielsweise an Autobahnauffahrten, ausgearbeitet [May90] [HT97]. Wenn das Zusammenfadeln von Fahrzeugen an einer Weiche eines

Gepackbeforderungssystems optimiert werden soll, ergeben sich ahnliche Herausforderungen, so dafi diese Ideen, wie die Bildung von Konvois, auf das Gepackbeforderungssystem ubertragen werden konnen.

Die Fahigkeit eines Systems, zukunftige Belastungen vorherzusagen, beeinflufit die Qualitat von Routenvorschlagen mafigeblich. Daher wurden in der Literatur zahlreiche Untersuchungen uber dieses Thema erstellt. Im Gegensatz zu dem Gepackbeforderungssystem fehlt im Strafienverkehrsumfeld die genaue Information uber die Ziele unduber die Aktionen der Verkehrsteilnehmer. Ein weiteres Problem liegt in der nur partiellen Anbindung einiger Verkehrsteilnehmer an die Verkehrsbeeinflussungssysteme, so dafi nicht alle Beteiligten auf Basis der gleichen Informationen entscheiden konnen.

Ein sehr interessanter Ansatz zur Erstellung dynamischer Routenempfehlungen wird von [TT94] vorgestellt. Zur Steigerung der Genauigkeit der Vorhersagen melden sich die einzelnen Verkehrsteilnehmer fruhzeitig bei den mutmafilich zu passierenden Strecken an. Dieses Vorgehen wird in Kapitel 4.2.2 wieder aufgegriffen.

Mit dem Fortschreiten der Computertechnik werden inzwischen auch Systeme zur vollautomatischen Steuerung von Fahrzeugen untersucht. Von [HV00] wird z.B. ein System zur automatischen Steuerung von Fahrzeugen auf Autobahnen vorgestellt. Die Forschung auf diesem Gebiet findet vor allem im Bereich der Fahrzeug-Lokalisation und der automatischen Erkennung von H indernissen statt. Diese Herausforderungen sind fur das Gepackbeforderungssystem weitestgehend nicht vorhanden, da es sich hierbei um eine kunstliche, vergleichsweise einfache Umwelt handelt, und di e Schienen die Bewegungsfreiheitsgrade der Fahrzeuge weitgehend einschranken. Die oberste Ebene der automatischen Steuerung, die fur die Lastverteilung zustandig ist, fand alut [HV00] bei der Entwicklung die geringste Beachtung. Zum Einsatz in dieser Arbeit bedurfte es weitergehender Entwicklungsarbeit, zumal abweichende Randbedingungen vorliegen.

In [MI01] wird ein Planungsverfahren basierend auf Auktionen vorgeschlagen. Einsatz findet das Auktionsverfahren bei der Ersteigerung von R outenabschnitten, wobei jedem Fahrzeug ein Budget fur die Auktion zur Verfugung steht. Da den einzelnen Fahrzeugen nur ein begrenztes Budget zur Verfugung gestellt wird, kann es vorkommen, dab keine vollstandigen Routen ersteigert werden konnen. In Kapitel 4.1.3wird der Auktionsgedanke aufgegriffen, um dort ein Verfahren ohne Budgets zu entwickeln. So kann sichergestellt werden, dab stets vollstandige Routen erstellt werden. In [MI01] wird dafur kein zufriedenstellendes Verfahren fur den Umgang mit unvollstandigen Routen angegeben.

Eine gute Ubersicht uber Verfahren zur Erstellung von Fahrplanen fur Zuge wurde in [IS01] erstellt. Die dort vorgestellten Verfahren basieren allerdings auf zentral arbeitenden Verfahren undkonnen somit nicht ohne weiteres denAnforderungen eines dezentralen Steuerungsansatzes gerecht werden. Die Verwendung vonA uktionsverfahren fur die Fahrplanerstellung wird unter anderem auch in [PU01] vorgeschlagen.

4 Dezentrale Koordination und Steuerung der DCVs’ eines Gepackbeforderungssystems

In diesem Kapitel wird die Steuerungsalgorithmik besprochen, die zur Losung der Aufgabenstellung in Frage kommt. Es werden verschiedene Ansatze kurz andiskutiert und auf ihre Anwendbarkeit fur das zu entwerfende Gepackbeforderungssystem hin untersucht. Der favorisierte Losungsvorschlag wird daraufhin in Kapitel 5 detaillierter ausgearbeitet.

Die Steuerungsalgorithmik muB bestimmte Eigenschaften aufweisen, um einen zufriedenstellenden Betrieb des Gepackbeforderungssystems zu ermoglichen:

- Sicherstellung des Transportes aller Gepackstucke unter Einhaltung der Transportzeitbeschrankungen
- Robustheit gegenuber Ausfall eines Streckenabschnitts oder Defekt eines DCVs
- Optimierungsmoglichkeiten zur Anpassung an verschiedene Anforderungen
- Realisierbarkeit der Kommunikation bezuglich Bandbreitenbeschrankung (DCVs konnen nur uber FunkLAN o.a. kommunizieren)
- Koordinierung einer grofien Anzahl an DCVs (bis uber 1000 DCVs)

In einem dezentralen Steuerungssystem ist es unabdingbar, daB die einzelnen Entscheidungstrager (DCVs) direkt oder indirekt Informationen untereinander austauschen konnen, um eine Optimierung des Systems zu ermoglichen [Kie97]. Da es bei einem System dieser GroBe und Dynamik mit gleichzeitiger Beschrankung der Rechen- und Kommunikationsbandbreite unmoglich ist, eine vollstandige Transparenz des Systemzustands herzustellen, mussen moglichst verdichtete Informationen in Form von Nachrichten ausgetauscht werden.

Die Steuerung des Gepackbeforderungssystems laBt sich in zwei Aufgabenbereiche unterteilen. Es besteht einerseitsdie Aufgabe, eine Fahrroute fur DCVs zu bestimmen. Andererseits mussen den leeren DCVs Beladestationen zugeordnet werden, so daB moglichst alle Transportaufgaben schnell und z uverlassig erledigt werden konnen, unter der Nebenbedingung, daB nicht gebrauchte DCVs das Beforderungssystem nicht behindern [IAT95].

Das Management der leeren DCVs’ stellt die hochstrangige Aufgabe der Steuerung dar und schrankt die Wahl des anwendbaren Routingverfahrens ein. Um die Wahl des Steuerungsansatzes ubersichtlich darzulegen, wird zuerst das Thema der Koordinierung der leeren DCVs’ erortert, bevor die Algorithmik der Routenwahl angegangen wird.

4.1 Management der leeren DCVs’

Die Wahl des Verfahrens zum Management der leeren DCVs’ spielt eine entscheidende Rolle bei der Sicherstellung der geforderten Eigenschaften des Systems. Wird diese Aufgabenstellung nicht zufriedenstellend erfullt, kann es zum Beispiel zu einer lokalen Unterversorgung des Systems mit leeren DCVs fuhren. Eine wesentliche Einschrankung stellt das Fehlen von Zwischenspeichern dar. Parkende DCVs blockieren die Strecke.

Im Rahmen der Diskussion moglicher Losungsansatze wird zuerst auf einfache Auftragsvergabestrategien, dann auf ein potentialbasiertes Verfahren und schlieBlich auf ein marktbasiertes Verfahren eingegangen.

4.1.1 Einfache Steuerungsalgorithmen

In Anwendungsfeldern der Fabrikautomation und de r Informatik wurden sehr einfache Steuerungsalgorithmen zur Auftragsvergabe entwickelt. Diese verwenden jeweils eine einzige klare Regel. Zu den am weitesten verbreiteten Regeln gehoren [WWW+98]:

- priority-first
- first-come first-served
- shortest-job-first

Werden derartige Regeln in Systemen verwendet, laBt sich der Kommunikationsaufwand sehr gering halten. Andererseits bieten sie auf Grund ihrer Einfachheit kaum Moglichkeiten, das System an spezielle Anforderungen anzupassen. Fur jedes dieser einfachen Verfahren ist es leicht, eine einfache Routentopologie zu finden, fur die der Transport jedoch sehr ineffizient erfolgt.

Wird die Auftragsvergabe an leere DCVs rein prioritatsorientiert vorgenommen (priority first), werden die unterschiedlichen Weglangen nicht berucksichtigt. Dadurch werden leere DCVs unter Umstanden sehr lange Wege in Kauf nehmen, obwohl ein ahnlich hoch priorisierter Auftrag in der unmittelbaren Umgebung verfugbar ist. Werden unnotig lange Wege von den DCVs zuruckgelegt, fuhrt dies zu einer ubermaBig langen Bindung der DCVs und einer hohen Streckenauslastung, so dafi das Gesamtsystem vergleichsweise ineffizient betrieben wird.

Wahlen die DCVs jeweils die Beladestation mit dem altesten Auftrag (first-come first- served), werden (wie bei priority-first) unter Umstanden unnotig lange Wege zuruckgelegt.

Wird die Strategie des shortest-job-first von den DCVs befolgt, wird sichergestellt, dafi sie immer den nachstgelegenen Auftrag annehmen. Sind jedoch mehrere Beladestationen hintereinander gelegen (wie in dem simulierten System aus Kapitel 6), kann das wahrend Zeiten hoher Auslastung dazu fuhren, dafi die Auftrage der hintersten Beladestation erst sehr verspatet abgearbeitet werden.

Wegen fehlender Anpassungs- und Optimierungsmoglichkeiten eignen sich diese einfachen Steuerungsalgorithmen nicht zur Steuerung eines Gepackbeforderungssystems.

Diese Probleme lassen sichjeweils durch Einfuhrung weiterer Regeln vermeiden, allerdings wird die Algorithmik dann komplizierter. Sie wird von dem Bereich der marktbasierten Verfahren abgedeckt, vgl. Kapitel 4.1.3.

4.1.2 Potentialverfahren

Die leeren DCVs sind alle hinsichtlich der Auftragsubernahme untereinander austauschbar. Der Ansatz des Potentialverfahrens nutzt diese Eigenschaft des Systems aus, um sowohl die Herausforderung der Auftragsvergabe wie auch des Routings der leeren DCVs gleichzeitig anzugehen. Es wird im Vorfeld der Beladung keine explizite Verteilung der einzelnen Transportauftrage auf die leeren DCVs vorgenommen. (Fur dieses Verfahren ist die Namensgebung destination coded vehicle mifiverstandlich, um aber keinen alternativen Begriff fur die gleichen Fahrzeuge unter einer anderen Steuerung einzufuhren, werden sie weiterhin DCVs genannt.) Die Routinginformation wird allein durch den Potentialansatz gewonnen.

Bei den meisten Potentialansatzen stellt sich das Problem ein, dafi lokale Minima auftreten konnen. Diese konnten verhindern, dafi DCVs, die immer in Richtung eines abfallenden Potentials fahren, ihre Ziele jemals erreichen wurden. In [TVH01] wird ein Potentialansatz vorgeschlagen, der auf der Idee eines elektrischen Widerstandsnetzwerkes beruht. Die Berechnung der Strome in diesem Netzwerk lafit sich somit auf ein lineares Problem zuruckfuhren. Durch die physikalische Stromerhaltung kann sichergestellt werden, dafi keine lokalen Minima auftreten konnen.

Zur Berechung des Potentials fur das Gepackbeforderungssystem konnten alle Entladestationen als geerdet angenommen werden. Die Beladestationen nehmen einen Strom I auf. Die einzelnen Knoten des Netzwerkes sind uber Widerstande verbunden. Die Widerstandswerte werden proportional zur Auslastung und Lange der Strecke gewahlt, so daB der Strom bevorzugt uber wenig ausgelastete und kurze Strecken flieBt. Das Potential der einzelnen Knoten kann nun anhand der Stromflusse berechnet werden. Den Entladestationen kann ein Innenwiderstand zugewiesen werden, der umgekehrt proportional zu der Anzahl der entladenen DCVs ist. Damit kann sichergestellt werden, daB die Aktivitat der Entladestationen bei der Stromberechnung berucksichtigt wird.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4.1.2

In Abbildung 4.1.2 ist ein einfaches System aus zwei Entladestationen auf der linken Seite und zwei Beladestationen auf der rechten Seite zu sehen. Nehmen die Beladestationen, in Abhangigkeit von ihrem Bedarf an leeren DCVs’ einen Strom von 10A bzw. 100A auf, kann die Stromverteilungen in dem Netzwerk berechnet werden. An der oberen Weiche teilt sich der Strom von 46A in zwei Teilstrome von 10A bzw. 36A auf. Entsprechend dieser Relation konnen leere DCVs , die an dieser Weiche ankommen, mit einer Wahrscheinlichkeit von 22% zu der oberen Beladestation und mit 78% zur unteren geleitet werden.

Wegen der Abhangigkeit der Widerstande vonder Streckenauslastung werden die Strome mit zunehmender Systemauslastung uber weniger ausgelastete (physisch langere) Strecken geleitet. Eine gleichmaBige Steigerung der Stromerzeugung in allen Beladestatioen fuhrt zu einer Prioritatsverlagerung weg von der Gepackbeforderung hin zum Management der leeren DCVs’. Dabei ware zu untersuchen, ob sich auf diese Weise ein Gleichgewicht zwischen diesen beiden Transportarten einstellt oder aber Schwingungen auftreten.

Zur Routenwahl an Verzweigungen bieten sich verschiedene Entscheidungskriterien fur leere DCVs an. Eine Ausfuhrungsform besteht in der Auswahl desjenigen Streckenabschnitts, der den starksten Strom fuhrt. Es ist aber auch moglich, die Entscheidung auf stochastischer Grundlage entsprechend der Verteilung der Stromflusse zu treffen. Da der Strom durch alle Netzzweige flieBt, die Be- und Entladestationen verbinden, wurden die DCVs mit niedriger Wahrscheinlichkeit auch sehr lange Strecken wahlen. Die Wahl unnotig langer Strecken fuhrtjedoch zu einer geringeren Effizienz des Gesamtsystems.

Weiterhin stellt sich die Herausforderung eine dafur zu sorgen, daB sich nicht zu viele DCVs auf den Weg zu einer Beladestation begeben. Um eine Ubersattigung des Bedarfs an leeren DCVs’ zu vermeiden, ist es naheliegend, den quantitativen Bedarf in Gegenfahrtrichtung zu propagieren. Verzweigende Weichen, denen bekannt ist, daB in einer Richtung kein Bedarf mehr besteht, konnen dann alle leeren DCVs in die andere Richtung leiten.

Dazu melden die Beladestatioenen neben dem virtuellen Strom jeweils noch die absoluten Anzahlen der benotigten, leeren DCVs an die in Fahrtrichtung gesehen vor den Stationen liegenden Strecken. Damit ist den Strecken bekannt, wie hoch der aktuelle Bedarf an leeren DCVs hinter ihnen ist. Die Anzahl leerer DCVs, die sich auf den jeweiligen Strecken befinden, wird von dem propagierten Bedarf abgezogen, um auf diese Weise eine indirekte Anmeldung zu ermoglichen. Dieser Bedarf wird dann wiederum jeweils den weiter vorgelagerten Strecken mitgeteilt. Weichen, die in Fahrtrichtung eine Verzweigung darstellen, addieren die Bedarfswerte der beiden nachgelagerten Strecken und geben sie an die vorgelagerte Strecke weiter. Schwieriger gestaltet es sich bei Weichen, die in Fahrtrichtung eine Vereinigung der Verkehrsstrome vornehmen. Da der Bedarf in umgekehrter Richtung fortgepflanzt werden muB, stellt sich die Frage, wie er auf die beiden vorgelagerten Strecken aufgeteilt wird.

Einfache Losungsansatze, wie die gleichmaBige Verteilung des Bedarfs auf beide vorgelagerten Strecken, fuhren zu keiner befriedigenden Losung. In diesem Fall ist es vorstellbar, daB der Bedarf von einer der beiden Strecken nicht gedeckt werden kann. Der anderen Strecke ware es moglich, den gesamten Bedarf zu decken. Da aber nur der halbe Bedarf dort bekannt ist, wird auch nur der halbe Bedarf gedeckt. Es wird offensichtlich kein effizienter und zufriedenstellender Betrieb des Gesamtsystemsystems erfolgen.

Zur Losung dieser Problematik kann, analog zur Propagierung des Bedarfs in Gegenfahrtrichtung, die Anzahl der leeren DCVs in Fahrtrichtung, ausgehend von den Entladestationen, propagiert werden. Nun stellt sich das eben beschriebene Problem der Propagierung an verzweigenden Weichen genau komplementar zu dem Fall der Bedarfspropagierung. Eine Moglichkeit ist nun, de n Bedarf jeweils bevorzugt in der Richtung zu propagieren, in der leere DCVs vorhanden sind und umgekehrt. Diese Propagierung sowohl des Bedarfs wie auch der Anzahl leerer DCVs kann verhindern, daB sich zu viele leere DCVs auf den Weg zu einer Beladestation begeben.

Bei der weiteren Betrachtung des System muB man feststellen, daB bei der Propagierung der leeren DCVs die Restfahrzeiten keinerlei Berucksichtigung finden. Genauso wird nicht zwischen kurzfristigem und l angfristigem Bedarf der Beladestationen unterschieden. Der Aspekt der Nichtbeachtung der Zeit fuhrt vor allem bei System, die von ihrer Anlage her eine mittelfristige Planung erlauben, zu einer ineffizienten Aufgabenverteilung auf die DCVs. Zum Beispiel konnte es bei zwei nahe beieinander gelegenen Beladestationen vorkommen, das ein leeres DCV zu der Station fahrt, die erst zukunftig ein DCV benotigt, wahrend die andere Station bei Ankunft schon unmittelbar auf die Verladung eines Gepackstucks wartet.

Da keine zufriedenstellende Losung fur die offenen Fragen gefunden wurde, kann das Potentialverfahren im Rahmen dieser Arbeit nicht eingesetzt werden.

4.1.3 Marktbasiertes Verfahren

Auktionen oder marktbasierte Verfahren konnen in dezentralen Systemen eingesetzt werden, um einen Interessenausgleich der einzelnen Teilnehmer zu erzielen und eine Koordinierung ihrer Aktivitaten zu erreichen. In der Literatur finden sich Verfahren zur dezentralen Steuerung von Transporteinheiten, die auf Auktionsmechanismen basieren [WWW+98] [MI01] [BSOO].

Werden diese Verfahren auf das Gepackbeforderungssystem ubertragen, konnen die einzelnen Teilnehmer durch Agenten modelliert werden, die jeweils fur ein DCV oder eine Beladestation an Auktionen teilnehmen. Die begrenzte Kommunikationsbandbreite zwischen DCVs untereinander und zwischen DCVs undS treckenrechnern stellt einen limitierenden Faktor fur die Auswahl moglicher Auktionsverfahren dar. Da das System von einem Systemanbieter komplett geplant und realisiert wird, kann diese Organisation wahrend des Entwurfs darauf achten, daB die einzelnen, an den Auktionen beteiligten Einheiten (DCVs und Beladestationen) „ehrliche“ Gebote abgeben. Von daher besteht keine Notwendigkeit aufwendige Auktionsverfahren wie beispielsweise die Vickery Auktion einzusetzen, deren Ziel darin besteht, die Auktionsteilnehmer zu ehrlichen Geboten zu motivieren [BSOO].

Vor dem Hintergrund dieser Uberlegungen wird ein abgeandertes Verfahren des Kontraktnetzes nacch [FerOl] zur Bestimmung der Ziele leerer DCVs als vorteilhaft fur die Anwendung im Gepackbeforderungssystem erachtet. Der erste Schritt der Auftragsvergabe per Kontraktnetz ist normalerweise die Formulierung der Anfrage. Da es aber nur eine Aufgabenart im Auktionsumfeld des Gepackbeforderungssystems gibt, namlich die Fahrt eines leeren DCV’s zu einer Beladestation, um dort ein Gepackstuck fur den Weitertransport aufzunehmen, wird auf den ersten Schritt, der Anfrage durch ein DCV, verzichtet. Anstatt dessen kann davon ausgegangen werden, dab stets leere DCVs auf der Suche nach neuen Zielen sind und di e Beladestationen kontinuierlich Angebote fur leere DCVs abgeben. Entsprechend dem zweiten Schritt des Kontraktnetzes veroffentlichen die Beladestationen Angebote fur die Fahrt eines leeren DCVs zu dieser Station. Im darauffolgenden dritten Schritt bewerten die DCVs diese Angebote und entscheiden sich fur das fur sie gunstigste. Sollten mehrere Angebote gleich gut sein, kann eine der entsprechenden Beladestationen per Los gewahlt werden. Dem vierten Schritt des Kontraktnetzmodells entspricht die Bestatigung der Beladestation, dab sie den Auftrag verbindlich an das DCV vergibt. Wird diese Auftragsbestatigung nicht vergeben, mub das DCV sich erneut um einen anderen Auftrag bemuhen.

Da die Kriterien zur Bewertung der Angebote durch die DCVs, sowie die Vorschriften zur Erstellung der Angebote durch die Beladestationen, dem Systemdesigner sehr viele Freiheiten lassen, kann ein solches System sehr gut an spezielle geforderte Systemeigenschaften angepabt werden. Wegen der vielfaltigen Moglichkeiten des Entwurfs wird das Gepackbeforderungssystem auf Basis eines abgewandelten Verfahrens des Kontraktnetzes entworfen.

Durch geeignete Informationsfilterung auf den Streckenrechnen labt sich das Kommunikationsaufkommen so weit beschranken, dab die Verwendung eines solchen Verfahrens realisierbar ist. In den Kapiteln 5 und 6 wird detaillierter auf das in dieser Arbeit umgesetzte marktbasierte Verfahren eingegangen.

4.2 Routenwahl

Es werden verschiedene Verfahren zur Routenwahl untersucht. Da von der Verwendung eines marktbasierten Verfahrens zur Auftragsvergabe an leere DCVs ausgegangen wird, ist allen DCVs in dem System ein klares Fahrziel bekannt. Die Aufgabe der Routenwahl besteht also darin, den einzelnen DCVs eine moglichst gunstige Route zu ihrem Ziel aufzuzeigen.

Dabei ist zu beachten, dab nicht unbedingt die schnellste Route eines individuellen DCVs die gunstigste aus der Sicht des Gesamtsystems sein mufi. Um einen effizienten Betrieb des Gesamtsystems zu ermoglichen, ist es wichtig, Stauungen zu vermeiden.

In diesem Umfeld lassen sich Algorithmen bezuglich der Planungsgenauigkeit unterscheiden in Algorithmen, die :

- die gesamte Route vor Abfahrt mit verbindlichen Zeitfenstern und zugehoriger Trajektorie planen,
- die die gesamte Route vor Abfahrt ohne verbindliche Zeitfenster planen und
- die nicht die gesamte Route vor Abfahrt planen.

Entsprechend der Bezeichnung der Routingverfahren in Datennetzen, werden im folgenden solche Verfahren, die die gesamte Route vor Abfahrt bestimmen als Source routing und solche, bei denen die Route erst wahrend der Fahrt bestimmt wird, als Hop-by-hop routing bezeichnet.

Als Reservierung mit v erbindlichem Zeitfenster und Trajektorie wird ein Algorithmus bezeichnet, der einem DCV fur alle Streckenelemente seiner Route in Abhangigkeit von dem jeweiligen Eintrittszeitfenster ein bestimmtes Austrittszeitfenster garantiert, ganz imSinne der Alltagsaussage: ,,Ich komme heute Abend zwischen 18.03 Uhr und 18.07 Uhr zum Essen und gehe zwischen 19.32 Uhr und 19.35 Uhr.“ Findet eine Anmeldung ohne verbindliche Zeitangabe statt, so wird nur mitgeteilt, dab zu einem noch unbestimmten Zeitpunkt die Ressource belegt werden wird: ,,Ich komme, vermutlich gegen Abend, zum Essen vorbei.“ Ohne Anmeldung wird im voraus keinerlei Mitteilung uber die geplanten Aktionen kommuniziert, sondern bei Ankunft: ,,Hallo, da bin ich! Hoffentlich hast Du schon fertig gekocht.“ Diese drei Varianten werden im Folgenden untersucht.

4.2.1 Hop-by-hop routing ohne Anmeldung

Es ist moglich, ahnlich dem Routing der Datenpakete im Internet, DCVs zu ihrem Ziel zu steuern, ohne dab die gesamte Route vor Fahrtantritt bestimmt wird. Verfahren, die anjedem Netzknoten den jeweilig nachsten bestimmen, werden im Bereich der Informatik als ,,hop- by-hop“ routing bezeichnet [GSA01].

Wenn die Trajektorie der DCVs nicht vor Abfahrt exakt festgelegt wird, mub die Streckenfahrtrichtung fest vorgegeben werden, um dies als Quelle moglicher Deadlocks auszuschlieben und so das Steuerungsproblem rechentechnisch beherrschen zu konnen. Die Netztopologie mufi daruber hinaus stark zusammenhangend sein, damit keine Senken auftreten, die die DCVs nicht mehr verlassen konnen [KS01].

Die Weichen arbeiten also ahnlich den Routern in Datennetzwerken, die die Datenpakete zu ihrer nachsten Station schicken. Die gesamte Planung wird inkrementell an den Netzknoten vorgenommen. Jede Weiche kann als Agent modelliert werden. Die Weichenagenten informieren sich untereinander uber den Zustand der Verbindungswege, d.h. ube r die virtuellen Benutzungskosten. Ein DCV gibt den Weichenagenten nur sein Ziel und gegebenenfalls Zusatzinformationen an, so dafi die Weichen dann den nachsten hop wahlen konnen. Die Weichen teilen dem DCV mit, welchen Weg es zu wahlen hat, so dafi das DCV die gewahlte Route ausfuhren kann.

Nur einige der zu Beginn des Kapitels 4 geforderten Eigenschaften der Steuerungsalgorithmik konnen von diesem Steuerungskonzept erfullt werden:

- Robustheit gegenuber Ausfall eines Streckenabschnitts oder Defekt eines DCVs

Fallt eine Weiche aus, werden die Routingtabellen der anderen Weichen aktualisiert. Aus dem Bereich der Informatik sind verschiedene Verfahren bekannt, die eine unterschiedliche Ausbreitungsgeschwindigkeit der aktualisierten Informationen gewahrleisten. Sobald die Routingtabellen aktualisiert sind, werden neu ankommende DCVs um den defekten Streckenabschnitt herumgeleitet.

- Realisierbarkeit der Kommunikation bezuglich Bandbreitenbeschrankung

Das Kommunikationsaufkommen ist sehr gering, da keine langfristige Planung vorgenommen wird, sondern Entscheidungen an Weichen immer nur lokal getroffen werden.

- Koordinierung einer grofien Anzahl an DCVs (bis uber 1000 DCVs)

Da das Verfahren sehr stark lokal arbeitet, stellt eine grofie Anzahl an DCVs kein Problem dar.

[...]

Ende der Leseprobe aus 125 Seiten

Details

Titel
Konzeption eines autonomen Gepäckbeförderungssystems für Flughäfen
Hochschule
Universität Karlsruhe (TH)  (Institut für industrille Informationstechnologie)
Note
1,0
Autor
Jahr
2002
Seiten
125
Katalognummer
V190880
ISBN (eBook)
9783656158127
ISBN (Buch)
9783656158165
Dateigröße
1639 KB
Sprache
Deutsch
Schlagworte
konzeption, gepäckbeförderungssystems, flughäfen
Arbeit zitieren
Ivo Fischer (Autor:in), 2002, Konzeption eines autonomen Gepäckbeförderungssystems für Flughäfen, München, GRIN Verlag, https://www.grin.com/document/190880

Kommentare

  • Noch keine Kommentare.
Blick ins Buch
Titel: Konzeption eines autonomen Gepäckbeförderungssystems für Flughäfen



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden