Βέλτιστη Δρομολόγηση Οχήματος Σε Συνθήκες Αβεβαιότητας

Abstract

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