METHOD FOR CALCULATING A CONVEYANCE-TIME-OPTIMIZED OBJECT PATH IN AN OBJECT CONVEYANCE SYSTEM, APPROPRIATE STORAGE MEDIUM AND OBJECT CONVEYANCE SYSTEM

Beschreibung

Verfahren zur Berechnung eines förderzeitoptimierten Objektpfads in einem Objektfördersystem, entsprechendes Speicherme- dium und Objektfördersystem

Die Erfindung liegt auf dem technischen Gebiet der Objektfördersysteme, wie Gepäckfördersysteme, und betrifft insbesondere ein Verfahren zur Berechnung eines Objektpfads zur Beför- derung eines Objekts von einem wählbaren Startpunkt zu einem wählbaren Zielpunkt in einem Objektfördersystem, bei welchem eine Gesamtförderzeit des Objekts optimiert ist.

In modernen Gepäckförderanlagen erfolgt eine Annahme, Unter- suchung, Beförderung, Sortierung, Lagerung und Ausgabe von Gepäckstücken, wobei moderne Förder- und Bearbeitungskomponenten in Kombination mit Sensor- und Steuerungstechniken hierbei eine weitgehende Automatisierung der Abläufe erlauben. Da die Anforderungen hinsichtlich Größe, Durchsatz und Laufzeit, wie etwa in Flughäfen, ständig ansteigen, ergeben sich komplexe Anforderungen an eine Planung, Kontrolle und Steuerung derartiger Anlagen.

Ein zentrales Problem der Gepäckförderanlagen ist die Wahl des Wegs, den ein Gepäckstück durch die Anlage nehmen soll.

Die üblicherweise große Anzahl von Startpunkten und Zielpunkten bedarf einer hochgradigen Vernetzung, um ein Gepäckstück flexibel zum Ziel bringen zu können. Ferner werden wichtige Verbindungen oftmals mehrfach (redundant) angelegt, um auf diese Weise einen hohen Durchsatz und weitestgehende Ausfallsicherheit zu gewährleisten. Somit stehen einem zu befördernden Gepäckstück im Allgemeinen eine große Anzahl von möglichen Transportwegen offen, wobei jedoch Umwege im Hinblick auf die Transporteffizienz vermieden werden sollen. Weiterhin muss berücksichtigt werden, dass an Streckenzusammenführungen oder an Komponenten mit maximaler Kapazität oder schwankenden Bedienzeiten Stauungen entstehen können, welche die Gesamttransportzeit eines Gepäckstücks erhöhen können. Wenn solche Stauungen auf vorgelagerte Komponenten zurückwirken, kann es mitunter sogar zu einer teilweisen oder kompletten Blockierung der Anlage kommen. Insofern sollte die Wegeauswahl auch eine mögliche Rückstaubildung hemmen, indem Engpässe umfahren werden, obgleich sich dadurch die Transportdauer eines Objekts zunächst erhöhen kann. Erschwerend kommt hinzu, dass eine Entscheidung über den benutzten Transportweg bei jedem neuen Gepäckstück gefällt werden muss und unter Umständen sogar noch während des Transports veränderten Bedingungen ange- passt werden sollte. Dies bedeutet, dass eine Entscheidung über den Transportweg in Echtzeit erfolgen sollte, um die Weichen in der Anlage mit den nötigen Informationen versorgen zu können.

Diese Aufgabe wurde bislang so gelöst, dass ein Gepäckstück entlang des zeitlich bzw. räumlich kürzesten Wegs zu seinem Bestimmungsort geleitet wurde, was sich in einfachen Fördersystemen durchaus als optimale Lösung darstellen kann. Hierbei wird die zeitliche Länge eines Gepäckstückpfads als die Summe der normalerweise deterministischen Zeitdauern zur Förderung des Gepäckstücks über die in dem Gepäckstückpfad enthaltenen Förderstrecken berechnet.

Eine übliche Vorgehensweise zur Ermittlung eines räumlich bzw. zeitlich kürzesten Objektpfads besteht nun darin, das Fördersystem als Flussgraph mit den Komponenten des Fördersystems entsprechenden Knoten und den Förderstrecken des Fördersystems entsprechenden Kanten zu modellieren. Zur Berechnung eines kürzesten Wegs in einem solchen gerichteten Gra- phen mit positiven Kanten- oder Knotenlängen wird beispielsweise der Dij kstra-Algorithmus verwendet, welcher dem Fachmann an sich wohlbekannt ist und hier nicht näher erläutert werden muss.

Jedoch hat sich gezeigt, dass die ausschließliche Verwendung von schnellsten bzw. kürzesten Wegen in komplexeren Anlagen zu Schieflasten führen kann, wenn - wie oben schon erläutert - Stauungen an Knoten (z. B. Zusammenführungen von För- derstrecken oder Komponenten mit einer nur geringen maximalen Kapazität, wie beispielsweise eine Gepäckuntersuchungsstation) auftreten. Tritt beispielsweise der Fall auf, dass es zwei ähnlich lange Wege zwischen einem Startpunkt und einem Zielpunkt gibt, werden grundsätzlich alle Gepäckstücke entlang des kürzeren Wegs geleitet. Unter Umständen kann dies zu einer Überlastung des kürzeren Wegs führen, obgleich der fast genau so kurze Alternativweg weiterhin ungenutzte Kapazitäten bietet. Solche Schieflasten können im Stand der Technik zwar durch lokale Abänderungen des Wegs gemindert werden, jedoch hat sich erwiesen, dass solche lokalen Regeln bei schwankenden Verkehrslasten oft suboptimal sind.

Demgegenüber besteht die Aufgabe der vorliegenden Erfindung darin, ein Verfahren zur Ermittlung eines förderzeitoptimier- ten Objektspfads zur Beförderung eines Objekts von einem Startpunkt zu einem Zielpunkt zur Verfügung zu stellen, durch welches die genannten Nachteile der herkömmlichen Verfahren vermieden werden können.

