A novel time-dependent model for route planning in public transit networks
A novel time-dependent model for route planning in public transit networks
Date
2021-10-21
Authors
Μαχαίρα, Παρασκευή-Μαρία-Μαλεβή
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
TRIPLA query algorithm, Multimodal journey planning, REX model, Schedule-based timetables