Titelaufnahme

Titel
Squeaky wheel optimization / von Martin Nussbaumer
Verfasser/ VerfasserinNussbaumer, Martin
Begutachter / BegutachterinPferschy, Ulrich
Erschienen2008
UmfangIV, 119 S. : Zsfassung
HochschulschriftGraz, Univ., Diss., 2008
Anmerkung
Zsfassung in dt. und engl. Sprache
SpracheDeutsch
Bibl. ReferenzOeBB
DokumenttypDissertation
Schlagwörter (DE)Heuristik / SWO / traveling salesman / mehrdimensionales Rucksackproblem
Schlagwörter (EN)heuristics / SWO / traveling salesman / multidimensional knapsack problem
Schlagwörter (GND)Rucksackproblem / Metaheuristik / Travelling-salesman-Problem / Metaheuristik / Rucksackproblem / Metaheuristik / Online-Publikation / Travelling-salesman-Problem / Metaheuristik / Online-Publikation
URNurn:nbn:at:at-ubg:1-169 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Squeaky wheel optimization [1.2 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

Ziel der vorliegenden Arbeit ist es, "Squeaky Wheel Optimization" (SWO), ein modernes, iteratives, metaheuristisches Verfahren, weiterzuentwickeln und neue Anwendungsgebiete zu erschließen. Bisherige Anwendungen erfuhr SWO hauptsächlich im Bereich der Fertigungsplanung, wo vielversprechende Erfolge erzielt wurden, aber auch als Teilsystem von komplexeren Optimierungssystemen.Diese Arbeit beschreibt die erstmalige Anwendung von SWO mittels neu definierter Methoden im Rahmen zweier klassische Themen der kombinatorischen Optimierung: einerseits das Problem des Handlungsreisenden, andererseits das mehrdimensionale Rucksackproblem. Beide Problemstellungen sind als NP-schwer bekannt und es liegen Probleminstanzen vor, die zuvor bereits von einer Vielzahl von Optimierungsverfahren gelöst wurden. Die dabei erzielten Lösungswerte dienen den experimentellen Studien dieser Arbeit als Referenzwerte.Die Forschungen im Rahmen des mehrdimensionale Rucksackproblems stellen den Hauptteil dieser Arbeit dar. Zuerst wird der Ansatz der Implementierung vorgestellt und - untermauert durch experimentelle Studien - Schritt für Schritt weiterentwickelt. Zentraler Punkt ist hierbei der "Core"-Ansatz, welcher die Idee verfolgt, sich auf den tatsächlich "harten Kern" der jeweiligen Problemstellung zu konzentrieren. Es wird gezeigt, wie eine Kombination aus SWO und dem Core-Ansatz aussehen kann und wie drastisch Laufzeiten dadurch vermindertwerden können. In weiterer Folge können die Laufzeiten durch eine Zeitbudgetierung noch einmal verkürzt werden.Unter dem Strich wird eine neue Herangehensweise an klassische Problemstellungen der kombinatorischen Optimierung vorgestellt und in weiterer Folge dargelegt, wie anpassungsfähig dieses Verfahren im Hinblick auf seine Laufzeit ist. Weiters werden Problemfelder aufgeworfen und analysiert, wo der Einsatz sinnvoll ist und aufgrund welchen Gegebenheiten das Verfahren scheitern kann.

Zusammenfassung (Englisch)

The main intention of this thesis is to further improve a modern, iterative, metaheuristic optimization named "Squeaky Wheel Optimization" (SWO). Previously, SWO was applied in the field of scheduling problems with promising results, but also as a subpart of sophisticated optimization frameworks.This thesis describes an all-new and previously unknown approach to apply SWO to solve two of the very classic problems in combinatorial optimization, the traveling salesman problem and the multidimensional knapsack problem, both known to be NP-hard. Thereby, this thesis outlines new There are sets of problem instances for both optimization problems that have been established as benchmark instances in successive literature. The experimental part of this thesis refers to solution values found by other optimization techniques for these benchmark instances.The main part of this research focuses on the multidimensional knapsack problem. At first, the strategy of implementation is outlined and investigated in experimental studies. In the next part of the dedicated chapter, SWO is stepwise improved by further extensions. Key extension is the so-called "Core"-concept. This concept follows the idea to concentrate on the "core part" of the underlying optimization problem, while leaving parts of minor interest aside. A significant reduction in terms of runtime demand of SWO is the result. Subsequently, a time-budget is imposed so that the runtime demand is further reduced.Summarized, this thesis presents a new approach in combinatorial optimization and outlines the flexibility and adaptability of this optimization technique with respect to the runtime demand. Difficulties and challenges of implementation are analyzed and it is discussed why SWO may fail. In the end, possible fields of applications are shown.