Detailansicht
The time-dependent vehicle routing problem
Irena Ilic
Art der Arbeit
Diplomarbeit
Universität
Universität Wien
Fakultät
Fakultät für Wirtschaftswissenschaften
Betreuer*in
Richard Hartl
DOI
10.25365/thesis.21237
URN
urn:nbn:at:at-ubw:1-30076.73727.812959-7
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
In der Tourenplanung wird meistens angenommen, dass die Reisezeiten während des gesamten Planungshorizonts konstant sind. In der Realität ist es jedoch so, dass es während des Tages zu variablen Reisezeiten kommt. Vor allem im urbanen Bereich führen Staus zu längeren Reisezeiten. Im tageszeitabhängigen Tourenplanungsproblem wird dieser Aspekt berücksichtigt indem man annimmt, dass die Reisezeiten von der Tageszeit abhängen.
Die vorliegende Diplomarbeit gibt einen Überblick über die tageszeitabhängige Tourenplanung und präsentiert die Ergebnisse einer experimentellen Studie.
Im ersten Teil dieser Arbeit werden das klassische Tourenplanungsproblem und verschiedene Lösungsverfahren vorgestellt. Danach wird das tageszeitabhängige Tourenplanungsproblem beschrieben.
Im zweiten Teil wird zunächst ein Algorithmus basierend auf der Tabu Suche entwickelt um das kapazitierte Tourenplanungsproblem zu lösen. Die Lösungen werden dann mit tageszeitabhängigen Szenarien evaluiert, wobei jedes Szenario einen anderen Grad an Zeitabhängigkeit repräsentiert. Es wird gezeigt, dass die Gesamtkosten im Vergleich zu den ursprünglichen Kosten steigen. Desweiteren werden die Tourlängenbeschränkungen von vielen Touren nicht mehr erfüllt. Schließlich wird der ursprüngliche Algorithmus adaptiert um das tageszeitabhängige kapazitierte Tourenplanungsproblem zu lösen. Es wird gezeigt, dass die Gesamtkosten verbessert werden können wenn man tageszeitabhängige Reisezeiten einsetzt. Die Verbesserung ist umso stärker, je höher der Grad an Zeitabhängigkeit. Zusätzlich erfüllen die neuen Lösungen alle Tourlängenbeschränkungen.
Abstract
(Englisch)
Most vehicle routing models assume constant travel times throughout the whole planning horizon. In reality, however, travel times vary during the day. This is especially true for urban areas where daily traffic congestion leads to longer travel times. The time-dependent vehicle routing problem (TDVRP) takes this aspect into account by assuming that travel times depend on the time of the day.
This diploma thesis gives an overview of the TDVRP and presents the results of an experimental study.
The first part introduces the VRP and different solution methods. This is followed by a detailed description of the TDVRP.
The second part of the thesis presents an algorithm based on tabu search to solve the capacitated VRP (CVRP). Afterwards, the best solutions of the CVRP are evaluated with five time-dependent scenarios, each representing a different degree of time-dependency. Compared to the original CVRP results, the total costs increase significantly and several routes become infeasible. In the next step, the original algorithm is adapted to solve the TD-CVRP. It is shown that the total costs can be improved when assuming time-dependent travel times. The improvement is higher, the higher the degree of time-dependency. Furthermore, the new solutions satisfy all tour length constraints.
Schlagwörter
Schlagwörter
(Englisch)
vehicle routing problem time-dependent travel times
Schlagwörter
(Deutsch)
Tourenplanung tageszeitabhängige Reisezeiten
Autor*innen
Irena Ilic
Haupttitel (Englisch)
The time-dependent vehicle routing problem
Paralleltitel (Deutsch)
Das tageszeitabhängige Tourenplanungsproblem
Publikationsjahr
2012
Umfangsangabe
VI, 67 S. : graph. Darst.
Sprache
Englisch
Beurteiler*in
Richard Hartl
Klassifikation
85 Betriebswirtschaft > 85.99 Betriebswirtschaft: Sonstiges
AC Nummer
AC09409110
Utheses ID
18997
Studienkennzahl
UA | 157 | | |