Στην παρούσα διδακτορική διατριβή διερευνάται το Πρόβλημα Δρομολόγησης Οχημάτων Πολλαπλών Περιόδων με Χρονικά Παράθυρα (ΠΔΟΠΠΧΠ). Κάθε πελάτης σχετίζεται με ένα χρονικό παράθυρο περιόδων (ΧΠΠ), το οποίο ορίζεται ως το σύνολο περιόδων εξυπηρέτησης. Στόχος είναι η ελαχιστοποίηση του κόστους δρομολόγησης εντός ορίζοντα πολλαπλών περιόδων λαμβάνοντας υπόψη περιορισμούς χρονικών παραθύρων, χωρητικότητας οχημάτων και χρονικών παραθύρων περιόδων.Παρουσιάζουμε ένα γενικό μοντέλο, μία μέθοδο ακριβούς επίλυσης βάσει της Δυναμικής Δημιουργίας Μεταβλητών (ΔΔΜ – Column Generation) και προτείνονται δύο νέες αποτελεσματικές τεχνικές επιτάχυνσης της ΔΔΜ για την εύρεση κατώτατων ορίων. Οι τεχνικές αυτές εκμεταλλεύονται τις πολλαπλές περιόδους ώστε να αναγνωριστούν ομοιότητες εντός των υποπροβληματών και να αποφευχθεί η επίλυση όλων των υποπροβλημάτων σε κάθε επανάληψη. Η αποδοτικότητα των μεθόδων ελέγχθηκε για παραμέτρους όπως η γεωγραφική κατανομή των πελατών και τα υποδείγματα ΧΠΠ. Στην πλειονότητα των περιπτώσεων, οι νέες μέθοδοι συγκλίνουν γρηγορότερα στην βέλτιστη λύση του χαλαρωμένου προβλήματος, ειδικότερα στις περιπτώσεις αυξημένης πολυπλοκότητας (ευρεία ΧΠΠ). Για την εύρεση των βέλτιστων ακέραιων λύσεων στο ΠΔΟΠΠΧΠ υλοποιήθηκε μέθοδος branch-and-price. Προτείνονται δύο στρατηγικές διακλάδωσης που λαμβάνουν υπόψη τις πολλαπλές περιόδους, καθώς και μία απλή μέθοδος pruning που επιταχύνει την επίλυση και προσεγγίσει τις βέλτιστες λύσεις. Για την επίλυση του ΠΔΟΠΠΧΠ σε Εκτεταμένο Χρονικό Ορίζοντα, προτάθηκε η χρήση κυλιόμενου χρονικού ορίζοντα (ΚΧΟ).
University of the Aegena
