Keyword-Coverage Optimal Route Search on Temporal Transportation Networks
- 1School of Information Engineering, Henan University of Science and Technology, Luoyang 471023, China
Abstract
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.
Related
- Optimal transportation under McKean-Vlasov dynamics
- Overdetermined problem for optimal transportation
- On the Observability and Redundancy of Intelligent Transportation Networks
- Geometric flows of branched transportation networks
- Route optimization for urban hazardous materials transportation under time-varying road networks
BibTeX
@article{ge2026keywordcoverage,
title = {{Keyword-Coverage Optimal Route Search on Temporal Transportation Networks}},
author = {Youming Ge and Zhihang Ji},
journal = {Mathematics},
year = {2026},
month = oct,
doi = {10.3390/math14213927},
url = {https://www.mdpi.com/2227-7390/14/21/3927},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - Keyword-Coverage Optimal Route Search on Temporal Transportation Networks
AU - Youming Ge
AU - Zhihang Ji
PY - 2026
DA - 2026/10/27
JO - Mathematics
DO - 10.3390/math14213927
UR - https://www.mdpi.com/2227-7390/14/21/3927
AB - 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.
SN - 2227-7390
ER -