Optimization methods for the Family Capacitated Vehicle Routing Problem

Abstract

Η παρούσα διπλωματική εργασία εξετάζει το Family Capacitated Vehicle Routing Problem (F-CVRP), ένα εξειδικευμένο NP-hard πρόβλημα που ανήκει στην ευρύτερη κατηγορία των Προβλημάτων Δρομολόγησης Οχημάτων (VRP). Το F-CVRP μοντελοποιεί πραγματικές προκλήσεις στον τομέα των logistics, όπως η διαχείριση αποθηκών, όπου η βελτιστοποίηση των δρομολογίων με ακριβείς μεθόδους καθίσταται μη πρακτική λόγω του μεγέθους του προβλήματος.Διεξήχθη εκτενής βιβλιογραφική ανασκόπηση για την ανάλυση υπαρχουσών μεθοδολογιών επίλυσης του F-CVRP, αξιοποιώντας τόσο ευρετικές όσο και μεταευρετικές προσεγγίσεις. Η εργασία τεκμηριώνει την υλοποίηση διαφόρων τεχνικών επίλυσης, συμπεριλαμβανομένου ενός αλγορίθμου Ελάχιστου Κόστους Εισαγωγής για τη δημιουργία αρχικής εφικτής λύσης. Στη συνέχεια, εφαρμόζεται επαναληπτική Τοπική Έρευνα (LS) με tabu policy, η οποία βελτιώνει τα δρομολόγια μέσω μικρών τοπικών τροποποιήσεων, αποτρέποντας παράλληλα την επαναληπτική εξερεύνηση των ίδιων λύσεων. Επιπλέον, χρησιμοποιείται μία προσέγγιση Μεγάλης Γειτονιάς (LNS), ενισχυμένη με ένα Adaptive Memory framework, που εκμεταλλεύεται ποιοτικά χαρακτηριστικά των λύσεων για τη δημιουργία βελτιωμένων δρομολογίων.Οι προτεινόμενες μεθοδολογίες αξιολογήθηκαν με χρήση δεδομένων αναφοράς, συγκρίνοντας την υπολογιστική τους απόδοση και την ποιότητα των λύσεων. Τα αποτελέσματα δείχνουν ότι αυτές οι ευρετικές και μεταευρετικές τεχνικές είναι ιδιαίτερα αποτελεσματικές, παρέχοντας ανταγωνιστικές λύσεις σε εύλογους χρόνους υπολογισμού, ειδικά για μεγάλης κλίμακας περιπτώσεις προβλημάτων.

This thesis explores the Family Capacitated Vehicle Routing Problem (F-CVRP), a specialized NP-hard problem within the broader class of Vehicle Routing Problems (VRPs). The F-CVRP models real-world logistics challenges, such as warehouse management, where optimizing routing costs with exact methods is impractical due to problem size.A comprehensive literature review was conducted to analyze existing methodologies for solving the F-CVRP, drawing from heuristic and metaheuristic approaches. The thesis documents the implementation of several solution techniques, including a Minimum Cost Insertion algorithm for generating an initial feasible solution. An iterative Local Search (LS) with a tabu policy is applied, refining routes through small incremental changes while preventing cycling. Additionally, a Large Neighborhood Search (LNS) approach, augmented with an Adaptive Memory framework, leverages high-quality solution components to generate improved routes.The proposed methodologies were evaluated against benchmark datasets, comparing computational performance and solution quality. Results indicate that these heuristic and metaheuristic techniques are robust, yielding competitive solutions within reasonable computation times, particularly for large problem instances.