Mathematical models and optimization methods for vehicle routing problems under uncertainty

Abstract

This doctoral dissertation examines mathematical models and optimization methods for routing and service systems under uncertainty, with particular emphasis on the endogenous assignment of service time windows. In urban transportation, last-mile delivery, and appointment-based services, travel and service times are affected by unforeseen factors, creating uncertainty in arrival times and service start times. Within this context, the thesis studies the Time Window Assignment Problem under stochastic travel or service times and introduces the Stochastic Time Window Assignment Problem (STWAP), in which time windows are treated as decision variables and used as a mechanism for absorbing operational uncertainty. The thesis comprises two complementary research directions. In the first research direction, the STWAP is integrated into the Vehicle Routing Problem and treated as a recourse function within a hierarchical two-stage solution framework. An Adaptive Large Neighborhood Search (ALNS) metaheuristic is developed to generate routing solutions, while the time-window assignment problem is solved using exact linear and mixed-integer programming methods. Uncertainty in travel times is represented through continuous and discrete random variables, while service-reliability requirements are explicitly incorporated into the proposed models. In the second research direction, the STWAP is studied as a standalone optimization problem over predetermined sequences of jobs or service requests with stochastic service times. The accumulation of uncertainty throughout the sequence and stochastic waiting are explicitly taken into account, while the expected customer inconvenience caused by time-window deviations is evaluated using quadratic penalty functions, leading to a mixed-integer quadratic programming formulation. Extensive computational experiments and simulation studies investigate different probability distributions, service-level requirements, and penalty structures. The results highlight the interactions among time-window width, service reliability, expected inconvenience, and operational cost, demonstrating the value of endogenous time-window assignment for the design of reliable transportation and service systems operating under uncertainty.

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