Improving vehicle routing using traffic predictions

Vehicle routing through road networks is an important topic of research: time and money can be saved by reducing traffic jams, which would also reduce the burden on the environment. The problem of minimizing the travel time for a vehicle trip is easy to grasp but hard to solve, it is a highly complex shortest path problem. Our goal is to show that routing advice can be improved by using historical traffic data to predict the traffic conditions in the nearby future. We introduce several algorithms that combine historical data with live data in a smart way, our algorithm set contains fixed path algorithms, adaptive path algorithms and policy algorithms. In order to test their performance we create historical scenarios and test scenarios using micro-simulations because they can produce network-wide traffic data. We evaluate the realism of the simulations and highlight the problems that are encountered when trying to mimic reality. The results of the routing algorithms are compared to obtain a good insight in the advantages and drawbacks of the different algorithm types. We show that the best algorithms clearly outperform an algorithm based on the concept of modern in-car routing devices, even when only a limited amount of live data is available, which clearly shows that routing advice can be significantly improved using traffic predictions.AlgorithmicsSoftware and Computer TechnologyElectrical Engineering, Mathematics and Computer Scienc