A network-consistent time-dependent travel time layer for routing optimization problems

In the vehicle routing literature, there is an increasing focus on time-dependent routing problems, where the time (or cost) to travel between any pair of nodes (customers, depots) depends on the departure time. The aim of such algorithms is to be able to take recurring congestion into account when planning logistics operations. To test algorithms for time-dependent routing problems, time-dependent problem data is necessary. This data usually comes in the form of three-dimensional travel time matrices that add the departure time as an extra dimension. However, most currently available time-dependent travel time matrices are not network-consistent, i.e., the travel times are not correlated both in time and in space. This stands in contrast to the behavior of real life congestion, which generally follows a specific pattern, appearing in specific areas and then affecting all travel times to and from those areas. As a result of the lack of available network-consistent travel time matrices, it is difficult to develop algorithms that are able to take this special structure of the travel time data into account.In this paper, we present a method to generate time-dependent travel time matrices that are both spatially and temporally correlated and hence network-consistent. The novel travel time generation model is conceptually elegant, requires a minimal amount of input data and provides an efficient and effective way of storing the time-dependent travel time matrices. In this way, the data sets generated by our approach achieve a much larger degree of realism, without suffering from a decreased usability. The characteristics and applicability of the newly presented model are demonstrated on a time-dependent vehicle routing problem. The method to generate network-consistent time-dependent travel time data has been implemented in Java and is available for download (http://antor.ua.ac.be/network-consistent).

► We develop a method to generate network-consistent data sets for vehicle routing problems.
► Travel times in our data sets are both spatially and temporally correlated, like in real life.
► Like in real life, congestion in our data sets occurs in regions and at specific moments in time.
► These data sets are therefore much more realistic than most other data sets available in the literature.
► The data sets generated by our method should lead to better algorithms for time-dependent routing problems.