Mathematical models and optimization methods for vehicle routing problems under uncertainty

Source abstract

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