Μονάδα:
Κατεύθυνση / ειδίκευση Τηλεπικοινωνιακά Συστήματα και Δικτυακές Τεχνολογίες (ΤΗΛ)Βιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2011-11-04
Συγγραφέας:
Αριστοβουλίδης Σωκράτης
Στοιχεία επιβλεπόντων καθηγητών:
Aλέξης Δελής Καθηγητής ΕΚΠΑ, Παναγιώτης Ροντογιάννης Αναπλ. Καθηγητής ΕΚΠΑ
Πρωτότυπος Τίτλος:
Εύρεση βέλτιστων δρομολογίων σε σύστημα αστικών συγκοινωνιών με βάση το πρότυπο GTFS
Γλώσσες εργασίας:
Ελληνικά
Περίληψη:
Ενώ το πρόβλημα της εύρεσης της συντομότερης χρονικά διαδρομής σε ένα σύστημα
συγκοινωνιών είναι έως ένα βαθμό συναφές με το πρόβλημα εύρεσης της βέλτιστης
διαδρομής σε ένα οδικό δίκτυο παρόλα αυτά δεν αντιμετωπίζεται από τους
κλασσικούς αλγόριθμους που έχουν αναπτυχθεί για το σκοπό αυτό. Σημαντικός
παράγοντας διαφοροποίησης των δύο προβλημάτων είναι η χρονική διάσταση που
εισάγεται από το πρώτο πρόβλημα.
Ένα οδικό δίκτυο μπορεί να παρασταθεί με έναν κατευθυνόμενο γράφο και η
βέλτιστη διαδρομή μεταξύ δύο σημείων μπορεί να βρεθεί με τη χρήση ενός
κλασσικού αλγόριθμου (πχ Dijkstra, A*). Ένα σύστημα συγκοινωνιών εξυπηρετείται
από ένα σύνολο γραμμών κάθε μία από τις οποίες απαρτίζεται από ένα σύνολο
δρομολογίων τα οποία μπορούν να μεταβάλλονται ανάλογα με την ημέρα και την ώρα.
Το σύστημα περιγράφεται από το σύνολο όλων των στάσεων που το απαρτίζουν, τις
γραμμές και το πρόγραμμα δρομολογίων κάθε γραμμής. Η εύρεση της βέλτιστης
διαδρομής δεν εξαρτάται μόνο από την τοπολογία του δικτύου που σχηματίζεται από
τις στάσεις του συστήματος, αλλά και από τη χρονική συνάφεια των διελεύσεων των
συγκοινωνιακών μέσων από αυτές.
Η παρούσα εργασία προτείνει έναν αλγόριθμο εύρεσης της βέλτιστης διαδρομής (και
τυχόν εναλλακτικών διαδρομών με παρεμφερές κόστος) σε ένα σύστημα συγκοινωνιών.
Σε αντίθεση με τους κλασσικούς αλγόριθμους επίλυσης γράφων οι οποίοι εξετάζουν
διαδοχικούς κόμβους, η αναζήτηση της βέλτιστης διαδρομής γίνεται με την
εκτίμηση του κόστους των διαδρομών που σχηματίζονται από διαδοχικά (χωρικά και
χρονικά) υποσύνολα δρομολογίων όπως αυτά αποτυπώνονται στο πρόγραμμα
δρομολογίων του συστήματος.
Στο πλαίσιο της εργασίας έχει γίνει υλοποίηση του αλγόριθμου ο οποίος μπορεί να
εκτελεστεί μέσω ενός web interface και να παρέχει τη βέλτιστη διαδρομή μεταξύ
δύο σημείων και για δεδομένη ημέρα και ώρα αναχώρησης για το San Francisco και
την Αθήνα.
Λέξεις-κλειδιά:
Σύστημα Συγκοινωνιών, Γεωγραφικό Σύστημα Πληροφοριών, Δρομολόγιο, Αλγόριθμος, Σχεδιασμός Διαδρομής
Αρ. σελίδων ευρετηρίου:
5-6
Αρ. βιβλιογραφικών αναφορών:
15
