Fast travel-distance estimation using overhead graph

Abstract

Shortest path can be computed in real-time for single navigational instructions. However, in complex optimisation tasks, lots of travel-distances (lengths of shortest paths) are needed and the total workload becomes a burden. We present a fast method for estimating the travel-distance from one location to another by using an overhead graph that stores the ratio between the bird-distance and the travel-distance for few representative locations. The travel-distance is then estimated for any two locations using the corresponding value between their nearest nodes in the graph. We test the method within an optimization setting where the goal is to relocate health services so that the travel-distance of patients is minimised. We build the overhead graph using road network information from Open Street Map and experiment with real-world data in the region of North Karelia, Finland as a part of the ongoing IMPRO project. The results show that the average estimation error is 0.5 km with a graph of 512 nodes, and the total processing time reduces from 1.2 hours to 2.9 seconds per iteration in the optimisation process. The error in the estimated travel-distances is 2%, on average, which is significantly smaller than 8% of the second best estimation method.