Βέλτιστη δρομολόγηση οχημάτων με στοχαστικά μοντέλα

Abstract

Στην παρούσα διπλωματική εργασία μελετώνται διάφορα στοχαστικά προβλήματα βέλτιστης δρομολόγησης οχημάτων, τα οποία προκύπτουν σε καθημερινές εφαρμογές όπως η δρομολόγηση σχολικών λεωφορείων, οι υπηρεσίες έκτακτης ανάγκης και οι παραδόσεις κατ' οίκον. Περιλαμβάνει την εύρεση βέλτιστων διαδρομών για τα οχήματα ώστε να ελαχιστοποιούνται το κόστος και ο χρόνος. Αρχικά γίνεται μια αναφορά σε κάποια σημαντικά εργαλεία της Στοχαστικής Μοντελοποίησης τα οποία θα μας βοηθήσουν στην κατανόηση των επόμενων κεφαλαίων. Έχοντας αυτό το υπόβαθρο, αναλύουμε το πρόβλημα της βέλτιστης δρομολόγησης ενός οχήματος με στοχαστικές απαιτήσεις για τις περιπτώσεις ενός προϊόντος με διακριτές και συνεχείς απαιτήσεις και δυο συναφών προϊόντων με διακριτές και συνεχείς απαιτήσεις. Στη συνεχεία, θα μελετήσουμε τα στοχαστικά προβλήματα δρομολόγησης: ενός οχήματος για την βέλτιστη παράδοση δυο παρόμοιων προϊόντων με διακριτές απαιτήσεις και ενός οχήματος δυο τμημάτων για τη βέλτιστη παράδοση νέων και την παραλαβή παλιών προϊόντων με συνεχείς απαιτήσεις. Σε όλα τα παραπάνω στοχαστικά προβλήματα η βέλτιστη πολιτική δρομολόγησης έχει μια συγκεκριμένη δομή που βασίζεται σε ένα σύνολο κρίσιμων ποσοτήτων για κάθε πελάτη και γι'αυτό θα κατασκευάσουμε αλγορίθμους για τον υπολογισμό τους. Για την ολοκλήρωση αυτών των κεφαλαίων παραθέτουμε κάποια αριθμητικά παραδείγματα. Κλείνοντας, ασχολούμαστε με το κομμάτι των στοχαστικών προβλημάτων δρομολόγησης με χρονικά παράθυρα. Το πρώτο πρόβλημα είναι ένα στοχαστικό πρόβλημα παραλαβής και παράδοσης με αυστηρά χρονικά παράθυρα, ενώ το δεύτερο είναι ένα στοχαστικό αποθεματικό πρόβλημα δρομολόγησης συνεχούς χρόνου με χρονικά παράθυρα. Και τα δυο προβλήματα περιγράφονται αναλυτικά, ενώ για το πρώτο πρόβλημα παρέχουμε και μια προσέγγιση της λύσης.