A method and system for determining a route from a starting point to a destination on a road network are provided, where an estimation function for vertices of the road network is employed, and where a tiling covers an area in which at least a portion of the road network is contained. A resistance value of each tile of the tiling is provided, and the values of the estimation function for vertices of the road network are determined in accordance with the resistance values of the tiles of the tiling. In an example implementation, the resistance value of a given tile is a lower bound on or the minimum of the costs associated with an optimum route connecting any pair of vertices located on the boundary of the given tile divided by an air-line distance of the pair of vertices.