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

Τίτλος :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.
Λέξη κλειδί :Συσταδοποίηση
Δρομολόγηση
Ευρετικές μέθοδοι
Βελτιστοποίηση
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