δείτε την πρωτότυπη σελίδα τεκμηρίου στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
Εύρεση βέλτιστων δρομολογίων σε σύστημα αστικών συγκοινωνιών με βάση το πρότυπο GTFS
Ενώ το πρόβλημα της εύρεσης της συντομότερης χρονικά διαδρομής σε ένα σύστημα
συγκοινωνιών είναι έως ένα βαθμό συναφές με το πρόβλημα εύρεσης της βέλτιστης
διαδρομής σε ένα οδικό δίκτυο παρόλα αυτά δεν αντιμετωπίζεται από τους
κλασσικούς αλγόριθμους που έχουν αναπτυχθεί για το σκοπό αυτό. Σημαντικός
παράγοντας διαφοροποίησης των δύο προβλημάτων είναι η χρονική διάσταση που
εισάγεται από το πρώτο πρόβλημα.
Ένα οδικό δίκτυο μπορεί να παρασταθεί με έναν κατευθυνόμενο γράφο και η
βέλτιστη διαδρομή μεταξύ δύο σημείων μπορεί να βρεθεί με τη χρήση ενός
κλασσικού αλγόριθμου (πχ Dijkstra, A*). Ένα σύστημα συγκοινωνιών εξυπηρετείται
από ένα σύνολο γραμμών κάθε μία από τις οποίες απαρτίζεται από ένα σύνολο
δρομολογίων τα οποία μπορούν να μεταβάλλονται ανάλογα με την ημέρα και την ώρα.
Το σύστημα περιγράφεται από το σύνολο όλων των στάσεων που το απαρτίζουν, τις
γραμμές και το πρόγραμμα δρομολογίων κάθε γραμμής. Η εύρεση της βέλτιστης
διαδρομής δεν εξαρτάται μόνο από την τοπολογία του δικτύου που σχηματίζεται από
τις στάσεις του συστήματος, αλλά και από τη χρονική συνάφεια των διελεύσεων των
συγκοινωνιακών μέσων από αυτές.
Η παρούσα εργασία προτείνει έναν αλγόριθμο εύρεσης της βέλτιστης διαδρομής (και
τυχόν εναλλακτικών διαδρομών με παρεμφερές κόστος) σε ένα σύστημα συγκοινωνιών.
Σε αντίθεση με τους κλασσικούς αλγόριθμους επίλυσης γράφων οι οποίοι εξετάζουν
διαδοχικούς κόμβους, η αναζήτηση της βέλτιστης διαδρομής γίνεται με την
εκτίμηση του κόστους των διαδρομών που σχηματίζονται από διαδοχικά (χωρικά και
χρονικά) υποσύνολα δρομολογίων όπως αυτά αποτυπώνονται στο πρόγραμμα
δρομολογίων του συστήματος.
Στο πλαίσιο της εργασίας έχει γίνει υλοποίηση του αλγόριθμου ο οποίος μπορεί να
εκτελεστεί μέσω ενός web interface και να παρέχει τη βέλτιστη διαδρομή μεταξύ
δύο σημείων και για δεδομένη ημέρα και ώρα αναχώρησης για το San Francisco και
την Αθήνα.
(EL)
Though the problem of finding the best (quickest) path in an urban transit
system is related to some degree to the problem of finding the best route in a
road network, the first problem is not addressed adequately from the classic
graph solving algorithms that are used to solve the second problem. An
important difference between these two problems is the temporal dimension
introduced by the first problem.
A road network can be represented by a directed graph and the optimal route
between two points can be found using a classical algorithm (Dijkstra, A *). An
urban transit system is served by a set of lines each of which consists of a
set of services that can be changed depending on the day and time according to
the transit system schedule. The transit system is described by the set of
stops, routes, trips and the timetable of each trip. Finding the optimal path
depends not only on the topology of the network formed by the stops of the
system, but also on the temporal relevance of the means of transport crossing
them.
This essay proposes an algorithm for finding the best route (and any
alternative paths with similar costs) in a transit system. In contrast to the
classical graph-solving algorithms which examine subsequent nodes of the graph,
the search for the optimal path is performed estimating the cost of the paths
formed by successive (spatially and temporally) subsets services as reflected
in the schedule of the trips of the transit system.
As part of this work, the proposed algorithm has been implemented and can be
run from a web interface finding the best transit schedule between two
locations for a given time of departure for the cities of San Francisco and
Athens.
(EN)
*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.
Βοηθείστε μας να κάνουμε καλύτερο το OpenArchives.gr.
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
