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 Frauen- und Männerbilder in Frauenzeitschriften by Christian Hippe
Cover of the book Die Besteuerung von verheirateten Paaren in Deutschland by Christian Hippe
Cover of the book Schlägermädchen by Christian Hippe
Cover of the book Die geteilte deutsche Eisenbahn - Schienenverkehrsströme von 1945 bis 1989 in BRD und DDR by Christian Hippe
Cover of the book Gerichtliches Mahnverfahren für Nicht-Juristen in 20 Minuten by Christian Hippe
Cover of the book Mobiler Journalismus. Handy TV by Christian Hippe
Cover of the book Individualisiertes Lernen by Christian Hippe
Cover of the book Das Wort vom leidenden Gottesknecht im Kontext der Botschaft Deuterojesajas und in der Verkündigung des Neuen Testaments by Christian Hippe
Cover of the book Die medizinische Versorgung eines römischen Legionärs by Christian Hippe
Cover of the book Net Working Capital als Instrument zur Optimierung der Unternehmensprozesse by Christian Hippe
Cover of the book Die Entwicklung der AIDS Problematik by Christian Hippe
Cover of the book Optimale Trainingssteuerung (Analyse zur Fitnesstrainer B-Lizenz) by Christian Hippe
Cover of the book Erarbeitung und Sicherung des Passé Composé mit diversen Übungen und allen Unterrichtsmaterialien by Christian Hippe
Cover of the book Jugendliche mit Migrationshintergrund im deutschen Bildungssystem by Christian Hippe
Cover of the book Biografische Muster, Lebensläufe und Lebenskonstruktionen zwischen Kontinuität und Umbruch 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