Das Briefträgerproblem: Konstruktionsverfahren und Nachbarschaftssuche

ISBN-13: 9783640865208 / Niemiecki / Miękka / 2011 / 70 str.

Lars Laboch

Opis

Studienarbeit aus dem Jahr 2003 im Fachbereich BWL - Unternehmensforschung, Operations Research, Note: 1,7, FernUniversitat Hagen (FB WiWi, insbes. Operations Research), Veranstaltung: Seminar: Intelligente Strategien in Theorie und Praxis, 29/30 Jan. 2004 in Hagen, Sprache: Deutsch, Abstract: Zusammenfassung / Abstract Das Brieftragerproblem wurde 1962 erstmals von dem chinesischen Mathematiker Mei-Ko Kwan formuliert und ist dem Bereich kombinatorischer Optimierungsprobleme zuzuordnen. Der Brieftrager mu in einem bestimmten Gebiet die Post fur nahezu alle Haushalte verteilen. Um dies zu erreichen mussen alle Straen oder Wege innerhalb seines Gebietes mindestens einmal durchlaufen werden. Start- und Endpunkt der Tour ist das Postamt. Gesucht ist eine Rundreise auf der jede Strae oder jeder Weg genau einmal durchlaufen wird, da dies eine kostenminimale Tour darstellt. Eine solche Tour ist aber nicht immer gegeben. In einem solchen Fall mu der Brieftrager bereits abgearbeitete Teilstrecken erneut durchlaufen. Die Optimierungsaufgabe besteht darin, die Kosten dieser unproduktiven Teilstrecken zu minimieren. In bezug auf das zugrundeliegende Straen- bzw. Wegenetz ergibt sich eine Dreiteilung des Brieftragerproblems. Es konnen zum Beispiel nur Straen oder Wege vorliegen die frei in beide Richtungen passierbar sind. Ebenfalls konnen auch nur Einbahnstraen vorhanden sein, oder es kann ein Mix aus beiden gegeben sein. Die ersten beiden Varianten sind gut mit exakten Algorithmen aus dem Bereich der Graphentheorie zu losen. Bei einem Mix aus frei passierbaren Straen und Einbahnstraen stoen diese Verfahren jedoch an ihre Grenzen. Fur die Losung dieser Problemauspragung sind sogenannte Meta-Heuristiken gut geeignet. Diese Methoden konnen selbstverstandlich auch auf die beiden zuerst genannten Problemformulierungen anwendet werden. Sowohl Losungsansatze unter Verwendung von Meta-Heuristiken als auch durch Zuhilfenahme klassischer Methoden der Graphentheorie werde