  We study the earliest arrival problem in road networks with static
time-dependent functions as arc weights. We propose and evaluate the following
simple algorithm: (1) average the travel time in k time windows, (2) compute a
shortest time-independent path within each window and mark the edges in these
paths, and (3) compute a shortest time-dependent path in the original graph
restricted to the marked edges. Our experimental evaluation shows that this
simple algorithm yields near optimal results on well-established benchmark
instances. We additionally demonstrate that the error can be further reduced by
additionally considering alternative routes at the expense of more marked
edges. Finally, we show that the achieved subgraphs are small enough to be able
to efficiently implement profile queries using a simple sampling-based
approach. A highlight of our introduced algorithms is that they do not rely on
linking and merging profile functions.
