  Vehicle routing algorithms usually reformulate the road network into a
complete graph in which each arc represents the shortest path between two
locations. Studies on time-dependent routing followed this model and therefore
defined the speed functions on the complete graph. We argue that this model is
often inadequate, in particular for arc routing problems involving services on
edges of a road network. To fill this gap, we formally define the
time-dependent capacitated arc routing problem (TDCARP), with travel and
service speed functions given directly at the network level. Under these
assumptions, the quickest path between locations can change over time, leading
to a complex problem that challenges the capabilities of current solution
methods. We introduce effective algorithms for preprocessing quickest paths in
a closed form, efficient data structures for travel time queries during routing
optimization, as well as heuristic and exact solution approaches for the
TDCARP. Our heuristic uses the hybrid genetic search principle with tailored
solution-decoding algorithms and lower bounds for filtering moves. Our
branch-and-price algorithm exploits dedicated pricing routines, heuristic
dominance rules and completion bounds to find optimal solutions for problem
counting up to 75 services. Based on these algorithms, we measure the benefits
of time-dependent routing optimization for different levels of travel-speed
data accuracy.
