Cumulative Capacitated VRP optimization

Abstract

Η παρούσα διπλωματική εργασία εξετάζει το NP-hard Cumulative Capacitated Vehicle Routing Problem (CCVRP), το οποίο αποτελεί επέκταση του κλασικού Vehicle Routing Problem (VRP). Το CCVRP επικεντρώνεται στην ικανοποίηση της ζήτησης των πελατών, ενώ ταυτόχρονα στοχεύει στην ελαχιστοποίηση του χρόνου αναμονής τους, υπό περιορισμούς όπως η χωρητικότητα των οχημάτων. Στην εργασία αυτή, προτείνεται και εφαρμόζεται για πρώτη φορά μία νέα metaheuristic προσέγγιση για την επίλυση του συγκεκριμένου προβλήματος. Το προτεινόμενο metaheuristic βασίζεται στον συνδυασμό του εποικοδομητικού αλγορίθμου Nearest Neighbor (NN), της μεθόδου αναζήτησης Tabu Search (TS) και του αλγορίθμου Large Neighborhood Search (LNS). Η αποτελεσματικότητα αυτής της προσέγγισης αξιολογείται σε ευρύ φάσμα προβλημάτων, τα οποία είχαν αρχικά χρησιμοποιηθεί από τους Ngueveu et al. (2010) και έκτοτε αποτελούν πρότυπο αξιολόγησης για τέτοιου είδους προβλήματα. Επιπλέον, πραγματοποιείται ανάλυση της συνεισφοράς κάθε επιμέρους μεθόδου στη συνολική ποιότητα της λύσης (NN, NN+TS, NN+TS+LNS). Τα αποτελέσματα δείχνουν ότι, παρόλο που η προσθήκη του TS στον εποικοδομητικό αλγόριθμο έχει περιορισμένη επίδραση από μόνο του, ο συνδυασμός του με το LNS προσφέρει σημαντικά καλύτερα αποτελέσματα, με κόστος τον αυξημένο υπολογιστικό χρόνο. Σε σύγκριση με τα αποτελέσματα αναφοράς, το προτεινόμενο metaheuristic, αν και δεν τα φτάνει, προσεγγίζει αρκετά τις βέλτιστες τιμές, ιδιαίτερα για μικρά και μεσαίου μεγέθους προβλήματα.

This thesis explores the NP-hard Cumulative Capacitated Vehicle Routing Problem (CCVRP), which derived from the Vehicle Routing Problem (VRP). CCVRP focuses on fulfilling customer demands, while trying to minimize their waiting times under some constraints, such as vehicle capacity limitations. In this thesis, a new metaheuristic approach is tested for the first time on that type of problem. The proposed metaheuristic is based on the combination of the constructive algorithm Nearest Neighbor (NN), with the metaheuristic search method of Tabu Search (TS) and the two-face algorithm Large Neighborhood Search (LNS). The effectiveness of this approach is evaluated on a wide range of problems that were initially used by Ngueveu et al. (2010) and since then are a standard benchmark for that type of problem. Additionally, there is an analysis on the contribution that each component of the full algorithm has on the quality of the final solution (NN alone, NN+TS, and full NN+TS+LNS). Results indicate that while adding TS to the constructive algorithm has a small impact by itself, combining it with LNS yields significantly better results at the expense of computational time. Compared to the benchmark results, even though the metaheuristic approach does not match them for every instance, it is close to them, especially for small and medium instances.