Investigating optimization techniques for the consistent vehicle routing problem with heterogenous fleet

Abstract

Η παρούσα διατριβή διερευνά τεχνικές βελτιστοποίησης για το πρόβλημα συνεπούς δρομολόγησης οχημάτων με ετερογενή στόλο (HConVRP), μια σύνθετη παραλλαγή του προβλήματος δρομολόγησης οχημάτων (VRP) που ενσωματώνει την ετερογένεια του στόλου και τους περιορισμούς συνέπειας των υπηρεσιών. Η μελέτη επικεντρώνεται στη διασφάλιση ότι οι πελάτες λαμβάνουν υπηρεσίες από το ίδιο όχημα και τον ίδιο οδηγό σε πολλαπλές περιόδους, βελτιστοποιώντας παράλληλα το λειτουργικό κόστος.Προτείνεται ένας αλγόριθμος Variable Neighborhood Descent (VND) ως μια αποτελεσματική ευρετική προσέγγιση για την επίλυση του HConVRP. Ο αλγόριθμος διερευνά συστηματικά διαφορετικές δομές γειτονιάς - όπως ChangeVehicleChain, SwapVehicle, Relocation και 2-Opt - για να βελτιώσει επαναληπτικά τις λύσεις και να επιτύχει οικονομικά αποδοτική δρομολόγηση, διατηρώντας παράλληλα τη συνέπεια των υπηρεσιών.Πραγματοποιήθηκαν υπολογιστικά πειράματα σε σύνολα δεδομένων με διαφορετικές συνθέσεις πελατών (συχνών και μη συχνών), αποδεικνύοντας την αποτελεσματικότητα του VND στο χειρισμό της ποικιλομορφίας του στόλου και των απαιτήσεων συνέπειας. Τα αποτελέσματα υπογραμμίζουν ότι η VND παρέχει ανταγωνιστικές λύσεις σε σύγκριση με την Ιεραρχική Αναζήτηση Tabu (HTS), ενώ προσφέρει μεγαλύτερη υπολογιστική αποτελεσματικότητα για instances μεγάλης κλίμακας.This thesis investigates optimization techniques for the Consistent Vehicle Routing Problem with Heterogeneous fleet (HConVRP), a complex variant of the Vehicle Routing Problem (VRP) that integrates fleet heterogeneity and service consistency constraints. The study focuses on ensuring that customers receive service from the same vehicle and driver across multiple periods while optimizing operational costs.A Variable Neighborhood Descent (VND) algorithm is proposed as an effective heuristic approach to solve HConVRP. The algorithm systematically explores different neighborhood structures—such as ChangeVehicleChain, SwapVehicle, Relocation, and 2-Opt—to iteratively refine solutions and achieve cost-efficient routing while maintaining service consistency.Computational experiments were conducted on datasets with varying customer compositions (frequent and non-frequent), demonstrating the efficacy of VND in handling fleet diversity and consistency requirements. The results highlight that VND provides competitive solutions compared to Hierarchical Tabu Search (HTS) while offering greater computational efficiency for large-scale instances.Additionally, a custom web application was developed for solution generation, evaluation, and comparison, enhancing the practical applicability of the research. This study contributes to the field by advancing heuristic methods for multi-period routing problems, with direct applications in logistics, healthcare, and urban mobility.