Matheuristics: Hybride Algorithmen für Transportprobleme

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. Für all diese Problemklassen existieren sowohl heuristische als auch exakte Ansätze. 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. Bisherige Forschungsergebnisse deuten klar darauf hin, dass derartige Ansätze äußerst vielversprechend für die genannte Problemklasse sind. Der besonders innovative Aspekt liegt in der Berücksichtigung von Zweizielproblemen mit stochastischem Einfluss. Wir sind aber auch davon überzeugt, dass die resultierenden Forschungsergebnisse hilfreich für die zukünftige Entwicklung von Lösungsansätzen für weitere kombinatorische Problemklassen sind.

In diesem Projekt wurden innovative hybride Lösungsverfahren untersucht, die exakte und metaheuristische Techniken kombinieren. Die betrachteten Anwendungen umfassten vor allem periodische Tourenplanungsprobleme auch mit mehreren Optimierungszielen und Stochastizität. Tourenplanungsprobleme kommen in vielen äußerst relevanten, praktischen Bereichen des täglichen Lebens vor. Generell geht es um die Zustellung produzierter Güter an Kunden und die Entscheidungen wie und wann diese Güter abgeholt und zugestellt werden sollen. Verbesserungen in Lösungen haben oft direkte und erhebliche Auswirkungen auf die Kosten und weitere wichtige Faktoren wie Kundenzufriedenheit. Leider ist es schwierig, die meisten dieser Optimierungsprobleme in akzeptabler Zeit optimal zu lösen. Zahlreiche algorithmische Herangehensweisen wurden daher in den letzten Jahrzehnten für derartige komplexe kombinatorische Optimierungsaufgaben vorgeschlagen. Die vorhandenen Techniken können grob in zwei Hauptkategorien gegliedert werden: exakte und heuristische Algorithmen. Exakte Algorithmen garantieren optimale Lösungen; die Laufzeit steigt aber oft dramatisch mit der Größe einer Probleminstanz. Für größere Instanzen ist es daher häufig die einzige Möglichkeit, die Optimalitätsgarantie zugunsten geringerer Laufzeit aufzugeben und Näherungsverfahren (Heuristiken) einzusetzen, die häufig gute aber nicht notwendigerweise optimale Lösungen in akzeptabler Zeit liefern. In diesem Projekt wurden sehr unterschiedliche hybride Design-Muster für solche Verfahren entwickelt und untersucht. In Bezug auf die Lösungsqualität erwiesen sich die neu entwickelten Methoden in etlichen Fällen besser als bisherige State-of-the- art Verfahren. Wir verfolgten sowohl integrative als auch kollaborative hybride Ansätze. Die erfolgreichsten Design-Muster sind i) hybride Varianten auf Basis von Spaltengenerierungsverfahren. Diese Ansätze erscheinen insbesondere auch für andere Problemstellungen vielversprechend, wo ein klassisches Branch-and-Price für größere Instanzen nicht mehr geeignet ist. ii) Speziale Methoden basierend auf Set Covering und Netzwerkflußmodellen wurden erfolgreich für reale Aufgabenstellungen (wie z. B. kombinierte Standort und Tourenplanung, Gratiszeitungsauslieferung, Müllentsorgung und Fertigbetonauslieferung) angewendet. Die entwickelten Hybridverfahren liefern in der Regel bessere Ergebnisse als reine Metaheuristiken. iii) Für große Probleminstanzen haben wir ein Hybridverfahren entwickelt, dass schrittweise das Aggregationsniveau der relevanten Entscheidungen verfeinert und dadurch zu guten Lösungen in vernünftiger Laufzeit kommt. iv) Für das Tourenplanungsproblem mit mehrfacher Zielsetzung entwickelten wir wir ein hybrides Verfahren, womit die Effizienz des exakten Teilverfahrens verbessert wurde. Auch die stochastische Erweiterung des Problems mit mehrfacher Zielsetzung bei unsicherer Nachfrage, konnte durch geeignete Verfahren sinnvoll behandelt werden.