Diese Aufgabe wird nach dem Vorschlag der Erfindung durch ein Verfahren zur Berechnung eines förderzeitoptimierten Objektpfads eines Objekts in einem Objektfördersystem mit den Merkmalen von Anspruch 1 gelöst. Vorteilhafte Ausgestaltungen der Erfindung sind durch die Merkmale der Unteransprüche angegeben.

Erfindungsgemäß ist ein Verfahren zur Berechnung eines förderzeitoptimierten Objektpfads zur Beförderung eines Objekts von einem wählbaren Startpunkt zu einem wählbaren Zielpunkt in einem Objektfördersystem gezeigt. Das Objektfördersystem umfasst in herkömmlicher Weise Komponenten wie Stationen zur Annahme, Untersuchung, Sortierung, Lagerung und Ausgabe von Gepäckstücken, und Förderstrecken, wie Förderbänder, zur Be- förderung der Gepäckstücke. In Anlehnung an die in der Graphentheorie übliche Notation werden derartige Komponenten hier und im weiteren als "Knoten" bezeichnet, während die Förderstrecken auch als "Kanten" bezeichnet werden. Typi- scherweise, jedoch nicht zwingend, arbeiten die Förderstrecken mit einer jeweils konstanten Fördergeschwindigkeit, so dass die Förderstrecken-Förderzeiten, d.h. die Förderzeiten auf den jeweiligen Förderstrecken, proportional zu den För- derstreckenlängen sind. Das Objektfördersystem ist weiterhin (insbesondere an seinen Knoten) mit Signalgebern ausgestattet, die die Abfahrt der Objekte vom Startpunkt und ihre Ankunft am Zielpunkt einer Recheneinheit signalisieren. Die Recheneinheit kann anhand dieser Signale und den eventuell frü- her schon Objekten zugewiesenen Förderstrecken, welche noch nicht an ihren jeweiligen Zielpunkten angekommen sind und demzufolge noch im Objektfördersystem unterwegs sind, eine momentane Objektförderrate für die Knoten (oder auch Kanten) des Fördergraphen bestimmen. Zu diesem Zweck sind in der Re- cheneinheit Knoten (oder auch Kanten) zugewiesene Zähler implementiert, deren Zählwert der momentanten Objektförderrate durch einen Knoten (oder auch Kante) entspricht. Falls keine Objekte im Objektfördersystem unterwegs sind, kann eine mo- mentante Objektförderrate durch einen Knoten auf "Null" ge- setzt werden. Mit dem Ausdruck "Objektförderrate soll hier und im weiteren die Anzahl der durch einen Knoten (oder auch Kante) pro Zeiteinheit transportierten Objekte verstanden sein. Hierbei wird vorzugsweise für solche Knoten eine Objektförderrate ermittelt, bei denen mit Stauungen zu rechnen ist. Derartige Knoten werden hier und im weiteren als " (potentielle) Stauknoten" bezeichnet und sind typischerweise Knoten mit zufälligen Abarbeitungszeiten und Zusammenführungen von Objektförderstrecken.

In dem Objektfördersystem sind Weichen in der Lage, die Objekte entlang eines geplanten Objektpfads von einem wählbaren Startpunkt zu einem wählbaren Zielpunkt zu leiten. Die Recheneinheit erhält hierbei die notwendigen Informationen über die wählbaren Start- und Zielpunkte der Objekte, sowie über die Abfahrt und die Ankunft der Objekte. Weiterhin steht die Recheneinheit in einer Wirkverbindung mit den Weichen und kann so einen geplanten Objektpfad an das Objektfördersystem kommunizieren . Zur Bestimmung eines förderzeitoptimierten Objektpfads für ein Objekt wird gegebenenfalls zunächst festgestellt, ob ein Transport von einem gewählten Startpunkt zu einem gewählten Zielpunkt physikalisch überhaupt möglich ist. Alternativ kann für alle Start- und Zielpunkte angenommen werden, dass ein Start- und Zielpunkt verbindender Objektpfad existiert.

Auf Basis der momentanen Objektförderraten an den potentiel- len Stauknoten, welche der Recheneinheit wie oben ausgeführt stets bekannt sind, werden dann für jeden Stauknoten voraussichtliche Wartezeiten an diesen Stauknoten ermittelt. Für die Berechnung einer voraussichtlichen Wartezeit an einem Stauknoten auf Basis der momentanen Objektförderraten wird vorzugsweise Warteschlangentheorie verwendet, welche dem

Fachmann an sich wohlbekannt ist, und hier nicht näher erläutert werden muss. Als voraussichtliche Wartezeit an einem Stauknoten kann insbesondere eine voraussichtliche gemittelte Wartezeit berechnet werden. Hierbei ist es insbesondere vor- teilhaft, wenn eine voraussichtliche gemittelte Wartezeit an einem Stauknoten als umgekehrt proportional zur Differenz aus einer maximalen Objektförderrate ("Kapazität") und der momentanen Objektförderrate durch den Stauknoten angenommen wird, falls diese Differenz positiv ist; andernfalls wird sie auf den Wert "Unendlich" gesetzt.

Gegebenenfalls kann dann geprüft werden, ob das Objektfördersystem bei der derzeitigen Auslastung überhaupt in der Lage ist, das Objekt vom gewählten Startpunkt zum gewählten Ziel- punkt zu transportieren. Falls dies nicht der Fall ist, ist es besonders vorteilhaft, wenn eine Abfahrt des Objekts verzögert wird und ein Zeitpunkt ermittelt wird, wann die Auslastung des Objektfördersystems einen Transport des Objekts zulässt. So kann die ermittelte voraussichtliche Wartezeit an einem Stauknoten auf einen Zählwert Unendlich gesetzt werden, wenn die voraussichtliche Objektförderrate größer ist als eine maximale Objektförderrate eines Stauknotens. Auf diese Weise kann vorteilhaft verhindert werden, dass ein ohnehin ausgelastetes bzw. überlastetes Objektfördersystem mit einem weiteren Objekt belastet wird.

