Modelling

Modellierung und kompetitive Analyse von Transportproblemen

Beschreibung

Transportsysteme (z.B. Bediengeräte von Hochregallagern, fahrerlose innerbetriebliche Versorgungsfahrzeuge) werden sorgfältig entworfen, damit notwendige Transportaufgaben effizient erledigt werden können. Derartige Systeme sind jedoch auch dadurch gekennzeichnet, dass eine Vorab-Optimierung des operativen Einsatzes in der Regel nicht möglich ist. Während des Systembetriebs entstehen unvorhersagbar neue Transportaufträge, alte werden storniert; Störungen und Staus verändern die Systemeigenschaften. Diese Umstände machen eine Online-Planung erforderlich; unter Echtzeit-Bedingungen müssen gute Entscheidungen zur Abarbeitung der Aufträge getroffen werden.

Algorithmen für Online Probleme werden in der Literatur oft mit Hilfe der kompetitiven Analyse bewertet. Dabei vergleicht man den Zielfunktionswert einer vom Online-Algorithmus generierten Lösung mit dem Wert einer optimalen Offline-Lösung. Die kompetitive Analyse ist eine Worst-Case-Analyse, die in vielen Fällen übermäßig pessimistisch ist. Online-Steuerungsstrategien, die in der Regel - d.h. für die weitaus meisten Entwicklungen in der zum Zeitpunkt der Entscheidung unbekannten Zukunft - gute Ergebnisse liefern, in Ausnahmefällen aber völlig versagen, sind vom Standpunkt der kompetitiven Analyse her disqualifiziert. Bei Transportproblemen fällt auf, dass in der bekannten Literatur bisher kein Konzept vorhanden ist, offensichtlich absurde Anforderungen an das System aus der Analyse auszuschließen.

Ziel des Projekts ist es, praxistaugliche mathematische Modelle für derartige Online- (und Echtzeit-) Aufgaben zu entwerfen, diese Modelle mathematisch zu untersuchen und daraus algorithmische Strategien abzuleiten. Wir konzentrieren uns dabei auf Transportaufgaben, die zu Modellen aus dem Bereich der Kombinatorischen Optimierung (mit stochastischen Komponenten) führen. Hauptziel ist es stets, Online-Algorithmen mit mathematisch beweisbarer Güte zu entwickeln. Für einzelne konkrete Transportsysteme wollen wir echtzeit-taugliche Verfahren entwickeln und implementieren sowie ihre Praxistauglichkeit anhand echter Fallbeispiele in Zusammenarbeit mit Partnern in der Industrie testen.

Mit Hilfe des am Konrad-Zuse-Zentrum entwickelten Simulationspakets AMSEL ist langfristig eine Simulation des kompletten Transportsystems des Versandlagers der Herlitz PBS AG angestrebt; damit kann die Qualität der Modelle und Optimierungsverfahren unter Verwendung realer Daten schnell und zuverlässig getestet werden.

Ansprechpartner

• Dr. Sven O. Krumke

Mitarbeiter

• Prof. Dr. Dr. h.c. mult. Martin Grötschel
• Dr. Sven O. Krumke
• Dr. Jörg Rambau

Kooperationspartner

• Herlitz PBS AG , Berlin, Ansprechpartner bei Herlitz: Herr Eckle

Förderung

• Deutsche Forschungsgemeinschaft (DFG) im Schwerpunktprogramm Echtzeit-Optimierung großer Systeme

Projektdauer

10/1995 - 09/2001