Detailansicht
A large neighbourhood search for the 2-Echelon capacitated vehicle routing problem
Ulrich Breunig
Art der Arbeit
Diplomarbeit
Universität
Universität Wien
Fakultät
Fakultät für Wirtschaftswissenschaften
Betreuer*in
Richard Hartl
DOI
10.25365/thesis.19152
URN
urn:nbn:at:at-ubw:1-29680.41316.541363-0
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Verschiedene Konzepte der "City Logistic" behandeln die Auslieferung von Waren in dicht besiedelten Ballungsräumen. Einige davon laufen auf eine zweistufige Belieferung der Endkunden hinaus. Die Waren werden dabei in Zwischenlagern, sogenannten Satelliten, von großen Lastwägen auf kleinere Lieferwägen umgeladen.
Das grundlegende Prinzip stammt ursprünglich aus Rom, wo große Lastwägen nicht durch die engen Straßen im historischen Stadtkern passen. Die Satelliten liegen meist mit günstiger Verkehrsanbindung am Stadtrand verteilt.
Wir zeigen ein mathematisches Modell für dieses "2E-CVRP" (zweistufiges kapazitiertes Vehikel Routing Problem) und optimale Lösungen für kleine Testbeispiele, für die das Problem in annehmbarer Zeit exakt lösbar ist. Weiters zeigen wir die Implementierung einer Metaheuristik mit lokaler Suche, die auch für größere Aufgabenstellungen in relativ kurzer Zeit gute Ergebnisse liefert. Die optimalen Lösungen der kleinen Testbeispiele werden von der Metaheuristik in Bruchteilen der Rechenzeit gefunden, die das exakte Verfahren dafür braucht.
Für mehr als die Hälfte der getesteten bekannten Problemstellungen wurden die bisher besten bekannten Lösungen verbessert.
Abstract
(Englisch)
City Logistics involves different concepts of delivering goods to customers within densely populated areas. Many of them involve a two-tiered setup, which then is modelled in terms of a Two-Echelon Capacitated Vehicle Routing Problem. Large trucks deliver goods from a depot to intermediate facilities, so called satellites, where freight is transferred to smaller vehicles (city freighters), which then deliver it to customers. The goal is to satisfy all customer demands with the lowest possible costs and driven distance. A local-search metaheuristic based on a Large Neighbourhood Search is developed and implemented to find good solutions within limited computing time. A mixed integer programming model is used to create benchmarks for evaluating the quality of the solutions found by the metaheuristic, at least for small instances, where computing time is sufficient to solve to optimality.
Schlagwörter
Schlagwörter
(Englisch)
2E-CVRP City Logistic Two-Echelon Capacitated Vehicle Routing Problem Meta-Heuristic Large Neighbourhood Search
Schlagwörter
(Deutsch)
City Logistik Meta-Heuristik Transportproblem Routenproblem zweistufig
Autor*innen
Ulrich Breunig
Haupttitel (Englisch)
A large neighbourhood search for the 2-Echelon capacitated vehicle routing problem
Paralleltitel (Deutsch)
Eine Large Neighbourhood Search für das zweistufige kapazitierte Vehikel Routing Problem
Publikationsjahr
2012
Umfangsangabe
VI, 52 S. : graph. Darst.
Sprache
Englisch
Beurteiler*in
Richard Hartl
Klassifikationen
85 Betriebswirtschaft > 85.00 Betriebswirtschaft: Allgemeines ,
85 Betriebswirtschaft > 85.03 Methoden und Techniken der Betriebswirtschaft
AC Nummer
AC09025544
Utheses ID
17161
Studienkennzahl
UA | 157 | | |