Dann wird für den wählbaren Startpunkt und den wählbaren Zielpunkt ein diese verbindender Objektpfad in dem Objektfördersystem mit endlicher Gesamttransportzeit unter Berücksichtigung der Transportzeiten entlang der Kanten und der im vorhergehenden Schritt berechneten (beispielsweise mittleren) Wartezeiten an den Stauknoten unter der Voraussetzung ermit- telt, dass die Gesamttransportzeit in einer geeigneten Weise gewählt, insbesondere minimal ist.

Wenn kein Objektpfad mit endlicher Gesamttransportzeit ermittelt werden kann, so ist entweder eine Beförderung vom Start- punkt zum Zielpunkt unmöglich oder alle möglichen Pfade enthalten mindestens einen überlasteten Stauknoten, d.h. einen Stauknoten mit voraussichtlicher Wartezeit Unendlich. Im ersten Fall muss das Objekt auf eine andere Art zum Ziel befördert werden, im zweiten Fall kann nach dem Abklingen der Ü- berlastung erneut ein Objektpfad berechnet werden.

Das Objektfördersystem wird zur Ermittlung eines Start- und Zielpunkt verbindenden Objektpfads mit minimaler Gesamttransportzeit insbesondere unter Berücksichtigung der voraussicht- liehen Wartezeiten an den Stauknoten vorzugsweise als Flussgraph mit Knoten und Kanten modelliert. Bei dem auf diese Weise ermittelten Objektpfad kann es sich insbesondere um einen kürzesten (schnellsten) Objektpfad vom Startpunkt zum Zielpunkt in dem Objektfördersystem handeln. Ein solcher ins- besondere kürzester (schnellster) Objektpfad wird vorzugsweise mittels eines Netzwerkflussalgorithmus berechnet. Die Verwendung eines Netzwerkflussalgorithmus in einem als Flussgraph modellierten Objektfördersystem ist dem Fachmann an sich wohlbekannt und braucht hier nicht näher erläutert zu werden.

Die Weichen entlang des Objektpfads werden nun über das von ihnen zu transportierende Objekt und den zu nehmenden Weg in- formiert und das Objekt auf diesem Objektpfad vom Startknoten zum Zielknoten auf den Weg gebracht. Ein Signalgeber signalisiert nun die Abfahrt des Objekts an die Recheneinheit, was dazu führt, dass in der Recheneinheit jeweilige Zählwerte von Zählern für die Objektförderraten durch die Stauknoten, welche in dem dem Objekt zugewiesenen Objektpfad enthalten sind, um ein wählbares Inkrement erhöht werden. Sobald ein Signalgeber am Zielknoten die Ankunft des Objekts signalisiert, werden diese Objektförderraten wieder entsprechend um densel- ben Betrag erniedrigt. Wenn kein Objekt unterwegs sind, so sind somit alle Objektförderraten Null. Als wählbares Inkrement kann beispielsweise das Inverse der voraussichtlichen Förderstrecken-Förderzeitsumme, d. h. die Summe der voraussichtlichen Förderstrecken-Förderzeiten der im Objektpfad enthaltenen Förderstrecken, gewählt werden.

In dem erfindungsgemäßen Verfahren kann es weiterhin vorteilhaft sein, wenn ein Objekt am Startpunkt verbleibt, solange die ermittelte Gesamtförderzeit für einen förderzeitoptimier- ten Objektpfad einen wählbaren Maximalwert, bei dem es sich insbesondere um einen unendlich großen Zahlenwert handeln kann, überschreitet.

In dem erfindungsgemäßen Verfahren können insbesondere für unterschiedliche Objektsorten, wie sperrige und nicht-sperrige Gepäckstücke, interne Signalgeber vorgesehen sein. Auf diese Weise können vorteilhaft für unterschiedliche Objektsorten auftretende verschiedene Förderraten durch Stauknoten in der Berechnung voraussichtlicher Wartezeiten an den Stauknoten berücksichtigt werden.

Die Erfindung erstreckt sich ferner auf ein Speichermedium für eine Datenverarbeitungsvorrichtung, in dem Befehle abgelegt sind, welche die Datenverarbeitungsvorrichtung zur Durchführung des wie oben beschriebenen Verfahrens veranlassen. Weiterhin erstreckt sich die Erfindung auf ein wie oben beschriebenes Objektfördersystem, in dem zusätzlich eine Recheneinheit vorhanden ist, welches ein wie oben beschriebenes Verfahren zur Beförderung eines Objekts von einem Startpunkt zu einem Zielpunkt veranlasst.

Die Erfindung wird nun anhand eines nicht einschränkenden Ausführungsbeispiels näher erläutert. Das Ausführungsbeispiel betrifft eine Gepäckförderanlage, welche insbesondere zur Verwendung in Flughäfen geeignet und bestimmt ist.

1. Einführung

Gepäckfördersysteme kümmern sich um eine Annahme, Beförderung, Sortierung, Lagerung und zeitgerechte Abgabe des Gepäckstücks. Die meisten solcher Systeme verwenden Förderbänder als Hauptkomponente zum Bewegen der Gepäckstücke. Bei gewöhnlichen Förderbändern werden die Gepäckstücke direkt hier- auf platziert, wohingegen in fortgeschrittenen Fördersystemen die Gepäckstücke in Behältern platziert werden, die sich auf den Förderbändern bewegen. Wenn Behälter verwendet werden, ist die Bereitstellung von leeren Behältern ein zusätzlicher Aspekt, den es zu beachten gilt. In einem System können Be- hälter einer verschiedenen Größe und Nutzbarkeit vorhanden sein, um z.B. sperrige und nicht-sperrige Gepäckstücke zu befördern. In bestimmten Systemen werden die Gepäckstücke auch auf Fahrzeuge geladen, die selbsttätig die Verarbeitungs- und Abladestellen ansteuern. Dieser Fall soll auch umfasst sein, wenn "Förderstrecken" zitiert sind.

