A novel time-dependent model for route planning in public transit networks

• Κύριος συγγραφέας: Μαχαίρα, Παρασκευή-Μαρία-Μαλεβή
• Άλλοι συγγραφείς: Machaira, Paraskevi-Maria-Malevi
• Γλώσσα: English
• Έκδοση: 2022
• Θέματα: TRIPLA query algorithm; Multimodal journey planning; REX model; Schedule-based timetables; Πολυτροπική δρομολόγηση; Συγκοινωνιακά δίκτυα

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.