Generating Time Dependencies in Road Networks

In the last decade major progress has been made in accelerating shortest path queries in large-scale, time-dependent road networks. Most techniques are heuristically motivated and their performance is experimentally evaluated on real-world data. However, to our knowledge no free time-dependent dataset is available to researchers. This is the first work proposing algorithmic approaches for generating timedependent road networks that are built on top of static road networks in the scenario of systematic delays. Based on an analysis of a commercial, confidential time-dependent dataset we have access to, we develop algorithms that utilize either road categories or coordinates to enrich a given static road network with artificial time-dependent data. Thus, the static road-networks we operate on may originate from manifold sources like commercial, open source or artificial data. In our experimental study we assess the usefulness of our algorithms by comparing global as well as local statistical properties and the shortest-path structure of generated datasets and a commercially used time-dependent dataset. Until now, evaluations of time-dependent routing algorithms were based on artificial data created by ad-hoc random procedure. Our work enables researchers to conduct more reasonable validations of their algorithms than it was possible up to now.