Optimization methodologies for clustered vehicle routing problems

Abstract

Αυτή η εργασία αφορά το Ομαδοποιημένο Πρόβλημα Δρομολόγησης Οχημάτων (CluVRP), μια επέκταση του γνωστού Προβλήματος Δρομολόγησης Οχημάτων (VRP). Μετά από μια σύντομη βιβλιογραφική ανασκόπηση των μεθοδολογιών βελτιστοποίησης που έχουν αναπτυχθεί για να λύσουν το πρόβλημα, καθώς και ορισμένων εφαρμογών του στον πραγματικό κόσμο, παρουσιάζεται μια υλοποίηση με ένα συνδυασμό γνωστών μεθοδολογιών για την επίλυση του προβλήματος. Συγκεκριμένα, το πρόβλημα χωρίζεται σε δύο προβλήματα, το πρόβλημα δρομολόγησης υψηλού επιπέδου της επίσκεψης σε ομάδες πελατών και το πρόβλημα χαμηλού επιπέδου της δρομολόγησης εντός των ομάδων. Χρησιμοποιούνται δύο άπληστες προσεγγίσεις για να βρεθεί μια γρήγορη αρχική λύση, ενώ τρεις μεταευρετικές μέθοδοι χρησιμοποιούνται για τη βελτιστοποίησή της. Τέλος, η υλοποίηση δοκιμάζεται σε διάφορες συλλογές προβλημάτων VRP προσαρμοσμένες για το CluVRP και τα αποτελέσματα αναλύονται για να προσδιοριστεί ποια μέθοδος είναι πιο αποδοτική από άποψη χρόνου και κόστους.

This report addresses the Clustered Vehicle Routing Problem (CluVRP), an extension of the renowned Vehicle Routing Problem (VRP). After a brief literature review of the optimization methodologies applied to the problem and some real-world applications, an implementation of some well-known methodologies combined to solve the problem is presented. In particular, the problem is divided into two problems, the high-level routing problem of visiting customer clusters and the low-level problem of intracluster routing. Two greedy approaches are employed to get a fast initial solution, while three metaheuristic methods are utilized to optimize it. Finally, the implementation is tested on various VRP benchmark instances adapted for the CluVRP, and the results are analyzed to determine which method is more time- and cost-effective.