Keyword-Coverage Optimal Route Search on Temporal Transportation Networks

Source 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.