<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//OASIS//DTD DocBook XML V4.2//EN" "http://www.oasis-open.org/docbook/xml/4.2/docbookx.dtd">
<article lang="de"><title>Sequenzierung mit Ant-Colony-Systemen am Beispiel Querverteil-Wagen</title><articleinfo><authorblurb><para role="author">Clara Maria Novoa, M.E. </para><para role="authorinfo">Industrial and Systems Engineering Department (ISE), Lehigh University</para><para role="author">Dipl. Ing. Hubert Büchter, </para><para role="authorinfo">Fraunhofer Institut Materialfluss und Logistik (IML), Dortmund</para></authorblurb><abstract lang="de"><para role="abstractDE">Dieser Beitrag zeigt die Anwendung des Ant-Colony-System (ACS) Algorithmus auf die Sequenzierung von Querverteil-Wagen in einem Lager. Wir erweitern den Basisalgorithmus der Ant-Colony-Optimierung (ACO) für die Minimierung der Bearbeitungszeit einer Menge von Fahraufträgen für die Querverteil-Wagen. Im Vergleich zu dem Greedy-Algorithmus ist der ACO-Algorithmus wettbewerbsfähig und schnell. In vielen Lagerverwaltungssystemen werden die Fahraufträge nach dem FIFO-Prinzip (First-in-First-out) ausgeführt. In diesem Beitrag wird der ACO-Algorithmus genutzt, um eine optimale Sequenz der Fahraufträge zu bilden.</para></abstract><abstract lang="en"><para role="abstractEN">This paper presents an application of the ant-colony systems (ACS) algorithm for sequencing traversing-cars in a warehouse system. We extend the basic ant-colony optimization algorithm (ACO) for minimizing the time required to serve a set of incoming requests to the traversing-cars. We also develop a greedy algorithm. The comparison between ACS and the greedy algorithm indicates that the ACS algorithm is competitive and fast. In many warehouse management situa¬tions, the rule for sequencing requests for traversing cars is the FIFO rule. The results on this paper show that the ACS algorithm applies to warehouse traffic sequencing.</para></abstract><authorgroup><author><firstname>Clara Maria</firstname><surname>Novoa</surname></author><author><firstname>Hubert</firstname><surname>Büchter</surname></author></authorgroup><biblioid class="uri">urn:nbn:de:0009-12-7017</biblioid><biblioid class="doi">10.2195/LJ_Not_Ref_d_Buechter_052005</biblioid><keywordset><keyword>Ant-Colony optimization</keyword><keyword>Meta heuristics</keyword><keyword>Material flow systems</keyword><keyword>warehouse logistics</keyword><keyword>Fraunhofer-Institut für Materialfluss und Logistik</keyword><keyword>Logistic-Journal</keyword><keyword>eLogistics-Journal</keyword><keyword>technical logistics</keyword><keyword>intra-logistics</keyword><keyword>intralogistics</keyword><keyword>Ant-Colony-Optimierung</keyword><keyword>Metaheuristik</keyword><keyword>Materialfluss-Systeme</keyword><keyword>Lager-Logistik</keyword><keyword>warehouse logistics</keyword><keyword>material flow system</keyword><keyword>meta heuristics</keyword><keyword>WGTL</keyword><keyword>Wissenschaftliche Gesellschaft für Technische Logistik</keyword><keyword>elogistics journal</keyword><keyword>Prof Michael ten Hompel</keyword><keyword>Universität Dortmund</keyword><keyword>Uni Dortmund</keyword><keyword>Logistik</keyword><keyword>Logistics</keyword><keyword>Materialfluss</keyword><keyword>Material flow</keyword><keyword>Universitaet Dortmund</keyword><keyword>Intralogistics</keyword><keyword>intra logistics</keyword><keyword>intra-logsitics</keyword><keyword>Intralogistik</keyword><keyword>technische Logistik</keyword><keyword>DOI 10.2195/LJ_Not_Ref_d_Buechter_052005</keyword><keyword>Hubert Büchter</keyword><keyword>Clara Maria Novoa</keyword><keyword>ISSN 1860-5923</keyword></keywordset><subjectset scheme=""><subject></subject></subjectset><legalnotice><title>Lizenz</title><para>Jedermann darf dieses Werk unter den Bedingungen der Digital Peer Publishing Lizenz elektronisch übermitteln und zum Download bereitstellen. Der Lizenztext ist im Internet abrufbar unter der Adresse http://www.dipp.nrw.de/lizenzen/dppl/dppl/DPPL_v2_de_06-2004.html</para></legalnotice><titleabbrev></titleabbrev><volumenum>2005</volumenum><issuenum>Mai</issuenum><biblioset relation="journal"><issn>ISSN:1860-5923</issn><title>Logistics Journal : nicht-referierte Veröffentlichungen</title></biblioset></articleinfo><section><title><phrase role="GEN_upcast-HEADINGNUMBER">1.	</phrase>Überblick</title><para role="text">Der Abschnitt 2 beschreibt das zu lösende Problem. Abschnitt 3 zeigt eine Formulierung des Problems durch „Linear-Integer-Programming“. Abschnitt 4 gibt einen kurzen Überblick über die Literatur zum Thema Ant-Colony-Systeme (ACS). In Abschnitt  5 werden Erweiterungen des ACS-Algorithmus zur Lösung des Sequenzierungsproblems mit nur <emphasis>einem</emphasis> Querverteil-Wagen vorgestellt. In Abschnitt 6 wird ein Greedy-Algorithmus beschrieben und die nummerischen Ergebnisse für ACS- und Greedy-Verfahren diskutiert. In Abschnitt 7 wird der ACS-Algorithmus für zwei Querverteil-Wagen, die auf einer gemeinsamen Schiene fahren, erweitert. Abschnitt 8 fasst die Ergebnisse zusammen.</para><para role="text" /></section><section><title><phrase role="GEN_upcast-HEADINGNUMBER">2.	</phrase>Problembeschreibung</title><para role="text">Betrachten wir ein Lagersystem nach Abbildung 1.</para><para role="text" /><para role="Abbildung"><mediaobject><imageobject><imagedata width="97.13mm" depth="63.77mm" fileref="dippArticle-1.png" format="PNG" srccredit="embed" /></imageobject><caption><para role="caption">Abbildung <phrase role="GEN_SEQ">1</phrase>: Hochregallager mit 4 Gassen und 4 Kommissionierplätzen</para></caption></mediaobject></para><para role="text">Das Lager verfügt über einen I-Punkt IP (Identifikation Point), vier Kommissionier-Stationen PP (Pick Place) mit jeweils einem Ein- und Ausgangspuffer beschränkter Kapazität. Die vier Lagergassen werden jeweils durch ein Regalbediengerät AS/RS (Automatic Storage and Retrieval System) bedient und verfügen ebenfalls über einen Eingangspuffer IB (Input Buffer) und einen Ausgangspuffer OB (Output Buffer) beschränkter Kapazität. Jedes AS/RS kann einerseits Paletten zwischen IB und den Lagerfächern und andererseits zwischen den Lagerfächern und OB transportieren. Das Lager verfügt über einen einzelnen Ausgabepunkt OP (Output Point). Jeder Fahrauftrag für den Querverteil-Wagen hat mit einer gewissen Wahrscheinlichkeit einen der Puffer IB oder den Ausgabepunkt KP zum Ziel. Ebenso existieren Fahraufträge zu den Eingangspuffern und von den Ausgangspuffern der Kommissionierstationen. Die Querverteil-Wagen bewegen sich horizontal auf einer gemeinsamen Schiene zwischen dem Lagerbereich und den Kommissionier-Stationen. Die Quellpunkte der Fahraufträge sind in Abbildung 1 mit einem Pfeil in Richtung der Gasse des Querverteil-Wagens und die Senken mit einem Pfeil in Gegenrichtung gekennzeichnet. Zurzeit werden die Fahraufträge nach dem FIFO-Prinzip abgearbeitet.</para><para role="text" /></section><section><title><phrase role="GEN_upcast-HEADINGNUMBER">3.	</phrase>Formalisiertes Problem</title><para role="text">Wir nennen das oben beschriebene Problem der Sequenzierung der Fahraufträge „sequencing traversing-cars problem“ (STCP). Die Lösung ist die optimale Sequenz, die die Zeit für die Abarbeitung einer vergegebenen Menge von Fahraufträgen minimiert.</para><para role="text">Angenommen es existiert nur ein Querverteil-Wagen im System und die Anzahl der unterschiedlichen Quellen sei <emphasis>n</emphasis>. <emphasis>n<subscript>c</subscript></emphasis> sei die Anzahl der Elemente der Menge <emphasis>C</emphasis> der Fahraufträge, die sich aus der jeweils ersten Position einer Palette auf einer Quelle ergibt. <emphasis>C</emphasis> ist also die Menge der Fahraufträge, die zu einer gegebenen Zeit ausgeführt werden können. Zusätzlich enthält <emphasis>C</emphasis> den aktuellen Standort des Querverteil-Wagens, um die Kosten der ersten Fahrt zu einer Quelle berücksichtigen zu können. Wenn die Anforderung <emphasis>j</emphasis><inlinemediaobject><imageobject><imagedata width="3.53mm" depth="3.53mm" fileref="dippArticle-2.png" format="PNG" srccredit="embed" /></imageobject></inlinemediaobject><emphasis>C</emphasis> gewählt wird, fährt der Wagen von der Startposition <emphasis>o<subscript>j</subscript></emphasis> zur Zielposition <emphasis>d<subscript>j</subscript></emphasis>. Wenn die aktuelle Position des Wagens<emphasis> d<subscript>i</subscript></emphasis>,<emphasis> d<subscript>i </subscript>≠ o<subscript>j</subscript></emphasis> ist, muss die Leerfahrt von <emphasis>d<subscript>i</subscript> </emphasis>nach <emphasis>o<subscript>j</subscript></emphasis> berücksichtigt werden. Wird der Auftrag <emphasis>j</emphasis> unmittelbar nach dem Auftrag <emphasis>i</emphasis> ausgeführt, ergibt sich eine feste Zeit <emphasis>f<subscript>i</subscript></emphasis>, die der Wagen benötigt, um die Last von <emphasis>o<subscript>j</subscript></emphasis> nach <emphasis>d<subscript>j </subscript></emphasis> zu transportieren. Die Zeit, die zu minimieren ist, ist die Summe der Zeiten, in denen der Wagen unbeladen zum nächsten Auftragsziel fährt. Die Gleichung <link linkend="a">1</link> beschreibt die Zielfunktion. Ohne Verlust der Allgemeingültigkeit sind die Zeiten der Lastfahrten ebenfalls berücksichtigt. In der Gleichung <link linkend="a">1</link> ist <emphasis>x<subscript>ij</subscript></emphasis> eine 0/1-Entscheidungsvariable. Falls in der Lösung des STCP-Problems der Auftrag <emphasis>j</emphasis> unmittelbar auf den Auftrag <emphasis>i</emphasis> folgt, bekommt <emphasis>x<subscript>ij</subscript></emphasis> den Wert eins, sonst null.</para><para role="text"><inlinemediaobject><imageobject><imagedata width="35.97mm" depth="12.44mm" fileref="dippArticle-3.png" format="PNG" srccredit="embed" /></imageobject></inlinemediaobject>					(<anchor id="a" />1)</para><para role="text">Nach jeder Bearbeitung eines Fahrauftrages werden die Menge <emphasis>C </emphasis>der ausführbaren Kandidaten sowie der Zustand der Quellen und Senken aktualisiert. Die Einschränkungen des Traveling-Salesman-Problems (TSP) gelten ebenfalls für das hier zu lösende Problem der Sequenzierung (STCP). Jeder Auftrag hat genau einen Vorgänger und einen Nachfolger und eine Lösung darf keine Subtouren enthalten. Ein Auftrag <emphasis>j</emphasis> darf nur dann ausgeführt werden, wenn das Ziel <emphasis>d<subscript>j</subscript></emphasis> nicht vollständig belegt ist. Falls das Ziel für den Auftrag j nicht vollständig gefüllt ist, wird <emphasis>kd<subscript>j</subscript></emphasis> eins, sonst null. Die letzte Restriktion erfordert, dass die Bearbeitungszeiten an den Kommissionerstationen, den Übergabepuffern und dem Systemausgang mit in das Modell einzubeziehen sind. Aus diesem Grund werden die Zustände der Quellen und der Senken laufend aktualisiert. Die Gleichungen 2-5 stellen die Restriktionen des STCP dar.</para><para role="text"><inlinemediaobject><imageobject><imagedata width="30.15mm" depth="13.76mm" fileref="dippArticle-4.png" format="PNG" srccredit="embed" /></imageobject></inlinemediaobject>					(<anchor id="f2" />2)</para><para role="text"><inlinemediaobject><imageobject><imagedata width="30.15mm" depth="14.29mm" fileref="dippArticle-5.png" format="PNG" srccredit="embed" /></imageobject></inlinemediaobject>					(<anchor id="f3" />3)</para><para role="text"><inlinemediaobject><imageobject><imagedata width="74.88mm" depth="11.62mm" fileref="dippArticle-6.png" format="PNG" srccredit="embed" /></imageobject></inlinemediaobject>			(<anchor id="f4" />4)</para><para role="text">                <inlinemediaobject><imageobject><imagedata width="52.39mm" depth="6.88mm" fileref="dippArticle-7.png" format="PNG" srccredit="embed" /></imageobject></inlinemediaobject>			(<anchor id="f5" />5)</para><para role="text"><inlinemediaobject><imageobject><imagedata width="19.32mm" depth="6.88mm" fileref="dippArticle-8.png" format="PNG" srccredit="embed" /></imageobject></inlinemediaobject></para><para role="text" /></section><section><title><phrase role="GEN_upcast-HEADINGNUMBER">4.	</phrase>Literatur Überblick</title><para>In [<link linkend="Gagne01">Gagné01</link>], [<link linkend="Dorigo96">Dorigo96</link>], [<link linkend="Dorigo97">Dorigo97</link>], [<link linkend="deJong01">deJong01</link>] werden Ant-Colony-Algorithmen (ACO) beschrieben. In [<link linkend="Dorigo96">Dorigo96</link>] beschreiben die Autoren den Ant-System-Algorithmus (AS) und wen­den ihn zur Lösung des Traveling-Salesman-Problems (TSP) an. Der Ant-System-Algorithmus arbeitet ähnlich dem Verhalten realer Ameisen. Ameisen kommunizieren über Pheromone. Das sind Stoffe, die sie in unterschiedlicher Intensität auf den verschiedenen Wegen zwischen Nest und Futterstelle hinterlassen. Wenn mehr Ameisen den gleichen Weg nutzen, steigt die Pheromon-Intensität. Wenn auf dem Weg ein Hindernis erscheint, werden die Ameisen unterschiedliche Wege zur Futterquelle finden. Die Ameisen, die den kürzesten Pfad nutzen, werden schneller auf die Pheromon-Spur zurückkehren. Schließlich wird, unabhängig vom ersten gefundenen Pfad, der bevorzugte Pfad vom Nest zur Futterquelle zum kürzesten Pfad tendieren [<link linkend="Dorigo96">Dorigo96</link>]. Die Autoren testen die drei folgenden Versionen von Ant-Systemen: Ant-Density, Ant-Quantity und Ant-Cycle. Die Experimente zeigen die Überlegenheit der Ant-Cycle-Version, da dieser globale Informa­tionen für die Aktualisierung der Pheromon-Dichte nutzt, während die beiden anderen Versionen nur auf lokaler Information basieren. Die Experimente zeigen, dass der Algorithmus mit kommu­nizierenden Ameisen effektiver arbeitet als mit nicht kommunizierenden Ameisen. Der Synergie­effekt ist optimal, wenn die Anzahl der Ameisen etwa der Anzahl der Städte entspricht. Vergleiche von anderen spezialisierten TSP-Algorithmen mit Anwendung auf das 30-Städte-Problem zeigen, dass Ant-Cycle eine bessere Performance aufweist, auch wenn die anderen Algorithmen 2-Opt-Verfahren nutzen. Die erwähnten Algorithmen erreichen nur dann die Qualität von Ant-Cycle, wenn sie die Lin-Kernighan Heuristik nutzen. Auf das gleiche 30-Städte-Problem wurden Simu­lated Annealing, Ant-Cycle und Tabu Search mit einer Laufzeit von einer Stunde angewendet. Simulated Annealing berechnete ein nur geringfügig schlechteres Ergebnis als die anderen beiden.</para><para>In [<link linkend="Gagne01">Gagné01</link>] setzen die Autoren ACO-Algorithmen zur Lösung des Ein-Maschinen-Schedu­ling-Problems ein. Es gibt sequenz-abhängige Vorbereitungszeiten; die Zielfunktion minimiert die Verspätungszeiten. Das Verfahren enthält eine vorausschauende Abschätzung um die Güte der Teillösungen abzuschätzen.</para><para>In [<link linkend="Dorigo97">Dorigo97</link>] beschreiben die Autoren einen verbesserten ACO-Algorithmus, den Ant-Colony-System (ACS) Algorithmus. In AS und ACS Algorithmen bilden die Ameisen jeweils unter­schiedliche Touren. Jede Ameise wählt die nächste Stadt, um ihre eigene Tour, die von der Phe­romon-Dichte der Kanten und von der Distanz der Städte abhängt, einzufügen. Ameisen bevor­zugen Städte, die über kurze Wege mit einer hohen Pheromon-Dichte miteinander verbunden sind. Ein Zyklus endet, wenn alle Ameisen ihre Tour beendet haben. Ein Zyklus endet, wenn alle Amei­sen ihre Tour beendet haben. ACS beinhaltet im Gegensatz zu AS eine lokale Aktualisierung der Pheromon-Dichte der Kanten. Diese Aktualisierung erfolgt immer, wenn eine Kante durchlaufen wurde. Durch eine temporäre Reduzierung der Spurdichte (Verdunstung von Pheromon) werden die nachfolgenden Ameisen ermutigt, auch die Umgebung der bisher besten Lösung zu erkunden. Die globale Aktualisierung erfolgt in ACS nur auf Kanten der kürzesten Tour eines Zyklus, der alle Ameisen umfasst. Verdunstung tritt nur auf allen Kanten auf, die nicht zur besten Tour gehö­ren.</para><para>In [<link linkend="deJong01">deJong01</link>] setzt der Autor ein Multiple-Ant-Colony-System (MACS) zur Lösung eine Bus-Halteproblems (Bus-stop Allocation Problem, BAP) ein. Im BAP müssen alle Busse den Haupt­bahnhof anfahren. Das Problem ist die Aufteilung der verbleibenden n-1 Haltestellen auf m Bus­linien. Auf jeder Buslinie starten zwei Busse – beginnend an den beiden Endpunkten – in unter­schiedlichen Richtungen. Das Ziel ist die Minimierung der mittleren Reisezeit über alle Passa­giere, die an den unterschiedlichen Haltestellen warten. Jede Buslinie wird durch ein eigenes Ant-Colony-System (ACS) repräsentiert. In diesen m Ant-Colony-Systemen werden die Pheromon-Spuren der einzelnen Kolonien getrennt aktualisiert. Jede Kolonie besteht aus r Ameisen. Alle Ameisen mit der gleichen Ordnungsnummer bilden kolonieübergreifend eine Gruppe und tragen gemeinsam zu einer Lösung bei. Die numerischen Beispiele zeigen, dass ein Multiple-Ant-Colony-System bessere Ergebnisse liefert, als Greedy- und Simulated-Annealing-Algorithmen. In dieser Veröffentlichung sind die Wege in beiden Richtungen befahrbar, so dass keine Konflikte zwischen den Bussen auftreten können.</para><para role="text" /></section><section><title><phrase role="GEN_upcast-HEADINGNUMBER">5.	</phrase>Ant-Colony-System Algorithmus für einen Einzelwagen</title><para>Die Einzelschritte des ACO Algorithmus für die STCP-Lösung für einen Einzelwagen sind in Tabelle 1 zusammengefasst. Dieser Algorithmus weist gegenüber dem Ant-Colony-System nach [<link linkend="Gagne01">Gagné01</link>], [<link linkend="Dorigo96">Dorigo96</link>], [<link linkend="Dorigo97">Dorigo97</link>], [<link linkend="deJong01">deJong01</link>] einige Änderungen auf. Für STCP sind die Auf­träge analog zu den Wegen zwischen den Städten im TCP. Wenn kein ausführbarer Auftrag aus der Kandidatenmenge C mehr vorliegt, weil das Auftragsziel belegt ist, blockiert der Wagen. Diese Blockade dauert an, bis ein Auftragsziel bedient wird, so dass es durch den Wagen angefah­ren werden kann. Durch die Blockadezeit wird die Zyklusdauer größer als die Gesamtzeit, in der alle Ameisen ihre Tour vervollständigen können. Der Startpunkt für alle Ameisen wird nicht zu­fällig gewählt sondern er entspricht der initial gewählten Startposition. Aus diesem Grund ist es erforderlich, in der trail intensity matrix eine Zeile τ hinzuzufügen, die das Verkehrsaufkommen zwischen der initialen Position des Wagens und der Quellposition des ersten mögliche Auftrags einer Tour. Tabuk ist die aktuelle Tour für die Ameise k. Wenn Ameise k einen Auftrag bearbeitet, wird dieser Auftrag in die Tabuk –Liste eingetragen und aus der Warteschlange der Auftragsquelle entfernt. Die führenden Elemente der Warteschlangen der Quellpositionen sind ausführbare Auf­träge und sie bilden über alle möglichen Quellpositionen die Menge C der Auftragskandidaten. Die Entscheidung zwischen der Erkundung neuer Lösungen (Exploration) und Nutzung bekannter Lösungen (Exploitation) wird durch den Wert des Parameters q0 bestimmt. Bis jetzt werden keine lokalen Optmierungsverfahren wie die 3-Opt-Methode in unserem Algorithmus genutzt. Die Va­riable ηij repräsentiert die Sichtbarkeit der Spur. Sie ist als Kehrwert der Zeit definiert, die die unmittelbare Bearbeitung des Auftrages j nach Auftrag i benötigt. Die Bearbeitungszeit eines Auf­trages ist die Summe aus der Leerfahrt-, Lastfahrt-, Lastaufnahme- und Lastabgabezeit. Für den Wagen wird eine mittlere Geschwindigkeit von 1m/s angenommen. Die Wichtung der Intensitäts­matrix ist α, die Wichtung der Sichtbarbeit ist β. Die globale und die lokale Verdunstungsfaktoren werden mit ρg und ρl bezeichnet.</para><para role="text" /><table frame="all"><title>Tabelle 1: Ant-Colony-System-Algorithmus für einen Wagen</title><tgroup cols="1"><colspec colname="col1" colwidth="464.4pt" colnum="1" /><tbody><row><entry colname="col1" valign="top" rowsep="1" colsep="1" align="justify"><para role="text">Schritt 1: Intialisierung</para><para role="text">t=0 (t ist eine Laufvariable, die nach jedem globalen Update der Dichte-Matrix erhöht wird.) ; num_cycles=0;</para><para role="text" /><para role="text">Für jede Kante (i,j) initialisiere die Intensitäts-Matrix:</para><para role="text">  wenn der Auftrag  i vor dem Auftrag j bearbeitet werden kann τ<subscript>ij</subscript>(0) = τ<subscript>o </subscript>= (nL)<superscript>-1</superscript></para><para role="text">  sonst  τ<subscript>ij</subscript>(0)=0.</para><para role="text">Dabei ist n die Anzahl der Aufträge und L ist die Länge der Sequenz, die sich aus dem Greedy-Algorithmus ergibt. </para><para role="text" /><para role="text">Für alle k Ameisen</para><para role="text">  kopiere die initialen Quell- und Ziel-Stati,</para><para role="text">  set current_time[k]=ant_step[k]= 0</para><para role="text">  ant_finish[k] = false.</para><para role="text" /><para role="text">Schritt 2: Start</para><para role="text">Für jede Ameise k:</para><para role="text">  Setze die Ameise k auf die Startposition des Wagens</para><para role="text"> </para><para role="text">Schritt 3: Erzeuge eine Sequenz für jede Ameise</para><para role="text">Solange nicht alle Ameisen beendet haben</para><para role="text">  Für alle Ameisen k = 1 to num_ants </para><para role="text">     Wenn not ant_finish[k]</para><para role="text">          ant_step[k] = ant_step[k] +1;</para><para role="text">          Wähle einen Auftrag j, j∉Tabu<subscript>k</subscript> aus den l möglichen Kandidaten, der dem Auftrag i folgt, so dass:</para><para role="text"><inlinemediaobject><imageobject><imagedata width="98.43mm" depth="14.82mm" fileref="dippArticle-9.png" format="PNG" srccredit="embed" /></imageobject></inlinemediaobject>                    (<anchor id="f6" />6)</para><para role="text">           mit der Spurdichte τ<subscript>il</subscript>(t) zwischen den Aufträgen i und l für die Iteration t . J ist eine Zufallszahl. </para><para role="text">           Die Wahrscheinlichkeit, das der Auftrag  j gewählt wird ist</para><para role="text"><inlinemediaobject><imageobject><imagedata width="39.41mm" depth="15.35mm" fileref="dippArticle-10.png" format="PNG" srccredit="embed" /></imageobject></inlinemediaobject>                                                      (<anchor id="f7" />7)</para><para role="text">            Prüfe, ob eine Blockierung auftritt und aktualisiere current_time[k], Quellen und Senken</para><para role="text">            Wenn keine Blockierung vorliegt, führe ein local update auf dem gewählten Teilweg (i,j) aus:</para><para role="text"><inlinemediaobject><imageobject><imagedata width="57.68mm" depth="5.8mm" fileref="dippArticle-11.png" format="PNG" srccredit="embed" /></imageobject></inlinemediaobject>                                  (<anchor id="f8" />8)</para><para role="text">            Wenn Ameise k die Tour beendet hat, setze  ant_ finish[k] = true</para><para role="text">  Prüfe, ob alle Ameisen ihre Tour beendet haben.</para><para role="text" /><para role="text">Schritt 4: Globale Aktualisierung</para><para role="text">Berechne die Länge der Tour L<subscript>k </subscript>für jede Ameise k. Aktualisiere für jeden Teilweg (i,j) der optimalen Tour die Spur-Intensität: </para><para role="text"><inlinemediaobject><imageobject><imagedata width="129.37mm" depth="9.24mm" fileref="dippArticle-12.png" format="PNG" srccredit="embed" /></imageobject></inlinemediaobject>                (<anchor id="f9" />9)</para><para role="text">t = t+1;</para><para role="text" /><para role="text">Schritt 5: Abbruchbedingungen</para><para role="text">Solange (num_cycles &lt; max_cycles) und (keine Stagnation)</para><para role="text">num_cycles = num_cycles +1</para><para role="text">Für alle Ameisen k</para><para role="text">  current_time[k] =0, ant_step[k]=0, ant_finish[k]=false</para><para role="text">Initialisiere alle Ameisen durch Clonen der Initialzustände der Quelle und Senken</para><para role="text">Weiter mit Schritt 2</para></entry></row></tbody></tgroup></table><para role="tabelle" /><para role="text">Zu Bewertung werden die gesamte Weglänge und – falls vorhanden – die Blockierungszeiten berücksichtigt. Das Resultat ist die tatsächlich benötigte Zeit für die Auftragsausführung. Jeder Lauf basiert auf folgenden Parametern, die zu Beginn vorgegeben werden;</para><itemizedlist mark="disc" spacing="normal"><listitem><para role="text">Anzahl der Anforderungen von den unterschiedlichen Quellen,</para></listitem><listitem><para role="text">Ziele für die einzelnen Aufträge,</para></listitem><listitem><para role="text">Zielbelegung,</para></listitem><listitem><para role="text">Startposition des Wagens und</para></listitem><listitem><para role="text">Bearbeitungszeiten an den Zielpositionen.</para></listitem></itemizedlist><para role="text">Es wird eine zufällig gewählte Zahl von Aufträgen mit jeweils unterschiedlichen Quell- und Zielpositionen im Intervall Null bis zur Maximalkapazität der Quellen und der Senken mit einer Gleichverteilung  erzeugt. Das Ziel wird entsprechend den Werten einer Transportmatrix gewählt. Die Bearbeitungszeiten an den Kommissionierstationen und den Puffern wird einmal gleichverteilt im Intervall [30s, 60s] und einmal konstant mit 30sec angenommen.</para><para role="text">Für den Algorithmus wurden folgende Parameter gesetzt. Die Anzahl der Ameisen wurde auf  die jeweilige Anzahl der Aufträge gesetzt. Die Werte für <emphasis>α</emphasis>, <emphasis>β, ρ<subscript>local</subscript></emphasis>, and <emphasis>ρ<subscript>lglobal</subscript> </emphasis>wurden auf 1, 5, 0.9 und 0.9 gesetzt. Für <emphasis>q<subscript>0</subscript></emphasis> wurden die Werte 0, 0.5 und 1.0 eingesetzt. Die Maimalzahl der Zyklen für den Algorithmus wurde auf 5000 gesetzt. Bereits nach 50 Zyklen wurde keine Verbesserung des Ergebnisses erreicht. </para><para role="text" /></section><section><title><phrase role="GEN_upcast-HEADINGNUMBER">6.	</phrase>Nummerische Vergleiche: Greedy- und ACO-Algorithmus</title><para role="text">Der ACO-Algorithmus wurde mit UML (Unified Markup Language) designed und in Java mit der Entwicklungsumgebung Forte 3.0 programmiert. Der Greedy-Algorithmus wurde ebenfalls in Java codiert. Zunächst wurde das Greedy-Verfahren implementiert, da es einfach ist und schnelle Laufzeiten erwarten lässt. Die Ergebnisse wurden mit dem bisher verwendeten FIFO-Verfahren verglichen. Nach der Implementierung des Greedy-Verfahrens wurde der ACO-Algorithmus in Bezug auf Ergebnis-Qualität und Laufzeit untersucht.</para><para role="text">Der Greedy-Algorithmus nimmt in die Kandidatenmenge das erste Element jeder Quelle auf. Dann wird unter diesen Kandidaten derjenige ausgewählt, zu den der Wagen von seinem aktuellen Standort aus die kürzeste Leerfahrt hat. Die Gesamtzeit setzt sich aus der Zeit für die Leerfahrt zur Quelle und der Zeit für Lastfahrt zum Ziel zusammen. Das Verfahren terminiert, wenn alle Aufträge abgearbeitet sind. Abbildung 12 zeigt Mittelwerte für die Bearbeitungszeit aller Aufträge unter Einsatz des ACO-Algorithmus für 50% und 100% Exploration-Anteil und des Greedy-Algorithmus. Der Greedy-Algorithmus ist – insbesondere im Vergleich zur Ersparnis an Ausführungszeit – unwesentlich schneller als ACO. Das ACO-Verfahren mit 50% Exploration liefert das beste Ergebnis.</para><para role="Abbildung"><mediaobject><imageobject><imagedata width="102.66mm" depth="56.08mm" fileref="dippArticle-13.png" format="PNG" srccredit="embed" /></imageobject><caption><para role="caption">Abbildung <phrase role="GEN_SEQ">2</phrase>: Mittlere Bearbeitungszeit und Rechenzeit für ACO- und Greedy-Algorithmus.</para></caption></mediaobject></para><para role="text" /><para role="text">Tabelle 2 zeigt die Ergebnisse für die Läufe mit den beiden Verfahren im Detail. Die ACO-Ergebnisse gelten für 50% Exploration. Alle Quellen sind vollständig gefüllt, was 25 Aufträgen entspricht. Die Bearbeitungszeiten an den Kommissionierstationen und den Puffern werden als konstant angenommen.</para><para role="text" /></section><section><title><phrase role="GEN_upcast-HEADINGNUMBER">7.	</phrase>Erweiterung des ACS-Algorithmus für zwei Wagen</title><para role="text">Es werden zwei Kolonien mit jeweils <emphasis>k</emphasis> Ameisen eingesetzt. Je zwei Ameisen mit gleicher Ordnungszahl aus unterschiedlichen Kolonien bilden ein Paar, um das Problem gemeinsam zu lösen. Es werden zwei separate Matrizen für die Intensität der Pheromon-Spuren geführt. Diese Matrizen werden nach jeder Iteration <emphasis>t</emphasis>.aktualisiert. Wenn die Kolonie eins den Auftrag <emphasis>j</emphasis> als Nachfolger für den Auftrag <emphasis>i </emphasis>unter <emphasis>l </emphasis>Kandidaten wählt, muss (<link linkend="f6">6</link>) wie folgt angepasst werden:</para><para role="text" /><para role="text"><inlinemediaobject><imageobject><imagedata width="84.14mm" depth="17.45mm" fileref="dippArticle-14.png" format="PNG" srccredit="embed" /></imageobject></inlinemediaobject>                                (<anchor id="f10" />10)</para><para role="text" /><para role="text"><emphasis>J</emphasis> wird zufällig gewählt. Die Wahrscheinlichkeit für die Auswahl des Auftrages <emphasis>j </emphasis>wird durch (<link linkend="f11">11</link>) beschrieben:</para><para role="text"><inlinemediaobject><imageobject><imagedata width="60.84mm" depth="19.58mm" fileref="dippArticle-15.png" format="PNG" srccredit="embed" /></imageobject></inlinemediaobject>					(<anchor id="f11" />11)</para><para role="text" /><para role="text">In den Gleichungen (<link linkend="f10">10</link>) und (<link linkend="f11">11</link>)  ist <emphasis>ψ</emphasis><superscript>1</superscript><subscript><emphasis>ij</emphasis> </subscript>ein Maß für die Durchführbarkeit des Auftrages <emphasis>j</emphasis> nach dem Auftrag <emphasis>i</emphasis> durch eine Ameise <emphasis>k</emphasis> aus Kolonie eins wenn die entsprechende Ameise der Kolonie zwei mit der gleichen Ordnungsnummer einen Auftrag ausführt oder im Zustand Idle ist. Um mögliche Konflikte zu erkennen, werden die Pfadnummer und die Bearbeitungszeit der beiden Ameisen eines Paares verglichen. Zur Vermeidung von Konflikten auf Haltepositionen kann die Einführung von Idle-Zeiten erforderlich werden. In Gleichung (<link linkend="f11">11</link>) stellt <emphasis>χ</emphasis> das Gewicht für <emphasis>ψ</emphasis><superscript>1</superscript><subscript>ij</subscript> dar. Der Wert <emphasis>χ</emphasis> wurde mit 1.0 angenommen. Numerische Rechnungen zeigen, dass ACS bessere Ergebnisse liefert als ein Greedy-Verfahren. Die Rechenzeit erhöht sich jedoch auf bis zu 90 Sekunden.</para><para role="text" /><para role="text" /><table frame="all"><title>Tabelle 2: ACO Ergebnisse für einen Querverteil-Wagen</title><tgroup cols="9"><colspec colname="col1" colwidth="86.2pt" colnum="1" /><colspec colname="col2" colwidth="40.0pt" colnum="2" /><colspec colname="col3" colwidth="44.1pt" colnum="3" /><colspec colname="col4" colwidth="44.1pt" colnum="4" /><colspec colname="col5" colwidth="44.1pt" colnum="5" /><colspec colname="col6" colwidth="44.1pt" colnum="6" /><colspec colname="col7" colwidth="44.2pt" colnum="7" /><colspec colname="col8" colwidth="44.2pt" colnum="8" /><colspec colname="col9" colwidth="50.9pt" colnum="9" /><tbody><row><entry colname="col1" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle" /></entry><entry colname="col2" valign="bottom" rowsep="1" colsep="1" namest="col2" nameend="col5" align="justify"><para role="tabelle">ACO Algorithm</para></entry><entry colname="col6" valign="top" rowsep="1" colsep="1" namest="col6" nameend="col8" align="justify"><para role="tabelle">Greedy Algorithm</para></entry><entry colname="col9" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle" /></entry></row><row><entry colname="col1" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">Run</para></entry><entry colname="col2" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">Number of cycles</para></entry><entry colname="col3" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">Tour length</para><para role="tabelle">Seconds</para></entry><entry colname="col4" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">Blocked time</para><para role="tabelle">Seconds</para></entry><entry colname="col5" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">Total time</para><para role="tabelle">Seconds</para></entry><entry colname="col6" valign="top" rowsep="1" colsep="1" align="justify"><para role="tabelle" /><para role="tabelle">Tour Length</para></entry><entry colname="col7" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">Blocked time</para><para role="tabelle">Seconds</para></entry><entry colname="col8" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">Total time</para><para role="tabelle">Seconds</para></entry><entry colname="col9" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">% Decrease in total time</para></entry></row><row><entry colname="col1" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">1</para></entry><entry colname="col2" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">55</para></entry><entry colname="col3" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">240.50</para></entry><entry colname="col4" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">0.00</para></entry><entry colname="col5" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">240.50</para></entry><entry colname="col6" valign="top" rowsep="1" colsep="1" align="justify"><para role="tabelle">285.90</para></entry><entry colname="col7" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">0.00</para></entry><entry colname="col8" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">285.90</para></entry><entry colname="col9" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">15.87</para></entry></row><row><entry colname="col1" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">2</para></entry><entry colname="col2" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">57</para></entry><entry colname="col3" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">268.80</para></entry><entry colname="col4" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">7.50</para></entry><entry colname="col5" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">276.30</para></entry><entry colname="col6" valign="top" rowsep="1" colsep="1" align="justify"><para role="tabelle">321.30</para></entry><entry colname="col7" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">0.00</para></entry><entry colname="col8" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">321.30</para></entry><entry colname="col9" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">14.01</para></entry></row><row><entry colname="col1" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">3</para></entry><entry colname="col2" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">55</para></entry><entry colname="col3" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">272.90</para></entry><entry colname="col4" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">0.00</para></entry><entry colname="col5" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">272.90</para></entry><entry colname="col6" valign="top" rowsep="1" colsep="1" align="justify"><para role="tabelle">318.30</para></entry><entry colname="col7" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">0.00</para></entry><entry colname="col8" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">318.30</para></entry><entry colname="col9" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">14.26</para></entry></row><row><entry colname="col1" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">4</para></entry><entry colname="col2" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">55</para></entry><entry colname="col3" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">252.00</para></entry><entry colname="col4" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">0.00</para></entry><entry colname="col5" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">252.00</para></entry><entry colname="col6" valign="top" rowsep="1" colsep="1" align="justify"><para role="tabelle">280.60</para></entry><entry colname="col7" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">0.00</para></entry><entry colname="col8" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">280.60</para></entry><entry colname="col9" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">10.19</para></entry></row><row><entry colname="col1" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">5</para></entry><entry colname="col2" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">55</para></entry><entry colname="col3" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">267.90</para></entry><entry colname="col4" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">1.30</para></entry><entry colname="col5" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">269.20</para></entry><entry colname="col6" valign="top" rowsep="1" colsep="1" align="justify"><para role="tabelle">327.90</para></entry><entry colname="col7" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">0.00</para></entry><entry colname="col8" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">327.90</para></entry><entry colname="col9" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">17.90</para></entry></row><row><entry colname="col1" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">6</para></entry><entry colname="col2" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">55</para></entry><entry colname="col3" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">333.00</para></entry><entry colname="col4" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">0.00</para></entry><entry colname="col5" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">333.00</para></entry><entry colname="col6" valign="top" rowsep="1" colsep="1" align="justify"><para role="tabelle">392.40</para></entry><entry colname="col7" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">0.00</para></entry><entry colname="col8" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">392.40</para></entry><entry colname="col9" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">15.14</para></entry></row><row><entry colname="col1" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">7</para></entry><entry colname="col2" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">53</para></entry><entry colname="col3" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">306.10</para></entry><entry colname="col4" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">0.00</para></entry><entry colname="col5" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">306.10</para></entry><entry colname="col6" valign="top" rowsep="1" colsep="1" align="justify"><para role="tabelle">311.90</para></entry><entry colname="col7" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">0.00</para></entry><entry colname="col8" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">311.90</para></entry><entry colname="col9" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">1.86</para></entry></row><row><entry colname="col1" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">8</para></entry><entry colname="col2" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">56</para></entry><entry colname="col3" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">256.50</para></entry><entry colname="col4" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">0.00</para></entry><entry colname="col5" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">256.50</para></entry><entry colname="col6" valign="top" rowsep="1" colsep="1" align="justify"><para role="tabelle">299.30</para></entry><entry colname="col7" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">0.00</para></entry><entry colname="col8" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">299.30</para></entry><entry colname="col9" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">14.30</para></entry></row><row><entry colname="col1" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">9</para></entry><entry colname="col2" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">56</para></entry><entry colname="col3" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">307.00</para></entry><entry colname="col4" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">1.20</para></entry><entry colname="col5" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">308.20</para></entry><entry colname="col6" valign="top" rowsep="1" colsep="1" align="justify"><para role="tabelle">346.80</para></entry><entry colname="col7" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">0.00</para></entry><entry colname="col8" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">346.80</para></entry><entry colname="col9" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">11.13</para></entry></row><row><entry colname="col1" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">10</para></entry><entry colname="col2" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">61</para></entry><entry colname="col3" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">218.90</para></entry><entry colname="col4" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">0.00</para></entry><entry colname="col5" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">218.90</para></entry><entry colname="col6" valign="top" rowsep="1" colsep="1" align="justify"><para role="tabelle">297.00</para></entry><entry colname="col7" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">0.00</para></entry><entry colname="col8" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">297.00</para></entry><entry colname="col9" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">26.30</para></entry></row><row><entry colname="col1" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">Average</para></entry><entry colname="col2" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">55.80</para></entry><entry colname="col3" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">272.36</para></entry><entry colname="col4" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">1.00</para></entry><entry colname="col5" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">273.36</para></entry><entry colname="col6" valign="top" rowsep="1" colsep="1" align="justify"><para role="tabelle">318.14</para></entry><entry colname="col7" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">0.00</para></entry><entry colname="col8" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">318.14</para></entry><entry colname="col9" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">14.08</para></entry></row><row><entry colname="col1" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">Standard deviation</para></entry><entry colname="col2" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">2.10</para></entry><entry colname="col3" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">34.30</para></entry><entry colname="col4" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">2.34</para></entry><entry colname="col5" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">34.41</para></entry><entry colname="col6" valign="top" rowsep="1" colsep="1" align="justify"><para role="tabelle">32.88</para></entry><entry colname="col7" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">0.00</para></entry><entry colname="col8" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">32.88</para></entry><entry colname="col9" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">6.16</para></entry></row><row><entry colname="col1" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">Coef. of variation</para></entry><entry colname="col2" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">3.76%</para></entry><entry colname="col3" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">12.59%</para></entry><entry colname="col4" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">234.2%</para></entry><entry colname="col5" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">12.59%</para></entry><entry colname="col6" valign="top" rowsep="1" colsep="1" align="justify"><para role="tabelle">10.34%</para></entry><entry colname="col7" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">-</para></entry><entry colname="col8" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">10.34</para></entry><entry colname="col9" valign="bottom" rowsep="1" colsep="1" align="justify"><para role="tabelle">43.69%</para></entry></row></tbody></tgroup></table><para role="tabelle" /></section><section><title><phrase role="GEN_upcast-HEADINGNUMBER">8.	</phrase>Fazit</title><para>Die Erweiterung des Ant-Colony-Algorithmus nach [<link linkend="Gagne01">Gagné01</link>], [<link linkend="Dorigo96">Dorigo96</link>], [<link linkend="Dorigo97">Dorigo97</link>], [<link linkend="deJong01">deJong01</link>] wurde zur Lösung des STCP-Problems mit einem und zwei Wagen auf einer Schiene erweitert. Das Ergebnis zeigt, das der ACO-Algorithmus eine viel versprechende Technik zur Auftrags-Sequenzierung im Lagerbereich darstellt. Dieser Beitrag sollte die Anwendung und die Erweiterung des ACO-Algorithmus auf andere Anwendungsgebiete zeigen. Schließlich bestätigt diese Arbeit die Vorteile der positiven Rückkopplung und der Synergie, die das ACO-Verfahren charakterisieren. Weitere Arbeiten sollten andere Optimierungsverfahren für diese Anwendung implementieren und numerische Vergleiche durchführen.</para><para role="text" /><para role="heading">Literatur</para><informaltable frame="none"><tgroup cols="2"><colspec colname="col1" colwidth="83.6pt" colnum="1" /><colspec colname="col2" colwidth="386.0pt" colnum="2" /><tbody><row><entry colname="col1" valign="top" rowsep="0" colsep="0" align="left"><para role="litID">[<anchor id="Gagne01" />Gagné01]</para></entry><entry colname="col2" valign="top" rowsep="0" colsep="0" align="left"><para role="litText">Gagné, Caroline; Price, Wilson L.; Gravel, Marc: Scheduling a single machine with sequence dependent setup times using ant colony optimization,” Faculté des Sciences de l’administration, Université Laval, Canada. S. 1-21.</para><para role="litText">[http://wwwdim.uqac.ca/~c3gagne/DocumentRech/ANTS2000_SchedulingSingleMachine.pdf - Stand 04/2005]</para></entry></row><row><entry colname="col1" valign="top" rowsep="0" colsep="0" align="left"><para role="litID">[<anchor id="deJong01" />deJong01]</para></entry><entry colname="col2" valign="top" rowsep="0" colsep="0" align="left"><para role="litText">Jong de, Jasper; Wiering, Marco: Multiple ant-colony systems for the Busstop Allocation Problem. University of Utrecht, IN: Cognitive Artificial Intelligence (2001), S. 1-8</para><para role="litText">[http://www.cs.uu.nl/groups/IS/studprojects/thesis_jasper.pdf – Stand 04/2005]</para></entry></row><row><entry colname="col1" valign="top" rowsep="0" colsep="0" align="left"><para role="litID">[<anchor id="Dorigo96" />Dorigo96]</para></entry><entry colname="col2" valign="top" rowsep="0" colsep="0" align="left"><para role="litText">Dorigo, Marco; Maniezzo, Vittorio; Colorni, Alberto: The ant system: Optimization by a colony of cooperating agents. IN: IEEE Transactions on Systems, Man and Cybernetics– Part B, 26(1996)1,  S. 1-26.</para></entry></row><row><entry colname="col1" valign="top" rowsep="0" colsep="0" align="left"><para role="litID">[<anchor id="Dorigo97" />Dorigo97]</para></entry><entry colname="col2" valign="top" rowsep="0" colsep="0" align="left"><para role="litText">Dorigo, Marco; Gambardella, Luca M.: Ant colony system: A cooperative learning approach to the traveling salesman problem. IN: IEEE Trans. Evol. Comp., 1(1997)1, S. 53-66.</para></entry></row></tbody></tgroup></informaltable><para role="text" /></section></article>