Management von Verladeterminals mit Entscheidungsbäumen

Mémoire (de fin d'études) , 2006 , 110 Pages , Note: 1,0

Gestion d'entreprise - Généralités

Entscheidungsbäume erscheinen im Umfeld des Data Mining aus verschiedenen Gründen als Mittel zur Klassifikation besonders attraktiv. Diese Arbeit stellt ein Entscheidungsbauverfahren vor, das nicht in einer Data Mining Umgebung sondern stattdessen auf ein logistisches Optimirungsproblem angewendet wird.

Die Anwendbarkeit von Entscheidungsbäumen wird anhand des Beispiels eines Kfz-Verladeterminals gezeigt: Im Rahmen eines Umschlagvorgangs bewegen Fahrer Fahrzeuge von Frachtschiffen zu Zwischenlagern. Kosten entstehen dabei hauptsächlich durch Fahrerlöhne sowie durch mögliche Ladeschäden im Hafen. Bei der Planung und Organisation des Umschlags ist eine möglichst geringe Gesamtzahl an Fahrern sowie eine Nivellierung des Personalbedarfs über die Zeit anzustreben.

In einer grundlegenden Arbeit wurde die Problemstellung bereits in ein mehrperiodiges mathematisches Modell abgebildet und der Personalbedarf durch Anwendung einer parametrisierbaren Lösungsstrategie bestimmt. Die Ermittlung von Strategieparametern erfolgte durch einen zeitaufwändigen Evolutionären Algorithmus. Die Verwendung hat den Nachteil, dass eine Bestimmung optimaler Startwerte notwendig ist.

Diese Arbeit stellt ein Entscheidungsbaumverfahren vor, das die Parameterwahl zeiteffizient auf der Basis historischer Umschlagsdaten durchführt. Der Einsatz von Entscheidungsbäumen benötigt keinerlei Startwerte. Die Problematik der Wahl optimaler Startwerte, mit der Evolutionäre Algorithmen behaftet sind, lässt sich somit umgehen. Im Verlauf dieser Arbeit wird gezeigt, dass der Einsatz von Entscheidungsbaumverfahren zur Lösung der Problemstellung möglich ist.

Im Anschluß folgt die Beschreibung eines Lösungsverfahrens mittels Entscheidungsbäumen. Eine Evaluation des Laufzeitverhaltens, der Lösungsqualität und der Robustheit vergleicht den vorgestellten Lösungsansatz mit bisher verwendeten Ansätzen. Diese Untersuchung dient dazu, die Qualität des vorgestellten Verfahrens zu beurteilen und Ansatzpunkte für weitere Lösungsverfahren zu eröffnen.

Inhaltsverzeichnis

Abbildungsverzeichnis

Abkürzungsverzeichnis

1 Einleitung

2 Problemschilderung
2.1 Mathematische Modellierung des Problems
2.1.1 Lagerhaltungssystem
2.1.2 Vorgänge
2.1.3 Zielsetzung der Betrachtung
2.1.4 Generierung von lösbaren Probleminstanzen
2.2 Problemlösung
2.2.1 Reduktion der Problemkomplexität
2.2.2 Greedy-Strategie
2.2.3 Balancing-Strategie
2.2.4 Adaptive-Strategie

3 Grundlagen der Entscheidungsbäume
3.1 Thematische Einordnung im Data Mining
3.2 Einführung in die Klassifikation
3.3 Entscheidungsbäume

4 Wissenschaftliche Grundlagen
4.1 Charakteristik der vorherzusagenden Werte
4.2 Attribute des Systems
4.2.1 Atomare Attribute des mathematischen Modells
4.2.2 Komplementäre Attribute
4.3 Zusammenhangsanalysen
4.3.1 Spearman’s rho
4.3.2 Pearson’sche Produkt-Moment-Korrelation
4.3.3 Kombination von Alpha und Beta
4.3.4 Autokorrelationsanalyse
4.3.5 Kreuzkorrelationsanalyse in Bezug auf Alpha
4.3.6 Kreuzkorrelationsanalyse in Bezug auf Beta
4.3.7 Zusammenfassung der Voraussagefähigkeiten

5 Konstruktion von Lösungsstrategien
5.1 Entscheidungsbaumgestützte Strategien
5.1.1 Chi-squared Automatic Interaction Detection (CHAID)
5.1.2 Classification and Regression Trees (CRT)
5.2 Weitere Strategien
5.2.1 Balancing-Strategie
5.2.2 Random-Strategie
5.2.3 Transformed-CHAID Strategie

6 Evaluation der Strategien
6.1 Laufzeitverhalten
6.2 Lösungsqualität
6.3 Robustheit

7 Zusammenfassung der Ergebnisse

8 Literaturverzeichnis

Abbildungsverzeichnis

Abbildung 1: Modellhafte Darstellung eines Kfz-Verladeterminals

Abbildung 2: Beispiel für die simulierte Lage der Standorte

Abbildung 3: Aktivitätsdiagramm zur Vorgehensweise mittels

Abbildung 4: Zustandsdiagramm zur Periodeneinteilung

Abbildung 5: Zustandsdiagramm zur Lagerzuordnung

Abbildung 6: Klassendiagramm der Simulation aus Programmsicht

Abbildung 7: Simulation aus Datensicht

Abbildung 8: Lernphase der Klassifikation

Abbildung 9: Anwendung des gelernten Models

Abbildung 10: Beispiel für einen Entscheidungsbaum

Abbildung 11: Histogramm für α(t)

Abbildung 12: Histogramm für β(t)

Abbildung 13: Autokorrelation für „Alpha“

Abbildung 14: Autokorrelation für „Beta“

Abbildung 15: Entscheidungsbaum für Alpha erzeugt mit CHAID

Abbildung 16: Entscheidungsbaum für Beta erzeugt mit CHAID

Abbildung 17: Entscheidungsbaum für Alpha erzeugt mit CRT

Abbildung 18: Entscheidungsbaum für Beta erzeugt mit CRT

Abbildung 19: Lösungen für die Normalsituation

Abbildung 20: Lösungen bei Variation der angestrebten Systemauslastung

Abbildung 22: Lösungen bei Variation der Vorgangsgröße

Abbildung 23: Lösungen bei Variation der Vorgangsgröße

Abbildung 24: Lösungen bei Erhöhung der angestrebten Verweildauer

Abbildung 25: Lösungen bei Erhöhung der Zeitfenstergröße

Abbildung 26: Lösungen bei Verringerung der Zeitfenstergröße

Abbildung 27: Lösungen bei höherer Anzahl interner Zwischenspeicher

Abbildung 28: Lösungen bei höherer Anzahl externer Verladeorte

Abbildung 29: Lösungen bei Verringerung der Arealgröße

Abbildung 30: Lösungen bei verkleinertem Areal

Abbildung 31: Lösungen bei vergrößertem Areal

Abbildung 32: Lösungen bei Variation der Zeitfenstergröße bei 80%

Abbildung 33: Lösungen bei Variation der Zeitfenstergröße bei 90%

Abbildung 34: Lösungen bei Variation der Zeitfenstergröße bei 100%

Abbildung 35: Normierter Durchschnitt aller bisherigen Lösungen

Tabellenverzeichnis

Tabelle 1: Beispielhafte Werte für α(t) und β(t)

Tabelle 2: Univariate Statistiken für α(t) und β(t)

Tabelle 3: Atomare Attribute des mathematischen Modells

Tabelle 4: Komplementäre Attribute

Tabelle 5: Korrelationsmaße in Bezug zu Alpha

Tabelle 6: Korrelationsmaße in Bezug zu Beta

Tabelle 7: Pearson'sche Produkt-Moment-Korrelation

Tabelle 8: Kreuzkorrelationen in Bezug auf Alpha

Tabelle 9: Kreuzkorrelationen in Bezug auf Beta

Tabelle 10: Interessante Abhängigkeiten von Alpha

Tabelle 11: Interessante Abhängigkeiten von Beta

Tabelle 12: Vergleich des Laufzeitverhaltens

Tabelle 13: Anzahl erfolgreicher Lösungsversuche

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1 Einleitung

Entscheidungsbäume erscheinen im Umfeld des Data Mining aus verschiedenen Gründen als Mittel zur Klassifikation besonders attraktiv. Die Konstruktion von Entscheidungsbäumen erfordert keinerlei Eingabeparameter seitens des Benutzers. Das erzeugte Klassifikationsmodell lässt sich intuitiv nachvollziehen. Entscheidungsbäume lassen sich im Vergleich mit anderen Methoden in relativ kurzer Zeit erzeugen. Die Genauigkeit ihrer Modelle ist mit anderen Klassifikationsmodellen vergleichbar oder überlegen.

Diese Arbeit stellt ein Entscheidungsbaum­verfahren vor, das nicht in einer Data Mining Umgebung sondern stattdessen auf ein logistisches Optimierungsproblem angewendet wird. Für eine solche Einsatzform von Entscheidungsbäumen existieren bisher noch keine dokumentierten Untersuchungen.

Die Anwendbarkeit von Entscheidungsbäumen wird anhand des Beispiels eines Kfz-Verladeterminals gezeigt: Die Distribution von Fahrzeugen im Automobilgewerbe erfolgt mit Hilfe unterschiedli­cher Transportmittel. Während Fahrzeuge mit großen Frachtern auf dem Seeweg in alle Welt verschifft werden können, müssen sie anschließend zum Weitertransport in das Lan­desinnere in einem Umschlaghafen umgeladen werden.

Im Rahmen des Umschlagvorgangs bewegen Fahrer die Fahrzeuge von den Frachtschiffen zu Zwischenlagern, von wo aus sie später zum Transport ins Hinterland auf LKWs oder Züge gefahren werden. Kosten entstehen dabei haupt­sächlich durch Fahrerlöhne sowie durch mögliche Ladeschäden im Hafen, die vorwiegend durch Schwankungen im Verkehrsaufkommen beim Verladeprozess auf­treten. Bei der Planung und Organisation des Umschlags ist deshalb eine möglichst ge­ringe Gesamtzahl an Fahrern sowie eine Nivellierung des Personalbedarfs über die Zeit anzustreben.

Eine grundlegende Arbeit von Professor Dr. Mattfeld^[1] bildet die Problemstellung in ein mehrperiodiges ma­thematisches Modell ab und bestimmt den Personalbedarf durch Anwendung einer pa­rametrisierbaren Lösungsstrategie. Die Ermittlung von Strategieparametern erfolgte hier unter anderem durch einen zeitaufwändigen Evolutionären Algorithmus. Die Verwendung hat den Nachteil, dass eine Bestimmung optimaler Startwerte notwendig ist.

Diese Arbeit stellt ein Entscheidungsbaum­verfahren vor, das die Pa­rameterwahl zeiteffizient auf der Basis historischer Umschlagsdaten durchführt. Der Einsatz von Entscheidungsbäumen benötigt keinerlei Startwerte. Die Problematik der Wahl optimaler Startwerte, mit der Evolutionäre Algorithmen behaftet sind, lässt sich somit umgehen. Im Verlauf dieser Arbeit soll untersucht werden, ob der Einsatz von Entscheidungsbaumverfahren zur Lösung der Problemstellung möglich ist.

Die Erörterung des Ausgangsproblems und bisheriger Lösungsansätze soll ein Verständnis der Problemstellung fördern. Es schließt sich die Präsentation eines Entscheidungsbaumverfahrens als alternativer Ansatz zur Problemlösung an. Vorher muss auf die Grundlagen von Entscheidungsbäumen eingegangen werden.

Die Voraussagefähigkeiten durch Entscheidungsbäume werden in Bezug auf die Problemstellung analysiert. Diese Untersuchung soll den Einsatz von Entscheidungsbäumen als Lösungsverfahren rechtfertigen.

Es schließt sich die Beschreibung eines Verfahrens mittels Entscheidungsbäumen an. Eine Evaluation des Laufzeitverhaltens, der Lösungsqualität und der Robustheit vergleicht den vorgestellten Lösungsansatz mit den bisherigen Ansätzen. Diese Untersuchung soll dazu dienen, die Qualität des vorgestellten Verfahrens zu beurteilen und Ansatzpunkte für weitere Lösungsverfahren zu eröffnen.

2 Problemschilderung

In Anlehnung an die Arbeit von Prof. Dr. Mattfeld^[2] erfolgt eine Beschreibung des Kfz-Umschlags an einem Verladeterminal. Dazu wird eine mathematische Modellierung des Verladeterminals vorgestellt, die eine zu lösende Problemstellung beinhaltet. Im Anschluss daran folgt eine Erläuterung bisheriger Ansätze zur Problemlösung.

2.1 Mathematische Modellierung des Problems

Zur Modellierung wird ein Lagerhaltungssystem mit einzuplanenden Vorgängen formuliert. Anschließend werden einzuhaltende Restriktionen hergeleitet und in die Modellierung integriert, wie Zeitvorgaben zur Durchführung der Vorgänge und Kapazitätsbetrachtungen bezüglich Lagerplatz und Personal. Unter diesen Nebenbedingungen folgen die Herleitung der Zielfunktion und schließlich die umfassende Modellformulierung.

2.1.1 Lagerhaltungssystem

Der zu beschreibende Kfz-Umschlag an einem Verladeterminal beinhaltet ein Lagerhaltungssystem mit Zwischenspeichern und Verladeorten. Ein Zwischenspeicher bietet die Möglichkeit, Fahrzeuge vorübergehend abzustellen und lässt sich mit einem Parkplatz vergleichen. Bei einem Verladeort handelt es sich um einen Punkt, an dem neue Fahrzeuge in dem System eintreffen oder es verlassen, beispielsweise eine Verladerampe für Schiffe, Züge oder Lastkraftwagen.

Sämtliche Zwischenspeicher und Verladeorte innerhalb eines Systems bilden zusammen die Menge der Systemstandorte. Jeder Standort ist durch eine Distanz zu den übrigen Standorten gekennzeichnet. Weiterhin besitzt jeder Standort einen Anfangslagerbestand und eine nicht zu überschreitende Lagerkapazität.

Die modellhafte Darstellung (vgl. Abbildung 1) eines Verladeterminals mit Zwischenspeichern und Verladeorten soll zur Veranschaulichung dienen. Auf der linken Seite sind zwei Fähren dargestellt, die am Verladeterminal eintreffen und gelöscht werden. Die geladenen Kraftfahrzeuge werden vorübergehend in Zwischenspeichern innerhalb des Systems untergebracht. Auf der rechten Seite des Terminals befindet sich ein Lastkraftwagen, der einige der Fahrzeuge aus den Zwischenspeichern als Ladung aufnimmt und weitertransportiert.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Modellhafte Darstellung eines Kfz-Verladeterminals

2.1.2 Vorgänge

Zur Abwicklung von ankommenden und abgehenden Kfz-Ladungen an Standorten innerhalb des beschriebenen Lagerhaltungssystems lassen sich (Verlade-)Vorgänge modellieren. Diese Vorgänge werden auch engl. Tasks genannt.

Bei einem Vorgang unterscheidet man zwischen drei Typen: Ein Einlagerungsvorgang stellt die Überführung einer ankommenden Ladung in ein Zwischenlager dar. Dagegen stellt ein Auslagerungsvorgang die Überführung einer Ladung aus einem Zwischenspeicher zu einem Verladeort dar. Ein Umladungsvorgang stellt die Überführung einer Ladung von einem Verladeort zu einem anderen Verladeort ohne Zwischenspeicherung dar.

Vorstellbar ist ein (Verlade-)Vorgang wie folgt: Einem Einlagerungsvorgang entspricht es, wenn Fahrzeuge von einem ankommenden Schiff auf einen Parkplatz als Zwischenspeicher gebracht werden. Das Verladen der Fahrzeuge vom Parkplatz auf einen Zug entspricht einem Auslagerungsvorgang. Einen Umladungsvorgang stellt die direkte Verladung von Fahrzeugen vom Schiff auf den Zug dar, ohne vorübergehendes anderwärtiges Abstellen der Fahrzeuge.

Jeder Vorgang kennzeichnet sich durch folgende Größen: Volumen, Quelle, Ziel und Zeitpunkt. Das Volumen gibt die Anzahl an Fahrzeugen an, aus der eine Kfz-Ladung besteht. Die Quelle und das Ziel stellen die Standorte dar, zwischen denen eine Kfz-Ladung bewegt wird. Bei Quelle und Ziel einer Ladung könnte es sich sowohl um Zwischenlager als auch um Verladeorte handeln. Der Zeitpunkt gibt an, wann der Vorgang innerhalb eines bestimmten Betrachtungszeitraumes abgewickelt wird. Der Betrachtungszeitraum ist in gleichmäßige Perioden unterteilt. Die Abwicklung eines Vorganges muss nicht in einer bestimmten Periode erfolgen. Sondern es wird zu jedem Vorgang ein Zeitfenster gewährt, innerhalb dessen er durchgeführt werden muss.

Ist eine neue Ladung eingetroffen, wird sie ausgehend von ihrem Ankunftsort eingelagert. Bei einer Einlagerung von Fahrzeugen ist ein gegebener Quell-Verladeort zu beachten. Das Zwischenlager kann frei gewählt werden. Beachtet werden muss, dass es gleichzeitig die Quelle des korrespondierenden Auslagerungsvorganges darstellt. Das Ziel einer Auslagerung ist der vorgegebene Ziel-Verladeort. Eine direkte Umladung erfolgt von einem gegebenen Quell-Verladeort zu einem gegebenen Ziel-Verladeort ohne Zwischenspeicherung. Somit bestehen keine Wahlmöglichkeiten.

2.1.3 Zielsetzung der Betrachtung

Das mathematische Problem ist so modelliert, das es sich innerhalb eines bestimmten Betrachtungszeitraumes mit diskreten Zeitpunkten befindet. Dieser Zeitraum wird in gleichmäßige Perioden eingeteilt.

Ein zu betrachtendes Lagerhaltungssystem besteht aus Standorten, zwischen denen innerhalb eines Zeitrahmens unterschiedliche Verladevorgänge ablaufen.

Die Durchführung eines (Verlade-)Vorgangs mit einem gegebenen Volumen an Fahrzeugen erfordert einen definierten Personalaufwand. Die benötigte Menge des Personalaufwands hängt von den Eigenschaften des Vorganges ab. So hängt der Personaleinsatz ab von der Distanz zwischen dem Quell- und Zielstandort und von der Anzahl der Fahrzeuge, die zwischen den beiden Standorten bewegt werden.

Das formulierte Modell hat eine Minimierung der Summe der Arbeitsmenge über alle Vorgänge und Perioden zum Ziel, um die Arbeitskosten möglichst gering zu halten. Zusätzliche Kosten entstehen durch mögliche Verkehrsunfälle im Verladeterminal, die vorwiegend durch Schwankungen im Verkehrsaufkommen beim Verladeprozess auf­treten. Deshalb besteht ein weiteres Ziel darin, den Personalaufwand möglichst gleichmäßig über alle Perioden des Betrachtungszeitraumes zu verteilen. Ziel ist sowohl eine Minimierung als auch eine Nivellierung der benötigten Arbeitsmenge innerhalb eines Betrachtungszeitraumes. Diese Zielsetzung wird durch eine Zielfunktion definiert, die eine Minimierung und gleichzeitig eine Nivellierung berücksichtigt. Die Ergebnisse der Zielfunktion werden als Zielfunktionswerte (ZF-Werte) bezeichnet.

Für das vorliegende Problem soll nach Möglichkeit eine optimale Lösung gefunden werden, es liegt ein Optimierungsproblem vor. Gesucht wird eine Problemlösung mit minimalem Zielfunktionswert. Variiert werden die Parameter oder Variablen der Zielfunktion.

Bei einer zweidimensionalen Optimierungsaufgabe kann man sich die Zielfunktion räumlich vorstellen, indem die Parameter die Längen- und Tiefenachse aufspannen^[3]. Die Höhe ist dann der Zielfunktionswert. Im Allgemeinen entsteht so ein Gebirge mit Bergen und Tälern. Wenn die Zielfunktion ein Gebirge darstellt, ist das Optimierungsproblem damit gleichzusetzen, in diesem Gebirge das tiefste Tal zu finden. Der Aufwand zur Lösung der Aufgabe hängt entscheidend von der Form des Gebirges ab. Besteht die Optimierungsaufgabe darin, von einem gegebenen Punkt im Gebirge aus das nächste relative Minimum oder Maximum in der Nachbarschaft zu finden, handelt es sich um eine lokale Optimierung. Dagegen ermittelt die globale Optimierung das absolute Minimum oder Maximum im gesamten Gebirge.

2.1.4 Generierung von lösbaren Probleminstanzen

Es folgt die Darstellung von Mattfelds Vorgehensweise zur Erzeugung lösbarer Probleminstanzen^[4]. Bei diesen Probleminstanzen handelt es sich um Umschlagsszenarien, die die in Abschnitt 2.1 dargestellte mathematische Modellierung konkretisieren. Zur Erzeugung einer lösbaren Probleminstanz werden Angaben zur Lage aller Standorte, Zeit, Ort und Größe sämtlicher ankommenden und abgehenden Ladungen innerhalb eines Betrachtungszeitraumes benötigt.

Eine Probleminstanz wird erzeugt, in dem im ersten Schritt die Standorte eines Lagerhaltungssystems mittels einer zufälligen Verteilung der Standorte innerhalb eines gewissen Intervalls (z.B. [-3,3]) bestimmt werden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Beispiel für die simulierte Lage der Standorte.
Dabei gilt: Zwischenspeicher sind schwarz und Verladeorte sind grau

Abbildung 2 verdeutlicht, wie eine zufällige Anordnung von Zwischenlagern (schwarz) und Verladeorten (grau) innerhalb der Systemgrenzen von [-3,3] aussehen könnte.

Der zweite Schritt versieht sämtliche Standorte innerhalb des Systems anhand zufälliger Werte mit einer maximalen Lagerkapazität und einem Anfangslagerbestand an Kraftfahrzeugen.

Der dritte Schritt erzeugt Vorgänge im Zeitablauf. Es werden für jeden Vorgang dessen Größe, dessen Herkunftsort (Verladeort), dessen Bestimmungsort (Verladeort), und ein Zeitfenster für dessen Durchführungszeitpunkt festgelegt.

So entsteht schließlich eine Probleminstanz, die sich über einen bestimmten Betrachtungsraum erstreckt. Diese Probleminstanz beinhaltet ein Lagerhaltungssystem mit maximalen Kapazitäten und Anfangsbeständen. Zu dieser Probleminstanz existiert ein Szenario an Verladevorgängen, deren Durchführung innerhalb bestimmter Zeitfenster einzuplanen ist. Somit entsteht die Simulation des Kfz-Umschlages an einem Verladeterminal. Damit die Simulation einen hinreichend allgemeinen Fall darstellt, erfolgt die Bestimmung aller Parameter durch empirisch gestützte Wahrscheinlichkeitsverteilungen.

2.2 Problemlösung

Es gilt, die zuvor erzeugten Probleminstanzen zu lösen. Alle Vorgänge einer Probleminstanz besitzen ein bestimmtes Zeitfenster, innerhalb derer der einzelne Vorgang durchgeführt werden muss. Gleichzeitig steht fest, um welche Anzahl von Fahrzeugen es sich bei einem Vorgang handelt.

Das Lösen einer Probleminstanz bedeutet, die Durchführung jedes Vorganges auf eine bestimmte Periode einzuplanen. Die Durchführung darf nur innerhalb eines vorgegebenen Zeitfensters geschehen. Zusätzlich gilt es für Einlagerungsvorgänge, einen geeigneten Zielort, d.h. ein Zwischenspeicher, zu bestimmen. Eine Problemlösung setzt sich aus der Bestimmung einer Vorgangsreihenfolge und einer Lagerzuordnung zusammen. Bei der Lösung einer Probleminstanz sind insbesondere Personalrestriktionen zu beachten. So kommt es nicht darauf an, eine gültige Lösung, sondern eine optimale Lösung gemäß Abschnitt 2.1.3 zu finden.

Die generierten Probleminstanzen lassen sich grundsätzlich auf zwei unterschiedliche Weisen lösen: exakt oder mittels einer Heuristik. Die exakte Lösung eines kombinatorischen Problems dieser Art resultiert schnell in einem unverhältnismäßigen Rechenaufwand. Auch wenn Methoden der kombinatorischen Optimierung im Bereich exakter Verfahren systematisch gute Ansätze liefern, reduziert sich die Komplexität des Problems unter Zuhilfenahme einer Heuristik.

2.2.1 Reduktion der Problemkomplexität

Dieser Abschnitt stellt eine zweistufige Heuristik von Mattfeld vor^[5]. Mit Hilfe dieser Heuristik reduziert sich die Komplexität des Problems, indem die Problemstellung in zwei Teilprobleme aufgeteilt und getrennt behandelt wird. In der ersten Stufe der Heuristik erfolgt die Verteilung der Vorgänge auf die Perioden, erst in der zweiten Stufe erfolgt anschließend eine Bestimmung der Lagerorte. Abbildung 3 stellt die beschriebene Vorgehensweise der zweistufigen Heuristik graphisch dar.

Zur Einplanung der Vorgänge in bestimmte Perioden wird ein Parameter α(t) є (0,1] und zur Lagerzuordnung ein Parameter β(t) є (0,1] verwendet. Diese beiden Parameter stellen Gewichte bei der Lösung der beiden Teilprobleme dar und sind abhängig vom Zeitverlauf. Mittels α(t) wird das erste Teilproblem gelöst und mittels β(t) die Lagerzuordnung bestimmt.

Man betrachte alle Vorgänge, die in einer bestimmten Periode zur Verfügung stehen. D.h. alle Vorgänge, in deren Zeitfenster eine bestimmte Periode t fällt, sollen analysiert werden. Diese Menge der zur Verfügung stehenden Vorgänge bezeichnet man auch als „Menge der möglichen Vorgänge“.

Das Gewicht α(t) bestimmt den Anteil an zur Verfügung stehenden Vorgängen, der in Periode t eingeplant wird. Ein großer Wert für α(t) bedeutet die Ausführung von fast allen Vorgängen in Periode t. Ein kleiner Wert zeigt an, dass die Durchführung der meisten Vorgänge erst in den nachfolgenden Perioden stattfindet. Somit gibt der Parameter α(t) indirekt vor, ob in einer Periode t Arbeitskraft möglichst eingespart wird oder ob in der Periode möglichst viel Arbeitskraft eingesetzt wird. Auf diese Weise gewährt der Parameter Alpha einen Spielraum für eine Nivellierung. Abbildung 4 stellt die Vorgehensweise bei der Periodeneinteilung mit Hilfe des Parameters Alpha in einem Zustandsdiagramm dar.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: Aktivitätsdiagramm zur Vorgehensweise mittels

einer zweistufigen Heuristik

Ein α(t) = 0,5 bedeutet, dass 50% aller in Periode t zur Verfügung stehenden Vorgänge verarbeitet werden. Bei den restlichen 50% dieser Vorgänge erfolgt eine Abwälzung auf nachfolgende Perioden. Ein α(t) mit dem Wert 0.5 stellt somit eine neutrale Gewichtung dar. Das bedeutet für die Periode t, dass die Alternative Arbeitskraft einzusparen genauso stark gewichtet ist, wie die Alternative möglichst viel Arbeitskraft einzusetzen.

Der Parameter β(t) dient als Gewichtung bei der Lagerzuordnung für Einlagerungsvorgänge. Zu jedem Einlagerungsvorgang existiert ein zugehöriger Auslagerungsvorgang. Bei der Wahl eines Zwischenspeichers als Ziel für einen Einlagerungsvorgang könnte ein Standort gewählt werden, der möglichst nah an der Quelle des Einlagerungsvorgangs liegt. Es könnte aber auch ein Standort gewählt werden, der möglichst nah am Ziel des entsprechenden Auslagerungsvorganges liegt. Der Parameter β(t) dient als Gewichtung bei der Lagerzuordnung und bestimmt, wo ein Zwischenspeicher zwischen Quell-Verladeort und Ziel-Verladeort liegen sollte.

Es besteht die Möglichkeit, bei der Einlagerung einen Zwischenspeicher zu wählen, der sich möglichst nah am Quell-Verladeort des Einlagerungsvorganges befindet. Somit fällt bei der Einlagerung ein recht geringer Arbeitsaufwand an. Bei der entsprechenden Auslagerung fällt ein umso höherer Arbeitsaufwand an. Genauso gibt es die Möglichkeit, bei der Einlagerung einen Zwischenspeicher zu wählen, der sich möglichst nah am Ziel-Verladeort des Auslagerungsvorganges befindet. Somit fällt bei der Einlagerung ein recht hoher Arbeitsaufwand an. Bei der entsprechenden Auslagerung fällt ein umso geringer Arbeitsaufwand an.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4: Zustandsdiagramm zur Periodeneinteilung

Somit dient der Parameter zur Angleichung des Arbeitsaufkommens, indem der Parameter steuert, ob in Periode t weit entfernte oder nahe liegende Standorte gewählt werden. Er gibt an, wie wichtig es ist, Arbeitszeit in Periode t im Hinblick auf Folgeperioden einzusparen. Ein Vorgang wird beispielsweise in t=1 eingelagert und in t=2 wieder ausgelagert. Die Parameter β(1) und β(2) geben an, wie wichtig es ist, Arbeitskraft in t=1 mit Hinblick auf t=2 einzusparen und umgekehrt. Auf diese Weise kontrolliert β(t), ob in einer Periode t nahe oder ferne Speicherorte präferiert werden.

Ein großes β(t) in der Einlagerungsperiode und ein kleines β(t) in der entsprechenden Auslagerungsperiode eines Vorganges bedeutet, dass in der Einlagerungsperiode ein nahes Ziel zu suchen ist, während bei der Auslagerung ein weiterer Weg zurückzulegen ist. Im umgekehrten Fall bedeutet ein kleines β(t) in der Einlagerungsperiode und ein großes β(t) in der entsprechenden Auslagerungsperiode, dass in der Auslagerungsperiode ein nahes Ziel zu wählen ist, während bei der Einlagerung ein weiterer Weg zurückzulegen ist. Abbildung 5 stellt die Lagerzuordnung graphisch dar.

Analog zu Alpha stellt ein β(t) = 0.5 eine neutrale Gewichtung dar. Der Arbeitsaufwand zum Zeitpunkt der Einlagerung ist genauso stark gewichtet, wie bei der Auslagerung.

Abbildung 6 gibt die beschriebene Simulation des Verladeterminals aus einer Programmsicht wieder. Das Programm besteht aus zwei Teilen. Ein Teil dient zur Erzeugung von Probleminstanzen und ein anderer zur Lösung der Probleminstanzen. Die Probleminstanzerzeugung setzt sich aus mehreren Klassen zusammen: einem Lagerhaltungssystem mit Standorten und einer Abfolge von Vorgängen. Der Teil zur Problemlösung bedient sich einer Klasse zur Vorgangseinplanung und einer Strategie, die die Parameter Alpha und Beta für ein Vorgangsszenario vorgibt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5: Zustandsdiagramm zur Lagerzuordnung

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6 : Klassendiagramm der Simulation aus Programmsicht

Abbildung 7 zeigt die Simulation aus einer Datensicht. Es werden die Beziehungen der verschiedenen Attribute der Simulation untereinander deutlich. So setzt sich ein Lagerhaltungssystem aus mehreren Standorten zusammen. Eine Lösungsheuristik wird auf ein bestehendes Lagerhaltungssystem angewendet und plant mehrere Vorgänge ein. Diese Sicht auf die Daten ist notwendig für das Verständnis der weiteren Vorgehensweise in dieser Arbeit.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 7: Simulation aus Datensicht

Mattfeld^[6] reduziert die Lösung der Probleminstanzen soweit, dass lediglich die oben vorgestellten Parameter α(t) є (0,1] und β(t) є (0,1] für jede Periode eines Betrachtungszeitraumes zu bestimmen sind. Zur Ermittlung dieser Parameter im Hinblick auf eine optimale Lösung liegen bisher drei verschiedene Strategien vor, die kurz erläutert werden sollen.

2.2.2 Greedy-Strategie

Mattfeld schlägt als Lösungsstrategie einen gierigen Algorithmus vor^[7], weil dieser sehr schnell ist und dabei gute Näherungslösungen erzielt. Eine geringe Auslastung der Zwischenspeicher innerhalb des Lagerhaltungssystems erlaubt die größtmögliche Wahlmöglichkeit bei der Lagerzuordnung. Bei dieser Strategie wird die Lagerauslastung der drei Vorgangstypen betrachtet. Der grundsätzlichen Vorgehensweise zur Reihenfolgenbestimmung liegt bei dieser Strategie folgendes Kalkül zugrunde:

1. Eine Umladung beeinflusst die Zwischenspeicher nicht, da sie keine Zwischenlagerung beinhaltet. Eine Umladung erfolgt so früh wie möglich.
2. Eine Auslagerung entlastet die Zwischenspeicher des Lagerhaltungssystems und ist somit einer Umladung vorzuziehen. Eine Auslagerung erfolgt ebenfalls so früh wie möglich.
3. Eine Einlagerung belastet die Zwischenspeicher des Lagerhaltungssystems und wird deshalb einer Umlagerung und einer Auslagerung nachgestellt. Eine Einlagerung erfolgt so spät wie möglich.

Die Lagerzuordnung geschieht nach folgendem Prinzip: Um den benötigten Personalaufwand so gering wie möglich zu halten, ist der Standort mit der kleinsten Entfernung zum Quell-Verladeort und zum Ziel-Verladeort als Zwischenspeicher zu wählen.

2.2.3 Balancing-Strategie

Eine Balancing-Strategie stellt Mattfeld als Alternative zur Greedy-Strategie vor^[8]. Bei dieser Strategie wird der Wert von α(t) so bestimmt, dass dieser von der durchschnittlichen Anzahl von Vorgängen abhängt, deren Durchführung in eine Nachfolgeperiode verschoben wurde.

Die Bestimmung von α(t) erfolgt durch eine Betrachtung der Anzahl zur Verfügung stehender Vorgänge. Gleichzeitig ist die Anzahl der durchschnittlich in die Nachfolgeperiode verschobenen Vorgänge zu berücksichtigen. Die Anzahl der durchschnittlich in die Nachfolgeperiode verschobenen Vorgänge wird von der Anzahl zur Verfügung stehender Vorgänge abgezogen. Der daraus resultierende Wert wird durch die Anzahl an zur Verfügung stehenden Vorgängen geteilt und ergibt α(t).

Der Parameter für die Lagerzuordnung β(t) ist bei dieser Strategie konstant auf β(t) = 1 festgelegt.^[9]

2.2.4 Adaptive-Strategie

Als eine weitere Alternative zur Greedy-Strategie existiert ein Evolutionärer Algorithmus (EA) als iterative stochastische Suchmethode^[10], die auf den Prinzipien der natürlichen Evolution basiert. Bei diesem Verfahren werden verschiedene Lösungen für das vorliegende Problem als eine Population von Lösungskandidaten betrachtet.

Die Evolution ist in der Lage, durch Manipulation des Erbgutes selbst komplexe Lebensformen und Organismen an ihre Umwelt- und Lebensbedingungen anzupassen^[11]. Sie löst damit ein sehr schwieriges Optimierungsproblem. Die erstaunlichste Eigenschaft der Evolution ist die relative Einfachheit ihrer Vorgehensweise und das Zusammenwirken der verschiedenen Steuerungsmechanismen. In einem einfachen Modell lässt sich der durchgeführte Suchprozess auf einfache Prinzipien zurückführen: Mutation, Rekombination und Selektion.

Die Mutation des Erbgutes ist ein ungerichteter Prozess, dessen Sinn in der Erzeugung von Alternativen und Varianten liegt. Aus Sicht der Optimierungstheorie kommt der Mutation die Aufgabe zu, lokale Optima zu überwinden. Sie sorgt dafür, dass die Population von Lösungskandidaten nicht frühzeitig gegen ein lokales Optimum konvergiert.

Die Rekombination (Crossover) der Erbinformation liegt hinsichtlich ihres Beitrages zur Zielfindung im Rahmen der Evolution zwischen Mutation und Selektion. Die Stellen, an denen ein Crossover zwischen homologen Chromosomen stattfindet, werden zufällig bestimmt. Die eigentliche Rekombination erfolgt aber nicht mehr zufällig. Nahe beieinander liegende und funktional verbundene Gene werden seltener getrennt als weiter auseinander liegende Gengruppen. Ein EA könnte auch ohne Rekombination auskommen, in bestimmten Fällen ist die Anwendung von Rekombination jedoch effizienter.

Die Selektion ist für die eigentliche Steuerung der Suchrichtung der Evolution zuständig. Sie bestimmt die Richtung, in der sich das Erbgut verändert, indem sie festlegt, welche Phänotypen sich stärker vermehren. Die Selektion wäre, wenn es keine Störungen gäbe, eine deterministische Komponente innerhalb der Evolution. In der Natur wird die Selektion immer wieder durch meist zufällige Ereignisse gestört. Auch die am besten an ihre Umgebung angepassten Individuen können durch ein Unglück sterben, bevor sie Nachkommen zeugen. Damit würde die genetische Information, die ein Optimum darstellt, verloren gehen.

Ein typischer EA umfasst die folgenden Schritte:

1. Initialisierung: Erzeugen einer ausreichend großen Menge unterschiedlicher "Individuen". Diese Menge stellt eine Population von Lösungskandidaten zur Problemlösung dar.
2. Evaluation: Für jeden einzelnen Lösungskandidaten aus der Population wird anhand einer Zielfunktion (auch Fitness-Funktion genannt) ein Wert bestimmt.
3. Selektion: Zufällige Auswahl von Lösungskandidaten aus der vorhandenen Lösungskandidatenmenge. Dabei werden Lösungskandidaten mit besseren Zielfunktionswerten mit einer höheren Wahrscheinlichkeit ausgewählt.
4. Rekombination: die Genome verschiedener Individuen werden gemischt und aus den neuen Parametern eine neue Generation von Individuen erzeugt (Vermehrung)
5. Mutation: Zufällige Veränderung der Wertekombinationen der Individuen der neuen Generation.
6. Nach einem bestimmten Verfahren wird die Menge neuer Individuen aus der Menge alter Individuen und der Menge mutierter Nachfolger der Gewinner der Menge alter Individuen gebildet. Das Verfahren wird anschließend ab Schritt 2 wiederholt, oder nach einem Abbruchkriterium beendet und der beste verfügbare Lösungskandidat als Lösung definiert.

Bei der Anwendung auf eine Probleminstanz bestimmt der EA Werte für die Parameter α(t) und β(t). Mit diesen Werten wird die Probleminstanz gelöst und aus der Problemlösung ein Zielfunktionswert (siehe Abschnitt 2.1.3) ermittelt. In zahlreichen Iterationen werden die Werte für α(t) und β(t) vom EA durch Mutation, Rekombination und Selektion immer wieder variiert, bis schließlich eine möglichst gute Lösung vorliegt. Nach zahlreichen Iterationen liegt eine mittels EA optimierte Lösung vor.

Problematisch bei der Verwendung eines EA ist, dass er einige Startparameter erfordert. Beispielsweise ist die Festlegung einer Mutationsrate (hoch oder niedrig), einer Populationsgröße (groß oder klein) und eines Startwertes für einen Zufallsgenerator zwingend erforderlich. Die Mutationsrate bestimmt, wie stark Lösungskandidaten in der Mutationsphase Veränderungen unterliegen sollen. Zur Mutation der Lösungskandidaten werden anhand eines Zufallgenerators erzeugte Werte eingesetzt. Die Populationsgröße bestimmt die Anzahl an zu betrachtenden Lösungskandidaten.

Die Qualität der Lösung, die mit Hilfe des EA bestimmt wird, hängt sehr stark von dessen Anfangsparametern ab. Diese Anfangsparameter muss ein versierter Benutzer bestimmen. Das bedeutet, dass der EA zwar dabei hilft, eine optimale Lösung für eine Probleminstanz zu finden. Das eigentliche Problem verlagert sich auf die Bestimmung möglichst guter Startwerte für den EA.

An dieser Stelle kommen die Entscheidungsbäume als Technik zur vorhersagenden Modellierung zum Einsatz. Mit Hilfe von Entscheidungsbäumen wird in den folgenden Abschnitten eine weitere Lösungsstrategie entwickelt. Der Vorteil bei der Verwendung von Entscheidungsbäumen gegenüber einem EA ist, dass bei Entscheidungsbäumen keinerlei Startparameter erforderlich sind. Die Qualität der so erzeugten Lösungen ist unabhängig von der Wahl geeigneter Startparameterwahl. Der folgende Abschnitt vermittelt Grundlagen für das Verständnis von Entscheidungsbäumen.

3 Grundlagen der Entscheidungsbäume

Entscheidungsbäume werden als Technik zur Klassifikation im Data Mining verwendet. Deshalb folgt eine thematische Einordnung dieser Arbeit im Rahmen des Data Mining. Daran anschließend wird eine Einführung in die Klassifikation gegeben. Abschließend erfolgt eine Vorstellung von Entscheidungsbäumen als Technik zur Klassifikation.

3.1 Thematische Einordnung im Data Mining

Es existiert eine Vielzahl von Applikationen, in denen riesige Datenmengen anfallen, beispielsweise Daten von Scannerkassen. In diesen Daten können Informationen und Muster verborgen liegen, deren Kenntnis potentiell nützlich seien könnte. Rapide anwachsenden Datenmengen werden schnell unüberschaubar. Das Data Mining ist eine Wissenschaft^[12], die sich die Extraktion von nicht-trivialen, impliziten, zuvor unbekannten und potentiell nützlichen Informationen oder Mustern aus großen Datensätzen zur Aufgabe gemacht hat.

Das Data Mining selbst gliedert sich in fünf unterschiedliche Aufgabenbereiche^[13]:

1. Explorative Datenanalyse (EDA),
2. Mustererkennung,
3. Inhaltserkennung,
4. Beschreibende Modellierung und
5. Vorhersagende Modellierung.

Die Explorative Datenanalyse hat zur Aufgabe, die Daten zu durchforschen, ohne dass eine konkrete Idee vorliegt, wonach eigentlich gesucht wird. Ziel einer Mustererkennung ist das Entdecken von typischen oder atypischen Mustern in den Datensätzen. Die Inhaltserkennung spürt anhand eines vorgegebenen Musters ähnliche Muster in den Datensätzen auf. Das Ziel der beschreibenden Modellierung ist, eine Darstellung für die vorliegenden Datensätze zu finden. Dagegen ist Aufgabe der Vorhersagenden Modellierung, auf den in den Datensätzen vorliegenden Attributen basierend den Wert eines weiteren Attributes vorherzusagen.

Zur Vorhersagenden Modellierung stehen unterschiedliche Methoden zur Verfügung, beispielsweise Klassifikation oder Regression. Die Erzeugung von Entscheidungsbäumen dient zur Klassifikation. In der Vergangenheit wurden viele unterschiedliche Klassifikationsmodelle in der Literatur vorgeschlagen^[14]. Darunter befinden sich Entscheidungsbäume, lineare Regression, Nachbarschaftssuche, Regelinduktion, Künstliche Neuronale Netze, Fuzzy set theory und Bayes-Klassifikation. Entscheidungsbäume sind in der Data Mining Umgebung besonders attraktiv^[15]. Das erzeugte Klassifikationsmodell ist aufgrund seiner Repräsentation intuitiv nachvollziehbar^[16]. Zur Konstruktion von Entscheidungsbäumen werden keinerlei Eingabeparameter vom Benutzer benötigt. Entscheidungsbäume können, verglichen mit anderen Methoden, in relativ kurzer Zeit erzeugt werden. Die Genauigkeit der durch Entscheidungsbäume erstellten Modelle ist vergleichbar oder sogar besser als die anderer Klassifikationsmodelle^[17].

Diese Arbeit stellt die Anwendung eines Entscheidungsbaumverfahrens auf ein logistisches Optimierungsproblem am Beispiel des Kfz-Umschlags an einem Verladeterminal vor.

3.2 Einführung in die Klassifikation

Der Prozess der Klassifikation besteht in der Regel aus zwei Schritten^[18].

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 8: Lernphase der Klassifikation

Der erste Schritt ist die Lernphase oder Trainingsphase, dargestellt in Abbildung 8. In der Lernphase wird aus einem vorgegebenen Datensatz ein Model erzeugt, das die Daten innerhalb dieses Datensatzes beschreibt. Es wird dabei angenommen, dass jedes Tupel des Datensatzes einer bestimmten Klasse angehört. Ein Tupel bezeichnet eine Zusammenstellung von Objekten. Die Klassenzugehörigkeit wird durch ein bestimmtes Attribut, dem „Class-Label“, bestimmt. Die Tupel, die analysiert werden um das Model zu konstruieren, bilden den Trainingsdatensatz. Da für jedes Tupel des Trainingsdatensatzes ein Class-Label zur Verfügung steht, ist dieser erste Schritt als überwachtes Lernen bekannt. Im Gegensatz dazu ist beim unüberwachten Lernen das Class-Label unbekannt.

Typischerweise lässt sich ein gelerntes Model in Form von Klassifikationsregeln, Entscheidungsbäumen oder mathematischen Formeln präsentieren.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 9 : Anwendung des gelernten Models

Der zweite Schritt ist die Anwendung des Models zur Klassifikation, dargestellt in Abbildung 9. Die Vorhersagegenauigkeit des Models wird überprüft. Bei der Holdout-Methode wird nur ein Teil aller Tupel eines vorliegenden Datensatzes als Trainingsdatensatz verwendet. Die restlichen Tupel werden dazu verwendet, die Vorhersagegenauigkeit des Models abzuschätzen. Dabei wird für jedes dieser restlichen Tupel das bekannte Class-Label mit der vom Model vorhergesagten Klassenzugehörigkeit verglichen. Ganz wichtig für eine erfolgreiche Klassifikation ist bei der Anwendung der Holdout-Methode, dass keine statistische Abhängigkeit zwischen Trainingsdatensatz und den restlichen Daten besteht.

Sobald das Model als akzeptabel eingeschätzt wird, kann es anschließend zur Klassifikation von zukünftigen Tupeln eingesetzt, deren Klassenzugehörigkeit, d.h. deren Class-Label, unbekannt ist.

3.3 Entscheidungsbäume

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 10: Beispiel für einen Entscheidungsbaum

Ein Entscheidungsbaum^[19] ist ein gerichteter, zyklenfreier Graph mit einer baumartigen Struktur, die aus einer Wurzel, Kanten, Knoten und Blättern besteht. Er beginnt von der Wurzel aus mit einem Stamm, an dessen Ende sich eine Verzweigung (Knoten) befindet, die in mehrere verzweigte Äste (Kanten) führt. Jeder Endpunkt (Blatt) des Baums ist durch einen eindeutigen Weg erreichbar. Jeder Knoten kennzeichnet dabei den Test für ein Attribut, jede Kante kennzeichnet das Ergebnis eines solchen Testes und jedes Blatt repräsentiert eine Klasse. Abbildung 10 zeigt einen typischen Entscheidungsbaum. Er repräsentiert eine beispielhafte Klassifikation für einen Computerkauf. Anhand dieses Modells lässt sich vorhersagen, ob ein neuer Kunde einen Computer kaufen wird oder nicht. Interne Knoten des Baumes stellen dabei die Tests für ein Attribut dar. Blätter zeigen die jeweilige Klassenzugehörigkeit an.

Um einen unbekannten Kunden zu klassifizieren, werden Attribute des Kunden (beispielsweise Alter, Geschlecht, Kreditwürdigkeit) gemäß des Entscheidungsbaumes getestet. Dabei wird von der Wurzel des Baumes ausgegangen. In dem Beispiel würde als erstes das Alter des Neukunden erfragt werden. Anschließend würde entsprechend der Antwort solange dem Pfad des Baumes gefolgt werden, bis ein Blatt erreicht ist. Das gefundene Blatt könnte dann die Klassenzugehörigkeit des zu klassifizierenden Neukunden voraussagen.

4 Wissenschaftliche Grundlagen

Mit Hilfe von Entscheidungsbäumen soll eine weitere Strategie entwickelt werden, die das Problem der Startparameter umgeht. Von den bisher vorhandenen Strategien hat sich der EA als die beste herausgestellt^[20]. Die vom EA gewählten Werte für Alpha bzw. Beta werden aufgezeichnet. Mit Hilfe eines Entscheidungsbaumes wird dann auf der Basis dieser historischen Daten in einer neuen Situation ein Wert für Alpha bzw. Beta vorhergesagt.

In diesem Abschnitt wird auf die wissenschaftlichen Grundlagen für den Einsatz von Entscheidungsbäumen zur Problemlösung eingegangen. Dazu erfolgt die Charakterisierung der von einem EA bestimmten Werte der Parameter Alpha und Beta, um ein Verständnis für die vorherzusagenden Werte zu vermitteln. Der Vorhersage müssen Attribute zugrunde liegen, die die Zustände des mathematischen Modells widerspiegeln. Es schließt sich eine Diskussion der zur Verfügung stehenden Attribute oder Systemzustände aus der Modellierung des Kfz-Terminals an. Weiterhin werden die Voraussagefähigkeiten durch Entscheidungsbäume in Bezug auf die Problemstellung analysiert. Diese Untersuchung soll den Einsatz von Entscheidungsbäumen als Lösungsverfahren rechtfertigen.

4.1 Charakteristik der vorherzusagenden Werte

Die von einem EA bestimmten Werte der Parameter Alpha und Beta sollen genau charakterisiert werden. Eine Charakterisierung ist notwendig, da die Wahl einer geeigneten Vorgehensweise zur Entscheidungsbaumerzeugung besonders von den Eigenschaften der vorherzusagenden Werte abhängig ist (vgl. Kapitel 0).

Zur vorgestellten Generierung von Probleminstanzen existiert eine Implementierung von Mattfeld in der Programmiersprache C++. Diese Implementierung beinhaltet auch die drei in Kapitel 2.2 vorgestellten Heuristiken zur Lösung der Probleminstanzen. Die Implementierung wird mit den Startparametern versehen, die auch Mattfeld verwendet^[21], um sicher zu stellen, dass möglichst realistische Problemsituationen in der Simulation betrachtet werden. Aus den von der Implementierung erzeugten Lösungen lassen sich die Werte für α(t) und β(t) entnehmen, die mittels EA bestimmt wurden.

Tabelle 1 liefert eine beispielhafte Auflistung von Werten für Alpha und Beta in Abhängigkeit von einer Periode t, die mittels eines EA für eine bestimmte Probleminstanz bestimmt wurden. Diese Auflistung soll eine konkrete Vorstellung für die Werte von Alpha und Beta vermitteln. Es wird ein Betrachtungszeitraum von zehn Perioden zugrunde gelegt.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 1: Beispielhafte Werte für α(t) und β(t)

Aus der Implementierung werden 100.000 verschiedene durch den EA bestimmte Werte für Alpha bzw. Beta entnommen, um sie zu analysieren.
Tabelle 2 fasst die charakteristischen Eigenschaften der Werte von α(t) und β(t) zusammen.

Abbildung in dieser Leseprobe nicht enthalten

Sowohl für α(t) als auch für β(t) liegen die Werte im Bereich von etwa 0,3 bis 0,7 mit einem Mittelwert von etwa 0,5. Ein exakter Wert von 0,5 stellt sowohl für α(t) als auch für β(t) eine neutrale Gewichtung dar (siehe Kapitel 2.2.1).

Um Aussagen über die Wahrscheinlichkeitsverteilungen der Werte von α(t) bzw. β(t) zu treffen, lassen sich die zwei folgenden Histogramme heranziehen, eines für die Werte von α(t) und eines für die Werte von β(t):

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 11: Histogramm für α(t)

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 12 : Histogramm für β(t)

Anhand der beiden Histogramme in Abbildung 11 bzw. Abbildung 12 lassen sich einige Aussagen über die Werte von α(t) und β(t) ableiten. Zum einen liegt bei beiden eine Normalverteilung vor, da beide Histogramme den Verlauf einer Gaußschen Glockenkurve beschreiben. Folglich stellt das neutrale Gewicht von 0,5 den am häufigsten gewählten Wert dar.

Gleichzeitig ist eine Ähnlichkeit bei der Verteilung der Werte von α(t) und β(t) erkennbar, was auf viele gemeinsame Eigenschaften schließen lässt. Für die Wahl einer Vorgehensweise (vgl. Kapitel 0) ist diese Erkenntnis von Vorteil, da keine gesonderten Eigenschaften von α(t) bzw. β(t) berücksichtigt werden müssen.

4.2 Attribute des Systems

Für die Vorhersage von α(t) und β(t) mittels eines Entscheidungsbaums werden Attribute benötigt, die die Zustände des zugrunde liegenden mathematischen Modells widerspiegeln. Aus dem von Mattfeld formulierten Modell gehen einige Attribute direkt hervor. Diese werden im nächsten Abschnitt als „atomare“ Attribute vorgestellt. Daneben bietet es sich an, aus einer Kombination dieser Attribute so genannte „komplementäre“ Attribute (vgl. nachfolgendes Kapitel) zu erstellen.

4.2.1 Atomare Attribute des mathematischen Modells

Für die Vorhersage von α(t) und β(t) mittels eines Entscheidungsbaums werden Attribute benötigt, die die Zustände des zugrunde liegenden mathematischen Modells darstellen.

Tabelle 3 listet sämtliche Attribute des mathematischen Modells auf, so genannte atomare Attribute. Sie listet das mathematische Symbol auf, das in der Modellformulierung verwendet wird, dessen Bedeutung und Wertzuweisungszeitpunkt. Insbesondere der Zeitpunkt der Wertzuweisung ist bedeutend, da anhand dessen die Attribute kategorisiert werden können.

Abbildung in dieser Leseprobe nicht enthalten

Anhand des Zeitpunktes der Wertzuweisung lassen sich die aufgelisteten Attribute in drei verschiedene Kategorien einteilen:

1. Feste oder indirekte Vorgabe der Werte bei Programmaufruf. Der Wert bleibt über alle Perioden des Betrachtungszeitraums konstant.
2. Wertzuweisung zu Periodenbeginn. Der Wert bleibt innerhalb einer Periode konstant.
3. Wertzuweisung für jeden Vorgang individuell. Die Werte variieren innerhalb einer Periode.

Die Werte sämtlicher Attribute der ersten Kategorie werden in der Simulation vor oder bei der Generierung einer Probleminstanz festgelegt und behalten während der Problemlösung ihren Wert konstant bei. Da die Werte von α(t) und β(t) in Abhängigkeit von einer Periode t vorhergesagt werden sollen, erhalten vor allem die veränderlichen Zustände des Lagerhaltungssystems während der Problemlösung Bedeutung. Die Attribute der ersten Kategorie dürften eher zu vernachlässigen sein, da deren Wert nicht von der Periode t abhängt.

Bei den Attributen der zweiten Kategorie handelt es sich um Attribute des Modells, deren Wert sich zu Beginn einer jeden Periode ändert und über die gesamte Periode konstant bleibt. Hier liegen Attribute oder Systemzustände vor, deren Wert von der Periodenanzahl t abhängig ist. Da die Werte für α(t) und β(t) ebenfalls in Abhängigkeit einer Periode t zu definieren sind, eignen sich die Attribute der zweiten Kategorie am ehesten als Vorhersagegrundlage für α(t) und β(t).

Die Werte der Attribute der dritten Kategorie ändern sich ständig während der Problemlösung. Diesen Attributen werden nicht nur zu Beginn einer jeden Periode, sondern auch in deren Verlauf neue Werte zugewiesen. Bei diesen Attributen der dritten Kategorie handelt es sich insbesondere um die Eigenschaften eines Vorgangs. Da die Werte für α(t) und β(t) in Abhängigkeit von einer Periode t modelliert werden sollen, eignen sich die Attribute der dritten Kategorie eher schlecht als Vorhersagegrundlage.

4.2.2 Komplementäre Attribute

Vermutlich reichen die im vorigen Abschnitt vorgestellten atomaren Attribute aufgrund der Modellkomplexität nicht als Grundlage für die Vorhersage von α(t) und β(t) aus. Aus den vorgestellten atomaren Attributen lassen sich durch deren Kombination und Aggregation neue, so genannte komplementäre Attribute erstellen. Sie könnten die Vorhersagegrundlage verbessern, indem sie weitere Informationen über Systemzustände liefern.

So existiert beispielsweise in dem mathematischen Modell das Attribut „Lagerbestand des Standortes i nach Durchführung aller Vorgänge in Periode t“. Dieses Attribut beziffert die Anzahl der in einem Zwischenspeicher gelagerten Fahrzeuge. Ein anderes Attribut „Lagerkapazität des Standortes i“ beziffert die maximal mögliche Anzahl an Fahrzeugen, die in einem Zwischenspeicher gelagert werden können. Bei diesen beiden Eigenschaften handelt es sich um „atomare Attribute“, da diese direkt aus der mathematischen Modellierung hervorgehen.

Diese beiden angesprochenen atomaren Attribute lassen sich so kombinieren, dass ein neues Attribut entsteht. Anhand der absoluten Lagerauslastung und der maximal möglichen Lagerkapazität lässt sich eine relative Lagerauslastung errechnen. Auf diese Weise entsteht durch Kombination zweier Attribute ein neues Attribut, das nicht mehr direkt aus der mathematischen Modellierung ersichtlich ist. Solch ein indirekt erstelltes Attribut wird als „komplementäres Attribut“ bezeichnet.

Als weiteres komplementäres Attribut wird beispielsweise ein Gleichmäßigkeitskoeffizient bestimmt, der die Gleichmäßigkeit der Auslastung der Zwischenspeicher wiedergeben soll. Dieser Koeffizient errechnet sich anhand der FormelAbbildung in dieser Leseprobe nicht enthalten. Der WertAbbildung in dieser Leseprobe nicht enthaltenbeziffert die relative Auslastung eines einzelnen Zwischenspeichers und der Wert Abbildung in dieser Leseprobe nicht enthaltendie gemittelte relative Auslastung aller Zwischenspeicher zusammen. Hohe Werte dieses Gleichmäßigkeitskoeffizienten geben eine ungleichmäßige Füllung der Zwischenspeicher an, d.h. dass einige Speicher recht voll und andere Speicher recht leer sind. Ein niedriger Gleichmäßigkeitskoeffizient deutet an, dass alle Zwischenspeicher untereinander einen ähnlichen Füllstand aufweisen. Die Kenntnis dieses Gleichmäßigkeitskoeffizienten könnte bei der Vorhersage von α(t) und β(t) hilfreich sein.

Neben dem Gleichmäßigkeitskoeffizienten werden insgesamt fünfzig verschiedene komplementäre Attribute aus dem Modell abgeleitet, um eine möglichst gute Grundlage zur Vorhersage von α(t) und β(t) schaffen zu können.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 4 listet fünfzig verschiedene komplementäre Attribute auf, die exemplarisch für weitere Untersuchungen eingesetzt werden sollen. Die Erstellung weiterer komplementärer Attribute ist möglich. In den beiden rechten Spalten wird angegeben, ob das einzelne Attribut zum Zeitpunkt der Vorhersage von α(t) bzw. β(t) in Periode t zur Verfügung steht. Diejenigen Attribute, deren Wert vor der Vorhersage von Alpha bzw. Beta nicht bekannt ist, können bei der Vorhersage nicht behilflich sein. Trotzdem macht es Sinn, auch diese Attribute mitzubetrachten, denn eventuell lässt sich deren Wert indirekt zum Vorhersagezeitpunkt erschließen.

4.3 Zusammenhangsanalysen

Ein Entscheidungsbaumverfahren kann dazu eingesetzt werden, auf der Basis komplementärer Attribute Werte von Alpha bzw. Beta vorherzusagen. Der folgende Abschnitt dient dazu, eine Rechtfertigung für den Einsatz von Entscheidungsbäumen als Lösungsverfahren zu liefern. Dazu werden mögliche Voraussagefähigkeiten durch Entscheidungsbäume in Bezug auf die Problemstellung erörtert. Ziel dieser Untersuchung ist es, die Eignung der komplementären Attribute zur Vorhersage von Alpha bzw. Beta zu ermitteln.

Dazu dienen Assoziations- bzw. Korrelationsmaße, die einen eventuellen Zusammenhang zwischen Variablen aufdecken. Ein Zusammenhang zwischen zwei Variablen könnte dazu benutzt werden, anhand des Wertes der einen Variablen den Wert der zusammenhängenden zweiten Variablen zu erschließen. In diesem Zusammenhang soll der Wert von Alpha bzw. Beta aus den Attributen des Lagerhaltungssystems erschlossen werden. Diese Attribute müssen auf Zusammenhänge zu Alpha bzw. Beta untersucht werden.

Bei den zu betrachtenden komplementären Attributen handelt es sich um Intervalldaten bzw. um Ordinaldaten mit sehr vielen Merkmalsausprägungen. Die Korrelationsmaße Spearman’s rho und Pearson’s rho² sowie die Autokorrelationsanalyse und die Kreuzkorrelationsanalyse liefern die geeigneten Maße, die auf die komplementären Attribute anzuwenden sind^[22].

Zu der von Mattfeld vorgestellten Generierung von Probleminstanzen existiert eine Implementierung. Sie umfasst die drei bereits vorgestellten Strategien zur Lösung dieser Probleminstanzen. Um zu überprüfen, wie gut sich die komplementären Attribute zur Vorhersage der Werte von Alpha bzw. Beta eignen, wird diese Implementierung eingesetzt. Die Implementierung wird mit den gleichen Startparametern wie von Mattfeld versehen^[23], um möglichst realistische Werte zu erhalten. Die verwendeten Startparameter lauten wie folgt (in Klammern befinden sich jeweils die Variablennamen, die in der Implementierung verwendet werden):

Parameter für die Generierung eines Lagerhaltungssystems:

- Seed bei Generierung des Areals (Location-Seed): variiert von 1 bis 30
- Anzahl interner Zwischenspeicher (no_of_area): 10
- Anzahl externer Verladeorte (no_of_terminal): 30
- Minimale Größe des zu generierenden Areals (min_sizeof_area): 100
- Maximale Größe des zu generierenden Areals (max_sizeof_area): 1900
- Standardabweichung bei Arealgenerierung (std_dev): 1,0
Parameter für die Generierung eines Szenarios:
- Seed bei Generierung von Vorgängen (Task-Seed): variiert von 1 bis 30
- Periodenanzahl (Periods): 50
- Minimale Vorgangsgröße (min_sizeof_task): 50
- Maximale Vorgangsgröße (max_sizeof_task): 250
- Angestrebte Systemauslastung (load): variiert von 0.8 über 0.9 bis 1.0
- Angestrebte Verweildauer in den internen Speichern (stay): 8,0
- Zeitfenstergröße, Zeitraum zwischen EST und LST (wind): variiert von 0.0 über 0.125, 0.25, 0.375 bis 0.5

Parameter für den EA:

- Seed: variiert von 1 bis 30

Der Implementierung werden diese Startparameter übergeben. Teilweise handelt es sich um zu variierende Werte. Die Implementierung wird mehrfach hintereinander aufgerufen. Die Startparameter werden variiert, um unterschiedliche Situationen zu erzeugen. Die Vorhersage von Alpha bzw. Beta soll nicht auf eine bestimmte Situation spezialisiert, sondern möglichst allgemein einsetzbar sein. Dazu müssen bei der folgenden Betrachtung viele unterschiedliche Situationen berücksichtigt werden, was durch Variation der Startparameter gewährleistet wird. So wird beispielsweise an mehreren Stellen in der Implementierung ein Seed verwendet. Bei dem Seed handelt es sich um den Startwert für einen Zufallsgenerator. Um eine Unabhängigkeit der Vorhersage für Alpha und Beta von diesem Seed gewährleisten zu können, ist ein wiederholter Aufruf der Implementierung mit variiertem Seed notwendig.

Jeder für Alpha bzw. Beta bestimmte Wert wird aus der Implementierung ausgelesen und zusammen mit den Werten der komplementären Attribute als zusammengehöriger Datensatz abgespeichert.

Der Wert von Alpha bzw. Beta, der vom EA bestimmt wurde, stellt das zu lernende Class-Label dar (siehe Kapitel 3.3). Die komplementären Attribute bilden den Systemzustand, der bei der Bestimmung von Alpha bzw. Beta vorlag, ab. Nach dem wiederholten Aufruf der Implementierung mit den variierten Startparametern liegen 100.000 Datensätze vor, die im Folgenden als Erfahrungswerte dienen und analysiert werden. Eine Anzahl von 100.000 Erfahrungswerten sollte für eine repräsentative Analyse ausreichend sein.

4.3.1 Spearman’s rho

Spearman's rho gibt an, ob ein statistisch signifikanter linearer Zusammenhang zwischen zwei Variablen besteht^[24]. In der Statistik heißen Unterschiede signifikant^[25], wenn sie nur mit einer geringen Wahrscheinlichkeit durch Zufall zustande kommen. Ein linearer Zusammenhang ist gegeben^[26], wenn ein direkter Zusammenhang zwischen zwei Größen x und y nach der Formel y = a · x + b vorliegt. A und b können beliebige konstante Werte sein.

Am wirkungsvollsten ist dieses Korrelationsmaß bei einer Normalverteilung der zugrunde liegenden Daten. Dieses Korrelationsmaß ist robust gegen Ausreißer, d.h. es wird durch Extremwerte in den Daten nicht beeinflusst.

In der Statistik spricht man von einem Ausreißer^[27], sobald ein Messwert oder Befund nicht in eine erwartete Messreihe passt oder allgemein nicht den Erwartungen entspricht. Die "Erwartung" wird meistens als Streuungsbereich um den Erwartungswert herum definiert, in dem sich die meisten aller Messwerte befinden, beispielsweise der Quartilabstand Q75 - Q25. Werte außerhalb dieses Intervalls bezeichnet man meist willkürlich als Ausreißer.

Mit dem Korrelationsmaß Spearman's rho lässt sich herausfinden, ob zwischen zwei gleichverteilten Variablen ein linearer Zusammenhang besteht. Bei festgestelltem Zusammenhang ist mit Hilfe von Pearson’s rho² bestimmbar, wie stark der gefundene Zusammenhang ist. Die Ergebnisse dieser Untersuchung sind in Tabelle 5 bzw. in Tabelle 6 dargestellt.

Die Werte von Spearman’s rho liegen im Bereich von -1 bis +1. Ein Wert von 0 deutet an, dass kein Zusammenhang besteht. Je weiter die Werte von 0 verschieden sind, desto höher besteht die Wahrscheinlichkeit für einen vorliegenden Zusammenhang. Einen Wert von -1 bzw. +1 zeigt an, dass mit hoher Wahrscheinlichkeit ein Zusammenhang besteht.

4.3.2 Pearson’sche Produkt-Moment-Korrelation

Pearson'sche Produkt-Moment-Korrelation (auch „Pearson’s rho²") misst, wie groß ein linearer Zusammenhang zwischen den Werten zweier Variablen ist^[28]. Die Werte von Pearson’s rho² liegen im Bereich von -1 bis +1. Ein Wert von 0 zeigt an, dass kein Zusammenhang besteht, während eine +1 einen perfekten positiven Zusammenhang und eine -1 einen perfekten negativen Zusammenhang anzeigt. Am wirkungsvollsten ist Pearson’s rho² als Korrelationsmaß bei Normalverteilung. Leider ist dieses Korrelationsmaß im Gegensatz zum vorherigen nicht robust gegen Ausreißer. Dieses Korrelationsmaß kann nur mit großer Vorsicht auf Variablen angewendet werden, bei denen extreme Werte (Ausreißer) vorliegen.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 5 und Tabelle 6 listen die Werte der Korrelationsmaße für die komplementären Attribute in Bezug auf Alpha und Beta auf. Aufgeführt werden die komplementären Attribute, deren Werte vor Bestimmung von Alpha bzw. Beta bereits bekannt sind. Nicht aufgeführte Attribute tragen zur Bestimmung von Alpha bzw. Beta nicht bei, da sie vor der Bestimmung von Alpha bzw. Beta nicht bekannt sind. Spearman's rho deutet an, ob ein signifikanter linearer Zusammenhang erkennbar ist und gibt den entsprechenden Wert zu jedem komplementären Attribut an. Liegt kein signifikanter Zusammenhang vor, so ist ein „X“ gesetzt.

Pearson’s rho² zeigt an, wie stark die gefundenen linearen Zusammenhänge sind unter dem Vorbehalt der Normalverteilung und dem Nichtvorhandensein von Ausreißern. Relativ starke Zusammenhänge sind fett hervorgehoben.

Die Attribute, die sich nach diesen Tabellen am ehesten zur Vorhersage von Alpha eignen sind „Nutzen (Priorität x Volumen) der möglichen Vorgänge“ mit 40% Zusammenhang und „Mittlere Priorität der möglichen Vorgänge“ mit 38% Zusammenhang zu Alpha. Diese Zusammenhänge liegen unter 50% und sind als schwache bis mittelstarke Zusammenhänge zu bewerten.

Für Beta liegen nach Spearman's rho ebenfalls Attribute mit einem Zusammenhang vor. Die Zusammenhänge sind allerdings so schwach, dass sie kaum signifikant sind. Das Attribut „Gesamtvolumen aller durchzuführender Vorgänge“ zeigt mit 14% den stärksten Zusammenhang, danach folgt „Volumen an Vorgängen mit EST = t“ mit 9%.

Die Analyse der Vorhersagekraft komplementärer Attribute liefert, insbesondere für Beta, keine starken Zusammenhänge. Man beachte, dass beide Korrelationsmaße lediglich lineare Zusammenhänge messen und anzeigen. Selbst wenn insbesondere für Beta nur schwache lineare Zusammenhänge gefunden wurden, ist die Existenz starker Zusammenhänge zwischen einem komplementären Attribut und Alpha bzw. Beta möglich. Um eventuelle nicht-lineare Zusammenhänge aufzudecken, werden weitere Zusammenhangsanalysen durchgeführt.

4.3.3 Kombination von Alpha und Beta

In den beiden vorherigen Abschnitten wurde untersucht, ob ein signifikanter linearer Zusammenhang zwischen einem der komplementären Attribute und Alpha bzw. Beta vorliegt.

In der vorliegenden Simulation eines Verladeterminals können Engpässe bei dem Personaleinsatz auftreten. Eventuell werden sich auftretende Engpässe auf beide Strategieparameter gleichzeitig auswirken. Demnach könnten Alpha und Beta so miteinander korreliert sein, dass kleine Werte für Alpha zusammen mit kleinen Werten für Beta und große Werte für Alpha zusammen mit großen Werten für Beta auftreten.

Es gäbe die Möglichkeit, Alpha und Beta zusammen vorherzusagen, anstatt beide Werte getrennt zu behandeln. Daraus ließe sich eine zweistufige Strategie erstellen. In der ersten Stufe würde für die Simulation ein Wert vorhergesagt, der das Vorliegen einer Engpasssituation beziffert. Aus diesem Wert könnten dann in einer zweiten Stufe Werte für Alpha und Beta abgeleitet werden.

Nunmehr soll die Möglichkeit untersucht werden, einen gemeinsamen Wert für Alpha und Beta vorherzusagen. Dazu wird überprüft, ob signifikante lineare Zusammenhänge zu möglichen Kombinationen aus Alpha und Beta bestehen. Es existiert eine Vielzahl von Möglichkeiten zur Kombination von Alpha und Beta. Es folgt eine Untersuchung der Pearson'schen Produkt-Moment-Korrelationen für einige exemplarische Kombinationen.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 7: Pearson'sche Produkt-Moment-Korrelationen für Kombinationen
von Alpha und Beta

Tabelle 7 gibt die Pearson’sche Produkt-Moment-Korrelation für Kombinationen von Alpha und Beta wieder. Vertikal werden die komplementären Attribute aufgeführt und horizontal Alpha, Beta und Kombinationen aus Alpha und Beta. Für das Attribut „Alpha der Vorperiode“ liegt beispielsweise ein linearer Zusammenhang in Höhe von 8% zu Alpha und -3% zu Beta vor. Zur Kombination „α + β“ besteht ein Zusammenhang von 3%, zu „α * β“ ebenfalls 3% usw.

Keine Kombination von Alpha und Beta zeigt einen deutlich stärkeren Zusammenhang als Alpha bzw. Beta einzeln. An einigen Stellen gibt es einen etwas stärkeren Zusammenhang, diese Verbesserungen sind jedoch recht gering. Beispielsweise liegt für „Volumen möglicher Tasks“ ein Zusammenhang von 19% zu Alpha und 8% zu Beta vor. Die Kombination α-β weist einen Zusammenhang von 20% auf, was eine leichte Anhebung darstellt. Dieser Vorteil um 1% ist so gering, dass er kaum signifikant ist. Ähnlich sieht es für die übrigen Attribute aus. Die durch Kombinationen von Alpha und Beta auftretenden Verbesserungen sind kaum signifikant. Die meisten Kombinationen aus Alpha und Beta stellen Verschlechterungen gegenüber Alpha bzw. Beta einzeln dar.

Die Vorhersage einer Kombination von Alpha und Beta bringt nach dieser Untersuchung gegenüber der Einzelvorhersage von Alpha und Beta keine Vorteile.

4.3.4 Autokorrelationsanalyse

Da die Pearson’sche Produkt-Moment-Korrelation und Spearman's rho lediglich lineare Zusammenhänge aufdecken können, folgt die Durchführung einer Autokorrelationsanalyse. Dieses Zusammenhangsmaß ist in der Lage, auch nichtlineare Zusammenhänge aufzudecken.

Damit die Autokorrelationsanalyse auf die vorliegenden Daten anwendbar ist, werden die Daten als eine Zeitreihe aufgefasst. Der Begriff der Zeitreihe setzt voraus, dass Daten nicht kontinuierlich anfallen. Stattdessen fallen die Daten diskret, d.h. in endlichen zeitlichen Abständen, an^[29].

Mit der Autokorrelationsanalyse wird untersucht, ob eine Zeitabhängigkeit statistischer Größen im Hinblick auf ihre Kohärenz besteht^[30]. Es stellt sich die Frage, inwieweit der zukünftige Verlauf einer die Zeitabhängigkeit beschreibenden Funktion f(t) mit dem aus der Vergangenheit bekannten Verlauf in Zusammenhang steht. Es wird versucht eine quantitative Aussage über die Periodizität oder Aperiodizität der Größe f(t) zu machen. Das gelingt mit Hilfe der so genannten Autokorrelationsfunktion.

Bei der Autokorrelationsanalyse wird gemessen, in wieweit ein Zusammenhang zwischen dem aktuellen Wert einer Variablen (beispielsweise Alpha oder Beta) und den Vergangenheitswerten derselben Variablen besteht. Man misst, ob eine Variable im Zeitverlauf mit sich selbst korreliert ist. Es könnte sich als Ergebnis herausstellen, dass der Wert von Alpha bzw. Beta der aktuellen Periode beispielsweise sehr stark in Zusammenhang mit dem Wert von Alpha bzw. Beta der Vorperiode steht. Solch eine Erkenntnis wäre bei der Vorhersage des aktuellen Wertes von Alpha bzw. von Beta von entscheidender Bedeutung.

Abbildung in dieser Leseprobe nicht enthalten

Bei der Autokorrelationsanalyse wird die Korrelation in verschiedene Grade differenziert^[31]. Existiert ein Zusammenhang zwischen dem aktuellen Wert einer Variablen und deren Wert von vier Perioden zuvor, so handelt es sich um eine Autokorrelation vierten Grades. Existiert ein Zusammenhang zu deren Wert vor zwölf Perioden, so handelt es sich um eine Autokorrelation zwölften Grades.

Die Autokorrelationsfunktion misst, ob im Zeitverlauf bei einer Variablen ein Zusammenhang zu sich selbst existiert^[32]. Auf der vertikalen Achse des Autokorrelationsdiagramms wird das Lag, d.h. die Zeitverzögerung, mit Werten von 1 bis 200 dargestellt. Jeder horizontale Balken symbolisiert ein Lag. Der dritte von unten gibt beispielsweise den Zusammenhang zwischen der Variablen zum Zeitpunkt t und zum Zeitpunkt t-3, d.h. t um drei Perioden zurückversetzt, wieder. Auf der horizontalen Achse wird der Autokorrelationswert für das entsprechende Lag mit Werten zwischen -1 und +1 dargestellt. Der Autokorrelationswert gibt die Stärke des gefundenen Zusammenhanges an. Ein Wert von 0 bedeutet, dass kein Zusammenhang besteht. Ein Wert von +1 deutet einen perfekt positiven Zusammenhang und ein Wert von -1 einen perfekt negativen Zusammenhang an.

Eine Variable könnte über den Zeitverlauf mit sich selbst positiv oder negativ korreliert sein. Bei einer positiven Autokorrelation folgen tendenziell positiven Werten positive Werte und negativen Werten negative Werte. Bei einer negativen Korrelation tendieren die Werte zu einer Positiv-Negativ-Sequenz über die Zeit.

Die beiden Diagramme in Abbildung 13 und Abbildung 14 stellen die Autokorrelationswerte für die Variablen Alpha und Beta dar. Bei der Auswertung der Diagramme soll der Frage nachgegangen werden, ob der Wert von Alpha bzw. Beta mit sich selbst korreliert ist.

Ein Konfidenzintervall gibt den Bereich an, in dem sich eine untersuchte Häufigkeit mit einer bestimmten Sicherheitswahrscheinlichkeit befindet^[33]. Wird z.B. durch eine Meinungsumfrage der aktuelle Wähleranteil einer bestimmten Partei ermittelt, so nennt das Konfidenzintervall den Bereich, in dem sich auf der Grundlage der Befragung der Anteil der Partei mit großer (z.B. wenigstens 99-prozentiger) Sicherheit befindet.

Schwarze Balken in den beiden Diagrammen repräsentieren die gemessenen Autokorrelationswerte. Im Autokorrelationsdiagramm wird eine schwarze Linie dargestellt, die ein fünfundneunzig prozentiges Konfidenzintervall repräsentiert. Balken, die nicht über dieses Konfidenzintervall hinausreichen, sind nicht statistisch signifikant. Für die Variable Alpha ist das Konfidenzintervall so minimal, dass es in der Darstellung an dieser Stelle nicht sichtbar wird.

Mattfeld verwendet einen Betrachtungshorizont von 50 Perioden^[34]. Um möglichst viele signifikante Zusammenhänge zu erfassen, wird an dieser Stelle ein erweiterter Betrachtungszeitraum von 200 Perioden (200 Lags) verwendet.

Es soll analysiert werden, ob periodisch auftretende Lags existieren. Diese würden saisonale Effekte darstellen. In den vorliegenden Diagrammen treten unregelmäßig positiv und negativ auftretende Ausschläge ohne ersichtliches Schema auf. Da keine Regelmäßigkeit bei den Ausschlägen erkennbar ist, sind saisonale Effekte bei Alpha und Beta nicht feststellbar.

Über dem Zeitraum von 200 Perioden sind Autokorrelationen bei Alpha in den Perioden 1, 2, 3, 199 und 200 und bei Beta in Perioden 1, 9, 198, 199 und 200 besonders ausgeprägt. Bei dem Lag 200 treten sowohl für Alpha als auch für Beta die größten Autokorrelationswerte auf (ca. 25% bei Alpha und ca. 7% bei Beta). Alle anderen Autokorrelationswerte befinden sich deutlich darunter. Bei einer Korrelation von 25% ist höchstens von einer moderaten Korrelation zu sprechen. Sämtliche signifikanten Autokorrelationen unterschiedlichen Grades für Alpha und Beta sind schwach, d.h. nur wenig signifikant und vermutlich nicht stark genug, um eine Vorhersage von Alpha bzw. Beta zu ermöglichen.

Die stärksten Zusammenhänge sind für ein Lag von 200 Perioden bei Alpha und bei Beta erkennbar. Demnach könnte ich einen bekannten Wert von Alpha aus der Periode t dazu verwenden, einen Wert für Alpha in der Periode t+200 vorherzusagen. Betrachtet wird im Allgemeinen ein Betrachtungszeitraum von 50 Perioden. Ein zeitversetzter Zusammenhang über 200 Perioden ist daher unbrauchbar.

Mit Hilfe der Autokorrelationsfunktion konnten keine starken Zusammenhänge bei Alpha bzw. Beta aufgedeckt werden. Es bleibt zu untersuchen, ob vielleicht Korrelationen zwischen einer dieser Variablen und einem der komplementären Attribute existieren.

4.3.5 Kreuzkorrelationsanalyse in Bezug auf Alpha

Die in den vorherigen Abschnitten vorgestellten Korrelationsmaße Spearman’s rho und Pearson’s rho² liefern lediglich lineare Zusammenhänge zwischen Attributen. Die Autokorrelationsanalyse liefert Abhängigkeiten eines Attributs zu sich selbst über den Zeitverlauf. Um das Vorhandensein von nicht-linearen Abhängigkeiten von Alpha bzw. Beta aufzudecken, wird im folgenden Abschnitt eine Kreuzkorrelationsanalyse durchgeführt. Der erste Teil untersucht, ob Zusammenhänge zwischen Alpha und einer anderen Variablen existieren. Im zweiten Teil wird nach Zusammenhängen in Bezug auf die Werte von Beta gesucht.

Wie bei der Autokorrelationsanalyse werden die vorliegenden Daten als eine Zeitreihe aufgefasst. Es soll der Frage nachgegangen werden, ob der Wert von Alpha bzw. Beta mit einer anderen Variablen über den Zeitverlauf korreliert ist. Die Kreuzkorrelation liefert Beziehungen zwischen Variablen über einem Zeithorizont.

Im Folgenden ist ein Zusammenhang zwischen dem zukünftigen Verlauf einer die Zeitabhängigkeit beschreibenden Funktion f(t) mit dem aus der Vergangenheit bekannten Verlauf einer anderen Funktion g(t) zu messen. Man versucht eine quantitative Aussage über die Periodizität oder Aperiodizität der Größe f(t) in Bezug zu g(t) zu machen. Das gelingt mit Hilfe der Kreuzkorrelationsfunktion.

Auch bei der Kreuzkorrelation werden als Maß für die Stärke eines gefundenen Zusammenhangs Werte zwischen -1 und +1 geliefert. Ein Wert von 0 bedeutet, dass kein Zusammenhang besteht. Ein Wert von +1 deutet einen perfekt positiven Zusammenhang und ein Wert von -1 einen perfekt negativen Zusammenhang an.

Tabelle 8 listet alle komplementären Attribute auf, die zum Zeitpunkt der Bestimmung von Alpha bekannt sind. Zu jedem Attribut sind ein Prozentsatz und ein Lag in eckigen Klammern aufgeführt. Das Lag gibt an, um wie viele Perioden versetzt der größte Kreuzkorrelationswert vorhanden ist. Der Prozentsatz gibt den entsprechenden Kreuzkorrelationswert an.

Abbildung in dieser Leseprobe nicht enthalten

Für das Attribut „Alpha der Vorperiode“ liegt beispielsweise eine hundertprozentige, d.h. perfekte, Kreuzkorrelation mit Lag 1 zu Alpha vor. Das bedeutet, dass Alpha zum Zeitpunkt t-1 hundertprozentig von „Alpha der Vorperiode“ zum Zeitpunkt t abhängt. Der Wert von Alpha ist identisch mit dem Wert von „Alpha der Vorperiode“ der Folgeperiode. Dieser gefunden Zusammenhang ist bereits bekannt und auch so gewollt. Das Attribut „Alpha der Vorperiode“ wurde genau so konstruiert, dass es den Wert von Alpha aus der Vorperiode (t-1) trägt. Bei diesem aufgedeckten Zusammenhang handelt es sich um keine neue Erkenntnis, es wird jedoch verdeutlicht, dass die Kreuzkorrelationsanalyse korrekte Ergebnisse liefert.

Neben diesem bereits bekannten perfekten Zusammenhang liefert die Kreuzkorrelationsanalyse weitere Zusammenhänge in Bezug auf Alpha. Die meisten Zusammenhänge sind allerdings kaum signifikant. Neben dem Attribut „Alpha der Vorperiode“ weisen die Attribute „Minimale Priorität aller möglichen Vorgänge“, „Mittlere Priorität aller möglichen Vorgänge“ und „Nutzen (Priorität x Volumen) der möglichen Vorgänge“ den stärksten Zusammenhang zu den Werten von Alpha auf. Diese drei Assoziationen liegen in einem Bereich von ca. 30% bis 40% und sind als schwache bis mittelstarke Zusammenhänge zu bewerten. Als Grundlage zur Vorhersage von Alpha sollten diese drei Attribute am ehesten brauchbare Anhaltspunkte liefern, da für diese die stärksten Zusammenhänge nachgewiesen werden konnten. Alle anderen Attribute sind zur Vorhersage von Alpha, zumindest nach Aussage der Kreuzanalyse, eher zu vernachlässigen.

Bei der Verwendung dieser drei Attribute zur Vorhersage ist das in eckigen Klammern angegebene Lag zu beachten. Bei dem Attribut „Nutzen (Priorität x Volumen) der möglichen Vorgänge“ kann der Wert aus der Periode t zur Vorhersage von α(t) verwendet werden, da der stärkste Zusammenhang bei einem Lag von 0 vorliegt. Bei dem Attribut „Mittlere Priorität aller möglichen Vorgänge“ sollte der Wert aus der Periode t-1, also aus der Vorperiode, zur Vorhersage von α(t) verwendet werden. Entsprechend ist bei dem Attribut „Minimale Priorität aller möglichen Vorgänge“ der Wert aus der Periode t-2, also aus der Vor-Vorperiode, einzusetzen, da der stärkste Zusammenhang bei einem Lag von 2 nachgewiesen wurde.

4.3.6 Kreuzkorrelationsanalyse in Bezug auf Beta

Nach der Untersuchung von Zusammenhängen in Bezug auf die Werte von Alpha sollen Zusammenhänge in Bezug auf die Werte von Beta untersucht werden. Tabelle 9 listet, ähnlich wie im vorherigen Abschnitt, alle komplementären und zum Zeitpunkt der Bestimmung von Beta bekannten Attribute auf. Zu jedem Attribut ist ein Prozentsatz und ein Lag in eckigen Klammern aufgeführt. Das Lag gibt an, um wie viel Perioden versetzt der größte Zusammenhang vorhanden ist und der Prozentsatz den entsprechenden Kreuzkorrelationswert.

Abbildung in dieser Leseprobe nicht enthalten

Genau wie im vorherigen Abschnitt liegt bei dem Attribut „Beta der Vorperiode“ ein perfekter Zusammenhang zu Beta vor. Auch dieser Zusammenhang stellt keine neue Erkenntnis dar, da das Attribut „Beta der Vorperiode“ genau so konstruiert wurde.

Neben diesem bekannten perfekten Zusammenhang liefert die Kreuzkorrelationsanalyse weitere Zusammenhänge bezüglich Beta. Die meisten Zusammenhänge sind allerdings kaum signifikant. Neben dem Attribut „Beta der Vorperiode“ weisen die Attribute „Gesamtvolumen aller möglichen Vorgänge“, „Volumen an Vorgängen mit EST = t“, „Nutzen (Priorität x Volumen) der möglichen Vorgänge“ und „Arbeitsaufwand der letzten Periode“ den stärksten Zusammenhang zu den Werten von Alpha auf. Diese drei Zusammenhänge liegen in einem Bereich von ca. 30% bis 40% und sind als schwache bis mittelstarke Zusammenhänge zu bewerten, da sie unter 50% liegen. Als Grundlage zur Vorhersage von Beta sollten diese vier Attribute am ehesten brauchbare Anhaltspunkte liefern. Alle anderen Attribute sind zur Vorhersage von Beta, zumindest nach Aussage der Kreuzanalyse, eher zu vernachlässigen.

4.3.7 Zusammenfassung der Voraussagefähigkeiten

Im Folgenden werden alle mit Hilfe der zuvor angewendeten Assoziations- und Korrelationsmaße gefundenen Zusammenhänge zusammengefasst. Da mit Hilfe der Autokorrelationsanalyse keine brauchbaren Zusammenhänge aufgedeckt werden konnten, werden deren Ergebnisse nicht berücksichtigt.

Die Korrelationsmaße Spearman’s rho und Pearson’s rho² lieferten die Erkenntnis, dass die zwei Attribute „mittlere Priorität aller möglichen Vorgänge“ und „Nutzen (Priorität x Volumen) der möglichen Vorgänge“ einen schwachen bis mittelstarken Zusammenhang zu den Werten von Alpha aufweisen. Das Ergebnis der Kreuzkorrelationsanalyse bestärkt diese Erkenntnis und liefert einen weiteren schwachen bis mittelstarken Zusammenhang zu dem Attribut „Minimale Priorität aller möglichen Vorgänge“.

Als Ergebnis der in diesen Abschnitten durchgeführten Analysen lässt sich festhalten, dass sich diese drei genannten Attribute voraussichtlich am ehesten zur Vorhersage von Alpha eigenen. Bei der Konstruktion eines Entscheidungsbaumes zur Vorhersage der Werte von Alpha werden diese drei Attribute am ehesten Verwendung finden. Ihnen ist gemeinsam, dass sie Charakteristika der in einer Periode zur Verfügung stehenden Vorgänge (Priorität bzw. Nutzen) darstellen. Andere Attribute wie Charakteristika des Lagerhaltungssystems, z.B. Füllstand der Lager, sind zur Vorhersage von Alpha anscheinend eher unbrauchbar. Tabelle 10 fasst die gefundenen „interessanten“ Abhängigkeiten der Variablen Alpha zusammen:

Abbildung in dieser Leseprobe nicht enthalten

Die Korrelationsmaße Spearman’s rho und Pearson’s rho² lieferten leider nur geringfügig signifikante Abhängigkeiten von Beta. Erst die Kreuzkorrelationsanalyse brachte die Erkenntnis, dass die Attribute „Gesamtvolumen aller möglichen Vorgänge“, „Volumen an Vorgängen mit EST = t“, „Nutzen (Priorität x Volumen) der möglichen Vorgänge“ und „Arbeitsaufwand der letzten Periode“ schwache bis mittelstarke Zusammenhänge in Bezug auf die Werte von Beta aufweisen. Diesen Attributen ist gemein, dass sie Charakteristika der in einer Periode zur Verfügung stehenden Vorgänge (Volumen, Nutzen bzw. Arbeitsaufwand) darstellen. Für die Vorhersage von Beta sind andere Attribute wie z.B. Charakteristika des Lagerhaltungssystems (beispielsweise Füllstand der Lager) tendenziell unbrauchbar.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 11 fasst die gefundenen „interessanten“ Abhängigkeiten der Variablen Beta zusammen.

5 Konstruktion von Lösungsstrategien

Mattfeld gelingt es, die zugrunde liegende Problemstellung auf ein mehrperiodiges ma­thematisches Modell abzubilden und den Personalbedarf durch Anwendung einer pa­rametrisierbaren Lösungsstrategie zu bestimmen^[35]. Die Strategieparameter werden dabei durch einen zeitaufwändigen EA ermittelt. In diesem Kapitel soll stattdessen ein Entscheidungsbaum­verfahren als Strategie vorgestellt werden, das die Pa­rameterwahl zeiteffizient auf der Basis historischer Umschlagsdaten durchführt.

Die von einem EA ermittelten Strategieparameter stellen die historischen Umschlagsdaten dar, auf deren Basis ein Entscheidungsbaum konstruiert werden soll. Bestimmt der EA einen Wert für Alpha bzw. Beta, so wird dieser Wert zusammen mit den Werten aller komplementären Attribute aus der Implementierung ausgelesen und als zusammengehöriger Datensatz abgespeichert. Der vom EA bestimmte Wert von Alpha bzw. Beta stellt das zu lernende Class-Label dar. Die komplementären Attribute bilden den bei der Bestimmung von Alpha bzw. Beta vorliegenden Systemzustand ab. Nach dem wiederholten Aufruf der Implementierung mit den variierten Startparametern aus Kapitel 4 liegen 100.000 Datensätze vor. Diese Menge an Datensätzen sollte ausreichend repräsentativ sein und als Vorhersagegrundlage dienen.

Zur Bestimmung von Alpha und Beta mittels Entscheidungsbäumen gibt es zwei mögliche Vorgehensweisen: Einmal gibt es die Möglichkeit, Vergangenheitswerte von α(t) und β(t) mit den zugehörigen Systemzuständen zu sammeln und anschließend für zukünftige Situationen einen Wert von α(t) bzw. β(t) auf der Basis historischer Erfahrungswerte vorherzusagen. Die Werte von α(t) bzw. β(t) würden direkt vorhergesagt. Da es sich bei α(t) und β(t) um zwei verschiedene Funktionen handelt, müssen zwei unterschiedliche Entscheidungsbäume zur Konstruktion einer Strategie eingesetzt werden. Einer der Entscheidungsbäume dient zur Vorhersage eines Wertes von α(t) und der andere zur Vorhersage von β(t).

Anstatt der direkten Vorhersage ist es möglich, lediglich einen Systemzustand zu bestimmen. Der Systemzustand könnte beispielsweise entweder „Periode mit Engpass“ oder „Periode ohne Engpass“ lauten. Anhand dieses bestimmten Systemzustandes könnten dann Werte für α(t) bzw. β(t) entsprechend abgeleitet werden. Bei dieser Vorhergehensweise würde eine indirekte Vorhersage von α(t) bzw. β(t) stattfinden. Es würde die Konstruktion eines einzigen Entscheidungsbaumes ausreichen, um als Strategie auf der Basis historischer Erfahrungswerte einen Systemzustand zu bestimmen.

Die Zusammenhangsanalysen in den vorherigen Abschnitten (siehe Kapitel 4.3) haben ergeben, dass für Alpha bzw. Beta schwache bis mittelstarke Abhängigkeiten zu den in Kapitel 4.2.2 vorgestellten komplementären Attributen existieren. Diese komplementären Attribute könnten eventuell als Basis für die Vorhersage von α(t) bzw. β(t) dienen. Die gefundenen schwachen bis mittelstarken Abhängigkeiten rechtfertigen die Verwendung als Vorhersagegrundlage. Somit wird in dieser Arbeit die Vorgehensweise der direkten Vorhersage von Alpha bzw. Beta gewählt.

Das Ergebnis aus Kapitel 4.3.3 lautet, dass die Vorhersage einer Kombination von Alpha und Beta gegenüber der Einzelvorhersage dieser Parameter keine Vorteile hat. Die gemeinsame Vorhersage der Strategieparameter anhand eines Systemzustandes sollte demnach keine Vorteile gegenüber einer Einzelvorhersage von Alpha bzw. Beta mit sich bringen.

5.1 Entscheidungsbaumgestützte Strategien

Für die Erzeugung eines Entscheidungsbaumes steht eine Vielzahl von unterschiedlichen Verfahren zur Verfügung. Sie unterscheiden sich besonders dahingehend, welches Splittingkriterium und Pruningverfahren eingesetzt wird^[36]. Bei den Splittingkriterien bestehen Ansätze, die auf einer Informationstheorie oder auf Distanzmaßen basieren. Bei den Pruningkriterien gibt es die Möglichkeiten des Preprunings sowie des Postprunings. Nach herrschender Meinung in der Literatur gibt es beim Splitting und auch beim Pruning kein universelles Kriterium und die Wahl eines geeigneten Kriteriums hängt vorallem von den Eigenschaften des zugrundeliegenden Datensatzes ab. Weiterhin zeichnet sich ab, dass das Vorhandensein geeigneter Attribute für die Qualiät der Klassifikation wesentlich entscheidender ist, als die Wahl eines geeigneten Splitting- bzw. Pruningkriteriums.

Ein gutes Verständnis des zugrunde liegenden Problems sowie eine zur Verfügungsstellung geeigneter Attribute zur Vorhersage sind entscheidender für die Qualiät der Klassifikation als die Wahl eines geeigneten Verfahrens zur Entscheidungsbaumerzeugung. Da die Wahl eines Verfahrens eher wenig Bedeutung hat, wird in dieser Arbeit zur Erzeugung von Entscheidungsbäumen die Software-Suite SPSS^[37] eingesetzt, denn sie erlaubt einen komfortablen Umgang mit den zugrunde liegenden Daten. Sie bietet die Entscheidungsbaumerzeugungsverfahren Chi-squared Automatic Interaction Detection (CHAID), Exhaustive CHAID und Classification and Regression Trees (CRT) zur Auswahl an.

Die Verfahren Exhaustive CHAID und CRT werden in dieser Arbeit zur Konstruktion einer Strategie verwendet und sollen in den folgenden Kapiteln kurz charakterisiert werden^[38]. Auf die Verwendung des Verfahrens CHAID wird verzichtet. Denn die Verfahren CHAID und Exhaustive CHAID verfolgen denselben Ansatz, bei Exhaustive CHAID handelt es sich um eine Erweiterung von CHAID. Die Konstruktion der Strategien soll nun vorgestellt werden.

Die mit Exhaustive CHAID konstruierte Strategie soll später mit der mit CRT erzeugten Strategie verglichen werden, um zu verdeutlichen, in wieweit die Qualität der Klassifikation von der Wahl eines Entscheidungsbaumerzeugungsverfahrens abhängt.

5.1.1 Chi-squared Automatic Interaction Detection (CHAID)

Mit Hilfe von CHAID soll ein baumartiges Klassifikationsmodell entwickelt werden, an dessen Verzweigungspunkten beliebig viele Äste entspringen dürfen^[39]. Der CHAID-Algorithmus besteht aus einer Sequenz von Zusammenfassungen und Zerlegungen, gesteuert durch die Ergebnisse von diversen Assoziationsanalysen, in denen der Zusammenhang des Kriteriums mit einem Prädiktor beurteilt wird. Vereinfachend wird der CHAID-Algorithmus so beschrieben:

- Die Stichprobe wird in die Kategorien des besten Prädiktors aufgeteilt. Gut ist ein Prädiktor dann, wenn er eine signifikante Assoziation mit dem Kriterium nachweist. Dabei werden Prädiktorkategorien ohne bedeutsame Unterschiede zusammengefasst.
- Dann wird für jede der erhaltenen Gruppen eine weitere Zerlegung mit Hilfe der restlichen Prädiktoren versucht. Unter den Prädiktoren mit signifikanter Beziehung zum Kriterium wird der Beste bestimmt.
- Der Algorithmus läuft in jedem Zweig des entstehenden Baumes so lange, bis kein signifikanter Prädiktor mehr gefunden wird.

Während der klassische CHAID-Algorithmus bei der assoziations-steigernden Prädiktorvorbehandlung stoppt, sobald keine Kategorienpaare mehr aufgrund insignifikanter Kriteriumsunterschiede zu vereinigen sind, untersucht die exhaustive CHAID-Variante alle von einem Prädiktor ermöglichten Zerlegungen auf eine möglichst signifikante Kriteriums-Assoziation.

Die mit Exhaustive CHAID erzeugten Entscheidungsbäume werden für Alpha in Abbildung 15 bzw. für Beta in Abbildung 16 dargestellt. Beide Bäume weisen im Vergleich zu den mit CRT erzeugten Bäumen (vgl. Kapitel 5.1.2) eine recht hohe Komplexität auf, d.h. sie besitzen viele Verästelungen.

Für die Bestimmung von α(t) wird in der Periode t die Menge aller zur Verfügung stehenden Vorgänge (Tasks) betrachtet. Jede dieser Vorgänge besitzt einen bestimmten Nutzen. Der Nutzen jeder dieser Vorgänge wird zu einem Gesamtnutzen aufaddiert. Ist der Gesamtnutzen größer als der Wert 41.399, so wird der rechte Ast an diesem Knoten gewählt. Dem linken Ast ist zu folgen, falls der Gesamtnutzen kleiner oder gleich 41.399 beträgt. Diese Vorgehensweise, wonach an einem Knoten ein Test durchgeführt wird und der entsprechende Ast des Baumes gewählt wird, ist iterativ fortzusetzen. Das erreichte Blatt des Baumes bestimmt den Wert für α(t). Entsprechendes gilt für die Bestimmung von β(t).

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 15 : Entscheidungsbaum für Alpha erzeugt mit Exhaustive CHAID

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 16: Entscheidungsbaum für Beta erzeugt mit Exhaustive CHAID

Tabelle 10 fasst nachweisbare Abhängigkeiten von Alpha zu anderen Attributen zusammen. Nach dieser Tabelle konnte für das Attribut „Nutzen (Priorität x Volumen) der möglichen Vorgänge“ der größte Zusammenhang zu Alpha nachgewiesen werden. Für das Attribut „mittlere Priorität aller möglichen Vorgänge“ besteht der zweitgrößte und für das Attribut „minimale Priorität aller möglichen Vorgänge“ der drittgrößte Zusammenhang.

Der Entscheidungsbaum für Alpha führt in der von der Wurzel aus ersten Verästelung, d.h. in der ersten Ebene, einen Test auf das Attribut „Gesamtnutzen möglicher Tasks“ durch. In der zweiten Ebene wird das Attribut „Mittlere Priorität möglicher Tasks“ überprüft. In der dritten Ebene wird auf diese beiden Attribute hin und zusätzlich auf „Mittlerer Spielraum möglicher Tasks“ untersucht.

Für die Bestimmung von α(t) wird in der Periode t die Menge aller zur Verfügung stehenden Vorgänge betrachtet. Jeder dieser Vorgänge besitzt als Attribut einen bestimmten Nutzen, der zu einem Gesamtnutzen aufaddiert wird. Daraus ergibt sich der „Gesamtnutzen möglicher Tasks“. Jeder dieser Vorgänge besitzt auch eine Priorität. Aus der Menge all dieser möglichen Vorgänge ergibt sich die „Mittlere Priorität möglicher Tasks“. Genauso beinhaltet jeder dieser Vorgänge ein Zeitfenster, woraus ein „Mittlerer Spielraum möglicher Tasks“ hervorgeht. Dieser mittlere Spielraum gibt an, wie viele Perioden die Bearbeitung der Vorgänge im Durchschnitt hinauszögerbar ist.

Gemäß der Tabelle 10 entspricht die Wahl des Attributs „Gesamtnutzen möglicher Tasks“ als Kriterium in erster Ebene des Entscheidungsbaumes den Erkenntnissen aus dem Kapitel 4.3.7 und ist realistisch und nachvollziehbar. Genauso ist es mit der Wahl des Attributs „Mittlere Priorität möglicher Tasks“ an zweiter Ebene. Nur die Wahl des Attributs „Mittlerer Spielraum möglicher Tasks“ ist anhand der bisherigen Erkenntnisse nicht nachvollziehbar, da ein Zusammenhang zwischen diesem Attribut und Alpha nicht nachweisbar ist.

Dass dieses Attribut mit nicht nachweisbarem Zusammenhang zu Alpha erst in dritter Ebene und damit an wenig bedeutender Stelle des Entscheidungsbaumes verwendet wird, sollte noch akzeptabel sein. Wahrscheinlich wird die Qualität des Klassifikationsmodells dadurch nicht entscheidend beeinflusst. Es bleibt festzustellen, dass das Verfahren Exhaustive CHAID bei der Entscheidungsbaumerzeugung nicht immer nachvollziehbare Ergebnisse liefert. Möglich ist zwar ein Zusammenhang zwischen Alpha und „Mittlerer Spielraum möglicher Tasks“, dieser konnte aber nicht nachgewiesen werden.

Der Entscheidungsbaum für Beta führt in der ersten Ebene einen Test auf das Attribut „Volumen durchzuführender Tasks“ durch. In der zweiten Ebene wird das Attribut „Verhältnis möglicher zu durchzuführender Tasks vom Typ OUTPUT bzw. TRANS“ sowie „Gleichmäßigkeitskoeffizient des Volumens möglicher Tasks“ erprobt. In der dritten Ebene wird auf „Volumen der Tasks mit LST=t“ bzw. „Gleichmäßigkeitskoeffizient des Volumens möglicher Tasks“ und „Durchschnittlicher Gesamtaufwand über alle Perioden“ geprüft.

Für die Bestimmung von β(t) wird in der Periode t die Menge aller zur Verfügung stehenden Vorgänge betrachtet. Mit Hilfe des bereits bestimmten Parameters α(t) wird aus dieser Menge die Untermenge der durchzuführenden Vorgänge bestimmt. Summiert man das Volumen aller durchzuführenden Vorgänge auf, so ergibt sich der Wert des Attributs „Volumen durchzuführender Tasks“. Die Anzahl aller zur Verfügung stehenden Vorgänge in Relation zur Anzahl der durchzuführenden Vorgänge ergibt das „Verhältnis möglicher zu durchzuführender Tasks“. Dieses Verhältnis ist nach Vorgangstyp (Input, Output oder Transshipment) aufschlüsselbar.

Jeder Vorgang besitzt als Attribut ein bestimmtes Volumen, woraus ein durchschnittliches Volumen aller zur Verfügung stehender Vorgänge hervorgeht. Für das Volumen jedes dieser Vorgänge lässt sich eine Abweichung zum durchschnittlichen Volumen berechnen. Werden diese Distanzen quadriert und aufsummiert, so ergibt sich eine Euklidische Distanz. Diese Euklidische Distanz gibt einen Wert an, der einen „Gleichmäßigkeitskoeffizient des Volumens möglicher Tasks“ darstellt. D.h. kleine Werte des Gleichmäßigkeitskoeffizienten deuten an, dass die Volumina aller Vorgänge ähnlich groß sind. Grosse Werte des Gleichmäßigkeitskoeffizienten indizieren dagegen, dass es bei den Volumina der Vorgänge durchaus große Differenzen gibt.

Die Verarbeitung der in einer Periode t durchzuführenden Vorgänge verursacht einen bestimmten Gesamtarbeitsaufwand in der Periode t. Der „durchschnittliche Gesamtaufwand über alle Perioden“ gibt den Gesamtarbeitsaufwand an, der im Durchschnitt über alle Perioden von 1 bis t anfällt.

Die Wahl des Attributs „Volumen durchzuführender Tasks“ als Kriterium in erster Ebene entspricht den Erkenntnissen aus dem Kapitel 4.3 und ist nachvollziehbar. Genauso ist es mit der Wahl der Attribute für die weiteren Ebenen des Baumes für Beta.

Die verwendeten Attribute für den Baum zur Vorhersage von Alpha bzw. Beta, beziehen sich in der Regel auf Charakteristika von möglichen bzw. durchzuführenden Vorgängen. Lediglich bei der Verwendung des Attributs „Durchschnittlicher Gesamtaufwand über alle Perioden“ für Beta wird auf eine Eigenschaft des Lagerhaltungssystems zurückgegriffen. Die hauptsächliche Betrachtung von Charakteristika der Vorgänge deckt sich mit den Erkenntnissen aus Kapitel 4.3.7.

Des Weiteren fällt bei den Bäumen für Alpha bzw. Beta auf, dass alle vorhergesagten Werte in einem Bereich von etwa 0,45 bis 0,55 liegen. Die Werte für Alpha und Beta, die von einem EA bestimmt wurden (siehe Kapitel 4.1), liegen dagegen in einem Wertebereich von etwa 0,3 bis 0,7. Der Wertebereich der vom EA bestimmten Werte unterscheidet sich von den mittels Entscheidungsbäumen vorhergesagten Werten.

5.1.2 Classification and Regression Trees (CRT)

Bei dieser Methode wird die Segmentierung nicht durch Assoziations-Signifikanztests, sondern durch die Minimierung von Inhomogenitätsmaßen gesteuert^[40]. Sie ist der CHAID-Methode oft überlegen, wenn wie in unserem Fall metrische Prädiktoren vorliegen.

Die Entscheidungsbäume, die mit CRT für Alpha bzw. Beta erzeugt wurden, zeigen die Abbildungen Abbildung 17 und Abbildung 18:

Abbildung in dieser Leseprobe nicht enthalten

Für die Bestimmung von α(t) wird in der Periode t die Menge aller zur Verfügung stehenden Vorgänge betrachtet. Jeder besitzt als Attribut einen bestimmten Nutzen. Der Nutzen aller Vorgänge dieser Menge wird zu einem Gesamtnutzen aufaddiert. Ist der Gesamtnutzen größer als der Wert 41.640, so wird für α(t) ein Wert von 0,485 vorausgesagt. Ist der Gesamtnutzen kleiner oder gleich 41.640, so wird für α(t) dagegen ein Wert von 0,516 vorausgesagt. Für β(t) wird ein konstanter Wert von 0,503 für alle Perioden t bestimmt.

Bei dem Vergleich zwischen CRT und Exhaustive CHAID fällt auf, dass diese mit CRT erzeugten Entscheidungsbäume sehr einfach gehalten sind, da sie kaum Verästelungen besitzen. Es gilt zu beobachten, ob sich simple Entscheidungsbäume besser oder schlechter zur Vorhersage eignen als komplexe Bäume. Für das Phänomen der simplen Bäume ist ein bei CRT verwendetes Pruningverfahren verantwortlich. Als Pruning bezeichnet man die Entästelung eines Entscheidungsbaumes nach seiner Erzeugung, um die Genauigkeit des Baumes zu optimieren. Dies betrifft die Problematik des „Overfittings“^[41]. Der Entscheidungsbaum zur Vorhersage von Beta wurde vom Pruningverfahren so sehr zurechtgestutzt, dass lediglich ein konstanter Wert vorhergesagt wird.

In Kapitel 4.3.7 wurden gefundene Abhängigkeiten von Alpha zu anderen Attributen zusammengefasst. Die Zusammenhangsmasse liefern für das Attribut „Nutzen (Priorität x Volumen) der möglichen Vorgänge“ den höchsten Zusammenhang zu Alpha. Dieses Attribut entspricht dem Attribut „Gesamtnutzen möglicher Tasks (Vorgänge)“. Die Erstellung eines Entscheidungsbaumes, die sich am „Gesamtnutzen möglicher Tasks (Vorgänge)“ orientiert, entspricht also den Erkenntnissen aus dem Kapitel 4.3.7 und ist realistisch und nachvollziehbar.

5.2 Weitere Strategien

Im vorherigen Abschnitt wurde die Konstruktion zweier alternativer Strategien zur Problemlösung mit Hilfe von Entscheidungsbäumen vorgestellt. In diesem Abschnitt wird die Konstruktion weiterer Strategien beschrieben. In Anlehnung an die von Mattfeld^[42] verwendete Balancing-Strategie wird eine Balancing-Strategie 2 vorgestellt. Zusätzlich wird eine Random-Strategie eingeführt, die auf einem Zufallsverfahren basiert. Die bereits vorgestellte exhaustive CHAID-Strategie wird durch eine Transformation in eine weitere Strategie überführt.

5.2.1 Balancing-Strategie 2

Anhand der im vorherigen Abschnitt erzeugten Entscheidungsbäume konnte man beobachten, dass die vorhergesagten Werte bei allen Entscheidungsbäumen jeweils um einen Wert von 0,5 tendieren. Um zu untersuchen, was sich bei der Verwendung des exakten Wertes von 0,5 für Alpha bzw. Beta ergibt, wird eine weitere Strategie konstruiert.

Diese Strategie basiert auf der Balancing-Strategie aus dem Kapitel 2.2.3 und trägt daher den Namen Balancing-Strategie 2. Bei der ursprünglichen Balancing-Strategie wurde der Wert von Alpha variabel und der Wert von Beta=1 gesetzt. Bei dieser Variante soll aus dem zuvor genannten Grund folgendes gelten: Alpha = Beta = 0,5.

5.2.2 Random-Strategie

Die Lösungsqualität der bisher erzeugten Strategien lässt sich anhand einer zusätzlichen Strategie besser einschätzen. Bei dieser Strategie werden die Werte für Alpha bzw. Beta zufällig bestimmt. Die Strategie trägt daher den Namen Random-Strategie. Diese Strategie ermöglicht es, die Qualität einer zufälligen Lösung abzuschätzen und damit auf die Wirksamkeit anderer Strategien zu schließen. Schneidet eine Strategie qualitativ besser ab als die Random-Strategie, so ist jene Strategie erfolgreich. Ist die Qualität einer Strategie ähnlich wie die der Random-Strategie, so ist sie als nicht erfolgreich anzusehen, da das Ergebnis qualitativ einer zufälligen Lösung entspricht.

Die vom EA bestimmen Werte für Alpha bzw. Beta liegen in einem Bereich von 0,3 bis 0,7 (siehe Kapitel 4.1). Um mit möglichst realistischen Werten arbeiten zu können, werden bei der Random-Strategie Werte in genau diesem Bereich zufällig erzeugt und für Alpha bzw. Beta verwendet.

5.2.3 Transformed-CHAID Strategie

Die vorhergesagten Werte des Entscheidungsbaumes, der auf Exhaustive CHAID beruht, liegen in einem Bereich von 0,45 bis 0,55. Die Werte für Alpha bzw. Beta, die per EA bestimmt wurden, liegen dagegen in einem Bereich von 0,3 bis 0,7. Um zu beobachten, ob die Lösungsqualität vom verwendeten Wertebereich abhängt, wird eine weitere Strategie eingeführt.

Bei dieser Strategie werden die vorhergesagten Werte des Entscheidungsbaumes so transformiert, dass sie ebenfalls den Bereich von 0,3 bis 0,7 abdecken. Folgende Funktion wird zur Transformation verwendet:

Transformiertes Alpha(t) = 4 * Alpha(t) - 1.5

Transformiertes Beta(t) = 4 * Beta(t) - 1.5

Ein Wert von 0,45 für Alpha entspricht beispielsweise einem transformierten Wert von 4 * 0,45 – 1,5 = 0,3. Die Transformation sorgt dafür, dass die Werte des Entscheidungsbaumes im gleichen Wertebereich liegen wie die des EA.

6 Evaluation der Strategien

In den vorherigen Abschnitten wurden einige Strategien zur Lösung der Probleminstanzen vorgestellt. In diesem abschließenden Kapitel sollen die Strategien miteinander verglichen werden um Aussagen darüber machen zu können, welche Strategie am besten zur Problemlösung geeignet ist. Die Strategien unterscheiden sich vor allem im Laufzeitverhalten, in der Lösungsqualität, und in der Robustheit. Die Strategien werden in diesen drei Kategorien miteinander verglichen. Es soll nach Möglichkeit eine Strategie gefunden werden, die sämtlichen anderen Strategien in allen Belangen überlegen ist. Herauszufinden ist vor allem, ob eines der vorgestellten Entscheidungsbaumverfahren solch eine überlegene Strategie liefert.

6.1 Laufzeitverhalten

Tabelle 12 gibt das Laufzeitverhalten der vorgestellten Strategien wieder. Dargestellt wird die Zeit, die die jeweilige Lösungsstrategie zur Berechnung einer Lösung auf einem Computer mit Pentium IV Prozessor und 2,6 GHz Taktfrequenz benötigt. Es fällt auf, dass der EA im Vergleich besonders schlecht abschneidet. Für den EA wird wie bei Mattfeld^[43] eine Populationsgröße von 200 Individuen in 100 Generationen ausgewählt, um eine möglichst realistische Situation zu simulieren. Zur Berechnung einer Lösung benötigt der EA ca. 35.000 Evaluationen. Bei jeder Evaluation wird die Fitness eines Lösungskandidaten anhand der Zielfunktion beurteilt. Solch eine Berechnung ist sehr zeitaufwändig. Die Laufzeiten der übrigen Strategien betragen auf einem Computer mit Pentium IV Prozessor und 2,6 GHz Taktfrequenz unter eine Sekunde. Der Berechnungsaufwand ist für die übrigen Strategien wesentlich geringer. Für zeitkritische Anwendungen ist der EA den übrigen Strategien folglich unterlegen.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 12: Vergleich des Laufzeitverhaltens

6.2 Lösungsqualität

In den Abschnitten 2.2 und 0 wurden verschiedene Strategien zur Lösung der Probleminstanzen vorgestellt. In diesem Abschnitt sollen die Lösungsstrategien miteinander verglichen werden. Die Lösungsqualität spielt eine ganz entscheidende Rolle bei der Beurteilung, ob eine Strategie erfolgreich ist.

Zur Beurteilung der Lösungsqualitäten wird wie folgt vorgegangen: als erstes wird mittels der Implementierung eine Probleminstanz (siehe Kapitel 2.1.4) erzeugt. In einem zweiten Schritt werden die verschiedenen Strategien dann auf die zuvor erzeugte Probleminstanz angewendet. Aus den erzeugten Lösungen lassen sich bestimmte Werte ablesen, z.B. Zielfunktionswert, benötigter Arbeitsaufwand und Abweichung beim Arbeitsaufwand. Durch einen Vergleich dieser ermittelten Werte wird ein Schluss auf die Lösungsqualität möglich, da sie sich auf dieselbe Probleminstanz beziehen.

Von Mattfeld werden realistische Situationen beschrieben, die auf die Simulation zutreffen könnten^[44]. Es nicht möglich, anhand der Lösung einer bestimmten Probleminstanz generelle Aussagen über die Lösungsqualitäten zu tätigen. Im Folgenden werden unterschiedliche Probleminstanzen erzeugt. Sie entstehen durch den Aufruf der Implementierung mit unterschiedlichen Startparametern. Die Probleminstanzen sollen die unterschiedlichsten Situationen, in denen sich ein Verladeterminal in der Realität befinden könnte, möglichst repräsentativ darstellen. Auf diese Weise soll ermöglicht werden, generelle Aussagen über die Lösungsqualitäten ableiten zu können.

Es wird eine Art „Normalsituation“ formuliert. Engpässe in der Simulation reduzieren den Handlungsspielraum einer Lösungsstrategie. Die Normalsituation sollte eine Situation mit geringen Engpässen sein, um den Strategien einen großen Handlungsspielraum zu ermöglichen. Somit stehen bei einer Entscheidung viele Alternativen zur Auswahl. Die Wirksamkeit einer Lösungsstrategie sollte sich bei einer großen Wahlmöglichkeit am besten zeigen. Dies wird durch die Wahl folgender Startparameter für die Implementierung realisiert:

Parameter für die Generierung eines Lagerhaltungssystems:

- Seed bei Generierung des Areals: variiert von 1 bis 30
- Anzahl interner Zwischenspeicher (no_of_area): 10
- Anzahl externer Verladeorte (no_of_terminal): 30
- Min. Größe des zu generierenden Areals (min_sizeof_area): 100
- Max. Größe des zu generierenden Areals (max_sizeof_area): 1900
- Standardabweichung bei Arealgenerierung (std_dev): 1,0
Parameter für die Generierung eines Szenarios:
- Seed bei Generierung von Vorgängen: variiert von 1 bis 30
- Periodenanzahl (Periods): 50
- Minimale Vorgangsgröße (min_sizeof_task): 50
- Maximale Vorgangsgröße (max_sizeof_task): 250
- Angestrebte Systemauslastung (load): 0.8
- Angestrebte Verweildauer in den internen Speichern (stay): 8,0
- Zeitfenstergröße, Zeitraum zwischen EST und LST (wind): 0.25

Parameter für den EA:

- Seed: variiert von 1 bis 30

In Ergänzung zu der oben beschriebenen Normalsituation sollen sukzessive Engpässe eingeführt werden. Dazu werden bei weiteren Probleminstanzen einzelne Startparameter variiert. Anhand der einzeln variierten Parameter ist das Verhalten der Strategien unter geänderten Bedingungen zu beobachten.

Die folgenden Grafiken stellen die Lösungen der einzelnen Strategien in Bezug auf eine jeweilige Probleminstanz graphisch und auch tabellarisch dar. Begonnen wird mit der zuvor definierten Normalsituation. In dem Diagramm sind horizontal die unterschiedlichen Lösungsstrategien abgetragen. Vertikal sind vier verschiedene, aus den Lösungen abgeleitete Werte dargestellt. Im oberen Bereich des Diagramms sind diese vier Werte jeweils graphisch und im unteren Bereich jeweils tabellarisch abgebildet.

Bei den vier aus der Lösung abgeleiteten Werten handelt es sich um die durchschnittliche Abweichung des Arbeitsaufwands (Abk. „Dev Man“), den durchschnittlich benötigten Arbeitsaufwand (Abk. „Mean Man“), den Zielfunktionswert (Abk. „Objective“) und um die Differenz des Zielfunktionswertes zu dem Zielfunktionswert der Strategie CHAID (Abk. „Diff Objective“).

Diese Werte tragen folgende Bedeutung:

Gesamtarbeitsaufwand:

Arbeitszeit, die zur Durchführung aller Vorgänge über den gesamten Betrachtungszeitraum hinweg benötigt wird.

Durchschnittlich benötigter Arbeitsaufwand:

Gesamtarbeitsaufwand geteilt durch die Anzahl an Perioden im Betrachtungszeitraum.

Durchschnittliche Abweichung des Arbeitsaufwands:

Standardabweichung des in den einzelnen Perioden benötigten Arbeitsaufwandes vom durchschnittlichen Arbeitsaufwand.

Zielfunktionswert:

Funktion (vgl. Abschnitt 2.1.3) zur Minimierung der im Betrachtungszeitraum anfallenden Arbeitsmenge und zur gleichmäßigen Verteilung der Arbeit über alle Perioden des Betrachtungszeitraums.

Differenz des Zielfunktionswertes:

Differenz des Zielfunktionswertes der jeweiligen Strategie zu dem Zielfunktionswert der CHAID-Strategie.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 19: Lösungen für die Normalsituation

Abbildung 19 stellt die Lösungen graphisch und tabellarisch dar, welche die einzelnen Strategien für die Normalsituation bestimmt haben. Wie zuvor beschrieben, handelt es sich um eine Situation mit recht geringen Engpässen. Die durchschnittliche Auslastung der Zwischenspeicher beträgt 80%. Die Zeitfenstergröße beträgt 0,25 und die angestrebte Verweildauer in den internen Speichern beträgt 8 Perioden. Den Lösungsstrategien steht ein relativ großer Handlungsspielraum zur Verfügung. Der Zielfunktionswert, der durch die Lösung des EA erreicht wird, beträgt 5586 Arbeitseinheiten. Der durchschnittliche Arbeitsaufwand beträgt für den EA 5332 Arbeitseinheiten pro Periode. In den einzelnen Perioden liegt bei der Lösung des EA eine durchschnittliche Abweichung von 507 Arbeitseinheiten zum durchschnittlichen Arbeitsaufwand vor.

Vergleicht man die einzelnen Strategien miteinander, so fällt auf, dass der durchschnittliche Arbeitsaufwand bei sämtlichen Strategien ähnlich ausfällt. Hier besitzen die Lösungen eine qualitative Ähnlichkeit.

Unterschiede treten bei der Abweichung des durchschnittlichen Arbeitsaufwandes auf. Für die Strategie „Greedy“ liegt im Vergleich zum EA ein dreifach so großer Wert vor. Bei der Problemlösung ist der durchschnittliche Arbeitsaufwand und zugleich die Abweichung des durchschnittlichen Arbeitsaufwands zu minimieren. In dieser Situation schneidet die Greedy-Strategie erheblich schlechter als der EA ab. Die Lösung der Greedy-Strategie ist daher unbrauchbar. Ähnlich sieht es für die Balancing-Strategie aus.

Für die Balancing-Strategie 2 ist festzustellen, dass ein Wert von 838 für die Abweichung des durchschnittlichen Arbeitsaufwands vorliegt. Dieser Wert ist zwar schlechter als der des EA, aber immerhin ist diese Strategie in dieser Situation der Greedy-Strategie und der Balancing-Strategie durch einen geringeren Wert überlegen.

Die Random-Strategie liefert in dieser Situation das schlechteste Resultat für die Abweichung des durchschnittlichen Arbeitsaufwands. Wie in Abschnitt 5.2.2 beschrieben, dient diese Strategie nur zu Vergleichszwecken. Schneidet eine Strategie qualitativ besser ab als die Random-Strategie, so ist diese Strategie wirkungsvoll. Ist die Qualität einer Strategie ähnlich wie die der Random-Strategie, so ist diese Strategie als nicht wirkungsvoll anzusehen. In dieser Situation schneidet die Random-Strategie mit einem Wert von 1779 erheblich schlechter als alle anderen Strategien ab. Somit lässt sich feststellen, dass alle anderen Strategien wirkungsvoll arbeiten.

Die Strategie, die mittels des Verfahrens „CHAID“ erzeugt wurde, liefert in dieser Situation für die Abweichung des durchschnittlichen Arbeitsaufwands den zweitbesten Wert. Diese Strategie ist für die Normalsituation als recht erfolgreich anzusehen. Das Ergebnis des EA konnte nicht übertroffen werden, aber diese Strategie stellt eine Verbesserung zu der Greedy-Strategie und der Balancing-Strategie dar.

Bei der Strategie „CHAID (transf.)“ werden die vorhergesagten Werte der CHAID-Strategie in einen anderen Wertebereich überführt (siehe Kapitel 5.2.3). In dieser Normalsituation lässt sich eine leichte Verschlechterung gegenüber der ursprünglichen CHAID-Strategie vermerken. Das bedeutet, dass sich die Transformation des Wertebereichs unvorteilhaft auf die Lösungsqualität auswirkt.

Genauso liefert die mittels des Verfahrens „CRT“ erzeugte Strategie für die Abweichung des durchschnittlichen Arbeitsaufwands einen etwas schlechteren Wert als die CHAID-Strategie. Es bleibt festzustellen, dass das Verfahren zur Entscheidungsbaumerzeugung (vgl. Kaptitel 5.1) durchaus die Lösungsqualität beeinflusst. Allerdings sind die Unterschiede recht gering, da die Werte sich wenig unterscheiden.

Eine Betrachtung der Zielfunktionswerte bzw. die Differenz der Zielfunktionswerte zum Zielfunktionswert der CHAID-Strategie liefert vergleichbare Ergebnisse, wie die Betrachtung der Abweichung des durchschnittlichen Arbeitsaufwands. D.h. der EA liefert das beste Resultat, gefolgt von CHAID, Balancing-2, CHAID (transf.) und CRT. Danach folgen Balancing, Greedy und Random.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 20: Lösungen bei Variation der angestrebten Systemauslastung

Bei der in Abbildung 20 dargestellten Situation wird ein Engpass eingeführt. Dazu wird die angestrebte Systemauslastung von 80% über 90% bis 100% variiert.

Der EA liefert mit Abstand den geringsten Zielfunktionswert. Es liegt eine hohe Differenz zu dem Zielfunktionswert (ZF) der CHAID-Strategie vor. Am zweitbesten arbeitet die Greedy-Strategie gefolgt von der Random-Strategie. Die übrigen Strategien erreichen Werte, die schlechter sind als der der Random-Strategie. Es folgen Balancing, CHAID (transf.), Balancing 2, CRT und CHAID.

Dass die Random-Strategie im Vergleich zu den übrigen Strategien relativ gut abschneidet deutet an, dass der eingeführte Engpass für die Strategien ein Problem darstellt. Besonders schlecht sind Lösungen der Verfahren, welche auf einem Entscheidungsbaum basieren (CHAID, CRT und CHAID transf.). D.h., dass die entscheidungsbaumbasierten Verfahren den Engpass in dieser Situation schlecht bewältigen können.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 21: Lösungen bei Variation der Vorgangsgröße

Bei der Situation in Abbildung 21 ändert sich die Größe der Vorgänge. In der Normalsituation verwendet man ein Volumen von 50 bis 250 Fahrzeugen, diese reduzieren sich hier auf 50 bis 100 Fahrzeuge. Das Volumen der Fahrzeuge nimmt durchschnittlich ab. Für kleinere Fahrzeugmengen sollte es mehr Möglichkeiten geben, freie Speicherplätze zu finden. Der Handlungsspielraum für die Strategien sollte sich in dieser Situation vergrößern.

Wieder sind die Werte für den durchschnittlichen Arbeitseinsatz bei allen Strategien ähnlich. Der EA liefert den besten ZF-Wert. Die Entscheidungsbaumverfahren liefern zusammen mit der Balancing-Strategie 2 nach dem EA die besten Ergebnisse. Die Greedy-Strategie und die Balancing-Strategie schneiden schlechter ab. Als am schlechtesten stellt sich die Random-Strategie heraus.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 22: Lösungen bei Variation der Vorgangsgröße

In der Situation von Abbildung 22 erhöht sich das Volumen der Vorgänge auf 200 bis 250 Fahrzeuge. Das Volumen der Fahrzeuge nimmt im Vergleich zur Normalsituation durchschnittlich zu. Für größere Fahrzeugmengen sollte es weniger Möglichkeiten geben, freie Speicherplätze zu finden. Der Handlungsspielraum für die Strategien sollte sich in dieser Situation verkleinern. Somit wurde ein Engpass eingeführt.

Das Abschneiden der Strategien ähnelt dem der vorherigen Situation, bei der statt eines Engpasses ein erweiterter Handlungsspielraum eingeführt wurde. Es lässt sich feststellen, dass die Variation der Fahrzeugmengen die Lösungsqualität der Strategien kaum beeinflusst.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 23: Lösungen bei Erhöhung der angestrebten Verweildauer

In der Normalsituation beträgt die angestrebte Verweildauer der Vorgänge acht Perioden. Die angestrebte Verweildauer gibt an, wie lange die Fahrzeuge eines Vorgangs durchschnittlich in einem Zwischenspeicher gelagert werden sollten. In dieser Situation erhöht sich die angestrebte Verweildauer auf zehn Perioden, um eine Reaktion der Strategien darauf zu untersuchen.

Wie bei der Normalsituation ergeben die Lösungsstrategien für den durchschnittlichen Arbeitsaufwand ähnliche Werte. Unterschiede gibt es bei dem ZF-Wert bzw. bei der Abweichung des durchschnittlichen Arbeitsaufwandes.

Der EA liefert das beste Ergebnis und die Entscheidungsbaumverfahren zusammen mit der Balancing-Strategie 2 die zweitbesten Ergebnisse. Die Greedy-Strategie und die Balancing-Strategie schneiden schlechter ab und die Random-Strategie am schlechtesten.

Auswirkungen durch die Änderung der Verweildauer lassen sich nicht feststellen, da sich am Abschneiden der Strategien im Vergleich zur Normalsituation nichts geändert hat.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 24: Lösungen bei Erhöhung der Zeitfenstergröße

Bei der Situation in Abbildung 24 erhöht sich die Zeitfenstergröße im Vergleich zur Normalsituation. Die Zeitfenstergröße bestimmt die Dauer zwischen dem Eintreffen eines Vorgangs in das Verladeterminal und der Ausfuhr eines Vorgangs aus dem Verladeterminal. Je größer diese Zeitdauer, desto größer ist die Dispositionsmöglichkeit, in welcher Periode ein Vorgang bearbeitet werden soll. Eine Erhöhung der Zeitfenstergröße führt zu einer Vergrößerung des Handlungsspielraums.

Die Lösungen haben Ähnlichkeit zur Normalsituation. Die Werte für den durchschnittlichen Arbeitseinsatz sind ähnlich. Bei dem ZF-Wert schneidet der EA am besten ab, gefolgt von den Entscheidungsbaumverfahren und der Balancing-Strategie 2. Schlechter schneiden die Balancing-Strategie und die Greedy-Strategie und vor allem die Random-Strategie ab.

Auswirkungen durch die Änderung der Zeitfenstergröße lassen sich nicht nachweisen, da sich am Abschneiden der Strategien im Vergleich nichts geändert hat.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 25: Lösungen bei Verringerung der Zeitfenstergröße

Im Gegensatz zur Erhöhung der Zeitfenstergröße wird in Abbildung 25 die Zeitfenstergröße reduziert. Der Handlungsspielraum nimmt in dieser Situation ab.

Erneut sind die Werte für den durchschnittlichen Arbeitseinsatz ähnlich. Doch in dieser Situation haben die ZF-Werte sowie die Werte für die Abweichung bei dem durchschnittlichen Arbeitseinsatz mehr Ähnlichkeit untereinander. Lediglich der EA zeigt sich durch bessere Werte überlegen. Die Random-Strategie weist die schlechtesten Werte auf.

Auswirkungen durch die Änderung der Zeitfenstergröße sind in dieser Situation feststellbar: Die Reduktion des Handlungsspielraums führt zu einer Annäherung der Lösungsqualitäten.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 26: Lösungen bei höherer Anzahl interner Zwischenspeicher

Bei der Normalsituation wurde ein Lagerhaltungssystem verwendet, das aus 10 internen Zwischenspeichern und aus 30 externen Verladeorten besteht. Bei der Situation, die Abbildung 26 zugrunde liegt, ist die Anzahl interner Zwischenspeicher von 10 auf 20 erhöht. Die Ergänzung der Zwischenspeicher erhöht die Dispositionsmöglichkeiten. Der Handlungsspielraum für die Strategien erweitert sich.

Die Lösungen ähneln der Normalsituation. Die Werte für den durchschnittlichen Arbeitseinsatz sind approximativ. Bei dem ZF-Wert schneidet der EA am besten ab, gefolgt von den Entscheidungsbaumverfahren und der Balancing-Strategie 2. Schlechter stellen sich die Balancing-Strategie und die Greedy-Strategie und vor allem die Random-Strategie dar.

Die Erhöhung des Handlungsspielraums hat nach dieser Untersuchung keinen Einfluss auf die Lösungsqualität, da die Lösungsstrategien ähnlich wie bei der Normalsituation abschneiden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 27: Lösungen bei höherer Anzahl externer Verladeorte

Im Vergleich zur Ausgangssituation wird die Anzahl der Verladeorte von 30 auf 100 erhöht. Wie bei der vorherigen Situation vergrößert sich in diesem Fall der Handlungsspielraum der Strategien.

Die Lösungen sind der Normalsituation ähnlich und die Werte für den durchschnittlichen Arbeitseinsatz sind fast gleich. Bei dem ZF-Wert schneidet der EA am besten ab, gefolgt von den Entscheidungsbaumverfahren und der Balancing-Strategie 2. Schlechte Resultate ergeben die Balancing-Strategie, die Greedy-Strategie und vor allem die Random-Strategie.

Die Erhöhung des Handlungsspielraums hat keinen Einfluss auf die Lösungsqualität, da sich die Lösungsstrategien ähnlich wie bei der Normalsituation verhalten.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 28: Lösungen bei Verringerung der Arealgröße

Bei der Normalsituation wurde ein Lagerhaltungssystem mit einem Areal einer Größe zwischen 100 und 1900 Einheiten verwendet. Abbildung 28 zeigt die Arealgröße auf einen Wert zwischen 100 und 300 Einheiten reduziert, um eine Auswirkung der Strategien darauf zu untersuchen.

Die Werte für den durchschnittlichen Arbeitseinsatz variieren in dieser Situation zwischen den Strategien. Bei dem ZF-Wert schneidet der EA am besten ab, gefolgt von der CHAID-Strategie. Die Strategien Balancing 2, CRT und CHAID (transf.) sind ungünstiger. Die Greedy-Strategie und die Balancing-Strategie sind mit dem Ergebnis der Random-Strategie fast gleich.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 29: Lösungen bei verkleinertem Areal

Im Gegensatz zur Abbildung Abbildung 28 wird bei Abbildung 29 die Arealgröße auf einen Wert zwischen 100 und 3000 Einheiten vergrößert.

Die Lösungen haben Ähnlichkeit mit der Normalsituation. Die Werte für den durchschnittlichen Arbeitseinsatz sind ähnlich. Bei dem ZF-Wert schneidet der EA mit dem niedrigsten Wert ab, gefolgt von den Entscheidungsbaumverfahren und der Balancing-Strategie 2. Schlechter schneiden die Balancing-Strategie und die Greedy-Strategie und vor allem die Random-Strategie ab.

Auswirkungen durch die Vergrößerung des Areals sind nicht feststellbar, da sich am Abschneiden der Strategien im Vergleich zur Normalsituation nichts geändert hat.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 30: Lösungen bei vergrößertem Areal

Bei der Situation aus Abbildung 30 wird die Standardabweichung bei der Arealgenerierung von 8 auf 10 erhöht. Dieser Parameter ist für die flächenmäßige Ausdehnung der Standorte bei der Arealgenerierung verantwortlich. Die beim Fahrzeugtransport zurückzulegenden Strecken werden zwischen den Standorten größer. Ein Einfluss auf den Handlungsspielraum im Vergleich zur Normalsituation lässt sich nicht erkennen.

Die Lösungen haben erneut Ähnlichkeit mit der Normalsituation. Die Werte für den durchschnittlichen Arbeitseinsatz ähneln sich. Der ZF-Wert ist beim EA am niedrigsten, gefolgt von den Entscheidungsbaumverfahren und der Balancing-Strategie 2. Schlechter stellen sich die Balancing-Strategie, die Greedy-Strategie und vor allem die Random-Strategie dar.

Es fällt auf, dass es sich bei diesen Werte beinahe um dieselben Werte wie bei der Normalsituation handelt. In einigen Fällen wurden die Werte lediglich verzehnfacht. Die Erhöhung der Standardabweichung hat überhaupt keinen Einfluss auf die Lösungsstrategien, es findet lediglich eine Vervielfachung der resultierenden Werte statt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 31: Lösungen bei Variation der Zeitfenstergröße und

angestrebte Systemauslastung 80%

In der Situation von Abbildung 31 wird ein Engpass eingeführt, indem die Zeitfenstergröße variiert wird. Die Zeitfenstergröße wird einmal auf 0, einmal auf 0.125, dann auf 0.25, 0.375 und zuletzt auf 0.5 gesetzt. Die Zeitfenstergröße bestimmt die Zeitdauer zwischen dem Eintreffen eines Vorgangs in das Verladeterminal und der Ausfuhr eines Vorgangs aus dem Verladeterminal. Je größer diese Zeitdauer ist, desto größer ist die Dispositionsmöglichkeit, in welcher Periode ein Vorgang bearbeitet werden soll. Eine Erhöhung der Zeitfenstergröße führt zu einer Vergrößerung des Handlungsspielraums. Die Zeitfenstergröße beträgt durchschnittlich 0.25, hat also durchschnittlich den gleichen Wert wie in der Normalsituation. Eine Vergrößerung bzw. Verkleinerung Handlungsspielraums findet im Durchschnitt nicht statt.

Das Ergebnis ähnelt der Normalsituation. Die Werte für den durchschnittlichen Arbeitseinsatz sind ähnlich. Der ZF-Wert des EA ist am besten, d.h. am niedrigsten, gefolgt von den Entscheidungsbaumverfahren und der Balancing-Strategie 2. Schlechter stellt sich die Balancing-Strategie, die Greedy-Strategie und vor allem die Random-Strategie dar.

Die Variation der Zeitfenstergrößen hat keinen Einfluss auf die Qualität der Lösungen, da sich am Abschneiden der Strategien im Vergleich zur Normalsituation nichts geändert hat.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 32: Lösungen bei Variation der Zeitfenstergröße und

angestrebter Systemauslastung bei 90%

Die Situation in Abbildung 32 ist die gleiche wie die in Abbildung 31 mit variierter Zeitfenstergröße. Lediglich die angestrebte Systemauslastung wird von 80% auf 90% erhöht. Es entsteht ein zusätzlicher Engpass mit verringertem Handlungsspielraum, da durch die erhöhten Füllstände des Speichers weniger Dispositionsmöglichkeiten zur Verfügung stehen dürften.

Auch hier erbringt der EA das beste Ergebnis mit dem niedrigsten ZF-Wert. Das zweitbeste Ergebnis liefert die Random-Strategie. Da sämtliche Strategien mit Ausnahme des EA schlechter als die Random-Strategie abschneiden, stellt die Situation für die übrigen Strategien ein Problem dar. D.h. mit diesem Engpass kommen die restlichen Verfahren schlecht zurecht und der EA bleibt die einzige empfehlenswerte Strategie.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 33: Lösungen bei Variation der Zeitfenstergröße und

angestrebter Systemauslastung bei 100%

Die Situation in Abbildung 33 gleicht der der von Abbildung 31 bzw. von Abbildung 32. Die angestrebte Systemauslastung erhöht sich jedoch auf 100%. Der Engpass verschärft sich weiter und der Handlungsspielraum nimmt ab.

Dass sich der Engpass im Vergleich zur Abbildung 32 verschärft, zeigt sich in der Abbildung 33. Der EA bietet mit Abstand das beste Ergebnis. Auch das Ergebnis der zweitbesten Strategie, der Random-Strategie, ist ganz erheblich besser als das der übrigen Strategien.

Der zugespitzte Engpass stellt für die übrigen Strategien, die mit dem Engpass überfordert werden, ein ganz erhebliches Problem dar. In dieser Situation kommt der EA als einzige empfehlenswerte Strategie in Betracht.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 34: Normierter Durchschnitt aller bisherigen Lösungen

Abbildung 34 fasst die Ergebnisse aller vorherigen Situationen zusammen, indem ein normierter Durchschnitt aus allen bisherigen Ergebnissen gebildet wird. Eine Normierung der Ergebnisse der bisherigen Situationen ist notwendig, da sie absolut betrachtet nicht vergleichbar sind.

Es ist erkennbar, dass sich die Werte für den durchschnittlichen Arbeitsaufwand bei allen Strategien bis auf den EA in einem ähnlichen Bereich bewegen. Es gibt bei den unterschiedlichen Situationen nur geringfügige Abweichungen bei dem durchschnittlichen Arbeitsaufwand.

Anders sieht es bei der Abweichung des durchschnittlichen Arbeitsaufwandes aus. An dieser Stelle scheint der eigentliche Handlungsbedarf bei der Optimierung zu liegen. Den schlechtesten Wert weist die Random-Strategie auf, gefolgt von der Greedy-Strategie und der Balancing-Strategie. Bei der Balancing-Strategie 2 handelt es sich um eine Verbesserung gegenüber der Balancing-Strategie. Leichte Verbesserungen gegenüber der Balancing-Strategie-2 lassen sich durch den Einsatz von entscheidungsbaumgestützten Verfahren erreichen. Hier liefern die Strategien CHAID, CHAID (transf.) und CRT recht ähnliche Ergebnisse. Die Lösungen des EA konnten durch den Einsatz von Entscheidungsbäumen nicht übertroffen werden. Der EA weist im Durchschnitt aller Situationen und in jeder Einzelsituation die besten Lösungen auf.

Anhand der vorgestellten Situationen ist die Lösungsqualität der einzelnen Strategien ableitbar. Über alle Situationen hinweg bot der EA die besten Resultate. In Engpasssituationen waren die Resultate des EA wesentlich besser als die der übrigen Strategien. Ebenso zeigte sich der EA in Situationen mit gelockerten Engpässen stets als beste Strategie.

In vielen Situationen war die Greedy-Strategie etwas schlechter als die Balancing-Strategie. Die Balancing-Strategie 2 übertraf die ursprüngliche Balancing-Strategie meist. Mittels Entscheidungsbäumen konnte die Balancing-Strategie 2 übertroffen werden. Unter den mit Entscheidungsbäumen erzeugten Strategien zeigte sich kein klarer Favorit. So wies in einigen Situationen die CHAID-Strategie das beste Resultat auf, in anderen die transformierte Variante CHAID (transf.). Aber auch die CRT-Strategie brachte in einigen Situationen das beste Ergebnis unter den Entscheidungsbäumen hervor. Bei den Abweichungen zwischen den Entscheidungsbaumverfahren handelt es sich eher um Feinheiten, da keine großen Unterschiede zwischen den Werten aufgetreten sind. Die Random-Strategie zeigte sich in den meisten Situationen als die schlechteste Variante.

Gelegentlich bestanden Engpasssituationen, in denen alle übrigen Strategien im Unterschied zum EA schlechte Lösungen lieferten. Dabei handelt es sich um Situationen, in dem die Systemauslastung von 80% auf 90% oder 100% erhöht wird. Der EA scheint derartige Situationen gut zu bewältigen, während alle übrigen Strategien versagen. Bei der Erstellung der Entscheidungsbäume werden historische Werte zur Vorhersage von Alpha und Beta benutzt. Diese historischen Daten stammen aus Entscheidungen, die der EA in früheren Situationen getroffen hat. Wie sich bei den untersuchten Situationen gezeigt hat, erweisen sich die Entscheidungsbaumverfahren in Situationen als praktikabel, in denen die angestrebte Speicherauslastung 80% beträgt. Anhand der historischen Daten sind die Entscheidungsbäume auf derartige Situationen gut trainiert worden. Bei höherer Speicherauslastung als 80% reagieren die Entscheidungsbaumverfahren schlecht. Anscheinend wurden die Entscheidungsbäume nur auf Situationen mit 80% Systemauslastung gut trainiert.

Die Ergebnisse der Entscheidungsbäume sind bei geringer Speicherauslastung wenig aussagekräftig. Dort sollten konzeptionelle Änderungen ansetzen. Als Erweiterung könnte ein neuer Entscheidungsbaum darauf trainiert werden, nicht nur 80%-ige, sondern auch höhere Speicherauslastungen gut verarbeiten zu können. Dies könnte erreicht werden, indem zur Menge historischer Entscheidungen mehr Situationen mit 90%iger oder 100%iger Speicherauslastung hinzugenommen werden.

Eine weitere Optimierung lässt sich durch die Wahl eines geeigneten Verfahrens zur Entscheidungsbaumerzeugung erreichen. Denn es hat sich gezeigt, dass die entscheidungsbaumbasierten Strategien leichte Unterschiede in der Lösungsqualität aufweisen. So könnte in weiteren Untersuchungen ein Verfahren zur Entscheidungsbaumerzeugung gewählt werden, das sich mit seinen Eigenschaften besonders für die vorliegenden historischen Daten eignet.

6.3 Robustheit

Für die im vorherigen Abschnitt beschriebenen Situationen wurden die Lösungen der Strategien miteinander verglichen. Insgesamt sind 55 verschiedene Probleminstanzen erzeugt und teilweise zusammengefasst worden. Aus der Lösung der Probleminstanzen lässt sich neben den ZF-Werten auch ablesen, wie viele der insgesamt 55 Lösungsversuche erfolgreich waren. Denn nicht immer hat eine Strategie zu einer gegebenen Probleminstanz auch eine gültige Lösung geliefert. Benötigt die Lösung einer Probleminstanz mehr Zwischenspeicherflächen als verfügbar sind, so ist die Problemlösung ungültig.

Tabelle 13 gibt die Anzahl erfolgreicher Lösungsversuche der Strategien wieder. Dargestellt wird die Anzahl der gültigen Lösungen im Verhältnis zur Anzahl der Lösungsversuche.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 13: Anzahl erfolgreicher Lösungsversuche

Mit Hilfe des EA konnten in allen 55 Fällen, in denen diese Strategie zur Problemlösung zum Einsatz kam, eine gültige Lösung erzeugt werden. Mit den übrigen Strategien wurde in 43-45 von 55 Fällen eine brauchbare Lösung erzeugt. Dies entspricht einem Verhältnis von 86-90%. D.h. die übrigen Strategien erzeugen lediglich in 86-90% der Versuche eine gültige Lösung.

In Abschnitt 6.1 wurde der EA für zeitkritische Anwendungen als unterlegen festgestellt. Denn der EA benötigte erheblich mehr Berechnungszeit als die restlichen Strategien. Nach den Beobachtungen zeigt sich, dass der EA robuster als die übrigen Strategien ist. Bei einigen Anwendungen gilt die Voraussetzung, dass zu jeder Zeit eine gültige Lösung für eine Problemstellung bestimmbar ist. Beispielsweise wäre ein Einsatz in Bereichen der Medizin oder der Raumfahrt vorstellbar. Für derartige Anwendungen empfiehlt sich die Verwendung eines EA aufgrund dessen Robustheit.

7 Zusammenfassung der Ergebnisse

Entscheidungsbäume werden üblicherweise im Umfeld des Data Mining zur Klassifikation verwendet. Diese Arbeit stellt die Anwendung eines Entscheidungsbaum­verfahrens auf ein logistisches Optimierungsproblem anhand des Beispiels eines Kfz-Verladeterminals vor. Für eine solche Einsatzform von Entscheidungsbäumen existieren bisher noch keine dokumentierten Untersuchungen. Die Wahl von Strategieparametern geschieht zeiteffizient auf der Basis historischer Umschlagsdaten.

Bei dem bisher zur Problemlösung angewandten Evolutionären Algorithmus muss ein versierter Benutzer Anfangsparameter bestimmen. Es ist eine Abhängigkeit der Lösungen von der Qualität der Startwerte gegeben. Wesentlich ist bei dem Einsatz von Entscheidungsbäumen zur Problemlösung, dass keinerlei Startwerte für das Verfahren benötigt werden. Die Problematik optimaler Startwerte wird somit umgangen.

Zur Rechtfertigung des Einsatzes von Entscheidungsbäumen als Lösungsverfahren wurden die Voraussagefähigkeiten der Entscheidungsbäume erörtert. Es hat sich herausgestellt, dass zwischen den Systemzuständen der Simulation eines Verladeterminals und den vorherzusagenden Parametern Alpha bzw. Beta einige leichte bis mittelstarke Zusammenhänge vorhanden sind. Demnach sind Entscheidungsbaumverfahren zur Problemlösung geeignet.

Bei der Anwendung von Entscheidungsbäumen wurde beobachtet, dass die durch den EA bestimmten Parameter um einen Wert von 0,5 tendieren. Deshalb erfolgte die Formulierung einer Strategie, die stets einen exakten Wert von 0,5 für Alpha bzw. Beta vorgibt.

Bei der Evaluation unterschiedlicher Situationen hat sich der EA stets als das am meisten zur Problemlösung geeignete Verfahren herausgestellt. Denn die Lösungen des EA wiesen stets eine bessere Qualität auf, als die Lösungen der übrigen Strategien. So wurden vom EA die Lösungen mit dem vergleichsweise niedrigsten ZF-Wert bestimmt. In einzelnen Engpasssituationen übertraf der EA die restlichen Strategien sogar deutlich.

Die neu formulierte Balancing-Strategie 2, die stets das neutrale Gewicht von 0,5 verwendet, hat sich anhand der Lösungsqualität gegenüber der ursprünglichen Balancing-Strategie und der Greedy-Strategie als überlegen herausgestellt. In den meisten Situationen lieferte die Balancing-Strategie 2 ein besseres Ergebnis, das durch einen niedrigeren ZF-Wert gekennzeichnet ist. Eine leichte Verbesserung gegenüber der Balancing-Strategie 2 stellen die durch den Einsatz von Entscheidungsbäumen erstellten Strategien dar.

Die zufallsbasierte Random-Strategie ermöglicht es, die Qualität einer zufälligen Lösung abzuschätzen. Die Ergebnisse waren in der Regel schlechter, als die der Balancing-Strategie 2 und die der entscheidungsbaumbasierten Verfahren. Somit ist anzunehmen, dass der Erfolg der entscheidungsbaumbasierten Strategien kein Zufall ist. Stattdessen ist von einer wirksamen Nivellierung durch diese Strategien auszugehen.

Die Balancing-Strategie 2 und die entscheidungsbaumbasierten Strategien haben gemeinsam, dass sie Werte rund um 0,5 für Alpha bzw. Beta verwenden. Der EA verdeutlicht die Existenz treffenderer Werte als die neutralen Gewichte von 0,5 für Alpha bzw. Beta (siehe Kapitel 4.1). Demnach handelt es sich bei der Wahl des neutralen Gewichts für Alpha bzw. Beta nicht um ein globales Optimum. Stattdessen ist der EA in der Lage, mit Hilfe einer Vielzahl von zeitaufwändigen Evaluationen bessere Lösungen zu liefern.

Die in dieser Arbeit durchgeführten Evaluationen erlauben den Schluss, dass der Einsatz von Entscheidungsbäumen zur Lösung der vorliegenden Probleminstanzen möglich ist. Die vorgestellten entscheidungsbaumbasierten Strategien weisen eine geringere Komplexität als der EA auf. Diese Strategien benötigen entschieden weniger Laufzeit als der EA, allerdings bringen sie eine Verschlechterung gegenüber dem EA hinsichtlich Qualität und Robustheit mit sich. Für den Gewinn an Laufzeit, auf den es in zeitkritischen Situationen entscheidend darauf ankommt, ist eine leichte Qualitätsverschlechterung hinzunehmen. Steht ausreichend Laufzeit zur Verfügung, ist dem EA aufgrund dessen Lösungsqualität der Vorzug zu geben.

Als Ergebnis dieser Arbeit lassen sich folgende Ansatzpunkte für weitere Untersuchungen zu diesem Thema vorstellen:

In Kapitel 6.2 wurde gezeigt, das die verwendeten Entscheidungsbäume vermutlich zur sehr auf Situationen mit einer angestrebten Speicherauslastung von 80% spezialisiert sind. Neue, besser auf Situationen mit höherer Auslastung trainierte Entscheidungsbäume könnten durch die Verwendung eines modifizierten Datensatzes als Vorhersagegrundlage (vgl. Kapitel 6.2) erstellt werden. Es ist von einer qualitativen Verbesserung für Engpasssituationen mit hoher Speicherauslastung auszugehen, wenn die Spezialisierung auf Situationen mit 80% Auslastung aufgehoben werden könnte.

Weiter besteht die Möglichkeit, andere als die in dieser Arbeit eingesetzten Verfahren CHAID und CRT zur Entscheidungsbaumerzeugung zu verwenden. Zwischen den entscheidungsbaumbasierten Strategien haben sich leichte Unterschiede gezeigt. Demnach hat die Wahl eines Entscheidungsbaumerzeugungsverfahrens Auswirkungen auf die Lösungsqualität. Alternative Verfahren könnten Eigenschaften aufweisen, die sich besser für die Beschaffenheit der vorliegenden historischen Daten eignen. Die Verwendung dieser Verfahren könnte Verbesserungen in Bezug auf die Normalsituation ermöglichen (vgl. auch hier Kapitel 6.2).

Deutliche Verbesserungen könnten durch die Konstruktion einer Metaheuristik erreicht werden. Sie könnte so erstellt werden, dass alle zur Verfügung stehenden Strategien (bis auf den EA) auf eine Probleminstanz angewendet werden und die Lösung mit dem besten Ergebnis ausgewählt wird. Es ist zu erwarten, dass die Lösung der Metaheuristik erheblich schneller vorliegt als die Lösung des EA. Voraussichtlich liefert eine solche Metaheuristik qualitativ schlechtere Ergebnisse als der EA, denn er produzierte bei den bisherigen Untersuchungen stets das qualitativ beste Ergebnis. Gegenüber allen anderen Strategien stellt die Metaheuristik eine Verbesserung dar, da stets die Lösung der besten Strategie ausgewählt wird.

Weiterhin besteht die Möglichkeit (siehe Kapitel 0), eine zweistufige Strategie einzuführen. Bei dieser Strategie würden die Werte von Alpha und Beta nicht direkt aus den Attributen des Lagerhaltungssystems abgeleitet, sondern es würde aus dem Lagerhaltungssystem eine Stellgröße abgeleitet. Basierend auf dieser Stellgröße würden dann indirekt Werte für die Parameter Alpha und Beta bestimmt. Eine Verbesserung gegenüber der direkten Vorhersage von Alpha bzw. Beta könnte durch eine zweistufige Strategie erreicht werden.

8 Literaturverzeichnis

Berners - Lee, T. (2005): Autokorrelationsanalyse. Uni Dortmund. Internet Ressource, eingesehen am 25.04.2006,

http://berners-lee.physik.uni-dortmund.de/praktikum/F_Anleitungen/V58.pdf

Breiman, L.; Friedman, J. H.; Olshen, R. A. und Stone, C. J. (1984): Classification and Regression Trees. Belmont, CA. Wadsworth, 1984.

Duhme, M. (2005): Ansätze zur Konstruktion von Entscheidungsbäumen. Studienarbeit, TU-Braunschweig. Einsehbar am Lehrstuhl für Wirtschaftsinformatik der TU-Braunschweig.

Gehrke, J.; Ramakrishnan, R. und Ganti, V. (1998): Rainforest - a framework for fast decision tree construction of large datasets. Data Mining and Knowledge Discovery, 1998, 4(2/3), pages 127-162.

Han, J. und Kamber, M. (2001): Data Mining: Concepts and Techniques. Morgan Kaufmann, San Francisco, CA, 2001, pages 279-296.

Hand, D. J. (1997): Construction and Assessment of Classification Rules. John Wiley & Sons, Chichester, England, 1997.

Hand, D.; Mannila, H. und Smyth, P. (2001): Principles of Data Mining. MIT Press, Cambridge, Massachusetts. Kapitel 10.

Lim, T.-S.; Loh, W.-Y. und Shih, Y.-S. (1997): An empirical comparison of decision trees and other classification methods. Technical Report 979, Department of Statistics, University of Wisconsin, Madison, June 1997.

Mattfeld, D. C. und Orth, H. (2005): The Allocation of Storage Space for Transshipment in Vehicle Distribution. Working paper, Universität Braunschweig und Universität Hamburg.

Mehta, M.; Agrawal, R. und Rissanen, J.(1996): SLIQ: A fast scalable classifier for data mining. In Proceedings of International Conference on Extending Database Technology; 1996, pages 18-32.

Michie, D.; Spiegelhalter, D.J. und Taylor, C.C. (1994): Machine learning: neural and statistical classification. Ellis Horwood, London, 1994.

Murthy, S. K. (1995): On growing better decision treesfim data. PhD thesis, Department of Computer Science, Johns Hopkins University, Baltimore, Maryland 1995.

Murthy, S. K. (1998): Automatic construction of decision trees from data: A MultiDisciplinary Survey. Data Mining and Knowledge Discovery; 1998, Vol. 2, pages 345-389.

Orth, H. (2005): Modellierung und Verfahren zur Nivellierung des Personalbedarfs für den Kfz-Umschlag. Diplomarbeit, Universität Hamburg.

o. V. (1999): Time Series and Forecasting. SPSS Inc., Training Department. Internet Ressource, eingesehen am 22.02.2006, http://www.ts.vcu.edu/manuals/spss/guides/Time%20Series%20and%20Forecasting.pdf

o. V. (2004): Hilfe zum SPSS – Softwarepaket. SPSS Inc.

Quante, H. U. (2005): Seminar Methoden empirischer Sozialforschung und programmgestützte Datenanalyse für Sozialwissenschaftler. TU-Braunschweig. Internet Ressource, eingesehen am 04.04.2006, http://rz-cgi.tu-bs.de/spssseminar/spss-kap4.6.html.

Shafer, J.; Agrawal, R. und Mehta, M. (1998): SPRINT: A scalable parallel classifier for data mining. In Proceedings of 22nd International Conference on Very Large Data Bases (1996), pages 544-555.

Wikipedia.org (2006): Enzyklopädie. Internet Ressource, eingesehen am 29.03.2006, http://de.wikipedia.org/.

Wissen.de (2006): Onlinelexikon. Wissen Media Verlag. Internet Ressource, eingesehen am 19.05.2006, http://www.wissen.de/.

Hiermit erkläre ich an Eides Statt, dass ich die vorliegende Arbeit selbstständig verfasst und keine anderen als die angegebenen Quellen und Hilfsmittel verwendet habe.

Braunschweig, im Mai 2006

Moritz Duhme

Persönliche Angaben des Verfassers

Vorname: Moritz

Name: Duhme

Studiengang: Wirtschaftsinformatik

Matrikelnummer: 2666156,

Telefonnummer: 0179 – 780 91 94

E-Mail-Adresse: [e-mail]

[...]

---

^[1] Vgl. Mattfeld und Orth (2005).

^[2] Vgl. Mattfeld und Orth (2005).

^[3] Vgl. Wikipedia.org (2006).

^[4] Vgl. Mattfeld und Orth (2005), S. 10.

^[5] Vgl. Mattfeld und Orth (2005), S.14.

^[6] Vgl. Mattfeld und Orth (2005), S.14.

^[7] Vgl. Mattfeld und Orth (2005), S.14.

^[8] Vgl. Mattfeld und Orth (2005), S.19.

^[9] Vgl. Mattfeld und Orth (2005), S.20.

^[10] Vgl. Mattfeld und Orth (2005), S.20.

^[11] Vgl. Wikipedia.org (2006).

^[12] Vgl. Han und Kamber (2001).

^[13] Vgl. Hand (2001).

^[14] Vgl. Michie, Spiegelhalter und Taylor (1994) sowie Hand (1997).

^[15] Vgl. Breiman, Friedman, Olshen und Stone (1984).

^[16] Vgl. Breiman, Friedman, Olshen und Stone (1984) sowie Mehta, Agrawal und Rissanen (1996).

^[17] Vgl. Michie, Spiegelhalter und Taylor (1994) sowie Murthy (1995) und Lim, Loh und Shih (1997).

^[18] Vgl. Han und Kamber (2001).

^[19] Vgl. Han und Kamber (2001).

^[20] Vgl. Mattfeld und Orth (2005), S.21.

^[21] Vgl. Mattfeld und Orth (2005), S.13.

^[22] Vgl. Quante (2005), Kapitel 4.6 bzw. o.V. (2004).

^[23] Vgl. Mattfeld und Orth (2005), S.13.

^[24] Vgl. o.V. (2004).

^[25] Vgl. Wikipedia.org (2006).

^[26] Vgl. Wikipedia.org (2006).

^[27] Vgl. Wikipedia.org (2006).

^[28] Vgl. Quante (2005), Kapitel 4.6.

^[29] Vgl. Wikipedia.org (2006).

^[30] Vgl. Berners-Lee (2005), S. 1.

^[31] Vgl. o. V. (1999), S. 110.

^[32] Vgl. o. V. (1999), S. 112.

^[33] Vgl. Wissen.de (2006).

^[34] Vgl. Mattfeld und Orth (2005), S.13.

^[35] Vgl. Mattfeld und Orth (2005), S.15.

^[36] Vgl. Duhme (2005).

^[37] Software verfügbar unter www.spss.com.

^[38] Vgl. o. V. (2004).

^[39] Vgl. o. V. (2004).

^[40] Vgl. o. V. (2004).

^[41] Vgl. Duhme (2005).

^[42] Vgl. Mattfeld und Orth (2005), S.19.

^[43] Vgl. Mattfeld und Orth (2005).

^[44] Vgl. Mattfeld und Orth (2005), S.13.

• Université: Technical University of Braunschweig (Institut für Wirtschaftswissenschaften, Abteilung Allg. BWL, insbes. Wirtschaftsinformatik)
• Cours: Wirtschaftsinformatik
• Note: 1,0
• Auteur: Moritz Duhme (Auteur)
• Année de publication: 2006
• Pages: 110
• N° de catalogue: V111116
• ISBN (ebook): 9783640092130
• ISBN (Livre): 9783640121373
• Langue: allemand
• mots-clé: Management, Verladeterminals, Entscheidungsbäumen, Wirtschaftsinformatik