Detailansicht
Vehicle routing with multi-dimensional loading constraints
Günther Josef Füllerer
Art der Arbeit
Dissertation
Universität
Universität Wien
Fakultät
Fakultät für Wirtschaftswissenschaften
Betreuer*in
Richard Hartl
DOI
10.25365/thesis.936
URN
urn:nbn:at:at-ubw:1-29663.64063.338655-8
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Zwei der wichtigsten Problemstellungen in der Transportlogistik behandeln einerseits das
Verladen von Produkten auf LKWs und andererseits die ressourceneffiziente Belieferung
der Kunden auf dem gegebenen Straßennetz.
Bis dato wurden diese zwei Probleme mit Hilfe von kombinatorischer Optimierung getrennt
von einander behandelt und es existieren zahlreiche Publikationen zu beiden Themen in
den einschlägigen Fachzeitschriften. Erst in den letzten drei Jahren wurde einem integrierten
Ansatz, der beide Problemstellungen zu einem Optimierungsproblem vereint betrachtet.
Somit werden die Bestellungen einzelner Kunden nicht bloß über ihre Gewichte,
sondern auch über ihre Abmessungen definiert. Der klare Vorteil dieses Ansatzes liegt
darin, dass die einzelnen LKW Routen auch tatsächlich so gefahren werden können, da
die tatsächliche Beladung auch berücksichtigt wurde. Andererseits steigt die kombinatorische
Komplexität drastisch, weil das kapazitierte Vehicle Routing Problem (CVRP)
mit Bin Packing Problemen (BPP) kombiniert wird und beide Probleme für sich alleine
NP schwer sind.
Diese Dissertation präsentiert drei verschiedene Probleme, die sich neben der Frage welches
Fahrzeug beliefert welchen Kunden auch der Frage widmet, wie die bestellten Produkte
auf den LKW geladen werden können.
- Das Multi-Pile Vehicle Routing Problem (MP-VRP) bindet in das klassische CVRP
eine Beladekomponente ein, die zwischen eindimensionalem und zweidimensionalem
Bin Packing Problem angesiedelt ist. Die Problemstellungen wurden durch einen
österreichischen Holzzulieferer motiviert.
- Beim kapazitierten Vehicle Routing Problem mit zweidimensionalen Beladenebenbedingungen
(2L-CVRP) bestellt jeder Kunden rechteckige Objekte, welche auf der
rechteckigen Beladefläche des LKWs untergebracht werden müssen.
- Das allgemeinste Beladeproblem stellt das dreidimensionale Bin Packing Problem
dar. Hier bestellt jeder Kunde dreidimensionale Objekte, welche auf dem dreidimensionalen
Laderaum des LKWs untergebracht werden müssen. Das klassische dreidimensionale Bin Packing
Problem wird durch zusätzliche Beladenebenbedingungen
erweitert.
Momentan gibt es zu diesen kombinierten Problemen nur wenige Publikationen. Exakte
Ansätze gibt es momentan nur zwei, einen für das MP-VRP (hier können Probleme bis
zu 50 Kunden gelöst werden) und für das 2L-CVRP (hier können Probleme bis zu 30
Kunden exakt gelöst werden). Für Realweltanwendungen müssen jedoch Heuristiken gefunden
werden, welche größere Probleminstanzen lösen können. In dieser Arbeit wird
für alle drei Problemstellungen ein Ameisenalgorithmus verwendet und mit bestehenden
Lösungsansätzen aus dem Bereich der Tabu-Suche (TS) verglichen. Es wird gezeigt, dass
der präsentierte Ameisenansatz für die zur Verfügung stehenden Benchmarkinstanzen die
besten Ergebnisse liefert. Darüber hinaus wird der Einfluss verschiedener Beladenebenbedingungen
auf die Lösungsgüte untersucht, was eine wichtige Entscheidungsgrundlage für
Unternehmen darstellt.
Abstract
(Englisch)
Two of the most important problems in distribution logistics concern the loading of the
freight into the vehicles, and the successive routing of the vehicles along the road network,
with the aim of satisfying the demands of the clients.
In the combinatorial optimization field, these two loading and routing problems have been
studied intensively but separately yielding a large number of publications either for routing
or packing problems. Only in recent years some attention has been brought to their
combined optimization. The obvious advantage is that, by considering the information on
the freight to be loaded, one can construct more appropriate routes for the vehicles. The
counterpart is that the combinatorial difficulty of the problem increases consistently. One
must not forget that both the vehicle routing problem and the bin packing problem are
NP hard problems!
This thesis presents three different problems concerning the combination of routing and
loading (packing) problems.
- The Multi-Pile Vehicle Routing Problem (MP-VRP) incorporates an interesting
loading problem situated between one dimensional and two dimensional bin packing.
This problem has been inspired by a real world application of an Austrian wood
distributing company.
- The Capacitated Vehicle Routing Problem with Two-Dimensional Loading Constraints
(2L-CVRP) augments the classical Capacitated Vehicle Routing Problem
by requiring the satisfaction of general two dimensional loading constraints. This
means that customers order items represented by rectangles that have to be feasibly
placed on the rectangular shaped loading surface of the used vehicles.
- The most general packing problem to be integrated is the Three Dimensional Bin
Packing Problem (3DBPP) resulting in the Capacitated Vehicle Routing Problem
with Three-Dimensional Loading Constraints (3L-CVRP). Here the order of each
customer consists of cuboid shaped items that have to be feasibly placed on the loading space of the vehicle. A feasible placement is influenced by additional constraints
that extend the classical 3DBPP.
Concerning the literature solving these problems with exact methods it becomes clear that
this is only possible to some very limited extent (e.g.: the MP-VRP can be solved up to
50, the 2L-CVRP can be solved exact up to 30 customers, for the 3L-CVRP no exact
approach exists). Nevertheless for real world applications the problem instances are much
larger which justifies the use of (meta-)heuristics.
The rank-based Ant System was modified and extended to solve the combined problem
by integrating different packing routines. The designed methods outperform the existing
techniques for the three different problem classes.
The influence of different loading constraints on the objective value is investigated/is
intensively studied to support the decision makers of companies facing similar problems.
Schlagwörter
Schlagwörter
(Englisch)
Vehicle Routing Multidimensional Packing Loading Constraints
Schlagwörter
(Deutsch)
Vehicle Routing Packprobleme Beladenebenbedingungen
Autor*innen
Günther Josef Füllerer
Haupttitel (Englisch)
Vehicle routing with multi-dimensional loading constraints
Paralleltitel (Deutsch)
Vehicle Routing mit mehrdimensionalen Beladenebenbedingungen
Publikationsjahr
2008
Umfangsangabe
XVIII, 124 S. : graph. Darst.
Sprache
Englisch
Beurteiler*innen
Richard Hartl ,
Walter Gutjahr
Klassifikation
85 Betriebswirtschaft > 85.99 Betriebswirtschaft: Sonstiges
AC Nummer
AC05038212
Utheses ID
710
Studienkennzahl
UA | 084 | 157 | |