A novel time-dependent model for route planning in public transit networks
| datacite.contributor.RelatedPerson | Ευστράτιος Γαλλόπουλος | |
| datacite.contributor.Supervisor | Χρήστος Ζαρολιάγκης | |
| datacite.contributor.Supervisor | Σπυρίδων Κοντογιάννης | |
| dc.contributor.author | Μαχαίρα, Παρασκευή-Μαρία-Μαλεβή | |
| dc.contributor.other | Machaira, Paraskevi-Maria-Malevi | |
| dc.date.accessioned | 2022-12-23T06:43:54Z | |
| dc.date.available | 2022-12-23T06:43:54Z | |
| dc.date.issued | 2021-10-21 | |
| dc.degree | masterThesis | |
| dc.description.abstract | In this thesis, the non-FIFO time-dependent model with REalistic vehicle eXchange times (REX) is introduced for schedule-based public transport systems, along with two novel query al- gorithms for computing optimal multimodal journeys for either a single criterion (earliest arrivals) or two criteria (plus number of transfers). The REX model is a considerable en- hancement of the simple time-dependent model, with additional features towards handling non-negligible exchanges from one vehicle to another, as well as supporting non-FIFO in- stances which are typical in public transport, without compromising the space e ciency of the model. Apart from the novelty of the model, REX is also accompanied with two novel query algorithms, whose rationale is some short of “trip-targeted” label-correction propagation process: the rst algorithm, TRIP-based Label-correction propagation Algorithm (TRIPLA), efficiently solves the realistic earliest-arrival routing problem; the second algo- rithm, Multi-criteria TRIP-based Label-correction propagation Algorithm (McTRIPLA), solves the bicriteria variant of the problem, where apart from the earliest-arrival objective, the commuters also care for minimizing the number of vehicle exchanges. The set of Pareto- optimal journeys is discovered when all the arrival-times are bounded. We conduct a thor- ough experimental evaluation on real-world public transit networks which demonstrates that TRIPLA query algorithm for the REX model outperforms signi cantly all state-of-art query algorithms for multimodal routing in schedule-based public transport models, while McTRIPLA is competitive. | |
| dc.description.translatedabstract | Στην παρούσα διπλωματική εργασία, παρουσιάζεται το χρονο-εξαρτώμενο με ρεαλιστικούς χρόνους μετεπιβίβασης μοντέλο REX, για δίκτυα δημόσιων συγκοινωνιών που βασί- ζονται σε χρονοδιάγραμμα, μαζί με δύο νέους αλγόριθμους ερωτημάτων για τον υπολογισμό βέλτιστων πολυτροπικών ταξιδιών, είτε για ένα μόνο ένα κριτήριο βελτιστοποίησης (νωρίτερη αφίξη) είτε για δύο (επιπλέον ο αριθμός των μετεπιβάσεων). Το μοντέλο REX είναι μια σημαντική βελτίωση του απλού χρονο-εξαρτώμενου μοντέλου, με επιπλέον χαρακτηριστικά για την ενσωμάτωση μη αμεληταίου χρόνου μετεπιβιβάσεων από το ένα όχημα στο άλλο, καθώς και την υποστήριξη περιπτώσεων που δεν ικανοποιούν την FIFO ιδιότητα, οι οποίες είναι συχνές στα μέσα μαζικής μεταφοράς του πραγματικού κόσμου, χωρίς να διακυβεύεται η χωρική απόδοση του μοντέλου. Εκτός από την καινοτομία του νέου μοντέλου, το REX συνοδεύεται επίσης από δύο νέους αλγόριθμους ερωτημάτων, η λογική των οποίων περιλαμβάνει μία διαδικασία στοχευμένης διάδοσης διόρθωσης ετικετών: ο πρώτος αλγόριθμος, TRIP-based Label-correction propagation Algorithm (TRIPLA), επιλύει αποτελεσματικά το ρεαλιστικό πρόβλημα δρομολόγησης νωρίτερης άφιξης. Ο δεύτερος αλγόριθμος, Multi-criteria TRIP-based Label-correction propagation Algorithm (McTRIPLA), λύνει τη δικριτηριακή παραλλαγή του προβλήματος, όπου εκτός από την νωρίτερη άφιξη, οι επιβάτες ενδιαφέρονται επίσης για την ελαχιστοποίηση του συνολικού αριθμού των μετεπιβιβάσεων. Το σύνολο των βέλτιστων κατα Pareto προτεινόμενων ταξιδιών ανακαλύπτεται όταν ορισυικοποιηθούν όλοι οι χρόνοι άφιξης. ∆ιεξάγουμε μια διεξοδική πειραματική αξιολόγηση σε δίκτυα δημόσιας συγκοινωνίας του πραγματικού κόσμου, η οποία δείχνει ότι ο αλγόριθμος ερωτημάτων TRIPLA για το μοντέλο REX υπερτερεί σημαντικά όλων των αλγορίθμων ερωτημάτων της βιβλιογραφίας που αφορούν πολυτροπική δρομολόγηση σε μοντέλα δημόσιων συγκοινωνιών βάσει χρονοδιαγράμματος, ενώ ο McTRIPLA είναι ανταγωνιστικός | |
| dc.identifier.uri | https://hdl.handle.net/10889/24215 | |
| dc.language.iso | en | |
| dc.rights | Attribution-NonCommercial-NoDerivs 3.0 United States | * |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/us/ | * |
| dc.subject | TRIPLA query algorithm | |
| dc.subject | Multimodal journey planning | |
| dc.subject | REX model | |
| dc.subject | Schedule-based timetables | |
| dc.subject.alternative | Πολυτροπική δρομολόγηση | |
| dc.subject.alternative | Συγκοινωνιακά δίκτυα | |
| dc.title | A novel time-dependent model for route planning in public transit networks | |
| dc.title.alternative | Ένα νέο χρονο-εξαρτώμενο μοντέλο δρομολόγησης για δίκτυα μαζικής μεταφοράς |