Αλγόριθμοι Δρομολόγησης Με Μέσα Μαζικής Μεταφοράς Στο Δίκτυο Των Αθηνών

Abstract

Τα τελευταία χρόνια το πρόβλημα της δρομολόγησης στα μεταφορικά δίκτυα γίνεται ολοένα και πιο επίκαιρο. Αντικείμενο αυτής της διπλωματικής είναι η δρομολόγηση με μέσα μαζικής μεταφοράς στο δίκτυο της Αττικής, δηλαδή δεδομένου του μεταφορικού δικτύου της Αττικής, μίας αφετηρίας και ενός προορισμού, η εύρεση μονοπατιού από την αφετηρία προς τον προορισμό που να είναι " βέλτιστο " ή κοντά στο " βέλτιστο ".Για τον σκοπό αυτό μελετάμε τους κυριότερους αλγόριθμους δρομολόγησης, τους κλασσικούς αλλά και τις σύγχρονες προσεγγίσεις. Η μελέτη γίνεται αρχικά από μαθηματική πλευρά ωστόσο το κύριο σημείο ενδιαφέροντος είναι η επάρκεια που εμφανίζουν αυτοί οι αλγόριθμοι από πρακτική πλευρά κατά την εφαρμογή τους σε πραγματικά μεταφορικά δίκτυα. Το ενδιαφέρον μας είναι στραμμένο στο υπολογιστικό κόστος, τις απαιτήσεις σε μνήμη, την ποιότητα της λύσης που δίνεται, την ευκολία στην υλοποίηση και την δυνατότητα επέκτασης των αλγορίθμων για την επίλυση παραλλαγών του shortest- path προβλήματος. Εξετάζονται ακόμα οι δομές δεδομένων προκειμένου και εντοπίζονται εκείνες που οδηγούν σε ταχύτερη υλοποίηση των αλγορίθμων δρομολόγησης.Γίνεται επίσης μελέτη της έννοιας του δικτύου, των βασικών του χαρακτηριστικών, των μέτρων και των δυνατών τρόπων απεικόνισής του. Αναλύονται οι ιδιαιτερότητες των μεταφορικών δικτύων, οι βασικότερες διαφορές τους από τα randomly generated δίκτυα και οι κυριότεροι παράγοντες- χαρακτηριστικά του δικτύου που επιδρούν στην επίδοση των αλγορίθμων κατά τη δρομολόγηση σ' ένα μεταφορικό δίκτυο.Γίνεται υλοποίηση των αλγορίθμων Dijkstra και A- Star, πειραματική αποτίμησή τους και διερεύνηση της επίδρασης των ευριστικών τεχνικών στην επίδοση των δύο αλγορίθμων. Εξετάζουμε πώς η γεωγραφική απόσταση ως ευριστική συνάρτηση μπορεί να καθοδηγήσει την αναζήτηση στην περίπτωση του A- Star και πώς η χρήση των hubs στην περίπτωση του Dijkstra μπορεί να μας οδηγήσει γρηγορότερα στην εύρεση συντομότερου μονοπατιού. Γίνεται σύγκριση μεταξύ του Dijkstra, του A- Star και του Dijkstra με χρήση hubs σε ότι αφορά το υπολογιστικό κόστος και το κόστος των μονοπατιών που δίνει ως λύση καθένας από τους αλγορίθμους στο μεταφορικό δίκτυο των Αθηνών.