Dynamische Elemente in kombinatorischen Optimierungsproblemen

Routen- und Tourenplanung anhand naturinspirierter Optimierungsverfahren


Kombinatorische Optimierungsprobleme behandeln das Suchen bestimmter Elemente innerhalb einer endlichen Menge von Lösungskandidaten, welche eine gegebene Kostenfunktion maximieren bzw. minimieren. Sie haben viele verschiedene Anwendungsgebiete und spielen daher in der Praxis eine große Rolle. Sei es das Finden kürzester Wege, das Optimieren des Belegungsplans von Maschinen innerhalb eines Betriebs oder das Festlegen einer optimalen Lieferroute für bestimmte Güter, all diesen Fragestellungen liegt jeweils ein kombinatorisches Optimierungsproblem zugrunde.

Ein bekannter Vertreter kombinatorischer Optimierungsprobleme ist das Travelling Salesperson Problem (TSP). Ziel ist es dabei, eine kürzeste Rundreise durch eine bestimmte Anzahl von Städten zu finden, sodass jede Stadt genau einmal besucht wird. Wie bei vielen anderen kombinatorischen Optimierungsproblemen ist die Menge der Lösungskandidaten, selbst bei einer vergleichsweise kleinen Anzahl an Städten, schon so groß, dass die optimale Lösung im Allgemeinen nicht mehr gefunden werden kann. Man muss sich folglich darauf beschränken gute Lösungen zu finden, die nahe am Optimum liegen und somit das Optimierungsproblem nur annäherungsweise lösen.

Hierbei helfen naturinspirierte Optimierungsverfahren als digitale Analogien zu Phänomen aus der Natur, welche Strategien für eine effektive Suche nach guten Lösungen in der Menge der Lösungskandidaten liefern. Als Beispiel soll der Ameisenalgorithmus erwähnt werden, welcher das Futtersucheverhalten von Ameisen nachbildet. Diese ermitteln mit Hilfe von Geruchsstoffen den kürzesten Weg zwischen Nest und Nahrungsquelle. Andere Algorithmen zur Lösung kombinatorischer Optimierungsprobleme imitieren das Prinzip der natürlichen Selektion („Survival of the fittest“) innerhalb des Evolutionsprozesses oder das Schwarmverhalten von Fischen oder Vögeln.

Im Rahmen des Forschungsvorhabens sollen diese Algorithmen im Rahmen einer Erweiterung des klassischen TSP angewandt werden: dem Vehicle Routing Problem (VRP). Hierbei soll für eine Flotte von Lieferfahrzeugen ein Lieferplan erstellt werden, bei dem Kunden in einer optimalen (kostenminimalen) Reihenfolge beliefert werden. Derartige Probleme werden wegen ihrer großen Rechenzeit derzeit meist über Nacht gelöst, so dass am nächsten Morgen ein guter Lieferplan vorliegt. Dies hat jedoch zur Konsequenz, dass im Tagesverlauf eintretende Ereignisse wie Stau, Fahrzeugausfall, neue Lieferaufträge etc. nicht mehr berücksichtigt werden können. Es stellt sich folglich die Forschungsfrage, wie man diese dynamisch auftretenden Ereignisse in den Algorithmen berücksichtigen und somit nahezu in Echtzeit auf sie reagieren kann.

Für weitere Informationen und bei Interesse an dem Projekt wenden Sie sich bitte an Simon Anderer.

Autor Text und Abbildungen: Simon Anderer

 

Kontakt

Fakultät für Wirtschaftswissenschaften

Sprechzeiten Sekretariat:
Montag - Freitag
09:00 - 13:30 Uhr

K103B und K104A
Moltkestr. 30, 76133 Karlsruhe
E-Mail Sekretariat.Wspam prevention@hs-karlsruhe.de

Anfahrtsplan
Lage- und Gebäudeplan