Optimization methodologies for the clustered vehicle routing problem

Abstract

Το Ομαδοποιημένο Πρόβλημα Δρομολόγησης Οχημάτων (Clustered Vehicle Routing Problem – CluVRP) αποτελεί επέκταση του κλασικού προβλήματος VRP, όπου οι πελάτες είναι προκαθορισμένα ομαδοποιημένοι σε clusters και εξυπηρετούνται διαδοχικά, με σεβασμό στους περιορισμούς χωρητικότητας των οχημάτων. Η παρούσα διπλωματική εργασία προτείνει ένα πλαίσιο επίλυσης δύο φάσεων για το CluVRP. Αρχικά, κατασκευάζεται μία αρχική λύση εφαρμόζοντας τον αλγόριθμο nearest-neighbor στα κέντρα των clusters, δημιουργώντας έτσι μία αρχική διαδρομή με βάση τα κέντρα. Στη συνέχεια, εφαρμόζεται μια διαδικασία δυναμικού προγραμματισμού τύπου split, η οποία διαχωρίζει αυτή τη διαδρομή σε υποδιαδρομές που ικανοποιούν τους περιορισμούς χωρητικότητας. Κάθε τέτοια διαδρομή με κέντρα επεκτείνεται ώστε να περιλαμβάνει όλους τους πελάτες του αντίστοιχου cluster. Στη δεύτερη φάση, εφαρμόζονται δύο μεταευρετικοί αλγόριθμοι Tabu Search: ο κλασικός Tabu Search (Classic Tabu Search), που χρησιμοποιεί σταθερή διάρκεια απαγόρευσης και εξετάζει τυχαίες κινήσεις two-opt και swap σε κάθε επανάληψη, και ο δυναμικός Tabu Search (Adaptive Tabu Search), ο οποίος εφαρμόζει τις ίδιες κινήσεις αλλά περιορίζεται σε δυναμικά προσαρμοζόμενη λίστα επιλογών και τροποποιεί τη διάρκεια της απαγορευτικής μνήμης του με βάση τη στασιμότητα της αναζήτησης.

The Clustered Vehicle Routing Problem (CluVRP) extends the classic VRP by requiring that customers are pre-assigned to fixed clusters, served in contiguous blocks under vehicle-capacity limits. This thesis introduces a two-phase solution framework for CluVRP. At first, a feasible initial solution is constructed by applying a nearest-neighbor heuristic on the given cluster centroids to form a preliminary centroid tour, then uses a split dynamic programming procedure to partition that tour into capacity-feasible routes. Each centroid-based route is expanded into its full customer. The next part embeds these moves in two Tabu Search metaheuristics; a Classic Tabu Search (CTS) that uses a fixed tenure and evaluates random two-opt and swap moves per iteration and an Adaptive Tabu Search (ATS) that shares the same moves but restricts itself to a dynamically-sized shortlist and adjusts its tenure based on search stagnation.