Efficient Multi-Modal Route Planning with Result Diversity: A TNT Approach
Hannah Bast, Mirko Brodesser, Sabine Storandt
Journal of Data Processing, Vol. 15, No. 3, 2025.
DOI: https://doi.org/10.6025/jdp/2025/15/3/91-106
Link: https://www.dline.info/jdp/fulltext/v15n3/jdpv15n3_1.pdf
Abstract:
The paper computed small yet representative sets of reasonable paths in a multi-modal transportation
scenario involving cars, walking, and transit. Traditional route planning systems typically optimize for a
single mode of transportation, but TNT aims to offer diverse and practical path combinations without preselecting
a specific mode.
Using Pareto sets with multiple optimization criteria like duration, transfer penalty, and car duration, the
method captures diverse routes. However, not all Pareto-optimal paths are reasonable, so the authors define
three types of reasonable paths based on relative durations: only car, mixed transit with limited car and
walking, and much transit with walking. Thresholds filter unreasonable paths and extract concise results.
Speed-up techniques include extending dominance by early results, rounding transfers to full minutes, and
using implicit walking duration. Experimental results across cities like New York demonstrate that TNT
effectively reduces query times to about one second on average while maintaining high result quality. The
work emphasizes generating manageable, representative route options rather than strictly optimal ones,
enhancing usability in real-world applications.