Estimation and determination of shortest path length in a road network with obstacles

This paper presents a modelling of natural obstacles in a road network for improving the commonly applied lower bound on the distance between two points: the Euclidean distance. Then, two applications of this new lower bound are proposed: the estimation of distances and an improvement of the Dijkstra algorithm. In both cases, the numerical experiments performed using the Swiss road network lead to obtaining very good results. Indeed, distances are estimated with a low percentage error on average and CPU times required by the Dijkstra method are significantly lower than those previously measured.