Optimization methods for complex vehicle routing and scheduling problems

Abstract

This PhD dissertation is interested in the development of optimization methods for solving complex and large scale Vehicle Routing and Scheduling Problems (VRSP). The main focus is given on studying the computational efficiency and effectiveness of hybrid metaheuristic algorithms. In an attempt to fill in the gaps of the literature identified earlier, the major effort will focus on the Vehicle Routing Problem with Time Windows (VRPTW) and the proposed optimization methods will be tested on several medium and large scale benchmark data sets. Attention will be also given on other variants of the VRPTW with practical and operational side-constraints namely the Open VRPTW (OVRPTW) and the Heterogeneous Fleet VRPTW (HFVRPTW) and the VRPTW with Multiple Compartments and Commodities (MCCVRPTW). Finally, driven from an industrial application we will examine the integration of the suggested methods within a novel Decision Support System that enables schedulers to tackle VRPTW problems with real life operational constraints. A hybrid Multi Start Local Search and a novel Arc Guided Evolutionary Algorithm are proposed for solving the VRPTW. For both approaches an extensive empirical study is performed and the role of key algorithmic elements is analyzed. Computational experiments demonstrate that the proposed optimization methods obtain the best overall results compared to the current state of the art. Considering the Open VRPTW a formal description is first provided followed by a greedy look-ahead construction heuristic and a hybrid Evolutionary Algorithm. All critical aspects of the problem are captured while experimental results demonstrate the competitiveness of the methods with respect to other approaches. Subsequently, the HFVRPTW is addressed. A novel two phase solution framework is developed called Reactive Variable Neighborhood Tabu Search. Computational experiments show that high quality solutions can be reached via the proposed method illustrating its efficiency and effectiveness. Next a real-life VRPTW is presented that incorporates a number of side constraints such as multiple compartments and commodities, time windows, loading restrictions and limited vehicle fleet size and composition availability. An Adaptive Memory Programming method is proposed to address all critical aspects of the problem. Various computational experiments demonstrate the applicability of the method to real life vehicle routing and scheduling applications. Finally, an industrial Decision Support System is presented that handles the efficient and effective management of waste lube oils collection and recycling operations. The main effort is to examine the integration and cooperation of the vehicle routing and scheduling methods within an Enterprise Resource Planning system. The application of the DSS to an industrial environment improved productivity and competitiveness.

Η διδακτορική αυτή διατριβή πραγματεύεται την ανάπτυξη μεθόδων βελτιστοποίησης για την επίλυση πολύπλοκων προβλημάτων δρομολόγησης και χρονοπρογραμματισμού στόλου οχημάτων. Η κύρια προσπάθεια εστιάζεται στη μελέτη της υπολογιστικής δύναμης των υβριδικών μεταευρετικών αλγορίθμων. Σε μια προσπάθεια να καλυφθούν τα κενά της βιβλιογραφίας η διδακτορική αυτή διατριβή έρχεται να προτείνει ιδιαίτερα αποδοτικές και αποτελεσματικές μεθόδους για την επίλυση του Προβλήματος Δρομολόγησης Στόλου Οχημάτων με Χρονικά Παράθυρα (ΠΔΣΟΧΠ) καθώς επίσης και άλλων εκδοχών του. Πιο συγκεκριμένα επιχειρείται για πρώτη φορά η μοντελοποίηση του Ανοικτού ΠΔΣΟΧΠ και η ανάπτυξη νέων μεθόδων για το ΠΔΣΟΧΠ με Ετερογενή Στόλο Οχημάτων. Ακόμη εξετάζεται επισταμένως και επιλύεται μια πραγματική βιομηχανική εφαρμογή με πολλαπλούς επιχειρησιακούς περιορισμούς. Τέλος, οι προτεινόμενες μέθοδοι βελτιστοποίησης ενσωματώνονται σε ένα πραγματικό Σύστημα Υποστήριξης Αποφάσεων. Για το ΠΔΣΟΧΠ προτείνεται μια υβριδική μεταευρετική μέθοδος πολλαπλών εκκινήσεων και ένας πρότυπος και μοντέρνος υβριδικός εξελικτικός αλγόριθμος. Η συγκριτική μέτρηση των επιδόσεων των μεθόδων σε πρότυπα προβλήματα της βιβλιογραφίας κατέδειξε την ανταγωνιστικότητα τους. Ιδιαίτερα δε αναφορικά με τη δεύτερη μέθοδο αξίζει να σημειωθεί ότι παρήγαγε τα καλύτερα αποτελέσματα παγκοσμίως τόσο σε μεσαίας όσο και σε μεγάλης κλίμακας προβλήματα. Η αποτελεσματικότητά τους είναι εμφανής παράγοντας, λύσεις υψηλής ποιότητας σε ανταγωνιστικούς υπολογιστικούς χρόνους σε σύγκριση με άλλες μεθόδους της βιβλιογραφίας. Για το Ανοικτό ΠΔΣΟΧΠ δημιουργείται ένα μαθηματικό μοντέλο το οποίο καλύπτει όλες τις πτυχές του προβλήματος, προτείνεται ένας ιδιαίτερα αποτελεσματικός ευρετικός κατασκευαστικός αλγόριθμος καθώς και ένας υβριδικός εξελικτικός αλγόριθμος. Αποτελέσματα σε πρότυπα προβλήματα της βιβλιογραφίας επαληθεύουν την καταλληλότητα και αποδοτικότητα των αλγορίθμων. Για το ΠΔΣΟΧΠ με Ετερογενή Στόλο Οχημάτων προτείνεται ένας υβριδικός μεταευρετικός αλγόριθμος πολλαπλών εκκινήσεων. Βασισμένος στις βασικές αρχές της Απαγορευμένης Έρευνας, ο αλγόριθμος αυτός συνδυάζει μηχανισμούς μεταβλητών γειτονιών και ευφυείς διαδικασίες εκμάθησης. Η συγκριτική μέτρηση των επιδόσεων του σε πρότυπα προβλήματα της βιβλιογραφίας κατέδειξε την ανταγωνιστικότητά του σε σύγκριση με άλλες μεθόδους. Τέλος, στο πλαίσιο της προσπάθειας μοντελοποίησης προβλημάτων με πραγματικούς επιχειρησιακούς περιορισμούς εξετάστηκε ένα πρόβλημα ζήτησης πολλαπλών προϊόντων τα οποία πρέπει να αποθηκεύονται σε διαφορετικά διαμερίσματα των οχημάτων κατά τη διάρκεια της εξυπηρέτησης των πελατών. Για την επίλυση του προβλήματος αυτού προτείνεται ένας αλγόριθμος Προγραμματισμού Προσαρμόσιμης. Αποτελέσματα σε πρότυπα προβλήματα της βιβλιογραφίας επαληθεύουν την απόδοση και την καταλληλότητα της μεθόδου.