Home | english  | Impressum | Sitemap | KIT

Online-Optimierung

Modellierung von Online-Problemen und Bewertungskriterien für Online-Algorithmen
Lagersystem
In Lager- und Materialflusssystemen lassen sich viele Fragestellungen als Online-Problem formulieren, ...
Packproblem
... bei Packungsproblem ist man mit ständig hinzukommenden Gegenständen konfrontiert, ...
Transportproblem
... und bei Routen- und Transportproblemen werden ständig neue Aufträge bekannt gegeben.

Die Online-Optimierung befasst sich mit der Optimierung von Systemen, die einem ständigen Zulauf an Daten unterliegen. Im Gegensatz zur klassischen Offline-Optimierung, bei der angenommen wird, dass alle Problemdaten bereits vor der Verwendung eines Lösungsverfahrens bekannt sind, müssen dynamisch bekanntgegebene Daten im Verfahrensablauf von Online-Algorithmen berücksichtigt werden. Die Anwendungsfelder der Online-Optimierung sind vielfältig und breit gestreut:

  • Lager- und Materialflusssysteme
  • Packungsprobleme
  • Transportprobleme
  • Rent-or-buy Probleme

Als klassisches Bewertungsmaß für Online-Algorithmen wird bislang vornehmlich die sogenannte Kompetitivität eingesetzt. Diese vergleicht den Zielfunktionswert des Online-Algorithmus mit dem Zielfunktionswert eines Offline-Algorithmus, der die gesamte Folge der Eingabedaten gekannt hätte. Da die Kompetitivität in Form einer Worst-Case-Analyse ermittelt wird, ist ihr Wert für praktische Problemstellungen häufig von geringer Aussagekraft. Vielmehr tritt oftmals sogar der Effekt auf, dass Online-Algorithmen mit einer verhältnismäßig guten Kompetitivität ein inakzeptables Verhalten für typische Eingabefolgen aufweisen. Grund hierfür ist das Design vieler Online-Algorithmen: Sie wurden ausschließlich vor dem Hintergrund einer möglichst guten Kompetitivität entwickelt, ohne Rücksicht auf problemtypische Eingabefolgen zu nehmen. Ein weiteres Defizit der kompetitiven Analyse ist die Vernachlässigung von Anforderungen realer Probleme: In vielen Praxis-Problemen wird erwartet, dass verwendete Lösungsalgorithmen in Echtzeit operieren, und dass der verwendete Speicherplatz beschränkt ist.

Unsere Zielsetzung für Forschungsarbeiten im Bereich der Online-Optimierung liegt in der Entwicklung eines umfassenden Frameworks zur Modellierung und Analyse von Online-Problemen. Zum Einen soll dieses Framework in der Lage sein, die wesentlichen Struktureigenschaften einer Problemstellung zu beschreiben; zum Anderen soll die Verwendung alternativer Bewertungskriterien für die Güte eines Online-Algorithmus dessen praktische Einsatzfähigkeit besser abschätzen als es bislang durch die Kompetitivität gelingt. Alternative Bewertungskriterien berücksichtigen als knappe Ressource gleichermaßen Information, Rechenzeit und Speicherbedarf.

Ein weiteres Ziel der Analyse stellt die Einbeziehung sogenannter Lookaheads dar. Hierunter versteht man das Vorhandensein einer Teilmenge zukünftiger Daten, die von einem Online-Algorithmus in die Entscheidungsfindung einbezogen werden können. Online-Probleme mit Lookahead stehen somit zwischen den beiden Extremfällen der Offline- und Online-Optimierung. In der Theorie der Online-Algorithmen blieben Lookahead-Effekte bislang ohne große Beachtung, obwohl sie in vielen praktische Problemstellungen, wie z.B. der Transportplanung - nachweislich zu einer deutlichen Verbesserung des Zielfunktionswerts beitragen. Im Rahmen der Forschungsarbeiten soll untersucht werden, welche Abhängigkeiten zwischen der Problemstellung und den zu erwartenden Lookahead-Effekten bestehen.

Ansprechpartner

Fabian Dunke