Baumzerlegungen unter Nebenbedingungen -- Ein Clusterverfahren zur Lösung praktischer Vehicle-Routing-Probleme

Hamacher, Anja (1997) Baumzerlegungen unter Nebenbedingungen -- Ein Clusterverfahren zur Lösung praktischer Vehicle-Routing-Probleme. PhD thesis.

Abstract

Kombinatorische Optimierungsprobleme, die bei Fragestellungen aus der Praxis auftreten, sind meist schwer zu lösen. Als besonders schwer in dieser Klasse gilt die Gruppe der Vehicle-Routing-Probleme (VRPs). Schon bei kleinen Probleminstanzen mit wenigen Kunden werden hier die Grenzen der exakten Lösbarkeit erreicht. Daraus ergibt sich, daß in praktischen VRPs mit größeren Kundenmengen nur heuristische Ansätze Verwendung finden können. Das im Mittelpunkt dieser Arbeit stehende Clusterverfahren entstand im Rahmen der Entwicklung eines Dispositionssystemes für eine Spedition der Lebensmittelbranche. Als die wesentliche Eigenschaft der dabei zu erstellenden Tourenpläne wurde die regionale Begrenzung der Auslieferungsgebiete für die einzelnen Fahrzeuge vorgeschrieben. Wir wählten daher die zur Lösung von VRPs gängige Vorgehensweise des Cluster first - Route second. Hierbei werden die zu beliefernden Kunden zunächst zu Clustern zusammengefaßt, um darauf aufbauend die Reihenfolge der Kunden eines Clusters, also die Touren bestimmen zu können. Das sich uns damit stellende Problem der Bestimmung von regional begrenzten Kundenclustern formulierten wir mathematisch als Baumzerlegungsproblem unter Nebenbedingungen. Erste Resultate waren ein allgemeiner NP-Vollständigkeitsbeweis und ein heuristischer Greedyansatz, der als Verallgemeinerung des von Kundu und Misra vorgeschlagenen Verfahrens zur Zerlegung von Bäumen mit einer Gewichtsfunktion aufgefaßt werden kann. Detailliertere Auseinandersetzungen mit dem Problem, den Praxisdaten und den NP-Vollständigkeitsbeweisen ergaben eine Unterscheidung der Baumzerlegungsprobleme sowohl nach dem Knotengrad der untersuchten Bäume als auch nach der Anzahl der Gewichtsfunktionen. Unter diesen Gesichtspunkten war es uns möglich, eine vollständige Klassifizierung der Baumzerlegungsprobleme unter Nebenbedingungen in Komplexitätsklassen zu erstellen: NP-vollständig im strengen Sinne ist das Baumzerlegungsproblem für Instanzen, bei denen die Anzahl der Gewichtsfunktionen mit der Problemgröße wächst. Bei Bäumen mit mindestens zwei Gewichtsfunktionen und unbeschränktem Knotengrad wird die Fragestellung zu einem Number-Problem. Es gelang uns hier, das Knapsack-Problem auf diese Teilklasse zu reduzieren und durch Angabe eines dynamischen Programmes die Pseudopolynomialität nachweisen. Bei Probleminstanzen mit einer Gewichtsfunktion ist der von Kundu und Misra beschriebene lineare Greedy-Algorithmus optimal. Für den bei der Clusterung auftretenden praxisrelevanten Fall der Zerlegung knotengradbeschränkter Bäume mit einer beschränkten Anzahl von Gewichtsfunktionen konnten wir ein exaktes polynomielles Verfahren entwickeln, das auf die Ideen des Greedyansatzes aufbaut. Die Implementation dieses Verfahrens lieferte auf den uns vorliegenden Datensätzen der zuvor erwähnten Spedition hervorragende Laufzeitresultate. Diese guten Ergebnisse konnten auch durch Anwendung des Verfahrens auf Planungsdaten einer weiteren Spedition bestätigt werden. Die vorliegende Arbeit gliedert sich in zwei Teile. Zunächst entwickeln wir im theoretischen Teil ein exaktes polynomielles Verfahren für Baumzerlegungen unter Nebenbedingungen. Im praxisorientierten zweiten Teil wenden wir dieses Verfahren an, um in zwei Vehicle-Routing-Problemen aus der Praxis eine regionale Clusterung der Kunden vorzunehmen. Der erste Teil beginnt mit einer Einführung der verwendeten Begriffe aus der Graphen- und Komplexitätstheorie. Es folgt die exakte Definition des Baumzerlegungsproblemes unter Nebenbedingungen. Abschnitt 3.2 stellt die oben erwähnten NP-Vollständigkeitsbeweise sowie das dynamische Programm für Baumzerlegungen mit konstanter Anzahl von Gewichtsfunktionen vor. Das exakte Verfahren zur Lösung von Baumzerlegungen mit beschränkter Anzahl von Gewichtsfunktionen auf knotengradbeschränkten Bäumen beschreiben wir in Abschnitt 3.4. Zunächst erläutern wir den generischen Basisalgorithmus, der den in diesem Kapitel aufgezeigten Verfahren zugrunde liegt. Die Darstellung des optimalen Greedy-Verfahrens für eine Gewichtsfunktion sowie dessen Verallgemeinerung, die unseren ersten Ansatz zur Lösung des Problemes darstellte, folgen. In Abschnitt 3.4.4 veranschaulichen wir das exakte Verfahren zunächst am Beispiel zweier Gewichtsfunktionen auf binären Bäumen. Hier enthält die Laufzeitabschätzung bereits alle wesentlichen Ideen des allgemeinen Falles, ist aber deutlich einfacher nachzuvollziehen. Die ausführliche Darstellung und Analyse des polynomiellen Verfahrens zur Lösung der Baumzerlegungen bei beschränktem Knotengrad und beschränkter Anzahl von Knotengewichtsfunktionen schließt sich an. Das Kapitel endet mit Laufzeitanalysen auf zufälligen Instanzen, die mit den theoretischen Ergebnissen verglichen werden. Der zweite Teil der Arbeit beschäftigt sich mit der Anwendung der Baumzerlegungen unter Nebenbedingungen auf VRPs. Abschnitt 4.1 definiert das VRP und gibt einen Überblick über die Vielfalt möglicher Fragestellungen in diesem Bereich. Abschnitt 4.2 erläutert dann, wie mit Hilfe von Baumzerlegungen die regionale Clusterung der Transportaufträge und die damit verbundene Zuordnung zu den einzelnen Fahrzeugen vorgenommen werden kann. Das Tourenplanungsproblem der Lebensmittelspedition sowie das zweite Anwendungsbeispiel für das Clusterverfahren beschreiben wir in den Abschnitten 4.3 und 4.4. Danach entwickeln wir eine Startheuristik für das erste Anwendungsproblem, in dem enge Zeitfenstervorgaben die Tourenzusammenstellung erschweren und geben einen Überblick über mögliche Verbesserungsverfahren. Die Planungsresultate werden in Abschnitt 4.6 zusammengestellt. Wir schließen die Arbeit mit einer Zusammenfassung unserer Ergebnisse.


Actions:
Download: [img] Postscript - Accepted Version
Download (4MB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr97-293
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Dec 2011 09:45
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/293