Optimierung mittels Nachbarschaftssuche am Beispiel des Rundreiseproblems

Business & Finance, Management & Leadership, Production & Operations Management
Cover of the book Optimierung mittels Nachbarschaftssuche am Beispiel des Rundreiseproblems by Christian Hippe, GRIN Verlag
View on Amazon View on AbeBooks View on Kobo View on B.Depository View on eBay View on Walmart
Author: Christian Hippe ISBN: 9783638418058
Publisher: GRIN Verlag Publication: September 15, 2005
Imprint: GRIN Verlag Language: German
Author: Christian Hippe
ISBN: 9783638418058
Publisher: GRIN Verlag
Publication: September 15, 2005
Imprint: GRIN Verlag
Language: German

Studienarbeit aus dem Jahr 2004 im Fachbereich BWL - Beschaffung, Produktion, Logistik, Note: 1,7, Universität Paderborn, 12 Quellen im Literaturverzeichnis, Sprache: Deutsch, Abstract: Das Rundreise- oder auch Travelling Salesman Problem ist eines der bekanntesten Probleme der kombinatorischen Optimierung. Leicht zu verstehen und daher häufig vorschnell als einfach lösbar eingestuft, stellte und stellt es die Wissenschaft immer noch vor große Herausforderungen, denn die Ergebnisfindung gestaltet sich schon bei geringer Problemgröße aufgrund sehr großer Lösungsräume als äußerst schwierig. Die Nachbarschaftssuche ist ein heuristisches Verfahren, das sehr gut zur Ermittlung der Lösung eines Rundreiseproblems eingesetzt werden kann. Durch den Vergleich verschiedener alternativer Lösungen erfolgt eine schrittweise Annäherung an das optimale Ergebnis, das in einer Minimierung der Reisekosten liegt. Dieses Prinzip machen sich alle in dieser Arbeit vorgestellten Heuristiken zu Nutze. Die Güte des Ergebnisses variiert dabei in Abhängigkeit von den jeweiligen Verfahrensregeln. In Kapitel 2 wird zunächst das Travelling Salesman Problem vorgestellt. In seiner Eigenschaft als Benchmark für Forschung und Entwicklung sind im Laufe der Zeit vor dem Hintergrund der schweren Lösbarkeit vielfältige Methoden entwickelt worden, die auf verschiedene Art und Weise zu Lösungen führen. Die bisher effizientesten und damit am häufigsten einsetzbaren Methoden sind Heuristiken, die jedoch nur annähernd optimale Ergebnisse liefern. In Kapitel 3 wird zunächst der Begriff Heuristik definiert. Im Anschluss daran folgt die Erläuterung der Systematik der Nachbarschaftssuche in ihrer Eigenschaft als Basis für heuristische Verfahren im Allgemeinen und im Hinblick auf den Zielgedanken des Rundreiseproblems. Der Darstellung eines Eröffnungsverfahrens, schließen sich in den nächsten Unterkapiteln Ausführungen zu Optimierungsverfahren an. Am Beispiel zweier r-optimaler Verfahren wird die Anwendung von reinen Verbesserungsverfahren in Bezug auf das Rundreiseproblem dargestellt. Simulated Annealing und Tabu Search dienen als Beispiele für lokale Suchverfahren im selben Kontext. Abschließend erfolgt ein kurzer Blick in das Feld der Forschung, die sich mit der Entwicklung immer neuer Varianten und Methoden von auf Nachbarschaftssuche basierenden Optimierungsverfahren beschäftigt.

View on Amazon View on AbeBooks View on Kobo View on B.Depository View on eBay View on Walmart

