Detailansicht
Vehicle routing problems with service consistency considerations
Attila Andras Kovacs
Art der Arbeit
Dissertation
Universität
Universität Wien
Fakultät
Fakultät für Wirtschaftswissenschaften
Betreuer*in
Richard Hartl
DOI
10.25365/thesis.34884
URN
urn:nbn:at:at-ubw:1-29551.33852.135666-2
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
In der Tourenplanung wird Servicekonsistenz oft als Mittel zur Steigerung der Kundenzufriedenheit eingesetzt. Ein Service, das jeden Tag zur gleichen Zeit stattfindet und von einem bekannten Fahrer durchgeführt wird, wird von Kunden hoch geschätzt. Zusätzlich arbeiten Fahrer effizienter, wenn sie immer wieder die gleichen Kunden in den gleichen Servicezonen besuchen.
Diese Dissertation beginnt mit einem Literaturüberblick über Arbeiten, die sich mit Servicekonsistenz in der Tourenplanung beschäftigen.
Ausgehend von dem Consistent Vehicle Routing Problem (ConVRP) präsentieren wir drei neue Modelle, anhand derer wir den Zielkonflikt zwischen Servicekonsistenz und Fahrtkosten untersuchen.
Als Erstes präsentieren wir eine gelockerte Variante des ConVRPs, bei der die Abfahrtszeiten vom Depot frei gewählt werden dürfen, um die Ankunftszeiten bei den Kunden anzupassen.
Im ConVRP wird Kundenzufriedenheit dadurch erreicht, dass ein Kunde von maximal einem Fahrer besucht wird und die maximale Abweichung zwischen den Besuchszeiten beschränkt ist.
In unserer zweiten ConVRP-Variante darf jeder Kunde von mehreren Fahrern besucht werden und die Abweichung in den Besuchszeiten wird in der Zielfunktion pönalisiert.
Abfahrtszeiten vom Depot sind flexibel, um die zeitliche Konsistenz zu verbessern. Außerdem dürfen Kunden jeweils nur am Vormittag oder nur am Nachmittag besucht werden.
Diese ConVRP-Variante wird Generalized ConVRP (GenConVRP) genannt.
Drittens präsentieren wir das Multi-Objective GenConVRP (MOGenConVRP) mit drei eigenständigen Zielfunktionen: Fahrtkosten, zeitliche Konsistenz und Fahrerkonsistenz.
Mehrzieloptimierung ist ein eleganter Ansatz, um den Konflikt zwischen unterschiedlichen Zielfunktionen zu untersuchen.
Für jede Problemvariante entwickeln wir spezialisierte Algorithmen.
Für unsere Experimente verwenden wir Benchmark-Instanzen für das ConVRP und neue Instanzen für das generische Problem.
Es ist empfehlenswert Kundenzufriedenheit durch geringe Abweichungen in den Ankunftszeiten zu erhöhen, da die Konsistenz in den Besuchszeiten bereits mit minimalem Kostenaufwand und mit minimaler Vergrößerung der Fahrzeugflotte deutlich verbessert werden kann. Die Variation in den Abfahrtszeiten vom Depot, die notwendig ist um die zeitliche Konsistenz zu verbessern, ist minimal.
Die durchschnittlichen Kosten, um jeden Kunden mit einem Fahrer zu besuchen, hängen von der Konsistenz in den Besuchszeiten ab: Je höher die Abweichung in den Besuchszeiten, desto höher sind die durchschnittlichen Kosten für Fahrerkonsistenz. D.h. Fahrerkonsistenz und zeitliche Konsistenz sind in vielen Fällen konfliktfreie Zielfunktionen.
Die Kosten können erheblich gesenkt werden, wenn jeder Kunde von mehr als einem Fahrer besucht werden darf.
Abstract
(Englisch)
In vehicle routing, customer satisfaction is often a result of consistent service. Customers appreciate service at regular times of the day provided by the same driver each time. Additionally, drivers become more familiar with their tasks if they visit the same customers and service regions repeatedly.
In this thesis, we first survey literature that addresses service consistency in vehicle routing.
Based on the consistent vehicle routing problem (ConVRP), we then introduce three new models in order to examine the trade-off between service consistency and routing cost.
First, we present a relaxed variant of the original ConVRP where the departure times from the depot
can be delayed to adjust the arrival times at customers.
The ConVRP takes customer satisfaction into account by assigning one driver to a customer and by bounding the variation in the arrival
times over a given planning horizon.
In our second ConVRP variant, each customer is visited by a limited number of drivers and the variation in the arrival times is penalized in the objective function. The vehicle departure times may be adjusted to obtain stable arrival times. Additionally, customers are associated with AM/PM time windows.
The problem is referred to as the generalized ConVRP (GenConVRP).
Third, we present the multi-objective GenConVRP (MOGenConVRP) with three independent objective functions: travel cost, arrival time consistency, and driver consistency.
Multi-objective optimization is a flexible approach for examining the trade-off between conflicting objective functions.
For each problem variant, we devise specialized solution algorithms.
We perform experiments on the benchmark instances for the ConVRP and on new instances generated for the generalized problem.
Decreasing variations in the arrival times, in order to improve customer satisfaction, is recommended to service providers because arrival time consistency can be improved significantly with modest increases in travel cost and fleet size. The variation of the vehicle departure times necessary to improve arrival time consistency is minor.
The average cost of visiting each customer with a separate driver depends on the level of arrival time consistency: The larger the maximum arrival time difference the higher the average cost of driver consistency, i.e., arrival time consistency and driver consistency tend to be non-conflicting.
Remarkable cost savings can be obtained by allowing more than one driver per customer.
Schlagwörter
Schlagwörter
(Englisch)
vehicle routing metaheuristic service consistency
Schlagwörter
(Deutsch)
Tourenplanung Metaheuristik Konsistenzanforderungen
Autor*innen
Attila Andras Kovacs
Haupttitel (Englisch)
Vehicle routing problems with service consistency considerations
Paralleltitel (Deutsch)
Tourenplanungsprobleme mit Konsistenzanforderungen
Publikationsjahr
2014
Umfangsangabe
XVIII, 173 S. : graph. Darst.
Sprache
Englisch
Beurteiler*innen
Walter Gutjahr ,
Daniele Vigo
Klassifikationen
31 Mathematik > 31.80 Angewandte Mathematik ,
85 Betriebswirtschaft > 85.03 Methoden und Techniken der Betriebswirtschaft
AC Nummer
AC12134180
Utheses ID
30940
Studienkennzahl
UA | 094 | 151 | 403 |