Leseprobe
Inhaltsverzeichnis
Darstellunsverzeichnis
Abkürzungsverzeichnis
Symbolverzeichnis
1 Einleitung
2 Die Tabusuche
2.1 Einordnung der Tabusuche
2.2 Der Tabusuche-Algorithmus
2.2.1 Idee
2.2.2 Lösungsschritte
2.2.3 Modellierung
2.3 Bewertung und Anwendung der Tabusuche
3 Das Warehouse-Location-Problem
3.1 Einordnung des Warehouse-Location-Problems
3.2 Problemformulierung
4 Anwendung der Tabusuche auf das Warehouse-Location-Problem
4.1 Verfahren zur Lösung des Warehouse-Location-Problems
4.2 Ein Tabusuche-Algorithmus zur Lösung des Warehouse-Location-Problems
4.2.1 Idee
4.2.2 Lösungsschritte
4.2.3 Datenstrukturen
4.2.4 Ablauf des Algorithmus am Beispiel
5 Zusammenfassung und Fazit
A Anhang
Literaturverzeichnis
Darstellunsverzeichnis
Tab. 4.1 Im Beispiel gegebene Transportkosten
Tab. 4.2 Im Beispiel gegebene fixe Kosten
Abb. 4.3 Startlösung im Beispiel
Abb. 4.4 Beste Lösung im Beispiel
Abb. A.1 Schritte bei der Tabusuche
Abb. A.2 Schritte des Tabusuche-Algorithmus von Michel und van Hentenryck
Tab. A.3 Ablauf des Algorithmus am Beispiel
Tab. A.4 Ermittlung des besten Zielfunktionswerts der Nachbarschaft im Beispiel
Abkürzungsverzeichnis
Abbildung in dieser Leseprobe nicht enthalten
Symbolverzeichnis
Abbildung in dieser Leseprobe nicht enthalten
1 Einleitung
In den Medien sind seit längerem Meldungen wie diese zu lesen:
”PostbautgrößtesdeutschesPaketzentrum.[...]NachAngabenderPost sollen in dem für einen zweistelligen Millionenbetrag errichteten 40.000 Qua- dratmeter großen Gebäude pro Stunde einmal 50.000 Sendungen sortiert wer- den. Der Neubau ist demnach Teil einer Gesamtinvestition von 750 Millionen Euro, mit der die Post ihr Paketnetzwerk modernisieren und ausbauen will.“1
”SiemenshatweitereStreichpläneseinesmilliardenschwerenSparpro- gramms bekannt gegeben. So sollen an verschiedenen deutschen Standorten Hunderte Arbeitsplätze wegfallen. Der Schaltanlagenbau Leipzig solle bis Mai[2014] geschlossen werden.“2
Diese Meldungen handeln von Standortentscheidungen, d. h. von Standortöffnungen und -schließungen. Da es auf dem Markt meist eine Vielzahl von Anbietern gibt, welche versuchen, den Kunden ihre Produkte zu verkaufen, herrscht ein massiver und steigen- der Wettbewerbsdruck und Unternehmen sind angehalten, ihre Kosten so gering wie möglich zu halten. Diese Tatsache trägt ebenso wie Veränderungen des Marktes und in der Bevölkerung dazu bei, dass Unternehmen ständig gezwungen sind, ihre Standort- struktur zu untersuchen und anzupassen. Die Eröffnung eines neuen Standortes ist mit hohen Investitionen verbunden und kann, wenn überhaupt, nur mit großem Aufwand rückgängig gemacht werden. Somit hat sie einen tiefgreifenden Einfluss auf die lang- fristige Unternehmensentwicklung. Aus diesem Grund sollte die Standortwahl gründlich untersucht und organisiert werden.
Viele Wissenschaftler haben sich bereits dieser Aufgabenstellung angenommen und verschiedene quantitative Modelle und Algorithmen entwickelt, um mit möglichst ge- ringem Aufwand sehr gute Lösungen zu generieren. Beim Warehouse-Location-Problem (WLP) sollen Depots zur Belieferung von Kunden so aus einer Menge potenzieller Depot- standorte ausgewählt werden, dass die Gesamtkosten minimiert werden. Die Tabusuche
1 EINLEITUNG 2
hat sich dafür als schnelles, effizientes und robustes Verfahren, herausgestellt, das mit großer Häufigkeit Lösungen von sehr guter Qualität liefert. Diese Arbeit untersucht die Anwendung dieses Verfahrens auf das Warehouse-Location-Problem..
Zunächst wird in Kapitel 2 eine Einordnung der Tabusuche vorgenommen, der zu- gehörige Lösungsalgorithmus erläutert und das Verfahren bewertet. Kapitel 3 umfasst die Einordnung und Formulierung des Warehouse-Location-Problems. Anschließend wer- den in Kapitel 4 verschiedene Verfahren zur Lösung dieses Problems aufgezeigt und der Tabusuche-Algorithmus von Michel und van Hentenryck für das unkapazitierte Warehouse-Location-Problem allgemein und am Beispiel beschrieben. Die Arbeit schließt in Kapitel 5 mit einer Zusammenfassung der Ergebnisse und einem Ausblick, welche Möglichkeiten sich durch die Anwendung der Tabusuche auf das Warehouse-Location- Problem in Zukunft ergeben könnten.
2 Die Tabusuche
2.1 Einordnung der Tabusuche
Die Tabusuche gehört zu den metaheuristischen Verfahren. Eine Metaheuristik ist ein allgemeiner, nicht problemspezifischer, iterativ ablaufender Prozess, bei dem durch untergeordnete Heuristiken die näherungsweise Lösung eines Optimierungsproblems ermittelt wird. Die einzelnen Stufen müssen problemspezifisch implementiert werden.1
Metaheuristiken werden zur Lösung kombinatorischer Optimierungsprobleme in Wis- senschaft und Wirtschaft z. B. bei der Tourenplanung oder der Stundenplanung in Schu- len eingesetzt.2 Die Berechnung der optimalen Lösung solcher Probleme ist meist nicht effizient, da es mit zunehmender Größe des Problems eine sehr große Anzahl von Lösungs- möglichkeiten gibt und deren Berechnung viel Zeit kostet. Seit den 1970er Jahren werden deshalb metaheuristische Verfahren entwickelt, die mit vertretbarem Rechenaufwand ei- ne näherungsweise Lösung des Optimierungsproblems erzeugen sollen.3
Die Tabusuche wurde zuerst 1986 von Glover4 und Hansen5 unabhängig voneinander untersucht und veröffentlicht. Seitdem haben viele Wissenschaftler sie weiter erforscht und auf verschiedene Problemstellungen angewendet.
Weitere metaheuristische Lösungsverfahren sind z. B. die Simulierte Abkühlung, Genetische und Evolutionäre Algorithmen.6
2.2 Der Tabusuche-Algorithmus
2.2.1 Idee
Es liegt ein Optimierungsproblem beschreibbar als Maximierungs- oder Minimierungsproblem mit einer Bewertungsfunktion vor.
Ein ähnliches, einfacheres Verfahren als die Tabusuche ist die Lokale Suche. Dabei
2.2 DER TABUSUCHE-ALGORITHMUS 4
wird in jeder Iteration die Lösung im Bereich der Nachbarschaft verbessert, bis ein lo- kales Optimum gefunden ist. Das Problem der Lokalen Suche besteht darin, dass das zuerst gefundene lokale Optimum als finale Lösung gewählt wird, obwohl es eine bessere Lösung geben kann. Auch die Tabusuche ist eine Form der Lokalen Suche, da in der Nachbarschaft der aktuellen Lösung nach weiteren Lösungen gesucht wird.7
Dabei wird aber nicht nur die aktuelle Nachbarschaft der Lösung in Betracht gezogen, sondern auch der bisherige Verlauf. Zu diesem Zweck wird eine Tabuliste geführt, die die Zwischenlösungen oder Züge, die zu diesen Lösungen geführt haben, speichert und sie für die kommenden Schritte tabu setzt. Dadurch verläuft die Suche nicht im Kreis zwischen lokalen Optima, denn irgendwann ist der gesamte Bereich um das Optimum tabu und die Suche muss in anderem Bereich des Lösungsraums fortgesetzt werden. Um Speicher- und Rechenaufwand gering zu halten, wird die Länge der Tabuliste auf eine konkrete Anzahl der letzten Züge beschränkt. Die Tabuliste wird stets nach dem FIFO-Prinzip geführt, weil der am längsten in der Liste enthaltene Eintrag zuerst durch einen neuen Eintrag ersetzt wird, wenn die Liste die maximale Anzahl an Einträgen enthält.8 Des Weiteren können Aspirationskriterien existieren. Das sind Kriterien, die dazu beitragen, dass Lösungen, die zwar tabu aber sinnvoll sind, trotzdem betrachtet werden.9
2.2.2 Lösungsschritte
Der allgemeine Ablauf der Tabusuche kann anhand von Abb. A.1 nachverfolgt werden.
1. Startlösung
Eine Startlösung wird entweder durch einen geeigneten Algorithmus oder zufällig erzeugt und zur aktuellen sowie zur besten Lösung deklariert.
2. Überprüfung des Abbruchkriteriums
Ist das Abbruchkriterium erfüllt, bricht das Verfahren ab und nimmt die beste Lösung in das Langzeitgedächtnis auf bzw. gibt die beste Lösung als finale Lösung aus. Abbruchkriterium kann eine maximale Rechenzeit oder eine maximale Anzahl von Iterationen sein.10 Möglich ist auch eine maximale Anzahl von Iterationen ohne Verbesserung oder das Erreichen eines vorher festgelegten Werts der Bewertungsfunktion.11
3. Nachbarschaft der aktuellen Lösung
2.2 DER TABUSUCHE-ALGORITHMUS 5
Die Nachbarschaft der aktuellen Lösung wird ermittelt und für jeden Nachbarn, der Wert der Bewertungsfunktion berechnet. Die Nachbarschaft ”umfasstalleLösungen,die durch eine elementare Transformation der [aktuellen] Lösung erzeugt werden können“.12
4. Wahl des besten zulässigen Nachbarn
Anschließend wird der Nachbar mit dem besten Wert der Bewertungsfunktion ausgewählt, es sei denn er steht auf der Tabuliste. Dieser Wert kann auch schlechter als der der aktuellen Lösung sein, um im gesamten Lösungsraum nach besseren Lösungen zu suchen und nicht in einem lokalen Optimum zu verweilen. Der gewählte Nachbar wird zur aktuellen Lösung erklärt. Eine solche Veränderung heißt Zug.13
5. Aktualisierung der Tabuliste
Die aktuelle Lösung wird in die Tabuliste aufgenommen. Verbessert sie die bisher beste Lösung, wird sie zur besten Lösung erklärt. In jedem Fall wird mit Schritt 2 fortgesetzt.
2.2.3 Modellierung
Die Tabusuche ist ein flexibles Verfahren, denn Bewertungsfunktion, Nachbarschaftsbeziehungen, Aspirationskriterien und Speicherparameter können problemindividuell modelliert werden. Die Bewertungsfunktion ist für die Güte der Lösung verantwortlich. Die Nachbarschaftsbeziehungen bestimmen die Richtung der Suche. Aspirationskriterien können z. B. nur Züge zulassen, die die aktuell beste Lösung verbessern oder auch andere Eigenschaften der Züge beachten.14
Bei der Tabusuche existieren zwei verschiedene Strategien, die im Wechsel eingesetzt werden sollten. Die Streuungsstrategie erzeugt unterschiedliche Lösungen, um Überblick über den Suchraum zu erlangen. Die Intensivierungsstrategie verbessert hingegen besonders gute Lösungen durch intensive Suche.15
Im Speicher werden die Parameter Recency, Frequency, Quality und Influence gespeichert. Recency ist zwingender Bestandteil eines Tabusuche-Algorithmus. Die anderen drei Parameter sind mögliche Erweiterungen.16
Recency, das Kurzzeitgedächtnis bzw. die Tabuliste, verhindert Zyklen und das Ver- harren in lokalen Optima. Ist sie kurz, wird intensiv in einem kleinem Bereich gesucht. Ist sie hingegen groß, wird ein großer Bereich nach Lösungen ergründet. Allerdings wird dadurch irgendwann der komplette Suchbereich tabu erklärt und eine Intensivierung ist
2.3 BEWERTUNG UND ANWENDUNG DER TABUSUCHE 6
schlecht möglich. Deshalb sollte die Größe der Tabuliste während Suche variiert werden.17 Frequency, das Langzeitgedächtnis, speichert alle Züge bzw. Lösungen und wie oft sie bereits verwendet wurden. Quality, das Qualitätsgedächtnis speichert besonders gute Lösungen, um von ihnen aus das Rechnen fortzusetzen. Das sind solche Lösungen mit geringem maximalen Abstand zur bisher besten Lösung. Influence speichert die jeweiligen Verbesserungen der einzelnen Züge.18
Die Tabusuche ist ein flexibles Verfahren, welches für viele Gebiete von Optimierungs- problemen geeignet ist.19 Sie ist leicht programmierbar und erfordert nur geringen Re- chenaufwand. Die Tabusuche ist eine der effizientesten Metaheuristiken, da sie Lösungen von hoher Qualität in relativ kurzer Zeit erzeugt.20 Großer Aufwand bei der Tabusuche erfordert das Anfertigen und Aktualisieren der Tabuliste und die Überprüfung des Zuges auf Gültigkeit. Außerdem ist die Festlegung der geeigneten Länge der Liste schwierig.21
Zwei ungelöste Probleme bei der Tabusuche sind Sackgassen und Plateaus. In einer Sackgasse befindet sich das Verfahren, wenn es in einen Zustand gelangt, zu dem es keine gültigen Nachbarschaften gibt, weil alle möglichen Nachbarn in der Tabuliste sind. Möglichkeiten zur Behebung des Problems könnten sein, die aktuelle Lösung als Endwert zu benutzen oder die älteste Lösung aus der Tabuliste zu entfernen, bis wieder eine gültige Nachbarschaft existiert. Ein weiteres Problem besteht, wenn die Bewertungsfunktion Plateaus enthält, d. h. der Wert der Bewertungsfunktion für alle Nachbarn gleich ist. Dadurch kann die Suche im Kreis verlaufen.22
Dennoch wird die Tabusuche heute für unterschiedliche Problemstellungen eingesetzt. Hauptanwendungsgebiete sind Produktionsplanung und logistische Probleme wie das Travelling Salesman Problem oder das Warehouse-Location-Problem.23 Erforscht wird der Einsatzes des Verfahrens z. B. in den Bereichen Multiprozessorsysteme, Verteilte Systeme und Embedded-Systeme.24 Häufig wird die Tabusuche auch mit einem anderen metaheuristischen Optimierungsverfahren wie dem Genetischen Algorithmus kombiniert, um noch bessere Ergebnisse zu generieren.25
3 Das Warehouse-Location-Problem
Nachfolgendes Kapitel ist in Anlehnung an Lasch verfasst.1
3.1 Einordnung des Warehouse-Location-Problems
Das Warehouse-Location-Problem wird im Rahmen der Standortplanung untersucht. Diese beschäftigt sich mit der optimalen räumlichen Lokalisierung von Standorten eines Unternehmens. Ein Standort ist der Ort der gewerblichen Niederlassung eines Unternehmens. Die Wahl eines Standorts hat langfristig großen Einfluss auf das Unternehmen und seine zukünftige Entwicklung. Die Standortplanung wird der strategischen Planungsebene zugeordnet, weil sie die räumliche Struktur des Logistiksystems bestimmt und Auswirkungen auf alle Güterflüsse im Netzwerk hat.
Grundsätzlich wird die Standortplanung nach volkswirtschaftlicher, betrieblicher und innerbetrieblicher Perspektive unterschieden. Im Folgenden wird lediglich die betriebli- che Standortplanung betrachtet, die Fragen der Standortwahl von Unternehmensnieder- lassungen wie Produktionsstätten, Warenlagern, Umschlagpunkten und Handelsfilialen untersucht.
Sie wird wiederum in Standortplanung in der Ebene, Standortbestimmung im Netz- werk und diskrete Standortplanung unterteilt. Das Warehouse-Location-Problem ist der diskreten Standortplanung zuzuordnen, bei der die Standorte aus einer bereits untersuch- ten und eingeschränkten Menge potenzieller Standorte ausgewählt werden. Die Begriffe Warehouse und Location kommen aus dem Englischen und werden mit Depot, Depot- standort, Lagerhaus oder Warenlager bzw. mit Ort oder Standort übersetzt.
Einige Autoren verwenden anstelle des Begriffs Warehouse-Location-Problem den Begriff Facility-Location-Problem (FLP), wobei Facility zu deutsch Einrichtung heißt. Andere Autoren setzen ersteres mit der Standortbestimmung für Auslieferungslager und letzteres mit der für Produktionsstätten gleich.2
[...]
1 stern.de (22.10.2012): Post baut größtes deutsches Paketzentrum.
2 Westdeutsche Allgemeine Zeitung (2013): Siemens will Werke schließen und Stellen ins Ausland verlagern.
1 Vgl. Kruse (2008): Evolutionäre Algorithmen, S. 3 f.
2 Vgl. Heppner (2005): Tabu-Search, S. 1.
3 Vgl. Bott (2006): Statische Ablaufplanung, S. 3.
4 Vgl. Glover (1989): Tabu search-part I sowie Glover (1990): Tabu search-part II .
5 Vgl. Hansen (1986): The Steepest Ascent Mildest Descent Heuristic for Combinatorial Programming.
6 Vgl. Heppner (2005): Tabu-Search, S. 1.
7 Vgl. Tahir (2008): Feature Selection, S. 74.
8 Vgl. Mayer (1998): Projektplanung bei beschränkten Ressourcen, S. 92.
9 Vgl. Heppner (2005): Tabu-Search, S. 2.
10 Vgl. Lasch (2012): Strategisches und operatives Logistikmanagement , S. 133.
11 Vgl. Tahir (2008): Feature Selection, S. 76.
12 Vgl. Mayer (1998): Projektplanung bei beschränkten Ressourcen, S. 89.
13 Vgl. Lasch (2012): Strategisches und operatives Logistikmanagement , S. 132.
14 Vgl. Heppner (2005): Tabu-Search, S. 2.
15 Vgl. ebd.
16 Vgl. Nagl (2008): Die Tabu-Suche, S. 19 f.
17 Vgl. Nagl (2008): Die Tabu-Suche, S. 19 f.
18 Vgl. Heppner (2005): Tabu-Search, S. 2.
19 Vgl. Nagl (2008): Die Tabu-Suche, S. 22.
20 Vgl. Pirim (2008): Tabu Search, S. 1.
21 Vgl. Stübbe (2009): Wartung und Instandhaltung, S. 354.
22 Vgl. Nagl (2008): Die Tabu-Suche, S. 7.
23 Vgl. Pirim (2008): Tabu Search, S. 17.
24 Vgl. Nagl (2008): Die Tabu-Suche, S. 20 f.
25 Vgl. ebd., S. 21.
1 Vgl. Lasch (2012): Strategisches und operatives Logistikmanagement , S. 187-236.
2 Vgl. Maßmann (2006): Kapazitierte stochastisch-dynamische Facility-Location-Planung, S. 37.