Online αλγόριθμοι δρομολόγησης για στοχαστικά δίκτυα σε πραγματικό χρόνο
Authors: Χρυσοχόου Ευαγγελία 
Published: August 2021

Η παρούσα διδακτορική διατριβή πραγματεύεται το γενικό πρόβλημα δρομολόγησης στόλου, γνωστό στην ξένη βιβλιογραφία ως “Vehicle Routing Problem”. Νοείται ως ένα από τα πιο σημαντικά προβλήματα των εφαρμοζομένων μαθηματικών της σύγχρονης εποχής και ίσως το δημοφιλέστερο πρόβλημα επιχειρησιακής έρευνας στον τομέα των μεταφορών. Ορίζεται ως το πρόβλημα του σχεδιασμού διαδρομών ελάχιστου κόστους ενός στόλου οχημάτων από ένα κεντρικό σημείο σε ένα δίκτυο πελατών, ικανοποιώντας ταυτόχρονα κάποιους συστημικούς περιορισμούς. Το φάσμα των εφαρμογών του εκτείνεται από τη διαχείριση στόλων διανομής προϊόντων έως τη σχολική μετακίνηση, αλλά και τη συλλογή απορριμμάτων.Η μελέτη του προβλήματος της δρομολόγησης σε συνθήκες αβεβαιότητας (πχ. μεταβαλλόμενη ζήτηση), καθώς και η ανάλυση και ενσωμάτωση της στοχαστικότητας στην ανάπτυξη μαθηματικών προτύπων (μοντέλων) και αλγορίθμων, τέθηκαν πρωταρχικοί στόχοι της έρευνας που εκπονήθηκε. Όταν ένα πρόβλημα βελτιστοποίησης επιλύεται υπό συνθήκες αβεβαιότητας, το ζητούμενο είναι η διαμόρφωση της πολιτικής που ελαχιστοποιεί το κόστος των αποφάσεων αλλά και το κόστος των εφικτών μέτρων αναπροσαρμογής των αρχικών επιλογών. Με γνώμονα την εύρωστη αξιολόγηση των επιλογών που προκύπτουν στο μοντέλο βελτιστοποίησης σε συνθήκες αβεβαιότητας, καθοριστικό ρόλο λαμβάνει η σαφής διατύπωση (μαθηματική τεκμηρίωση) των δυνατών μελλοντικών αποφάσεων – προοπτικών, αλλά και η διαδικασία ενσωμάτωσής τους στις εκ των προτέρων επιλογές. Οι μεθοδολογικοί πυλώνες διερεύνησης του προβλήματος της δρομολόγησης σε συνθήκες αβεβαιότητας, ήταν αρχικά η προσέγγιση του στοχαστικού προγραμματισμού και η “online“ βελτιστοποίηση. Το πρώτο μέρος της εργασίας επικεντρώνεται στους ακριβείς αλγορίθμους επίλυσης του γενικού προβλήματος της δρομολόγησης στόλου. Εστιάζοντας στις εμπορευματικές μεταφορές, η στοχαστικότητα της ζήτησης συσχετίζεται άμεσα με το ρυθμό απορρόφησης των προϊόντων, τις δυνατότητες διατήρησης αποθεμάτων, αλλά και τη μεταξύ τους αλληλεπίδραση. Επικεντρώνοντας το ενδιαφέρον στη στοχαστικότητα της ζήτησης σε συνάφεια με τους παράγοντες που την επηρεάζουν (δηλ. χωρητικότητα αποθηκών, ρυθμός απορρόφησης προϊόντων), εξετάζεται στο διδακτορικό η συνδυαστική διαχείριση της διανομής προϊόντων και εφοδιασμού αποθηκών γνωστή στην ξένη βιβλιογραφία ως “Inventory Routing Problem”, η οποία αποτελεί επέκταση του κλασσικού προβλήματος δρομολόγησης.Στο δεύτερο μέρος της εργασίας γίνεται εκτενής αναφορά των επιστημονικών συγγραμμάτων της συνδυαστικής διαχείρισης διανομής προϊόντων και εφοδιασμού των αποθηκών, επικεντρώνοντας και πάλι το ενδιαφέρον σε ακριβείς μεθόδους επίλυσης του προβλήματος. Με αφορμή την αναθεώρηση βασικής υπόθεσης των έως τώρα προτεινόμενων μαθηματικών προτύπων αναδείχτηκε η δυναμική μιας νέας πολιτικής, των προληπτικών διανομών όταν το μοντέλο εξετάζεται σε συνθήκες βεβαιότητας. Με γνώμονα την προοπτική επίλυσης του προβλήματος της συνδυαστικής διαχείρισης διανομής προϊόντων και εφοδιασμού αποθηκών σε συνθήκες αβεβαιότητας και στόχο τη δημιουργία ενός ευέλικτου συστήματος αποφάσεων, η διαδικασία της μεταφόρτωσης εισάγεται ως διορθωτική πολιτική ενός μοντέλου στοχαστικού προγραμματισμού. Αναπτύχθηκε ένα καινοτόμο μοντέλο δύο σταδίων στοχαστικού προγραμματισμού δρομολόγησης στόλου σε συνθήκες αβεβαιότητας. Η επίλυσή του επιτεύχθηκε εφαρμόζοντας τη μεθοδολογική προσέγγιση της αποσύνθεσης «L – Shaped». Το προτεινόμενο στοχαστικό μοντέλο αξιολογήθηκε επιλύοντας κατάλληλες τροποποιήσεις πρότυπων προβλημάτων ( Archetti et al.) . Συμπερασματικά, η απόφαση της πλαισίωσης του προβλήματος υπό το πρίσμα του στοχαστικού προγραμματισμού των μοντέλων δύο σταδίων, μας έδωσε τη δυνατότητα να οριοθετήσουμε την αλληλεπίδραση του κόστους της μεταφόρτωσης σε συνάφεια με το κόστος των προληπτικών διανομών και την αύξηση των επιπέδων διατήρησης των αποθεματικών.