We have a navigation module for our software, which is very good at finding the shortest route. However, finding the fastest route takes ages. From what I can tell, it appears the problem is in the heuristic estimation of the cost of the remainder of the route.

At the moment, we use the time it takes to travel from a selected node to the destination in a direct line at speed of 300km/h, but this does not work very well. Any ideas on what to try?