Keyword-Coverage Optimal Route Search on Temporal Transportation Networks
Mathematics · 27.10.2026 · 14 (21) · 3927
DOI: 10.3390/math14213927 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematics, online erschienen am 27.10.2026. Verfasst von Youming Ge und 1 weiteren Autor:innen. Die Arbeit nennt 25 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Henan Provincial Key Scientific Research Project of Higher Education Institutions.
Abstract (Originalsprache)
Scheduled public transit constrains both when a traveler can reach a point of interest and whether enough time remains to visit it. We study the Keyword-Coverage Optimal Route Search on Temporal Transportation Networks problem, which returns the top-k distinct routes that maximize weighted keyword coverage subject to timetable, time-window, and budget constraints. We define keyword coverage using feasible point-of-interest visits and prove the problem NP-hard by a polynomial-time reduction from Budgeted Maximum Coverage. To solve the problem, we first filter trips and stations using temporal reachability and a time-dependent minimum-budget profile. We then develop an exact best-first search that uses the minimum-budget profile and an admissible keyword-coverage upper bound to prune route prefixes safely. For faster candidate generation, we propose a bounded greedy search that maintains a certified feasible continuation. Every route returned by this heuristic satisfies the query constraints, although it has no proven coverage approximation ratio and may return fewer than k routes. After finalizing the revised algorithms and dwell-time scoring rule, we reran the evaluation on the Austin and Houston transit networks. The main study contains 3600 runtime measurements, and a separate route-level study independently checks 22,775 A*/AP route records from 1260 queries. AP returns the requested k routes on 874 queries. On 240 tractable queries with a positive exact reference, its mean best-score ratio relative to A* is 0.94, and it matches the exact best score on 224 queries. A* also matches the complete ordered top-k output of exhaustive enumeration on all 20 small instances.
Förderung
- Henan Provincial Key Scientific Research Project of Higher Education Institutions
Zitieren
APA
Ge, Y., & Ji, Z. (2026). Keyword-Coverage Optimal Route Search on Temporal Transportation Networks. Mathematics, 14(21), 3927. https://doi.org/10.3390/math14213927
Vancouver
Ge Y, Ji Z. Keyword-Coverage Optimal Route Search on Temporal Transportation Networks. Mathematics. 2026;14(21):3927. doi:10.3390/math14213927
BibTeX
@article{Ge2026,
author = {Ge, Youming and Ji, Zhihang},
title = {Keyword-Coverage Optimal Route Search on Temporal Transportation Networks},
journal = {Mathematics},
year = {2026},
volume = {14},
number = {21},
pages = {3927},
doi = {10.3390/math14213927}
}
EUVIMED