Patent ID: 8660789

Claim:
A method comprising: partitioning, in a computer, a road network graph into subgraphs, wherein the road network graph has associated time-dependent edge weights; for each one of the subgraphs, which includes interior nodes and border nodes, determining a minimum lower-bound fastest path cost between the border nodes and the interior nodes of the one subgraph, based on minimum edge weight values in the one subgraph; for each pair of the subgraphs, determining a minimum lower-bound fastest path cost between respective border nodes of the pair of subgraphs, based on minimum edge weight values between the pair of subgraphs; finding a path between a first node in a first of the subgraphs and a second node in a second of the subgraphs using a search directed in accordance with a lower-bound estimator of travel time, the lower-bound estimator comprising the minimum lower-bound fastest path cost between the border nodes and the interior nodes of the first subgraph, the minimum lower-bound fastest path cost between respective border nodes of the first and second subgraphs, and the minimum lower-bound fastest path cost between the border nodes and the interior nodes of the second subgraph.