Vehicle routing with time-dependent travel times: Theory, practice, and benchmarks

Vehicle routing with time-dependent travel times: Theory, practice, and benchmarks

Authors: Blauth Jannis; Held Stephan; Muller Dirk; Schlomberg Niklas; Traub Vera; Trobst Thorben; Vygen Jens

Discrete Optimization - 2024

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.

https://doi.org/10.1016/j.disopt.2024.100848

Cite as:

@article{blauth2024vehicle,
  title={Vehicle routing with time-dependent travel times: Theory, practice, and benchmarks},
  author={Blauth, Jannis and Held, Stephan and M{\"u}ller, Dirk and Schlomberg, Niklas and Traub, Vera and Tr{\"o}bst, Thorben and Vygen, Jens},
  journal={Discrete Optimization},
  volume={53},
  pages={100848},
  year={2024},
  publisher={Elsevier}
}



    Leave a Reply

    Your email address will not be published. Required fields are marked *

    x
    This site uses cookies to make navigation simple and efficient. By continuing you declare that you want to automatically accept the privacy policy. More. Close