Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/9910
Title: Μοντέλα και αλγόριθμοι χρονοεξαρτώμενης πολυτροπικής δρομολόγησης σε συγκοινωνιακά δίκτυα
Other Titles: Models and algorithms for multimodal time-dependent routing in transportation networks
Authors: Παρασκευόπουλος, Ανδρέας
Keywords: Πολυτροπική δρομολόγηση
Συγκοινωνιακό δίκτυο
Πίνακας δρομολογίων
Χρονο-εκτεταμένο γράφημα
Αλγόριθμοι
Σταθμοί
Στάσεις
Μέσα Μαζικής Μεταφοράς (ΜΜΜ)
Μετεπιβίβαση
Keywords (translated): Multimodal routing
Transport networks
Timetables
Time-extended graph
Algorithms
Dijkstra
A star
Stations
Stops
Transportation
Transit
Abstract: Στη σύγχρονη εποχή, η χρήση προηγμένων εφαρμογών δρομολόγησης καθίσταται όλο και πιο αναγκαία για όσους ταξιδεύουν. Σε αυτό το πλαίσιο, το ενδιαφέρον επικεντρώνεται σε εφαρμογές που παρέχουν έγκυρες διαδρομές καθ' όλη τη διάρκεια της μέρας, συνδυάζοντας πολλαπλά μέσα μεταφοράς. Το αντικείμενο της παρούσας διπλωματικής εργασίας είναι η εύρεση βέλτιστων πολυτροπικών διαδρομών σε συγκοινωνιακά δίκτυα Μέσων Μαζικής Μεταφοράς (ΜΜΜ). Το πρόβλημα που μελετάται αφορά τον υπολογισμό της βέλτιστης πολυτροπικής διαδρομής από ένα σταθμό-αφετηρία προς ένα σταθμό-προορισμό, σε οποιαδήποτε χρονική στιγμή αναχώρησης, με χρήση περισσότερων του ενός μέσων μεταφοράς (πολυτροπική μετακίνηση), έτσι ώστε να ελαχιστοποιείται το κόστος του ταξιδιού (απόσταση, διάρκεια, αριθμός μετεπιβιβάσεων). Στο πλαίσιο αυτό, εξετάζονται χρονο-εκτεταμένα γραφοθεωρητικά μοντέλα τα οποία αναπαριστούν όλα τα δυνατά δρομολόγια των ΜΜΜ. Συνεισφορά της διπλωματικής εργασίας αποτελεί ο σχεδιασμός και η υλοποίηση νέων αποδοτικών μεθόδων, σχετικά με: α) τον υπολογισμό βέλτιστων πολυτροπικών διαδρομών με οποιοδήποτε συνδυασμό ΜΜΜ, συμπεριλαμβανομένης της δυνατότητας χρήσης ηλεκτρικών αυτοκινήτων και πεζόδρομων, β) τη χρήση ευρετικών μεθόδων για την αποτελεσματική οριοθέτηση των βέλτιστων πολυτροπικών διαδρομών σε δίκτυα ευρείας κλίμακας και γ) την αποτελεσματική διαχείριση των καθυστερήσεων στα ΜΜΜ. Στα πλαίσια της διπλωματικής εργασίας, διεξήχθη εκτενής πειραματική αξιολόγηση των νέων μεθόδων σε συγκοινωνιακά δίκτυα μητροπολιτικού εύρους, όπως του Λονδίνου (με 14,085,810 κόμβους και 41,837,355 ακμές) και του Βερολίνου (με 4,335,387 κόμβους και 12,701,695 ακμές). Παρά το μεγάλο μέγεθος των δικτύων, οι υλοποιήσεις επιτυγχάνουν: α) τον υπολογισμό των βέλτιστων πολυτροπικών διαδρομών σε χρόνο λιγότερο από 10 ms και β) την ενημέρωση των δρομολογίων των οχημάτων, σε περίπτωση καθυστερήσεων, σε χρόνο λιγότερο από 1 ms.
Abstract (translated): Using advanced routing applications becomes more and more necessary for travelers. In this context, the focus is on applications that provide valid paths throughout the course of the day, combining multiple transportation modes. The object of this thesis is to find optimal routes in multimodal transportation networks. The studied problem concerns the computation of the optimal multimodal route from a source-station to a destination-station, at any given departure time, using more than one means of transport (multimodal movement), to minimize the travel cost (distance, duration, number of transfers). In this context, we consider time-expanded graph models which represent all possible journeys of public transport. Contribution of this thesis is the design and implementation of new efficient methods for: a) the computation of the optimal multimodal routes via public transport, including the possibility of using electric cars and footpaths, b) the use of heuristics for the effective delimitation of optimal multimodal routes in large-scale networks and c) the management of delays in transportation. As part of this thesis, we conducted an extensive experimental evaluation of the new methods in public metropolitan scale networks such as those of London (with 14,085,810 nodes and 41,837,355 edges) and Berlin (with 4,335,387 nodes and 12,701,695 edges). Despite the large size of networks, the implementations achieve: a) the computation of optimal multimodal routes in less than 10 ms and b) the updating public transport journey schedules, in case of delays, in less than 1 ms.
Appears in Collections:Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΜΔΕ)

Files in This Item:
File Description SizeFormat 
thesis.pdfthesis3.3 MBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons