Algorithmen

, problemspezifische Heuristiken und Metaheuristiken einteilen ( Abb. 1 ). Exakte Verfahren ermitteln zu einem Optimierungsproblem nachweislich die optimale Lösung. Aufgrund ihres hohen Rechenaufwands lassen sich jedoch nur Probleme mit beschränkter Größe in vertretbarer Zeit lösen. Ein Beispiel: Die Anwendung auf praktische Fragestellungen der Tourenplanung ist daher nach dem heutigen Stand der Forschung begrenzt, denn dort hat man Probleme mit mehreren hundert oder tausend Aufträgen zu lösen.

    Abbildung 1: Einteilung der Lösungsverfahren für Optimierungsprobleme
    Zur Klasse der exakten Lösungsverfahren gehören die vollständige Enumeration , Branch-and-Bound-basierte Verfahren und das A*-Verfahren .
Vollständige Enumeration: Das Problem wird gelöst, indem alle möglichen Lösungen durch Kombination aller möglichen Merkmale ermittelt und bewertet werden. Die Lösung mit der besten Bewertung stellt das Ergebnis dar. Aufgrund des extrem hohen Such- und Rechenaufwands bleibt die Anwendung des Verfahrens auf kleinere Probleme begrenzt.
Branch-and-Bound-basierte Verfahren: Es handelt sich um ein implizites Enumerationsverfahren, d. h. der Lösungsumfang wird reduziert, indem bestimmte Teilmengen des Lösungsraums bei der Suche ausgeschlossen werden. Dazu wird der Lösungsraum in Form eines Entscheidungsbaums organisiert, d. h. das zu lösende Problem wird in (überschneidungsfreie) Teilprobleme zerlegt. Die Lösungsmenge jedes Teilproblems soll kleiner sein als diejenige des Gesamtproblems und die Vereinigung der Lösungsmengen entspricht der Lösungsmenge des Gesamtproblems. Für jedes Teilproblem werden Schranken berechnet. Bei Minimierungsproblemen handelt es sich um untere, bei Maximierungsproblemen um obere Schranken (lower bzw. upper bounds). Diese Schranken entstehen, indem bestimmte Restriktionen des betrachtenden Teilproblems fallengelassen werden. Die Schranken (Ergebnisse) können bestenfalls erreicht werden, wenn das Teilproblem exakt gelöst wird. Aufgrund dieser Vorgehensweise ist es möglich, Teile des Lösungsraums frühzeitig auszusortieren, wenn der Wert einer Schranke darauf schließen lässt, dass die optimale Lösung des gesamten Problems sich nicht innerhalb dieses Teillösungsraums befindet. Für nicht ausgeschlossene Teillösungsräume wird das Verfahren der Aufspaltung wiederholt, bis die optimale Lösung gefunden wurde. Varianten dieses Verfahrens sind das Branch-and-Cut-Verfahren, das Branch-and-Price- sowie das Branch-and-Cut-and-Price-Verfahren.
Das A*-Verfahren: Es entstammt dem Forschungsbereich der künstlichen Intelligenz und kann als Verallgemeinerung des Branch-and-Bound-Verfahrens aufgefasst werden, da es ebenfalls auf dem Prinzip des Verzweigens und Ausschließens beruht. Der Algorithmus dient hauptsächlich der Berechnung eines kürzesten Pfades zwischen zwei Knoten in einem Graphen mit positiven Kantengewichten. Es werden Lösungen im Voraus ausgeschlossen, die mit Sicherheit einen schlechteren Zielfunktionswert aufweisen. Die Schätzung bedient sich im Unterschied zu Branch- and Bound-Verfahren einer Heuristik, beispielsweise zur Schätzung der Entfernung zwischen zwei Standorten. Das A*-Verfahren wird u. a. bei der Programmierung von Computerspielen eingesetzt, um beispielsweise den Weg des „Helden“ durch ein Labyrinth zu finden.
    Aufgrund der eingeschränkten Anwendbarkeit von exakten Lösungsverfahren für Optimierungsprobleme wurden Heuristiken entwickelt, mit deren Hilfe möglichst gute Lösungen in akzeptabler Rechenzeit ermittelt werden können. Sie werden auch als lokale Suchverfahren bezeichnet. Allerdings kann das Auffinden der optimalen Lösung nicht garantiert werden. Aufgrund der speziellen Anpassung der Verfahren an die Problemstellung werden sie als problemspezifische Heuristiken bezeichnet. Eine Einteilung in Konstruktionsverfahren und Verbesserungsverfahren ist üblich. Mithilfe von Konstruktionsverfahren wird zunächst eine Startlösung erzeugt, deren Güte meist noch weit vom „Optimum“ entfernt ist. Danach wird oft versucht, diese Lösung schrittweise zu verbessern. Grundsätzlich lassen sich die Lösungsheuristiken den folgenden Gruppen zuordnen [4]:
Eröffnungsverfahren zur Bestimmung einer ersten zulässigen Ausgangslösung
Lokale Such- und Verbesserungsverfahren zur Verbesserung einer gegebenen, aber zulässigen Lösung
Relationsbasierte Verfahren
Unvollständig ausgeführte exakte Optimierungsverfahren, zum Beispiel vorzeitig