Gepäckfördersysteme verbinden oftmals eine große Anzahl von beabstandeten Gepäckquellen und -zielen, und enthalten eine Vielzahl von dazwischenliegenden Verarbeitungseinheiten, um beispielsweise eine Sicherheitsüberprüfung, manuelle Kontrolle, Korrekturen und Lagerung von frühen Gepäckstücken durchzuführen. Hauptförderstrecken werden oftmals redundant implementiert, um die Ausfallsicherheit zu erhöhen und Ausfallzei- ten aufgrund von Wartungs-/Instandsetzungsarbeiten zu vermindern. Eine große Anzahl von Weichen und Zusammenführungen ermöglichen es, die Gepäckstücke zu sortieren und zu einem gewünschten Zielpunkt zu bringen. In bestimmten Systemen soll es auch möglich sein, einzelne Gepäckstücke zu ihrem Eigentümer wieder zurückzuführen, falls dies erforderlich ist. Dies kommt der Fähigkeit gleich, Gepäckstücke während ihres Wegs durch das System umzuleiten.

Eine Steuerung und der Betrieb von Gepäckfördersystemen erfordern eine gründliche Planung und Implementierung. Die Online-Bestimmung der Position eines Gepäckstücks in dem System ist ein wichtiges Eingangssignal für die Planung von Wegstrecken. Sensoren und Datennetzwerke sind hierbei wesentlicher Teil der Datenbeschaffung und der Verarbeitung. Aufgrund von neuen Signaltechniken und Signalverarbeitungstechniken ist es möglich, fortgeschrittene Algorithmen für die Kontrolle des Fördersystems zu verwenden. Ebenso können die Ergebnisse der Kontrolle direkt in das System implementiert werden.

Moderne Gepäckfördersysteme sind so gestaltet, dass sie mit großen Spitzenbelastungen fertig werden. Dies impliziert ein effizientes Design und Funktion, sowie die Lösung von umfangreichen und komplexen Optimierungsproblemen.

Fördersysteme haben die folgenden spezifischen Eigenschaften, die für ihre Leistung wichtig sind:

Auf einzelnen Strecken werden alle Gepäckstücke mit der glei- chen Geschwindigkeit transportiert. Gepäckstücke können einander normalerweise nicht überholen. Streckenweichen stellen die wesentlichen Stellen dar, wo die Verkehrsströme beein- flusst werden können. Wo sich Verkehrsströme vereinigen und vor Verarbeitungseinheiten mit langen oder veränderlichen Verarbeitungszeiten können Stauungen oder Blockierungen auftreten. An den Beladungsstellen müssen leere Behälter bereitgestellt werden. Es gibt verschiedene Typen von Gepäckstücken und Behältern. Diese Eigenschaften implizieren, dass wenn ein Gepäckstück erst einmal auf seinem Weg ist, nur noch eine eingeschränkte Kontrolle möglich ist und nur noch die Zustände der Strecken- weichen auf der Förderstrecke, einen Einfluss auf dessen Laufzeit und die Laufzeit der anderen Gepäckstücke in dem System haben. Somit ist eine gründliche Planung des Pfads eines Gepäckstücks durch das System für die Leistungsfähigkeit eines Gepäckfördersystems wesentlich.

Eine einfache Pfadzuweisung bestimmt die theoretische Laufzeit in der Weise, dass die Laufzeit der Förderstrecken und die Durchgangszeit durch Komponenten in einem Pfad summiert werden und der Pfad mit der kürzesten Gesamtlaufzeit einem Gepäckstück zugewiesen wird. Wenn eine Zuweisung von Pfaden an verschiedene Gepäckstücke festgelegt ist, kann die mittlere Last der Komponenten des Systems bestimmt werden. Diese Analyse beschränkt die Sicht auf die Mittelwerte der Zufallsvariablen und gibt Einblick in die minimalen Laufzeiten und den maximalen Durchsatz des Systems. Jedoch kann die Implementierung einer Kontrolle, die nur den kürzesten Pfaden folgt, zu einer Schieflast, insbesondere auf redundanten Strecken, führen. Sie kann sogar zu Blockierungen führen, weil bestimmte Strecken überlastet werden, während alternati- ve (zweitkürzeste) Pfade unbenutzt bleiben. Der Grund für diese Probleme liegt darin, dass mögliche zufällige Stauverzögerungen nicht beachtet werden. Auch können zufällige Effekte zu zeitweiligen Überlasten an bestimmten Engstellen führen, was eine Blockierung und Wartezeiten impliziert und den Durchsatz des Systems vermindert.

Es wird deshalb eine Wartezeitenanalyse an den Stellen des Systems durchgeführt, wo sich Wartezeiten aufbauen können (z.B. dort, wo sich Ströme vereinigen), um die erwarteten Verzögerungen in die Berechnungen des kürzesten Pfads einzubringen. Unter der Annahme, dass die Wartezeiten hauptsächlich von der Verkehrsintensität an einem Knoten abhängen und auf einer kleineren Zeitskala als die Transportzeiten variie- ren, kann man ein Gepäckstück auf den schnellsten Pfad leiten (einschließlich der erwarteten Wartezeiten) und die Verkehrsintensitäten entlang dieses Pfads während des Transports anpassen. Dies kommt einer Art Reservierung von Ressourcen gleich. Insbesondere kann eine Überlast schon am Eingang des Systems blockiert werden und systeminterne Blockierungssituationen vermieden werden.

Es werden hier zwei Algorithmen dargestellt, welche diese I- dee implementieren, einer für den strategischen Weg und einer für das Online-Pfadzuweisungsproblem.

Eine Verbesserung solcher Ansätze erfordert ein genaueres Modellieren insbesondere von temporären Effekten. Obgleich zeitabhängige Erweiterungen möglich sind, haben sie den Nachteil, dass sie die Berechnungszeit um Größenordnungen erhöhen.

2. Mathematischer Rahmen

Das Fördersystem, das in diesem Abschnitt modelliert wird, lässt verschiedene Einheiten (Objekte) zu, die durch das System transportiert werden.

Sei U der finite Satz von Einheiten, die durch das System bewegt werden, wie beispielsweise:

U : = {normales Gepäckstück, sperriges Gepäckstück, normaler leerer Behälter, sperriger leerer Behälter}

