Tabu Search

Studienarbeit aus dem Jahr 2002 im Fachbereich BWL - Unternehmensforschung Operations Research Note: 13 Universität Leipzig (Institut für Empirische Wirtschaftsforschung) Veranstaltung: HS Operations Research Sprache: Deutsch Abstract: Es gibt in der Theorie einige Problemstellungen die in ihren Grundlagen leicht zu verstehen und nachzuvollziehen sind. Man denke z.B. an das Rucksackproblem1 an verschiedenste Problemstellungen der Ressourcenplanung oder auch das Problem des Handlungsreisenden2 (TSP) welches später noch genauer betrachtet wird3. In der Praxis sind solche Probleme durchaus anzutreffen wie z.B. beim Beladen von Containern der Stunden- und Raumplanung einer Schule oder Universität oder der Planung einer LKW-Tour4.All diese Probleme weisen allerdings eine exponentielle Komplexität auf d.h. sie können kaum durch vollständige Enumeration5 gelöst werden. Schon ein TSP mit 10 zu besuchenden Orten führt zu über 36 Mio. Lösungsmöglichkeiten. Auch andere exakte Verfahren wie das Branch & Bound-Verfahren das auf einer unvollständigen begrenzten Enumeration basiert6 führen schnell zu einem unökonomischen Aufwand d.h. sie können kaum in einer vertretbaren Zeit gelöst werden.