Choosing heuristic for A* algorithm where cost is less than absolute distance
The simple options are to either multiply all path costs such that minimum cost is 1. Or multiply the heuristic such that the min cost is more or equal than the heuristic tells you for the same path.

The more complicated option is to look at the graph and estimate the chance that you will end up going through the low cost area. This requires some precalculation of the low cost areas and their influence on paths. 

For example a low cost highway, any heuristic that is close to it will need to get a bonus to account for taking the highway. But heuristics that are not going to take the highway can use the larger estimation.