(D

Hier können sich Gepäckstücke innerhalb eines Behälters auf einer Förderstrecke oder direkt (ohne Behälter) auf einer Förderstrecke befinden. Es wird angenommen, dass für jeden

Einheitstyp ue U mit einer Einheitslänge 1 (u) assoziiert ist. Da nicht jede Einheit von jeder Komponente verarbeitet werden kann, wird ein Satz von Behältertypen und Zuständen C eingeführt. Beispielsweise:

C : = {normal leer, normal beladen, sperrig leer, sperrig beladen, normal ohne, sperrig ohne} (2)

Hier bezieht sich normal auf Standard-Behälter oder Standard- Gepäckstücke, sperrig auf extra große Behälter oder Gepäckstücke, ohne wird für Einheiten verwendet, die nicht in einem Behälter liegende Gepäckstücke verarbeiten.

Sei N ein Satz von Knoten (Förderbänder, Beladungs- und Entladungsmaschinen, Zusammenführungen, Aufteilungen, oder Kreuzungen) . Für jeden Knoten n e N sei C (n) c C der Satz von Behältertypen, der durch den Knoten C verarbeitet werden kann. Z.B. kann C (n) = {normal ohne, sperrig ohne} für ein herkömmliches Förderband oder C (n) = {normal leer} für eine

Strecke, die verwendet wird, um leere Behälter zu Ladestellen zu bringen, verwendet werden.

Aus dem Satz von Behältertypen C (n) eines Knotens n kann man den Satz von Einheiten U(n) der durch den Knoten n verarbeitet werden kann, ableiten. In einer Matrix, wie sie in Tabelle 1 gezeigt ist, kann man spezifizieren, welche Einheiten für welche Behältertypen erlaubt sind.

Tabelle 1

Somit besteht U(n) aus allen Einheiten u e U₁ für welche es einen Behältertyp c e C(n) gibt, derart, dass "ja" in der Spalte u und Reihe c von Tabelle 1 angezeigt wird. In klarer Weise kann dieses Konzept von Einheitstypen und Behältertypen in leichter Weise auf komplexere Situationen (z.B. einen dritten Typ von Behältern) angepasst werden.

Es wird angenommen, dass es eine Laufzeit t(n) gibt, welche die minimale Zeit zum Überqueren des Knotens n ist (wenn es keine Blockierung oder Überlast gibt) . Wenn verschiedene Be- hältertypen verschiedene Laufzeiten benötigen, kann dies gehandhabt werden, indem der Knoten künstlich in mehrere Knoten aufgeteilt wird. Da die Geschwindigkeit auf einem herkömmlichen Förderband für alle Behälter gleich ist, müssen solche Fälle nicht betrachtet werden. Jedoch müssen die möglichen verschiedenen Behältergrößen in diesem Modell berücksichtigt werden, da der Durchsatz des Knotens von den Behälterlängen abhängt. (Gewöhnlich können weniger sperrig leere/beladene Behälter verarbeitet werden als wie normal leere/beladene Behälter.) Aus Gründen der Einfachheit wird angenommen, dass der Durchsatz invers proportional zu der Behältergröße ist (was physikalisch gerechtfertigt ist) . Es wird deshalb angenommen, dass v (n) > 0 die Geschwindigkeit des Knotens n ist, und, wenn 1 die dem Knoten n angebotene Behältergröße ist, der l/v(n) Behälter pro Zeiteinheit verarbeiten kann.

Sei L c N x N der Satz von Verknüpfungen (n, m) in Nx N derart, dass eine Station m direkt von der Station n erreicht werden kann.

Ein Pfad p in dem Fördersystem ist ein £-Tupel von Knoten p = (n_lr n₂, ..., n_k) für einige k e N (Menge der natürlichen Zahlen), derart, dass (n_ir n₁₊₁) e L für i = 1, ..., k-1 ist. Es wird S(p):=zii und T(p):= n_k für die Quelle bzw. Ziel eines Pfads p geschrieben. Der Satz von Knoten, die in einem Pfad enthalten sind, wird als N(p) bezeichnet. Es wird dem Pfad p = (n_lf ..., n_k) die Zeit

t(p).-=∑t(n,)= ∑t(n) ι=l mN(p)

zugewiesen. Die Zeit t (p) ist die Laufzeit zum Befördern durch alle Knoten, welche zu dem Pfad p gehören, wenn keine Stauungen auftreten. Für jeden Einheitstyp u e U kann man den Satz von Pfaden P (u) entlang dessen sich eine Einheit vom Typ u bewegen kann, definieren. Z.B. kann man definieren, dass P(u) alle Pfade p enthält, derart dass für jeden Knoten n e N(p) auf dem Pfad u e U(n) genügt.

Bestimmte Knoten in dem System führen bestimmte Aufgaben durch, wie ein Gepäck-Screening, Behälterbeladung/-entladung, Lagerung von leeren/beladenen Behältern... Um alle Knoten mit besonderen Aufgaben zu sammeln, werden Untersätze von N Gruppen eingeführt. Z.B. kann es die Gruppen von Check-in- Schaltern, Röntgendurchleuchtungsmaschinen oder Ankunftsge- päckkarussellen geben. Ein Bedarf oder eine Anforderung d kann einem Paar von Knoten zugewiesen werden. Ein solcher Bedarf wird spezifiziert durch seinen Quellknoten S (d) e N, Zielknoten T(d) e N, Einheitstyp u(d) e U und Intensität I (d) > 0. Die Intensität I (d) eines Bedarfs d spezifiziert die Anzahl von Gepäckstücken (pro Einheitszeit) des Typs u (d) , die von dem Quellknoten S (d) zu dem Zielknoten T (d) gebracht werden sollen. Zudem kann eine Zahl K(d) > 0 einem Bedarf zugefügt werden, und wenn K(d) > 0 gilt, muss man auch eine Gruppe G_± (d) c N für jedes 1 = 1, ..., K(d) spezifizieren. Diese Gruppen spezifizieren Zwischenziele, die jedes Gepäckstück des Bedarfs in der gegebenen Reihenfolge besuchen muss. Genauer tritt jedes Gepäckstück in dem Bedarf d an dem Knoten S (d) in das System ein, muss einen Knoten in Gi (d) besuchen, wenn K(d) > 0 gilt, dann einen Knoten in G∑(d) , wenn K(d) > 2 gilt, ..., und ver- lässt gegebenenfalls das System an dem Zielknoten T (d) . Somit kann das Fördersystem nur Anforderungen d genügen, für welche ein Pfad p = (n_lr ..., n_k) e P(u(d)) existiert, derart, dass rii = S (d) , n_k = T (d) ist, und es keine monotone Abbildung gibt J : {1, ..., K(d) } → {1, ..., k} derart, dass n_J(i) e G₁ (d) ist. Ein Pfad, der diesen Bedingungen genügt, wird als zugelassen für die Anforderung d bezeichnet. Sei P(d) der Untersatz von P (u (d) ) , der alle zugelassenen Pfade für die Anforderung d enthält.

Sei D der Satz von Anforderungen. Es wird das Quintupel (U, C, N, L, D) als ein Gepäckfördersystem bezeichnet. Eine Pfadzuweisung A ist eine Zuordnung, die jedem Paar (d, p) e D x P eine Zahl A(d, p) e R₊ (Menge der positiven reellen Zahlen) zuweist, derart, dass

A(d, p) = 0 für jedes d e D und p e P\P(d), (3) und ∑ A(d, p) = I (d) für jedes d e D (4)

P≡P(d)

Diese Bedingungen besagen, dass jeder Anforderung durch die zugelassenen Pfade genügt ist. Eine solche Pfadzuweisung nennt den Anteil A(p,d) der Intensität I (d) der Anforderung d, welcher entlang des Pfads p transportiert wird. Es sei bemerkt, dass Anforderungen Bewegungen von leeren Behältern, z.B. von einem Lager für leere Behälter zu einem anderen, umfassen können.

3. Vorverarbeitung

Die wichtigen Knoten in einem Fördersystem sind die Quellen, Zwischenziele, Ziele von Anforderungen, und jene Knoten, wo sich Gepäckströme vereinigen oder aufteilen. Zwischen solchen Knoten transportieren oftmals eine Reihe von gleichartigen Förderbändern, die mit der gleichen Geschwindigkeit arbeiten, Gepäckstücke/Behälter. Eine solche Reihe von Strecken kann durch eine einzelne Strecke zusammengefasst und ersetzt wer- den. In dieser Weise wird die Anzahl von Knoten in dem System auf die Anzahl der relevanten Knoten reduziert. In gleicher Weise entsprechen die Verbindungen dem reduzierten System einer Reihe von Verbindungen des ursprünglichen Systems .

Der Algorithmus zum Durchführen dieser Vorverarbeitung ist wie folgt: Für einen Knoten n e N sei I (n) e N u {0} (bzw. O(n) G Nu {0} die Zahl von Verbindungen (h, m) e L mit n = m (bzw. n = h) . Sammle jeden Knoten n e N₁ für welchen I(n)0(n) ≠ 1 und jeden Knoten n, der zu einer Quelle oder Ziel oder Zwischenziel einer Anforderung gehört, in dem Satz N'. Mit anderen Worten bedeutet dies

.

Als Nächstes wird jeder Knoten Ti₁ e N' und Verbindung In₁, n∑) e L betrachtet, und das Folgende gemacht: Wenn n∑ € N' gilt, dann gibt es exakt eine Verbindung (n₂, n₃) e L. Wenn n₃ noch kein Element aus N' ist, wiederhole diesen Schritt und erzeuge einen Pfad p := In₁, n₂, ..., n_k) , wo Ti₁ der erste Knoten mit n_k e N' ist. Betrachte den Pfad p als eine Verbindung von dem Knoten Ti₁ = S (p) zu dem Knoten n_k = T(p) und fü- ge ihn zu dem anfänglich leeren Satz von Verbindungen L ' hinzu.

Wenn diese Schleife und Iteration fertig ist, erhalten wir den vereinfachten Graphen N', L'. (Wenn bidirektionale Verbindungen in dem System vorliegen, müssen die Definitionen leicht modifiziert werden.) Eine solche Reduktion der Zahl von Knoten in dem Fördersystemgraphen kann einen großen Ein- fluss auf die Berechnungszeit in den folgenden Algorithmen haben. Gleichwohl wird vorgeführt, den ursprünglichen Satz von Knoten N und Kanten L in den folgenden Abschnitten zu verwenden.

4. Kürzeste Pfade und minimale Laufzeiten

Für ein gegebenes Gepäckfördersystem (U, C, N, L, D) kann man für jede Anforderung d e D die minimale Laufzeit berechnen, die erforderlich ist, um den Zielknoten T (d) von dem Quellknoten S (d) für eine Einheit des Typs u(d) auf einem zugelas- senen Pfad p e P (d) zu erreichen. Dies entspricht einer Lösung des Problems

Problem 1: "Finde einen Pfad p e P(d) , der t(p) minimiert ."

Dieses Minimalisierungsproblem mit Zwischenzielen kann in der folgenden Weise gelöst werden: Erzeuge einen Graphen, der einen Satz von Knoten der Tupel (n, i) mit i e N und i = 0,m ..., K(d) hat. Für jedes i = 0, ..., K(d) und Verbindung (n, m) e L mit u(d) e U(n) n U (m) sind die Knoten (n, i) und (m, i) mit einer Verbindung der Länge t (m) verbunden. Zusätzlich gibt es für jedes i = 0, ..., K(d) und n e G_±(d) eine Kante von (n, i - 1) zu (n, i) mit Länge 0. Jeder minimale Längenpfad von dem Knoten (S (d) , 0) zu T (d) , K(d)) in diesem Graphen gibt eine Lösung des obigen Minimalisierungsproblems an. Wenn (n_lf ii) , (n_2/ i∑) , •••_/ (n^, ijj ein solcher minimalisie- render Pfad ist, erhält man einen minimalisierenden Pfad des Problems 1, indem alle identischen darauf folgenden Knoten von dem Pfad (n_lr n₂, ..., n_k) entfernt werden. Die Pfade nor- maier Länge in dem konstruierten Graphen können berechnet werden, indem Standardalgorithmen, wie der Dijkstra- Algorithmus, verwendet werden.

Für weitere Bezugnahme sei N^d_f L^d die Knoten und Bögen in dem konstruierten Graphen für eine Anforderung d e D.

Durch Zuweisen der vollen Intensität einer Anforderung zu ihrem minimalisierenden Pfad, kann man eine Pfadzuweisung definieren. Diese Zuweisung wird mit A_mi„ bezeichnet. Ihre formale Definition ist: A_min(d, p) = 0, wenn p e P das Problem 1 für die Anforderung d e D nicht löst und A_min(d, p) = I (d) /h andererseits, worin h die Zahl von minimalisierenden Pfaden für die Anforderung d ist. (Ohne Verlust von Allgemeinheit kann man h = 1 annehmen, d.h. es gibt exakt einen minimalisieren- den Pfad für jede Anforderung d e D) .

5. Erwartete Last

Wenn man eine Verkehrszuweisung A hat, welche jedem Einheits- typ U G U und Pfad p e P(u) eine Zahl A(u, p) e R₊ zuweist, welche die Zahl von Einheiten dieses Typs ist, die sich entlang des Pfads p während jeder Zeiteinheit bewegen müssen, dann kann man die Last jedes Knotens in dem Netzwerk berechnen. Insbesondere kann man Engstellen identifizieren und die Schiefe der Lastverteilung untersuchen.

Die Last der Verkehrszuweisung A auf einem Knoten n e E ist

_P/n) .₌ Z Z^lOiMψλ₍₁₁₎ ueU peP(u)^V(ⁿ) mN(p)

Wenn ^_A(ΓΪ) größer als Eins ist, dann ist der Knoten n unter der Verkehrszuweisung A überlastet. In diesem Fall sollte man versuchen, alternative Pfade für jene Gepäckstücke oder leeren Behälter zu finden, die durch den Knoten n geleitet wer- den. 6. Wartezeiten

An Streckenzusammenführungen und Verarbeitungsstationen können Wartezeiten auftreten. Diese Verzögerungen hängen von der Last auf den Eingangsstrecken und der Arbeitszeitverteilung ab. Eine Berücksichtigung solcher Verzögerungen kann die Last ausgleichen und es dem System ermöglichen, auf zeitliche Stauungen zu reagieren.

Es sei z.B. angenommen, dass zwei Strecken Gepäckstücke zu einer Zusammenführung bringen, welche ein Gepäckstück pro Zeiteinheit bedienen kann. Es wird angenommen, dass mit der Wahrscheinlichkeit OC ein Gepäckstück auf Strecke Eins während eines Einheitszeitinterfalls ist und dass mit der Wahr- scheinlichkeit ß ein Gepäckstück auf der Strecke Zwei ist. Wenn zwei Gepäckstücke gleichzeitig erscheinen, wird eines von ihnen blockiert und verzögert, bis die Zusammenführung frei ist. Die Anzahl der verzögerten Gepäckstücke nimmt mit der Wahrscheinlich cφ (= Wahrscheinlichkeit von gleichzeiti- gern Ankommen der Gepäckstücke an beiden Strecken) um Eins zu, und nimmt mit der Wahrscheinlichkeit (1-CL) (1-$) (= Wahrscheinlichkeit, dass kein Gepäckstück auf beiden Strecken vorliegt) um Eins ab. Das Verhalten der Anzahl der verzögerten Gepäckstücke kann deshalb als ein Geburts- und Sterbepro- zess modelliert werden. Die stationäre Wahrscheinlichkeit μ^, dass k e N u {0} Gepäckstücke blockiert sind, ist

Hieraus bekommt man die mittlere Anzahl von wartenden Gepäckstücken als

Σ αIΛßU

(13)

Es sei festgestellt, dass

die Verkehrsintensität des Systems ist.

Leider können solche exakten Wartezeitenformeln nur in sehr spezifischen Situationen erhalten werden. Um diese Einschränkungen zu überwinden, wird vorgeschlagen, "Schwerverkehrnäherungen" zu verwenden, die als Nächstes eingeführt werden.

7. Schwerverkehrnäherungen

In dem Beispiel des vorigen Abschnitts ist der Ausdruck

p ;= CL(I-CL) + ßα-ßJ = P - P² + 2αß (15)

die Varianz in der Anzahl der Ankünfte pro Zeiteinheit. Wenn p nahe an Eins ist, ist die mittlere Wartezeit nahe an

^{ttß ~ α} (16) i-α-ß 2(l-p)

Näherungen dieser Form tauchen häufig in Wartezeitenanalysen auf. Sie sind besonders wichtig in Schwerverkehrsituationen, wo die Verkehrsintensität sich Eins nähert. Grob gesprochen, geben solche Näherungen an, dass die mittlere Wartezeit eines deterministischen Servers die Gesamtvarianz der zugeführten Ströme, geteilt durch zweimal die freie Kapazität, ist. Wenn ein Paket der Länge L eines Stroms mit einer kleinen Wahrscheinlichkeit p ankommt, ist seine Varianz

L²p - (Lp)² » L²p (17)

Wenn die Varianz eines Stroms, welcher aus A(u) Einheiten des Typs U G U pro Einheitszeit besteht, approximiert werden durch

YJ(U)²A(U) (18) Wenn man eine Zuweisung A(u,p) e R₊ hat, welche für jeden Einheitstyp u e C und zugewiesenem Pfad p e P(u) eine nicht negative Verkehrsintensität A(u,p) von Klasse u-Einheiten auf dem Pfad p spezifiziert, kann man die implizierten Verkehrslasten an den Knoten für n e N und u e U berechnen als (vgl. Gleichung (11) )

worin A(u,n) die induzierte Verkehrsintensität von Klasse u- Einheiten an den Knoten n gegeben durch

A(u,n) := £ A(u,p) (20) peP(u) nen(p)

Es sei festgestellt, dass gemäß Abschnitt 8 der Ausdruck

∑_ueUσ(u,n)l(u)p_A^u(n)_^∑_ueUσ(u,n)l(u)A(u,n) l-∑_u,_u?J^un)^~ v(n)-∑_ueUl(u)A(u,n)

