Titelaufnahme

Titel
Customer clustering in vehicle routing problems with time windows and multiple service workers / Dagmar D. Tschabrun
Verfasser/ VerfasserinTschabrun, Dagmar D.
Begutachter / BegutachterinReimann, Marc
Erschienen2014
UmfangVII, 71 Bl. : Zsfassung (2 Bl.) ; graph. Darst.
HochschulschriftGraz, Univ., Masterarb., 2014
Anmerkung
Zsfassung in dt. und engl. Sprache
SpracheEnglisch
DokumenttypMasterarbeit
Schlagwörter (GND)Travelling-salesman-Problem / Tourenplanung / Travelling-salesman-Problem / Tourenplanung / Online-Publikation
URNurn:nbn:at:at-ubg:1-58234 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Customer clustering in vehicle routing problems with time windows and multiple service workers [0.49 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

Diese Masterarbeit beschäftigt sich mit einer Variante des bekannten Tourenplanungsproblems mit Zeitfenstern (Vehicle Routing Problem with Time Windows, VRPTW). Die grundlegende Idee besteht in der Zusammenfassung von Kunden mit ähnlichen Charakteristiken. Durch ein Hinzufügen zusätzlicher Servicekräfte wird versucht, die gesamte Bedienzeit bzw. die Anzahl an benötigten Clustern zu minimieren. Diese Vorgehensweise ist vor allem dann sinnvoll, wenn das Parken bei einem Kunden nur innerhalb bestimmter Zeitfenster oder überhaupt nicht möglich ist. Dies trifft speziell auf dicht besiedelte Gebiete zu, in denen es notwendig ist, auf Parkplätze in der näheren Umgebung des Kunden auszuweichen. Diese Variante des VRPTW wird in der vorliegenden Masterarbeit als Kundenclustering in Tourenplanungsproblemen mit Zeitfenstern und mehreren Servicekräften bezeichnet (Customer Clustering Vehicle Routing Problem with Time Windows and Multiple Service Workers, CCVRPTWMS). Das Hauptaugenmerk der Arbeit liegt auf der Implementierung von fünf heuristischen Clustering Strategien welche entweder die gesamte Bedienzeit oder die Anzahl an Clustern minimieren. Integraler Bestandteil des Clusterings ist die Reihung der Kunden innerhalb des Clusters nach ihrer Belieferung durch die Servicekräfte. Als Ergebnis der verschiedenen Clustering Strategien ergeben sich der früheste und späteste Startzeitpunkt sowie die Bedienzeit für jeden Cluster. Diese Werte können für das Lösen eines VRPTW verwendet werden. Da das beschriebene Problem noch nicht publiziert wurde und auch keine Testinstanzen vorhanden sind, müssen neue Testinstanzen generiert werden. Abschließend werden die fünf entwickelten Heuristiken mit verschiedenen Parametersätzen getestet und evaluiert.

Zusammenfassung (Englisch)

This master thesis addresses a variant of the Vehicle Routing Problem with Time Windows (VRPTW). The basic idea is to combine customers with similar characteristics to clusters and to assign extra service workers to the clusters in order to reduce the total service time or the number of clusters. This variant is particularly relevant to situations in which parking at a customer's site is only allowed within limited time slots or not possible at all. This is especially relevant for densely populated areas. Accordingly, using a parking site in the vicinity of the customers is necessary. In this master thesis, this variant of the VRPTW is referred to as the Customer Clustering Vehicle Routing Problems with Time Windows and Multiple Service Workers (CCVRPTWMS). The main focus of this thesis is on the implementation of five different heuristic clustering strategies which minimize either the total service time of all clusters or the number of clusters. The essential part of the clustering is to schedule the order of the customers inside a cluster in which they are serviced by the service workers. The results of the different clustering strategies are the earliest starting time, the latest starting time and the service time of each cluster. These values can then serve as the input for an algorithm which solves the VRPTW. Since the illustrated problem has not been reported in the literature yet and no suitable benchmark instances exist, it is necessary to develop new instances for testing the different heuristics. Finally, the five developed heuristics are tested with different parameter settings to evaluated which one minimizes the total service time or reduces the number of clusters the most.