Back to search

National and Kapodistrian University of Athens

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

Abstract

dc:description

Ενώ το πρόβλημα της εύρεσης της συντομότερης χρονικά διαδρομής σε ένα σύστημα συγκοινωνιών είναι έως ένα βαθμό συναφές με το πρόβλημα εύρεσης της βέλτιστης διαδρομής σε ένα οδικό δίκτυο παρόλα αυτά δεν αντιμετωπίζεται από τους κλασσικούς αλγόριθμους που έχουν αναπτυχθεί για το σκοπό αυτό. Σημαντικός παράγοντας διαφοροποίησης των δύο προβλημάτων είναι η χρονική διάσταση που εισάγεται από το πρώτο πρόβλημα. Ένα οδικό δίκτυο μπορεί να παρασταθεί με έναν κατευθυνόμενο γράφο και η βέλτιστη διαδρομή μεταξύ δύο σημείων μπορεί να βρεθεί με τη χρήση ενός κλασσικού αλγόριθμου (πχ Dijkstra, A*). Ένα σύστημα συγκοινωνιών εξυπηρετείται από ένα σύνολο γραμμών κάθε μία από τις οποίες απαρτίζεται από ένα σύνολο δρομολογίων τα οποία μπορούν να μεταβάλλονται ανάλογα με την ημέρα και την ώρα. Το σύστημα περιγράφεται από το σύνολο όλων των στάσεων που το απαρτίζουν, τις γραμμές και το πρόγραμμα δρομολογίων κάθε γραμμής. Η εύρεση της βέλτιστης διαδρομής δεν εξαρτάται μόνο από την τοπολογία του δικτύου που σχηματίζεται από τις στάσεις του συστήματος, αλλά και από τη χρονική συνάφεια των διελεύσεων των συγκοινωνιακών μέσων από αυτές. Η παρούσα εργασία προτείνει έναν αλγόριθμο εύρεσης της βέλτιστης διαδρομής (και τυχόν εναλλακτικών διαδρομών με παρεμφερές κόστος) σε ένα σύστημα συγκοινωνιών. Σε αντίθεση με τους κλασσικούς αλγόριθμους επίλυσης γράφων οι οποίοι εξετάζουν διαδοχικούς κόμβους, η αναζήτηση της βέλτιστης διαδρομής γίνεται με την εκτίμηση του κόστους των διαδρομών που σχηματίζονται από διαδοχικά (χωρικά και χρονικά) υποσύνολα δρομολογίων όπως αυτά αποτυπώνονται στο πρόγραμμα δρομολογίων του συστήματος. Στο πλαίσιο της εργασίας έχει γίνει υλοποίηση του αλγόριθμου ο οποίος μπορεί να εκτελεστεί μέσω ενός web interface και να παρέχει τη βέλτιστη διαδρομή μεταξύ δύο σημείων και για δεδομένη ημέρα και ώρα αναχώρησης για το San Francisco και την Αθήνα.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Αριστοβουλίδης Σωκράτης

Rights

Language dc:language
Ελληνικά, Greek

Identifiers

dc:identifier.*
Identifier
uoadl:1317463

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Αριστοβουλίδης Σωκράτης. Εύρεση βέλτιστων δρομολογίων σε σύστημα αστικών συγκοινωνιών με βάση το πρότυπο GTFS. 2011. https://pergamos.lib.uoa.gr/uoa/dl/object/1317463