eine Näherung für die mittlere Zahl von wartenden Gepäckstücken an dem Knoten n ist. Hier ist o(u,n) die geeignete Proportionalitätskonstante für Typ u-Behälter an dem Knoten n. Es sei bemerkt, dass O(u,n) = 0 für die meisten Knoten, mit Ausnahme jener Knoten, wo Wartezeiten auftreten könnten, gilt. An diesen Knoten sollte O(u,n) über eine Wartezeitenanalyse, wie in Abschnitt 8 beispielhaft ausgeführt ist, abgeschätzt werden, oder aus Beobachtung abgeschätzt werden.

8. Online-Lastausgleich

In diesem Abschnitt ist ein Algorithmus angegeben, der einen Pfad für ein Gepäckstück bestimmt. Folgende Annahmen liegen diesem Algorithmus zugrunde: 1. Die Verkehrsintensitäten an den Knoten variieren auf kleineren Zeitskalen als die Lauf- Zeiten der Gepäckstücke. 2. Eine Objekteinheit modifiziert die Auslastung der Strecken nur geringfügig.

Wir definieren für eine Typ u-Einheit und einen Pfad p den Wert

s_A(u,p)

+ t(p)

Ein Erhöhen der Verkehrsintensität von Typ u-Einheiten auf dem Pfad p um eine kleine Intensität δ erhöht die Zahl von Trägern auf ihrem Weg in dem System um s_A(u,p)δ. Der Wert s_A(u,p) hat drei Komponenten: die Verzögerung t (p) auf dem Pfad p, die voraussichtliche Wartezeit

