Algorithmen

einem Thema, dessen Grundlagen in der theoretischen Informatik angesiedelt sind. Es geht um die Ermittlung von Lösungen für mathematische Optimierungsprobleme. Für eine Vielzahl dieser Fragestellungen existieren mathematische Verfahren und Algorithmen, mit deren Hilfe wir das Ergebnis exakt berechnen können. Existiert ein solcher Algorithmus, so kann die Lösung zwar immer noch komplex und aufwändig sein, aber man gelangt zum Ziel. Das Ergebnis ist im Regelfall auch eindeutig. Anders bei Problemstellungen, wo kein Lösungsverfahren bekannt ist oder die Art des Problems eine Anwendung eines herkömmlichen Verfahrens aus Zeitgründen nicht ermöglicht. Diese Probleme sind durchaus in einer großen Zahl in der Praxis anzutreffen und daher gar nicht allzu theoretischer Natur. Einige Beispiele verdeutlichen es: Sehr bekannt sind die verschiedenen Arten von Tourenplanungsproblemen (Vehicle Routing Problems). Gegenstand des Tourenplanungsproblems ist die Organisation einer bestimmten Menge von Transportaufträgen. Unter der Organisation versteht man dabei die Zuordnung der Transportaufträge zu den Fahrzeugen und die Festlegung der Anfahrtsreihenfolge an den Standorten. Mögliche Zielstellungen sind dabei die Minimierung der von den Fahrzeugen zurückzulegenden Strecke bzw. eine Minimierung der zum Transport notwendigen Fahrzeuge. Beide Zielkriterien leiten sich aus wirtschaftlichen Erwägungen wie z. B. der Minimierung der Kosten ab.
    Ein anderes Beispiel – ebenfalls aus dem Logistikbereich – sind Optimierungsprobleme bei Fluggesellschaften. Die Fragestellung kann dabei wie folgt umrissen werden [1]: Während der Planungsphase wird die Nachfrage geschätzt und aufbauend auf diesen Informationen werden die angebotenen Flugstrecken festgelegt. Während der Planung, die etwa ein halbes Jahr vor dem eigentlichen Ausführungstermin stattfindet, werden die genauen Abflugzeitpunkte und die zu benutzenden Flugzeugtypen (Fleet-Assignment) bestimmt. Erst wenige Wochen vor dem geplanten Zeitraum werden während der Ressourcenallokation den einzelnen Flugzeugen die zu bedienenden Flugstrecken zugewiesen (Tail-Assignment) und jeder einzelne Flug mit Flugpersonal (Crew-Assignment) versehen. Häufig muss die Fluggesellschaft während der Ausführung auf Änderungen reagieren, zum Beispiel aufgrund von witterungs- oder materialbedingten Störungen die Flugzeugumläufe anpassen. In diesen Fällen handelt es sich um eine dynamische Problemstellung. Die Planungen bei Änderungen werden nicht vollständig neu durchgeführt, sondern Anpassungen werden schrittweise eingebracht. Eine verwandte Problemstellung aus der Industrie ist zum Beispiel die Maschinenbelegungsplanung. Sie ist eines der wichtigen Probleme der Produktionswirtschaft. Die Aufgabe besteht darin, eine Zuordnung von Aufträgen zu Maschinen in einer gewissen Reihenfolge festzulegen, sodass ein bestimmtes Ziel, zum Beispiel die Minimierung der Durchlaufzeiten, bestmöglich erfüllt wird.
    Für alle diese Probleme sind spezielle Lösungsverfahren zu entwickeln. Aufgrund der hohen Komplexität der Problemstellungen (so genannte NP vollständige Probleme) ist die Anwendung von exakten Verfahren meist nicht möglich [2]. Daher muss auf Nährungsverfahren – so genannte Heuristiken – ausgewichen werden. Dazu jedoch später mehr. Tabelle 1 vermittelt einen Eindruck über zu erwartende Rechenzeiten in Abhängigkeit von der Komplexität und der Größe der Problemstellung. Sie sehen, wir brauchen alternative Lösungsansätze. Ansonsten erleben wir im wahrsten Sinne des Wortes das Ergebnis nicht.
Zeit
    Komplexitäts-funktion
10
20
30
40
50
60
n
0,00001 Sekunden
0,0002 Sekunden
0,00003 Sekunden
0,00004 Sekunden
0,00005 Sekunden
0,00006 Sekunden
n2
0,001 Sekunden
0,0004 Sekunden
0,0009 Sekunden
0,0016 Sekunden
0,0025 Sekunden
0,0036 Sekunden
n3
0,001 Sekunden
0,008 Sekunden
0,027 Sekunden
0,064 Sekunden
0,125 Sekunden
0,216 Sekunden
n5
0,1 Sekunden
3,2 Sekunden
24,3 Sekunden
1,7 Minuten
5,2 Minuten
13,0 Minuten
2n
0,001 Sekunden
1,0 Sekunden
17,9 Minuten
12,7 Tage
35,7 Jahre
366 Jahrhunderte
3n
0,059 Sekunden
58 Minuten
6,5 Jahre
3.855 Jahrhunderte
2 x 106 Jahrhunderte
1,3 x 103 Jahrhunderte
    Tabelle 1: Rechenzeiten in Abhängigkeit der Komplexität eines Algorithmus (Annahmen: von-Neumann-Maschine und einer Rechenzeitdauer von 10-6 Sekunden) [3]

2.1Exakte Verfahren und Heuristiken
    Die Ansätze zur Lösung (kombinatorischer) Optimierungsprobleme lassen sich in exakte Verfahren