Projekt

Algorithmen für Optimierungsprobleme

In Rahmen dieses Projekt sollen Algorithmen für Optimierungsprobleme implementiert und analysiert werden. Optimierungsprobleme spielen eine wichtige Rolle sowohl in der Wissenschaft als auch in der Praxis. Ein Beispiel dafür aus der Logistik ist die Distribution von Gütern zu den jeweiligen Abnehmern (siehe unten: Vehicle Routing Problem with Time Windows).

Dieses Semester stehen sogenannte Metaheuristiken im Mittelpunkt des Projektes. Das sind Algorithmen zum näherungsweisen Lösen von Optimierungsproblemen. Diese werden benötigt, da viele interessante Optimierungsprobleme NP-hart sind, d.h. für die besten bekannten Algorithmen wächst die benötigte Laufzeit zum Finden einer optimalen Lösung exponentiell in der Größe der Probleminstanzen. Ein Ziel von Metaheuristiken ist das Finden möglichst guter Lösungen in akzeptabler Laufzeit. Im Gegensatz zu Heuristiken sind Metaheuristiken auf mehr als nur ein Optimierungsproblem anwendbar.

Unverbindliche Anfragen sind jederzeit per E-Mail an Gunnar Völkel möglich.

Als Beispiel für die Anwendung von Ant Colony Optimization wird hier das Optimierungsproblem Vehicle Routing Problem with Time Windows (VRPTW) verwendet.

Bei diesem Problem geht es darum, ein Produkt an alle Kunden auszuliefern, wobei jeder Kunde eine bestimmte Menge des Produkts bestellt hat. Von jedem Kunden ist bekannt, in welchem Zeitfenster die Lieferung erfolgen darf. Zur Auslieferung steht ein Fuhrpark von Fahrzeugen gleicher Bauart zur Verfügung. Die Menge des Produkts, die ein Fahrzeug ausliefern kann, ist durch die Ladekapazität des Fahrzeugs beschränkt. Eine Lösung dieses Problems besteht im Allgemeinen aus mehreren Fahrzeugtouren (siehe Beispiel rechts).

Die Lösung dieses Problems ist für zahlreiche Anwendungen in der Wirtschaft bedeutend, unter anderem in der Lebensmitteldistribution, Pressedistribution, Distribution verschiedenster Güter oder auch der Müllabfuhr.

• Rich Pickup and Delivery Problems with Time Windows (RPDPTW)
  Metaheuristik: Ant Colony Optimization
  
  
• Job Shop Scheduling Problem (JSSP)
  Metaheuristik: Ant Colony Optimization
  
  
• Traveling Salesman Problem (TSP) und Vehicle Routing Problem with Time Windows (VRPTW)
  Metaheuristik: Ant Colony System
  
  

Gute Kenntnisse einer general-purpose Programmiersprache, wie z.B. Java, C/C++, Lisp oder Python, werden benötigt.

Ziel des Projekts ist es, die Problemstellung der Optimierungsprobleme des gewählten Themas zu erarbeiten sowie eine Implementierung der Metaheuristik des Themas zu planen und umzusetzen. Die Implementierung soll auf Probleminstanzen getestet und analysiert werden. Die Optimierungsprobleme, die Metaheuristik und deren Implementierung sollen in einem Projektbericht dokumentiert werden. Das Projektergebnis soll abschließend in einem ca. 30 minütigen Vortrag präsentiert werden.

Dieses Projekt richtet sich an Masterstudenten der Informatik, Medieninformatik und Software Engineering. Studenten aus Informatik verwandten Studiengängen (z.B. Mathematik) können auch teilnehmen, insofern ihre Prüfungsordnung das erlaubt.

Die Anmeldung zur Modulprüfung setzt keinen Leistungsnachweis voraus. Es wird aufgrund der schriftlichen Dokumentation, der Güte der erreichten Lö-
sung/Implementierung sowie des Abschlussvortrags eine Note (8 LP) ermittelt.

Marco Dorigo, Thomas Stützle: Ant Colony Optimization: Overview and Recent Advances. Technical Report TR/IRIDIA/2009-013, 2009, IRIDIA, Université Libre de Bruxelles, Brussels, Belgium. PDF

David Pisinger, Stefan Ropke: A general heuristic for Vehicle Routing Problems. Computers & Operations Research, 2007, 34, 2403-2435. PDF

Alberto Colorni, Marco Dorigo, Vittorio Maniezzo, Marco Trubian: Ant system for Job-shop Scheduling. Belgian Journal of Operations Research, Statistics and Computer Science, 1994. to appear(?). PDF

Eine kurze Erklärung zu Ant Colony Optimization