|
| Συλλογές |
|
| Τίτλος |
Solving the multi-depot vehicle routing problem
|
| Εναλλακτικός τίτλος |
Λύνοντας το πρόβλημα δρομολόγησης οχημάτων με πολλαπλές αποθήκες
|
| Δημιουργός |
Τριανταφυλλάκης, Ιωάννης, Triantafyllakis, Ioannis
|
| Συντελεστής |
Athens University of Economics and Business, Department of Management Science and Technology
Chatziantoniou, Damianos
Mourtos, Yiannis
Zachariadis, Emmanouil
|
| Τύπος |
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
|
| Άδεια χρήσης |
https://creativecommons.org/licenses/by/4.0/
|