Detailansicht
Decomposition strategies for large scale multi depot vehicle routing problems
Alexander Ostertag
Art der Arbeit
Dissertation
Universität
Universität Wien
Fakultät
Fakultät für Sozialwissenschaften
Betreuer*in
Richard Hartl
DOI
10.25365/thesis.2960
URN
urn:nbn:at:at-ubw:1-29777.00171.126565-3
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Das Umfeld in der heutigen Wirtschaft verlangt nach immer bessern Ansätzen, um
Transportprobleme möglichst effizient zu lösen. Die Klasse der ”Vehicle Routing Problems” (VRP) beschäftigt sich speziell mit der Optimierung von Tourenplanungsproblemen
in dem ein Service-Leister seine Kunden möglichst effizient beliefern muss. Eine der VRP-Varianten ist das ”Multi Depot Vehicle Routing Problem with Time Windows” (MDVRPTW), in dem Kunden von verschiedenen Depots
in einem fix vorgegebenen Zeitintervall beliefert beliefert werden müssen. Das
MDVRPTW ist im realen Leben dank seiner realitätsnahen Restriktionen sehr oft
vertreten. Typische Transportprobleme, wie sie in der Wirklichkeit auftreten, sind
jedoch oftmals so groß, dass sie von optimalen Lösungsansätzen nicht zufriedenstellend
gelöst werden können.
In der vorliegenden Dissertation werden zwei Lösungsansätze präsentiert, wie
diese riesigen, realitätsnahen Probleme zufriedenstellend bewältigt werden können.
Beide Ansätze benutzen die POPMUSIC Grundstruktur, um das Problem möglichst
intelligent zu dekomponieren. Die Dekomponierten und damit kleineren Subprobleme
können dann von speziell entwickelten Algorithmen effizienter bearbeitet
und letztendlich gelöst werden. Mit dem ersten Ansatz präsentieren wir
eine Möglichkeit Transportprobleme zu dekomponieren, wenn populationsbasierte
Algorithmen als Problemlöser eingesetzt werden. Dazu wurde ein maßgeschneiderter
Memetischer Algorithmus (MA) entwickelt und in das Dekompositionsgerüst eingebaut um ein reales Problem eines österreichischen Transportunternehmens
zu lösen. Wir zeigen, dass die Dekomponierung und Optimierung
der resultierenden Subprobleme, im Vergleich zu den Ergebnissen des MA ohne
Dekomposition, eine Verbesserung der Zielfunktion von rund 20% ermöglicht.
Der zweite Ansatz beschäftigt sich mit der Entwicklung einer Dekomponierungsmethode
für Lösungsalgorithmen, die nur an einer einzigen Lösung arbeiten. Es wurde ein ”Variable Neigborhood Search” (VNS) als Optimierer in das POPMUSIC
Grundgerüst implementiert, um an das vorhandene Echtwelt-Problem heranzugehen.
Wir zeigen, dass dieser Ansatz rund 7% bessere Ergebnisse liefert als
der pure VNS Lösungsansatz. Außerdem präsentieren wir Ergebnisse des VNS
Dekompositionsansatzes die um rund 6% besser sind als die des MA Dekompositionsansatzes.
Ein weiterer Beitrag dieser Arbeit ist das Vorstellen von zwei komplett verschiedenen
Ansätzen um das Problem in kleinere Sub-Probleme zu zerteilen. Dazu
wurden acht verschiedene Nähe-Maße definiert und betrachtet. Es wurde der
2,3 und 4 Depot Fall getestet und im Detail analysiert. Die Ergebnisse werden
präsentiert und wir stellen einen eindeutigen Gewinner vor, der alle Testinstanzen
am Besten lösen konnte. Wir weisen auch darauf hin, wie einfach die POPMUSIC
Dekomponierung an reale Bedürfnisse, wie zum Beispiel eine möglichst
schnelle Ergebnisgenerierung, angepasst werden kann. Wir zeigen damit, dass
die vorgestellten Dekomponierungsstrategien sehr effizient und flexibel sind, wenn
Transportprobleme, wie sie in der realen Welt vorkommen gelöst werden müssen.
Abstract
(Englisch)
The optimization of transportation activities is of high importance for companies
in today’s economy. The Vehicle Routing Problem (VRP) class is dealing with
the routing of vehicles so that the customer base of a company can be served
in the most efficient way. One of the many variants in the VRP class is the
Multi Depot Vehicle Routing Problem with Time Windows (MDVRPTW) which
extends the VRP by additional depots from which customers can be served, as
well as an individual time window for each customer in which he is allowed to
be served. Modern carrier fleet operators often encounter these MDVRPTW in
the real world, and usually they are of very large size so that exact approaches
cannot solve them efficiently. This thesis presents two different approaches how
this real world large scale MDVRPTWs can be solved. Both approaches are based
on the POPMUSIC framework, which intelligently tries to decompose the large
scale problem into much smaller sub-problems. The resulting sub-problems can
then be solved more efficiently by specialized optimizers. The first approach in
this thesis was developed for population based optimizers. A Memetic Algorithm
(MA) was developed and used as an optimizer in the framework to solve a real
world MDVPRTW from an Austrian carrier fleet operator. We show that decomposing
the complete problem and solving the resulting sub-problems improves the
solution quality by around 20% compared to using the MA without any decomposition.
The second approach specially focuses on decomposition strategies for
single solution methods. More precisely, a Variable Neighborhood Search (VNS)
was implemented in the POPMUSIC framework to solve the real world instances.
We show that decomposing the problem can yield improvements of around 7%
compared to using the pure VNS method. Compared to the POPMUSIC MA
approach the second approach can further improve the solution quality by around
6%. Another contribution in this thesis is the development of two generally different ways to measure proximity when creating sub-problems. In detail we tested
eight different proximity measures and analyzed how good they decompose the
problem in different environments. We tested the two, three and four depot case
and present a clear winner that can outperform all other measures. Further we
demonstrate that the POPMUSIC approach can flexibly be adjusted to real world
demands, like a faster solution finding process, while at the same time maintaining
high quality solutions. We show that a decomposition strategies combined with
state of the art metaheuristic solvers are a very efficient and flexible tool to tackle
real world problems with regards to solution quality as well as runtime.
Schlagwörter
Schlagwörter
(Englisch)
Multi Depot Vehicle Routing Problem Memetic Algorithm decomposition popmusic Variable Neigborhood Search large scale real world
Schlagwörter
(Deutsch)
Transportproblem Echtwelt Memetischer Algorithmus Variable Neighborhood Search Popmusic Dekomposition
Autor*innen
Alexander Ostertag
Haupttitel (Englisch)
Decomposition strategies for large scale multi depot vehicle routing problems
Paralleltitel (Deutsch)
Dekompositionsstrategien für große Multi Depot Vehicle Routing Probleme
Publikationsjahr
2008
Umfangsangabe
X, 124 S. : graph. Darst.
Sprache
Englisch
Beurteiler*innen
Karl Dörner ,
Walter Gutjahr
Klassifikation
85 Betriebswirtschaft > 85.32 Beschaffung, Materialwirtschaft
AC Nummer
AC05039462
Utheses ID
2577
Studienkennzahl
UA | 084 | 157 | |