in den Stauknoten entlang des Pfades p und den Einfluss für andere Gepäckstücke

Unter gegebenen Verkehrsintensitäten p_n für den Knoten n e N (welche anfänglich Null sind) , wenn ein zu der Anforderung d gehörendes Gepäckstück ankommt, ist das Folgende zu tun:

Berechne den schnellsten Pfad für das Gepäckstück unter den vorausgesagten mittleren Wartezeiten. Das heißt, finde den Pfad p e P(u(d)), welcher den Ausdruck s_A(u,p) minimalisiert . (Dies kann gemacht werden, indem ein Netzwerkflussproblem mit dem Dij kstra-Algorithmus gelöst wird, wie in Abschnitt 5. Erneuere die Verkehrsintensität der Knoten entlang des mini- malisierenden Pfads p durch Erhöhen von A(u,p) um l/t(p). Leite das Gepäckstück entlang des Pfads p. Umgekehrt, wenn ein Gepäckstück an seinem Zielpunkt T (d) ankommt und entlang des Pfads p geleitet wurde, dann vermindere A(u,p) um l/t(p). In dieser Weise stellt A(u,p)t(p) die Anzahl von Gepäckstücken dar, die derzeit auf dem Pfad p unterwegs sind.

Wenn die Gesamtverkehrsintensität

p, •^•= ∑P:⁽29⁾ ueU

Eins übersteigt, oder äquivalent,

ist der zugehörige Knoten n für neue Gepäcke blockiert, da er überlastet ist. Wenn einige der Gepäckstücke, einen zugewie- senen Pfad durch einen solchen Knoten n haben, an ihrem Zielort ankommen, nimmt A(u,n) ab und der Knoten n wird gegebenenfalls für neue Pfadzuweisungen verfügbar.

Es werden nun Kommentare zu dem vorgeschlagenen Algorithmus gegeben:

1. (Ankunftszeitvoraussagen) Die Summe

_{t(p)+ ∑} «(u.nßfuMu.n)_(3i)

Jztp) v⁽n^{) ~}L«_*u^l(u)A(u>ⁿ⁾

kann als die voraussichtliche Laufzeit eines Gepäckstücks auf dem Pfad p interpretiert werden. Unter Verwendung dieser Zahl kann man versuchen, vorauszusagen, ob ein Gepäckstück rechtzeitig ankommt. Solche Voraussagen können verfeinert werden, indem die Varianz der Verzögerung auf einem verfolgten Pfad bewertet wird. 2. (Ressourcenzuweisung) Man kann die Zunahme der Intensität entlang eines minimalisierenden Pfads während der Reise eines Gepäckstücks als eine Art von Ressourcenzuwei- sung/Reservierung interpretieren.

3. (Lastausgleich) Stark genutzte Knoten, wo Wartezeiten auftreten können, werden von den Gepäckstücken gemieden. Auf diese Weise erreicht der Algorithmus einen automatischen Lastausgleich. Redundante Strecken und andere Alternativpfade mit einer vergleichbaren Laufzeit werden in gleicher Weise belastet .

4. (Exogene Blockierung) Eine Blockierung wird zu den BeIa- dungssteilen des Systems verschoben. Anstatt ein willkürliches Einbringen zu gestatten und somit ein internes Blockieren des Systems zu riskieren, blockiert der Algorithmus das Einbringen am Eingang. Auf diese Weise kann er Transportzeiten auf annehmbaren Werten halten, Überlastzustände erkennen und Zusammenbruchswahrscheinlichkeiten reduzieren.

5. (Anpassung an Beobachtungen) Da die meisten Ausdrücke in dem Algorithmus eine sehr natürliche und suggestive Interpretation haben, kann man leicht die Parameter an Beobachtungen anpassen. Z.B. ist der Ausdruck

die voraussichtliche Wartezeit an dem Knoten n aufgrund von Stauungsverzögerungen. Wenn dieser Wert aus Beobachtungen berechnet werden kann und es sich herausstellt, dass er von seiner Voraussage abweicht, können die Faktoren o(u,n) ange- passt werden, um den Unterschied zu vermindern. Auf diese Weise kann man eine gute Übereinstimmung zwischen Theorie und Praxis erzielen. 6. Der Algorithmus ist einfach und flexibel. Z.B. kann man durch Reduzieren des Satzes von Pfaden P die Aufmerksamkeit auf zwei (oder drei, ...) alternative Pfade zwischen einer Quelle und einer Senke beschränken.