  We develop theoretical foundations and practical algorithms for vehicle
routing with time-dependent travel times. We also provide new benchmark
instances and experimental results. First, we study basic operations on
piecewise linear arrival time functions. In particular, we devise a faster
algorithm to compute the pointwise minimum of a set of piecewise linear
functions and a monotonicity-preserving variant of the Imai-Iri algorithm to
approximate an arrival time function with fewer breakpoints.
  Next, we show how to evaluate insertion and deletion operations in tours
efficiently and update the underlying data structure faster than previously
known when a tour changes. Evaluating a tour also requires a scheduling step
which is non-trivial in the presence of time windows and time-dependent travel
times. We show how to perform this in linear time.
  Based on these results, we develop a local search heuristic to solve
real-world vehicle routing problems with various constraints efficiently and
report experimental results on classical benchmarks. Since most of these do not
have time-dependent travel times, we generate and publish new benchmark
instances that are based on real-world data. This data also demonstrates the
importance of considering time-dependent travel times in instances with tight
time windows.
