Solving the multi-depot vehicle routing problem

Abstract

Η παρούσα διπλωματική εργασία αφορά στην δημιουργία 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.