Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/11733
Title: Αλγοριθμικά ζητήματα κινητικότητας σε έξυπνες πόλεις
Other Titles: Algorithmic aspects of mobility in smart cities
Authors: Γιαννακοπούλου, Καλλιόπη
Keywords: Αλγόριθμοι
Έξυπνες πόλεις
Κινητικότητα
Μοντελοποίηση
Πίνακας δρομολογίων
Βέλτιστες διαδρομές
Διαχείριση καθυστερήσεων
Εφαρμογή κινητών συσκευών
Ενημέρωση πληροφορίας πινάκων δρομολογίων
Keywords (translated): Algorithms
Smart cities
Mobility
Modelling
Timetable information systems
Optimal routes and itineraries
Delay management
Updating timetable information systems
Mobile application
Abstract: Τα τελευταία χρόνια δίνεται συνεχώς όλο και μεγαλύτερη έμφαση στις προσωποποιημένες υπηρεσίες ταξιδιωτικής πλοήγησης και ανανεωνόμενης κινητικότητας μέσα σε έξυπνες πόλεις. Οι υπηρεσίες αυτές συνδυάζουν Μέσα Μαζικής Μεταφοράς (ΜΜΜ) και μικρά ηλεκτρικά αυτοκίνητα ή ποδήλατα, χρησιμοποιώντας τη λεγόμενη τεχνική του πληθοπορισμού για συλλογή δεδομένων κίνησης πραγματικού χρόνου και αξιολόγησης προτεινόμενων διαδρομών. Στόχος είναι η δημιουργία ενός συστήματος που θα επιτρέπει τη γρήγορη εύρεση βέλτιστων διαδρομών. Οι βασικότερες προκλήσεις στο σχεδιασμό ενός τέτοιου συστήματος είναι τεχνολογικές και αλγοριθμικές. Η τεχνολογική πρόκληση αφορά στη συλλογή, αποθήκευση, διαχείριση, και ενημέρωση ενός τεράστιου όγκου συγκοινωνιακών δεδομένων που είναι συνήθως χρονοεξαρτώμενα, και η παροχή (μέσω αυτών) προσωποποιημένων υπηρεσιών ανανεωνόμενης κινητικότητας σε έξυπνες φορητές συσκευές. Αυτή η πρόκληση αντιμετωπίζεται συνήθως με τη δημιουργία ενός περιβάλλοντος υπολογιστικού νέφους, το οποίο αφενός θα υποστηρίζει την αποθήκευση, διαχείριση, και ενημέρωση των δεδομένων και αφετέρου θα φροντίζει για την παροχή πληροφοριών στις εφαρμογές των έξυπνων φορητών συσκευών για εύρεση βέλτιστων διαδρομών. Η αλγοριθμική πρόκληση αφορά στην ανάπτυξη καινοτόμων αλγορίθμων για την παροχή αποδοτικών υπηρεσιών ταξιδιωτικής πλοήγησης σε έξυπνες φορητές συσκευές, με δεδομένα που θα λαμβάνουν από το υπολογιστικό νέφος. Οι υπηρεσίες αυτές εξασφαλίζουν την εύρεση ρεαλιστικών και χρήσιμων διαδρομών, αλλά και την άμεση παροχή ενημερωμένων διαδρομών στους συνδεδεμένους χρήστες, σε περίπτωση καθυστερήσεων, για την επικαιροποίηση του αρχικού πλάνου τους. Σκοπός είναι η δημιουργία μιας αλγοριθμικής βάσης για την υποστήριξη υπηρεσιών κινητικότητας σε αστικά συγκοινωνιακά περιβάλλοντα με χρήση ΜΜΜ. Τα συστήματα ΜΜΜ, που λειτουργούν βάσει συγκεκριμένου πίνακα δρομολογίων, πρέπει όχι μόνο να ανταποκρίνονται σε πραγματικό χρόνο σε ερωτήματα χρηστών για εύρεση βέλτιστων διαδρομών, αλλά και να προβαίνουν σε ενημερώσεις των αποθηκευμένων συγκοινωνιακών πληροφοριών προκειμένου να ανταποκρίνονται (επίσης σε πραγματικό χρόνο) στις συχνές αλλαγές των προκαθορισμένων δρομολογίων λόγω καθυστερήσεων. Τα βασικότερα αλγοριθμικά ζητήματα κινητικότητας και ταξιδιωτικής πλοήγησης (εύρεσης βέλτιστων διαδρομών ως προς ορισμένα κριτήρια) σε συστήματα ΜΜΜ αφορούν στα θεμελιώδη προβλήματα της νωρίτερης άφιξης (ΝΑ - μετακίνηση ενός επιβάτη από ένα σταθμό S σε ένα σταθμό T, στον ελάχιστο δυνατό χρόνο), του ελάχιστου αριθμού μετεπιβιβάσεων (ΕΑΜ - μετακίνηση ενός επιβάτη από ένα σταθμό S σε ένα σταθμό T, με τον ελάχιστο αριθμό μετεπιβιβάσεων), και της δυναμικής ενημέρωσης της πληροφορίας των πινάκων δρομολογίων σε περίπτωση καθυστερήσεων. Τα προβλήματα ΝΑ και ΕΑΜ έχουν εκτενώς μελετηθεί στη βιβλιογραφία κάτω από δύο προσεγγίσεις: τη διανυσματοκεντρική μοντελοποίηση (όπου οι πίνακες δρομολογίων αναπαριστάνονται ως διανύσματα) και τη γραφοκεντρική μοντελοποίηση (όπου οι πίνακες δρομολογίων αναπαριστάνονται ως γραφήματα). Προηγούμενες πειραματικές μελέτες είχαν δείξει ότι οι διανυσματοκεντρικές προσεγγίσεις είναι γρηγορότερες όσον αφορά το χρόνο απάντησης των ερωτημάτων από τις γραφοκεντρικές. Από την άλλη πλευρά, οι διανυσματοκεντρικές προσεγγίσεις δεν έχουν μελετηθεί ως προς την αποδοτική ενημέρωση του πίνακα δρομολογίων σε περίπτωση καθυστερήσεων. Στα πλαίσια της διδακτορικής διατριβής αναπτύχθηκαν νέες γραφοκεντρικές μέθοδοι που επιλύουν αποδοτικά τα προαναφερθέντα θεμελιώδη αλγοριθμικά προβλήματα κινητικότητας σε αστικά περιβάλλοντα με χρήση ΜΜΜ, καθώς και μια εφαρμογή ταξιδιωτικής πλοήγησης σε έξυπνες συσκευές, η οποία περιλαμβάνει και αξιολόγηση των προτεινόμενων διαδρομών από τους χρήστες χρησιμοποιώντας αρχές πληθοπορισμού. Πιο συγκεκριμένα: (α) Μελετήθηκαν εκτενώς σύγχρονα γραφοκεντρικά δυναμικά μοντέλα αναπαράστασης μεγάλου όγκου δεδομένων ως προς την καταλληλότητα αναπαράστασης πινάκων δρομολογίων. Η μελέτη επιβεβαίωσε την καταλληλότητα του ρεαλιστικού χρονοεκτεταμένο μοντέλου. (β) Αναπτύχθηκαν δύο νέα γραφοκεντρικά μοντέλα αναπαράστασης πινάκων δρομολογίων, το ανηγμένο χρονοεκτεταμένο μοντέλο και το δυναμικό μοντέλο πινάκων δρομολογίων DTM, τα οποία είναι χωρο-αποδοτικότερα σε σχέση με το ρεαλιστικό χρονοεκτεταμένο μοντέλο. Για τα νέα μοντέλα, αναπτύχθηκαν αποδοτικοί αλγόριθμοι απάντησης ερωτημάτων ΝΑ και ΕΑΜ, καθώς και αποδοτικοί αλγόριθμοι ενημέρωσης των γραφοκεντρικών μοντέλων σε περίπτωση καθυστερήσεων. (γ) Αξιολογήθηκαν πειραματικά τα νέα γραφοκεντρικά μοντέλα αναπαράστασης πινάκων δρομολογίων και οι νέοι αποδοτικοί αλγόριθμοι απάντησης ερωτημάτων και ενημέρωσης σε περίπτωση καθυστερήσεων, σε 14 σύνολα πραγματικών συγκοινωνιακών δεδομένων MMM διαφόρων μεγεθών, τα οποία που περιλαμβάνουν τις μητροπολιτικές περιοχές του Βερολίνου, του Λονδίνου, της Ρώμης, της Αθήνας και της Μαδρίτης. Τα πειραματικά αποτελέσματα κατέδειξαν ότι οι αλγόριθμοι απάντησης ερωτημάτων του ανηγμένου χρονοεκτεταμένου μοντέλου υπερτερούν εκείνων του μοντέλου DTM, ενώ το αντίθετο συμβαίνει για τον αλγόριθμο ενημέρωσης σε περίπτωση καθυστερήσεων. Επίσης, τα πειραματικά αποτελέσματα κατέδειξαν ότι οι χρόνοι απόκρισης ερωτημάτων των νέων γραφοκεντρικών μοντέλων είναι συγκρίσιμοι, ή/και καλύτεροι, από/με αυτούς των γνωστών διανυσματοκεντρικών μοντέλων. (δ) Αναπτύχθηκε μια εφαρμογή κινητών συσκευών για ταξιδιωτική πλοήγηση σε αστικά περιβάλλοντα με χρήση ΜΜΜ, βασισμένη στα νέα γραφοκεντρικά μοντέλα, η οποία παρέχει την δυνατότητα στους χρήστες να αξιολογούν τις προτεινόμενες διαδρομές. H εφαρμογή καταδεικνύει την πρακτική εφαρμοσιμότητα των προτεινόμενων μοντέλων και αλγορίθμων.
Abstract (translated): An ever growing emphasis is put nowadays in developing personalized journey planning and renewable mobility services in smart cities. These services combine means of scheduled-based public transport and electric vehicles or bikes, using crowdsourcing techniques for collecting real-time traffic information and for assessing the recommended routes. The goal is to develop a system that will allow the fast, real-time computation of best routes. The main challenges in developing such a system are both technological and algorithmic. The technological challenge concerns the collection, storage, management, and updating of a huge volume of transport data that are usually time-dependent, and the provision (through these data) of personalized renewable mobility services in smartphones. This challenge is typically confronted by creating a cloud infrastructure that on the one hand will support the storage, management, and updating of data, while on the other hand it will handle the necessary data feed to the smartphone applications for providing the users with the requested best routes. The algorithmic challenge concerns the development of innovative algorithms for the efficient provision of journey planning services in smartphones, based on data they will receive from the cloud infrastructure. These services guarantee the computation of realistic and useful best routes, as well as the updating of the precomputed (route and timetable) information, in case of delays of scheduled public transport vehicles, so that the users can online update their routes to destination. The goal is to develop an algorithmic basis for supporting modern renewable mobility services, such as “mobility on demand” (where the next leg of a journey is decided in real-time) and “door-to-door” personalized mobility, in urban scheduled-based public transport environments. Scheduled-based public transport systems should not only compute in real-time end-user queries requesting best routes, but also to update the timetable information in case of delays. The core algorithmic issues of mobility and journey planning (regarding the computation of optimal routes under certain criteria) in scheduled-based public transport systems concern the efficient solution of the fundamental earlier arrival (EA) problem (compute a journey from station S to station T minimizing the overall traveling time required to complete the journey), the minimum number of transfers (MNT) problem (compute a journey from station S to station T minimizing the number of times a passenger is required to change vehicle), and the efficient updating of timetable information in case of vehicle delays. The EA and MNT problems have been extensively studied in the literature under two main approaches: the array-based modeling (where the timetable is represented as an array) and the graph-based modeling (where the timetable is represented as a graph). Experimental results have shown so far that the array-based approaches are faster in terms of query time than graph-based ones, as they are able to better exploit data locality and do not rely on priority queues. On the other hand, the arraybased approaches have not been theoretically or experimentally studied as far as the efficient updating of timetable information, in case of delays, is concerned. In this thesis, new graph-based models are being developed that solve efficiently the aforementioned fundamental algorithmic mobility problems in urban scheduled-based public transport systems, along with a mobile application (journey planner) running on Android-based smartphones that includes a service for the evaluation of the recommended routes by the users. In particular: (a) An extensive comparative evaluation was conducted on graph-based dynamic models that represent big data volumes regarding their suitability for representing timetable information. The study confirmed that the realistic time-expanded model is the most suitable for representing timetable information. (b) Two new graph-based models have been developed for representing timetable information, the reduced time-expanded model and the dynamic timetable model (DTM), both of which are more space-efficient with respect to the realistic time-expanded model. For both of the new models, new efficient algorithms were developed for fast answering of EA and MNT queries, as well as for updating the timetable information representation in case of delays. (c) An extensive experimental evaluation was conducted with the new graph-based models and their associated query and update algorithms on a set of 14 real-world scheduled-based transportation systems, including the metropolitan areas of Berlin, Athens, London, Rome, and Madrid. The experimental results showed that the query algorithms of the reduced time expanded model are superior to those of the DTM model, while the reverse is true regarding the update algorithms. In addition, the experimental study showed that the query algorithms of the new graph-based models compete favorably with those of the best array-based models. (d) A mobile, cloud-based, journey planner was developed whose core algorithmic engine builds upon the new graph-based models. The mobile application is accompanied by a service that allows the users to assess the recommended journeys. The journey planner demonstrates the practicality of the new graph-based models and their associated query and update algorithms.
Appears in Collections:Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΔ)

Files in This Item:
File Description SizeFormat 
Phd-Thesis-Giannakopoulou.pdf4.26 MBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons