  A novel landmark-based oracle (CFLAT) is presented, which provides
earliest-arrival-time route plans in time-dependent road networks. To our
knowledge, this is the first oracle that preprocesses combinatorial structures
(collections of time-stamped min-travel-time-path trees) rather than
travel-time functions. The preprocessed data structure is exploited by a new
query algorithm (CFCA) which computes (and pays for it), apart from
earliest-arrival-time estimations, the actual connecting path that preserves
the theoretical approximation guarantees. To make it practical and tackle the
main burden of landmark-based oracles (the large preprocessing requirements),
CFLAT is extensively engineered. A thorough experimental evaluation on two
real-world benchmark instances shows that CFLAT achieves a significant
improvement on preprocessing, approximation guarantees and query-times, in
comparison to previous landmark-based oracles, whose query algorithms do not
account for the path construction. It also achieves competitive query-time
performance and approximation guarantees compared to state-of-art speedup
heuristics for time-dependent road networks, whose query-times in most cases do
not account for path construction.
