In vielen Bereichen unserer Umwelt haben wir es mit Problemstellungen zu tun, die sich bei näherer Untersuchung als komplexe Optimierungsprobleme darstellen. Im betrieblichen Bereich handelt es sich dabei beispielsweise um die Produktionsplanung, die Investitionsplanung und die Tourenplanung.<p>Im außerbetrieblichen Bereich kann das Füllen eines Reisekoffers mit verschiedenen Gegenständen genannt werden. In den genannten Fällen ist es oft möglich, die gestellte Aufgabe mathematisch als ganzzahliges, lineares Optimierungsproblem zu formulieren. In solchen Fällen kann das Verfahren Tabu Search angewandt werden. Es eignet sich für eine Vielzahl von kombinatorischen Optimierungsproblemen. Der Einsatz von Tabu Search ist nicht auf einen bestimmten Problembereich beschränkt, sondern kann mit kleinen Modifikationen auf verschiedene Optimierungsprobleme angewandt werden.<br>Die Tabu Search ist ein heuristisches Verfahren zur Lösung von Optimierungsproblemen mit mehreren lokalen Optima. Es ist ein einfaches und sehr flexibles Werkzeug, mit dessen Hilfe sich nahezu optimale Lösungen, oft schon sehr schnell, ermitteln lassen [5].<p>Im Rahmen dieser Diplomarbeit wird ein Tabu Search Verfahren für das Standardproblem der Tourenplanung vorgestellt, das von Dr. A. Bortfeldt am Lehrstuhl Wirtschaftsinformatik der Fernuniversität Hagen entwickelt wurde. Ziel der Diplomarbeit ist, dieses Verfahren zu beschreiben und in Bezug auf die Lösungsqualität sowie die Performance zu erweitern.<br>Die Codierung erfolgt in der Programmiersprache C. Der Quelltext wurde mir zur Bearbeitung der Diplomarbeit von Dr. Bortfeldt zur Verfügung gestellt.<p>Zunächst wird in Kapitel 2 die Tabu Search Heuristik ausführlich vorgestellt.<br>In Kapitel 3 wird das Tourenplanungsproblem und seine Varianten beschrieben.<br>Kapitel 4 ist dem Tabu Search Verfahren von Bortfeldt gewidmet. Es folgt eine Beschreibung des Verfahrens sowie der Versuch die Performance und die Lösungsqualität zu verbessern. Dabei werden verschiedene Programmversionen und ihre Ergebnisse präsentiert.<p>Zum Ende soll aus den gewonnenen Erkenntnissen ein Verfahren entwickelt werden, das den Anforderungen an Performance und Lösungsqualität gerecht wird. Um eine Bewertung der erzielten Ergebnisse zu ermöglichen, wird das Verfahren auf Standard-Problemsets angewendet. |
