Κατά τις δύο τελευταίες δεκαετίες, οι αλγόριθμοι εύρεσης συντομότερης διαδρομής σε οδικά δίκτυα αποτέλεσαν μια ερευνητική περιοχή με έντονη δραστηριότητα που παρήγαγε σημαντικά ερευνητικά αποτελέσματα που χρησιμοποιούνται από χιλιάδες χρήστες σε όλο τον κόσμο. Δυστυχώς όμως, παρά την πληθώρα των επιμέρους μεθόδων και αλγόριθμων δεν υπάρχει μια μοναδική υπερ-μέθοδος που να μπορεί να επιλύσει κατά βέλτιστο τρόπο όλες τις δυνατές παραλλαγές ερωτημάτων για όλες τις πιθανές περιπτώσεις χρήσης. Για το σκοπό αυτό, η παρούσα διατριβή εστιάζει στη βελτίωση προηγούμενων μεθόδων που αφορούν ερωτήματα εύρεσης συντομότερης διαδρομής μεταξύ ενός ζεύγους σημείων και προτείνει νέους αλγόριθμους για πλήθος παραλλαγών του συγκεκριμένου προβλήματος, ειδικά στο πλαίσιο δυναμικών οδικών δικτύων με συχνές κυκλοφορικές ενημερώσεις. Τέτοιες σημαντικές παραλλαγές είναι: α) Το πρόβλημα “Ένας προς όλους” (εύρεση της απόστασης όλων των κόμβων του δικτύου από ένα συγκεκριμένο κόμβο) β) Το σχετιζόμενο πρόβλημα “Ένας-Προς-πολλούς” (στο οποίο θέλουμε να υπολογίσουμε την απόσταση μεταξύ ενός κόμβου - αφετηρία και ενός μεγάλου πλήθους άλλων στόχων). γ) Τα ερωτήματα “Εύρους” (εντοπίστε τους κόμβους που απέχουν λιγότερο από μια συγκεκριμένη απόσταση από τον κόμβο - αφετηρία), καθώς και δ) η εύρεση των k-πλησιέστερων γειτόνων (k-NN πρόβλημα) στο οποίο επιθυμούμε να εντοπίσουμε τους k-πλησιέστερους γειτονικούς κόμβους σε ένα κόμβο αφετηρία ανάμεσα από ένα πλήθος πιθανών στόχων. Για όλους τους παραπάνω διαφορετικούς ορισμούς ερωτημάτων συντομότερης διαδρομής σε οδικά δίκτυα, οι μέθοδοι και οι αλγόριθμοι που προτείνονται στην παρούσα διατριβή παρέχουν εξαιρετική απόδοση και πολύ σύντομους χρόνους προεπεξεργασίας που τις καθιστά κατάλληλες για αξιοποίηση σε πλήθος εφαρμογών και περιπτώσεων χρήσης.

Ο δεύτερος κύριος στόχος της παρούσης διατριβής είναι να γεφυρώσει το χάσμα μεταξύ των διαφόρων τύπων ερωτημάτων συντομότερης διαδρομής σε οδικά δίκτυα και να προτείνει ένα ενιαίο πλαίσιο αλγόριθμων και δομών δεδομένων που να μπορεί να χειριστεί αποτελεσματικά όλες τις επιμέρους παραλλαγές των προβλημάτων συντομότερης διαδρομής, απαιτώντας ταυτόχρονα εξαιρετικά σύντομους χρόνους προεπεξεργασίας (λίγων δευτερολέπτων), ώστε να μπορεί επίσης να χρησιμοποιηθεί και στην περίπτωση δυναμικών οδικών δικτύων με συχνές κυκλοφορικές ενημερώσεις. Μια τέτοια λύση θα είναι εξαιρετικά χρήσιμη για πολλά πρακτικά προβλήματα και θα μπορεί να χρησιμοποιηθεί σε πλήθος εφαρμογών του πραγματικού κόσμου. Συνεπώς, στην παρούσα εργασία αναπτύξαμε και μια υπηρεσία πραγματικού-χρόνου, που επιδεικνύει τις πρακτικά αποτελέσματα των προτεινόμενων μεθόδων, αξιοποιώντας δεδομένα κίνησης που προέρχονται από στόλους οχημάτων. Επιπλέον, η παρούσα εργασία επεκτάθηκε σημαντικά σε άλλους τομείς, όπως το Geomarketing, οι ενημερώσεις χαρτών, καθώς και ο πληθοπορισμός των συναισθημάτων των χρηστών ταξιδιωτικών ιστολογίων σε σχέση με το γεωγραφική τοποθεσία τους.