1. Home page
  2. Search

Εύρεση βέλτιστων δρομολογίων σε σύστημα αστικών συγκοινωνιών με βάση το πρότυπο GTFS

This item is provided by the institution :
/aggregator-openarchives/portal/institutions/uoa   

Repository :
Pergamos Digital Library   

see the original item page
in the repository's web site and access all digital files if the item*



Εύρεση βέλτιστων δρομολογίων σε σύστημα αστικών συγκοινωνιών με βάση το πρότυπο GTFS
Αριστοβουλίδης Σωκράτης (EL)
born_digital_postgraduate_thesis
Διπλωματική Εργασία (EL)
Postgraduate Thesis (EN)
2011
Ενώ το πρόβλημα της εύρεσης της συντομότερης χρονικά διαδρομής σε ένα σύστημα συγκοινωνιών είναι έως ένα βαθμό συναφές με το πρόβλημα εύρεσης της βέλτιστης διαδρομής σε ένα οδικό δίκτυο παρόλα αυτά δεν αντιμετωπίζεται από τους κλασσικούς αλγόριθμους που έχουν αναπτυχθεί για το σκοπό αυτό. Σημαντικός παράγοντας διαφοροποίησης των δύο προβλημάτων είναι η χρονική διάσταση που εισάγεται από το πρώτο πρόβλημα. Ένα οδικό δίκτυο μπορεί να παρασταθεί με έναν κατευθυνόμενο γράφο και η βέλτιστη διαδρομή μεταξύ δύο σημείων μπορεί να βρεθεί με τη χρήση ενός κλασσικού αλγόριθμου (πχ 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)
Greek
Βιβλιοθήκη και Κέντρο Πληροφόρησης » Βιβλιοθήκη Σχολής Θετικών Επιστημών
Σχολή Θετικών Επιστημών » Τμήμα Πληροφορικής & Τηλεπικοινωνιών » ΠΜΣ Πληροφορική και Τηλεπικοινωνίες » Κατεύθυνση / ειδίκευση Τηλεπικοινωνιακά Συστήματα και Δικτυακές Τεχνολογίες (ΤΗΛ)
https://creativecommons.org/licenses/by-nc/4.0/
University of Athens
Pergamos Digital Library
Postgraduate Thesis



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)