Studienarbeit aus dem Jahr 2004 im Fachbereich BWL - Beschaffung, Produktion, Logistik, Note: 1,7, Universität Paderborn, 12 Quellen im Literaturverzeichnis, Sprache: Deutsch, Abstract: Das Rundreise- oder auch Travelling Salesman Problem ist eines der bekanntesten Probleme der kombinatorischen Optimierung. Leicht zu verstehen und daher häufig vorschnell als einfach lösbar eingestuft, stellte und stellt es die Wissenschaft immer noch vor große Herausforderungen, denn die Ergebnisfindung gestaltet sich schon bei geringer Problemgröße aufgrund sehr großer Lösungsräume als äußerst schwierig. Die Nachbarschaftssuche ist ein heuristisches Verfahren, das sehr gut zur Ermittlung der Lösung eines Rundreiseproblems eingesetzt werden kann. Durch den Vergleich verschiedener alternativer Lösungen erfolgt eine schrittweise Annäherung an das optimale Ergebnis, das in einer Minimierung der Reisekosten liegt. Dieses Prinzip machen sich alle in dieser Arbeit vorgestellten Heuristiken zu Nutze. Die Güte des Ergebnisses variiert dabei in Abhängigkeit von den jeweiligen Verfahrensregeln. In Kapitel 2 wird zunächst das Travelling Salesman Problem vorgestellt. In seiner Eigenschaft als Benchmark für Forschung und Entwicklung sind im Laufe der Zeit vor dem Hintergrund der schweren Lösbarkeit vielfältige Methoden entwickelt worden, die auf verschiedene Art und Weise zu Lösungen führen. Die bisher effizientesten und damit am häufigsten einsetzbaren Methoden sind Heuristiken, die jedoch nur annähernd optimale Ergebnisse liefern. In Kapitel 3 wird zunächst der Begriff Heuristik definiert. Im Anschluss daran folgt die Erläuterung der Systematik der Nachbarschaftssuche in ihrer Eigenschaft als Basis für heuristische Verfahren im Allgemeinen und im Hinblick auf den Zielgedanken des Rundreiseproblems. Der Darstellung eines Eröffnungsverfahrens, schließen sich in den nächsten Unterkapiteln Ausführungen zu Optimierungsverfahren an. Am Beispiel zweier r-optimaler Verfahren wird die Anwendung von reinen Verbesserungsverfahren in Bezug auf das Rundreiseproblem dargestellt. Simulated Annealing und Tabu Search dienen als Beispiele für lokale Suchverfahren im selben Kontext. Abschließend erfolgt ein kurzer Blick in das Feld der Forschung, die sich mit der Entwicklung immer neuer Varianten und Methoden von auf Nachbarschaftssuche basierenden Optimierungsverfahren beschäftigt.

More books from GRIN Verlag

Cover of the book Wissensmanagement in Unternehmensberatungen by Christian Hippe
Cover of the book Die Darstellung der Germanen in Tacitus' 'Germania' by Christian Hippe
Cover of the book Die Kommunikation von Gehörlosen by Christian Hippe
Cover of the book Stärkt Sport das Immunsystem? by Christian Hippe
Cover of the book Aspekte sozialer Integration und Desintegration durch Medien am Beispiel deutscher und ausländischer Jugendszenen und Subkulturen by Christian Hippe
Cover of the book Inhaltszusammenfassung und Kritik zu Vera F. Birkenbihls 'Trotzdem Lehren' by Christian Hippe
Cover of the book El comportamiento no verbal. Los gestos en diferentes culturas by Christian Hippe
Cover of the book Postsecondary Education and the Ivy League: Vanguard or Foul Play? by Christian Hippe
Cover of the book The fragile state concept and the emergence of the caliphate by Christian Hippe
Cover of the book Aspekte des Spracherwerbs - Ein Überblick by Christian Hippe
Cover of the book Methoden zur Bewertung von IT-Projekten by Christian Hippe
Cover of the book Die Legion Condor. Das Ausmaß und die Bedeutung der deutschen Unterstützung General Francos im Spanischen Bürgerkrieg by Christian Hippe
Cover of the book Spracherwerb im Kleinkindalter by Christian Hippe
Cover of the book Unlocking the Revenue Potential in Kenya by Christian Hippe
Cover of the book Merkmale der Personalentwicklung bei 'Global Players' by Christian Hippe
We use our own "cookies" and third party cookies to improve services and to see statistical information. By using this website, you agree to our Privacy Policy