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 Cicero betritt die politische Bühne by Christian Hippe
Cover of the book Auffinden und Markieren von Regionen in einem Binärbild by Christian Hippe
Cover of the book Das rhetorische Kommunikationsverfahren 'Kritisieren' by Christian Hippe
Cover of the book Vergleich lerntheoretischer Forschungsrichtungen und ihrer Lernprogramme by Christian Hippe
Cover of the book Vaterlosigkeit und weiblicher Heroismus am Beispiel von Kleists 'Penthesilea' und Schillers 'Jungfrau von Orleans' by Christian Hippe
Cover of the book Afroamerikanisches Christentum zwischen Protest und Assimilation - Studien zu Texten vor dem Bürgerkrieg by Christian Hippe
Cover of the book Wissensmanagement im Nonprofit-Bereich - Barrieren und deren Überwindung by Christian Hippe
Cover of the book Der Unterricht mit Kindern mit Migrationshintergrund by Christian Hippe
Cover of the book Der Rational-Choice-Ansatz zur Erklärung von Bildungsverhalten by Christian Hippe
Cover of the book Sport und Migräne by Christian Hippe
Cover of the book Funktionaler Analphabetismus - ein Problem und seine Ursachen by Christian Hippe
Cover of the book Die Wichtigkeit der Elternarbeit in der Grundschule unter besonderer Berücksichtigung des Elternabends by Christian Hippe
Cover of the book Verfilmung als ergänzende Dimension. 'Tristana' bei Benito Pérez Galdós und Luís Buñuel by Christian Hippe
Cover of the book Die Institutionalisierung des Lebenslaufs by Christian Hippe
Cover of the book Umsetzung der Kinästhetik in den Stationsalltag 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