Matheuristics: Hybride Algorithmen für Transportprobleme

01.01.2008 - 31.10.2010
Forschungsförderungsprojekt
Transportprobleme treten in vielen Bereichen des täglichen Lebens auf. Dabei geht es generell um die Zustellung von produzierten Gütern an Kunden und um die Entscheidung wann und von wem diese Güter den Kunden zugestellt werden. Eine Verbesserung der Lösung spiegelt sich direkt in den daraus resultierenden Kosten wider und beeinflusst auch andere wichtige Faktoren wie zum Beispiel die Kundenzufriedenheit. Aufgrund der Mannigfaltigkeit der zu treffenden Entscheidungen handelt es sich bei Transportproblemen um äußerst komplexe Kombinationen von Zuordnungsproblemen und Aufgabenstellungen aus dem Bereich der Reihenfolge- und Tourenplanung. Wir werden uns im Rahmen dieses Projekts auf spezielle Transportprobleme konzentrieren: Aufgabenstellungen, bei denen mehrfache Belieferungen der Kunden erforderlich sind. Mehrfache Belieferungen sind immer genau dann erforderlich, wenn eine bestimmte Anzahl Kunden wiederholt besucht werden muss. Das Ausgangsproblem wird durch das sogenannte periodische Tourenplanungsproblem beschrieben. Zusätzliche Flexibilität aus Sicht des Lieferanten ergibt sich aufgrund der Tatsache, dass die Anzahl der Besuche und die dabei gelieferte Menge an Produkten frei gewählt werden kann und nicht vom Kunden bestimmt wird. Dabei handelt es sich um verkäuferorganisiertes Lagerbestandsmanagement im Gegensatz zu käuferorganisiertem Lagerbestandsmanagement. Dadurch können weitere Kostenreduktionen erreicht werden. Die daraus resultierende Problemklasse der Inventory Routing Probleme wird ebenfalls im Rahmen dieses Projekts untersucht. Eine weitere interessante Aufgabenstellung liefert das periodische Ganzladungs-Problem, bei welchem Kunden wiederholt zumindest eine komplette Ladung des transportierten Gutes benötigen. Exakte Algorithmen dienen der Erzeugung von optimalen Lösungen sowie dem Beweis deren Optimalität. Da die Laufzeiten rapide mit der Größe der Probleminstanz ansteigen, können lediglich für kleinere oder mittelgroße Problemstellungen in vertretbarer Zeit exakte Lösungen gefunden werden. Bei größeren Instanzen ist es eher angebracht zu heuristischen Verfahren zu greifen, welche in vertretbarer Zeit gute, aber nicht notwendigerweise optimale Lösungen erzielen. Mathematische Programmierung und Metaheuristiken sind zwei ganz besonders bewährte Verfahren, welche in diesem Zusammenhang häufig zur Anwendung kommen und prinzipiell als komplementär angesehen werden können. Besonders die Kombination dieser Ansätze hat sich für verschiedene Aufgabenstellungen als äußerst vielversprechend herausgestellt. Die meisten der aktuell verwendeten hybriden Optimierungsverfahren, für die die Bezeichnung "Matheuristiken" verwendet wird, wenden relativ einfach gestaltete Kombinationsschemata an, ungeachtet möglicher tiefergreifender Synergieeffekte. Intensive Forschung in diesem Bereich soll helfen, zu einem besseren Verständnis zu gelangen und Empfehlungen abgeben zu können, unter welchen Umständen welche hybriden Strategien zielführend sind. Ziel dieses Projekts ist es, verschiedene hybride Ansätze von Metaheuristiken und ganzzahliger linearer Programmierung zu entwickeln. Angewendet auf die oben erwähnten Problemstellungen sollen bessere Lösungen als mit herkömmlichen Methoden erzielt werden. Im Einzelnen verfolgen wir die folgenden Ziele, an denen der Projektplan ausgerichtet ist: (i) die Performance heuristischer und exakter Ansätze durch deren Hybridisierung zu steigern und (ii) hybride Algorithmen für bi-kriterielle Optimierung und stochastische Problemstellungen zu entwickeln. Die letzten beiden Ansätze sind insofern wichtig, da in den meisten Anwendungen aus dem Bereich der Tourenplanung immer wieder Entscheidungen unter Unsicherheit getroffen werden müssen bzw. häufig mehr als nur eine Zielfunktion auftreten. Dieses Projekt ist das erste seiner Art, in welchem eine Auswahl an "matheuristischen" Lösungsmethoden für reale Transportprobleme mit mehrfachen Belieferungen angewendet und genauer erforscht werden.

Personen

Projektleiter_in

Projektmitarbeiter_innen

Institut

Förderungsmittel

  • FWF - Österr. Wissenschaftsfonds (National) Fonds zur Förderung der wissenschaftlichen Forschung (FWF)

Forschungsschwerpunkte

  • Information and Communication Technology

Schlagwörter

DeutschEnglisch
Matheuristicsmatheuristics
Metaheuristikenmeta heuristics
Ganzzahlige lineare Programmierunginteger linear programming
kombinatorische Optimierungcombinatorial optimization
Routenplanungsproblemevehicle routing problems

Externe Partner_innen

  • Universität Wien

Publikationen