Tabu Search

ISBN-13: 9783656525332 / Niemiecki / Miękka / 2013 / 26 str.

Jorg Heinicke

Opis

Studienarbeit aus dem Jahr 2002 im Fachbereich BWL - Unternehmensforschung, Operations Research, Note: 1,3, Universitat Leipzig (Institut fur 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 spater 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 Universitat oder der Planung einer LKW-Tour4. All diese Probleme weisen allerdings eine exponentielle Komplexitat auf, d.h. sie konnen kaum durch vollstandige Enumeration5 gelost werden. Schon ein TSP mit 10 zu besuchenden Orten fuhrt zu uber 3,6 Mio. Losungsmoglichkeiten. Auch andere exakte Verfahren wie das Branch & Bound-Verfahren, das auf einer unvollstandigen, begrenzten Enumeration basiert6, fuhren schnell zu einem unokonomischen Aufwand, d.h. sie konnen kaum in einer vertretbaren Zeit gelost werden.