Abstract
In many transportation problems, the fact that travel times vary depending on when one travels is an important aspect. As standard algorithms for calculating time-dependent travel times in road networks are too slow to handle the large number of requests made in a VRP solver, specialized algorithms are needed. We present a topology module for VRPs with time-dependent travel times. The model is based on the concept of a cost function that captures all relevant information about travel along one or more road links or paths. Cost functions form a closed semiring, which makes them suitable for use in standard shortest path algorithms. However, they may be computationally expensive. We therefore focus on reducing the effective size of the road network, by arranging it in a hierarchy of regions. For each region, we precompute the thoroughfare, which contains the road links in all shortest paths through the region. In a computation, the required thoroughfares are stitched together to produce a small network that yields the correct result. We also introduce approximations in the cost function calculations in order to manage their complexity. A demonstration on synthetic data is included.
