Βιβλιοθήκη ΟΠΑ - Ψηφιακό Αποθετήριο

ΠΥΞΙΔΑ Ιδρυματικό Αποθετήριο
και Ψηφιακή Βιβλιοθήκη

Όνομα χρήστη
Κωδικός πρόσβασης

Συλλογές :	Ιδρυματικό Αποθετήριο ΟΠΑ / AUEB Institutional Repository Σχολή Διοίκησης Επιχειρήσεων / School of Business Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας / Department of Management Science and Technology Μεταπτυχιακές Εργασίες / Postgraduate dissertations

Τίτλος :	Solving the multi-depot vehicle routing problem

Εναλλακτικός τίτλος :	Λύνοντας το πρόβλημα δρομολόγησης οχημάτων με πολλαπλές αποθήκες

Δημιουργός :	Τριανταφυλλάκης, Ιωάννης Triantafyllakis, Ioannis

Συντελεστής :	Zachariadis, Emmanouil (Επιβλέπων καθηγητής) Chatziantoniou, Damianos (Εξεταστής) Mourtos, Yiannis (Εξεταστής) Athens University of Economics and Business, Department of Management Science and Technology (Degree granting institution)

Τύπος :	Text

Φυσική περιγραφή :	34p.

Γλώσσα :	en

Αναγνωριστικό :	http://www.pyxida.aueb.gr/index.php?op=view_object&object_id=10283

Περίληψη :	Η παρούσα διπλωματική εργασία αφορά στην δημιουργία 4 κατασκευαστικών αλγορίθμων/ευρετικών για το πρόβλημα δρομολόγησης οχημάτων με πολλαπλές αποθήκες, με κάθε αλγόριθμο να περιλαμβάνει μια διαδικασία "επιλογής" και μια διαδικασία "δρομολόγησης". Η πρώτη φάση "επιλογής" χρησιμοποιεί 4 διαφορετικές μεθόδους συσταδοποίησης (μια ανά αλγόριθμο) για να μοιράσει πελάτες σε αποθήκες, ενώ η δεύτερη φάση χρησιμοποιεί μια εκδοχή του ευρετικού αλγορίθμου των Κλαρκ και Ράιτ, με περιορισμό στον αριθμό οχημάτων. Οι 4 αλγόριθμοι προσομοιώθηκαν σε 20 διαφορετικά σενάρια, και όλοι επέδειξαν ικανοποιητικά αποτελέσματα στις επιδόσεις τους, με τον αλγόριθμο συσταδοποίησης Κ-μέσων να φαίνεται ως ο πιο αποτελεσματικός σε σενάρια με αριθμό πελατών σχετικά μικρό και μεσαίο, όπου οι χρόνοι εκτέλεσης είναι σχετικά ασήμαντοι, ενώ για σενάρια με σχετικά μεγάλο αριθμό πελατών, ο πιο αποτελεσματικός αλγόριθμος είναι ο αλγόριθμος ιεραρχικής συσταδοποίησης με πλήρη σύνδεση, ακολουθούμενος από τον αλγόριθμο ιεραρχικής συσταδοποίησης με μέση σύνδεση. This master’s thesis considers 4 construction algorithms/heuristics for the Multi-Depot Vehicle Routing Problem with each one having a “selection” process and a “routing” process. The first phase/process uses 4 different clustering methods (one per algorithm) to assign customers to depots, while the second phase/process implements a variation of the Clarke & Wright Heuristic, with a vehicle number constraint. These 4 heuristics were tested in 20 different benchmark instances and all showed “robust” results in terms of performance, with the K-Means Based Algorithm appearing to be the optimal algorithm for relatively small and medium size instances where the execution times are generally unimportant, while for the relatively large size instances, the optimal algorithm appears to be the Hierarchical Clustering-Based Algorithm with Complete Linkage, followed by the Hierarchical Clustering-Based Algorithm with Average Linkage.

Περίληψη :

Η παρούσα διπλωματική εργασία αφορά στην δημιουργία 4 κατασκευαστικών αλγορίθμων/ευρετικών για το πρόβλημα δρομολόγησης οχημάτων με πολλαπλές αποθήκες, με κάθε αλγόριθμο να περιλαμβάνει μια διαδικασία "επιλογής" και μια διαδικασία "δρομολόγησης". Η πρώτη φάση "επιλογής" χρησιμοποιεί 4 διαφορετικές μεθόδους συσταδοποίησης (μια ανά αλγόριθμο) για να μοιράσει πελάτες σε αποθήκες, ενώ η δεύτερη φάση χρησιμοποιεί μια εκδοχή του ευρετικού αλγορίθμου των Κλαρκ και Ράιτ, με περιορισμό στον αριθμό οχημάτων. Οι 4 αλγόριθμοι προσομοιώθηκαν σε 20 διαφορετικά σενάρια, και όλοι επέδειξαν ικανοποιητικά αποτελέσματα στις επιδόσεις τους, με τον αλγόριθμο συσταδοποίησης Κ-μέσων να φαίνεται ως ο πιο αποτελεσματικός σε σενάρια με αριθμό πελατών σχετικά μικρό και μεσαίο, όπου οι χρόνοι εκτέλεσης είναι σχετικά ασήμαντοι, ενώ για σενάρια με σχετικά μεγάλο αριθμό πελατών, ο πιο αποτελεσματικός αλγόριθμος είναι ο αλγόριθμος ιεραρχικής συσταδοποίησης με πλήρη σύνδεση, ακολουθούμενος από τον αλγόριθμο ιεραρχικής συσταδοποίησης με μέση σύνδεση.
This master’s thesis considers 4 construction algorithms/heuristics for the Multi-Depot Vehicle Routing Problem with each one having a “selection” process and a “routing” process. The first phase/process uses 4 different clustering methods (one per algorithm) to assign customers to depots, while the second phase/process implements a variation of the Clarke & Wright Heuristic, with a vehicle number constraint. These 4 heuristics were tested in 20 different benchmark instances and all showed “robust” results in terms of performance, with the K-Means Based Algorithm appearing to be the optimal algorithm for relatively small and medium size instances where the execution times are generally unimportant, while for the relatively large size instances, the optimal algorithm appears to be the Hierarchical Clustering-Based Algorithm with Complete Linkage, followed by the Hierarchical Clustering-Based Algorithm with Average Linkage.

Λέξη κλειδί :	Συσταδοποίηση Δρομολόγηση Ευρετικές μέθοδοι Βελτιστοποίηση Clustering Routing Heuristics Optimization

Διαθέσιμο από :	2023-03-31 14:24:06

Ημερομηνία έκδοσης :	31-03-2023

Ημερομηνία κατάθεσης :	2023-03-31 14:24:06

Δικαιώματα χρήσης :	Free access

Άδεια χρήσης :

Αρχείο: Triantafyllakis_2023.pdf

Τύπος: application/pdf

Triantafyllakis_2023.zip

Είσοδος