Μοντέλα και αλγόριθμοι χρονοεξαρτώμενης πολυτροπικής δρομολόγησης σε συγκοινωνιακά δίκτυα

• Main Author: Παρασκευόπουλος, Ανδρέας
• Other Authors: Ζαρολιάγκης, Χρήστος
• Format: Thesis
• Language: Greek
• Published: 2017
• Subjects: Πολυτροπική δρομολόγηση; Συγκοινωνιακό δίκτυο; Πίνακας δρομολογίων; Χρονο-εκτεταμένο γράφημα; Αλγόριθμοι; Σταθμοί; Στάσεις; Μέσα Μαζικής Μεταφοράς (ΜΜΜ); Μετεπιβίβαση; Multimodal routing; Transport networks; Timetables; Time-extended graph; Algorithms; Dijkstra; A star; Stations; Stops; Transportation; Transit; 518.1

Στη σύγχρονη εποχή, η χρήση προηγμένων εφαρμογών δρομολόγησης καθίσταται όλο και πιο αναγκαία για όσους ταξιδεύουν. Σε αυτό το πλαίσιο, το ενδιαφέρον επικεντρώνεται σε εφαρμογές που παρέχουν έγκυρες διαδρομές καθ' όλη τη διάρκεια της μέρας, συνδυάζοντας πολλαπλά μέσα μεταφοράς. Το αντικείμενο της παρούσας διπλωματικής εργασίας είναι η εύρεση βέλτιστων πολυτροπικών διαδρομών σε συγκοινωνιακά δίκτυα Μέσων Μαζικής Μεταφοράς (ΜΜΜ). Το πρόβλημα που μελετάται αφορά τον υπολογισμό της βέλτιστης πολυτροπικής διαδρομής από ένα σταθμό-αφετηρία προς ένα σταθμό-προορισμό, σε οποιαδήποτε χρονική στιγμή αναχώρησης, με χρήση περισσότερων του ενός μέσων μεταφοράς (πολυτροπική μετακίνηση), έτσι ώστε να ελαχιστοποιείται το κόστος του ταξιδιού (απόσταση, διάρκεια, αριθμός μετεπιβιβάσεων). Στο πλαίσιο αυτό, εξετάζονται χρονο-εκτεταμένα γραφοθεωρητικά μοντέλα τα οποία αναπαριστούν όλα τα δυνατά δρομολόγια των ΜΜΜ. Συνεισφορά της διπλωματικής εργασίας αποτελεί ο σχεδιασμός και η υλοποίηση νέων αποδοτικών μεθόδων, σχετικά με: α) τον υπολογισμό βέλτιστων πολυτροπικών διαδρομών με οποιοδήποτε συνδυασμό ΜΜΜ, συμπεριλαμβανομένης της δυνατότητας χρήσης ηλεκτρικών αυτοκινήτων και πεζόδρομων, β) τη χρήση ευρετικών μεθόδων για την αποτελεσματική οριοθέτηση των βέλτιστων πολυτροπικών διαδρομών σε δίκτυα ευρείας κλίμακας και γ) την αποτελεσματική διαχείριση των καθυστερήσεων στα ΜΜΜ. Στα πλαίσια της διπλωματικής εργασίας, διεξήχθη εκτενής πειραματική αξιολόγηση των νέων μεθόδων σε συγκοινωνιακά δίκτυα μητροπολιτικού εύρους, όπως του Λονδίνου (με 14,085,810 κόμβους και 41,837,355 ακμές) και του Βερολίνου (με 4,335,387 κόμβους και 12,701,695 ακμές). Παρά το μεγάλο μέγεθος των δικτύων, οι υλοποιήσεις επιτυγχάνουν: α) τον υπολογισμό των βέλτιστων πολυτροπικών διαδρομών σε χρόνο λιγότερο από 10 ms και β) την ενημέρωση των δρομολογίων των οχημάτων, σε περίπτωση καθυστερήσεων, σε χρόνο λιγότερο από 1 ms.