Optimum route determination employing an estimation function

A method for determining a route to a destination on a graph employing as estimation function for a plurality of vertices of the graph, the estimation function providing a lower bound for costs associated with any route connecting a vertex of the graph and the destination, the method comprising:

• defining a tiling covering an area where at least a portion of the graph is contained;
• providing a resistance value for each tile of the tiling;
• and
• determining an estimation function value for a tile boundary vertex located on tile boundary in accordance with the resistance values of tiles of the tiling, where the resistance value of a given tile represents costs associated with routes connecting vertices of the graph located on a boundary of the given tile, so that a lower bound for costs associated with, the routes connecting vertices located on the boundary of the given tile is derivable based on the resistance value of the given tile.

A method for pre-processing road network data comprising:

• defining a tiling covering an area where at least a portion of the road network is contained;
• and
• for a tile of the tiling:
• determining vertices located on a boundary of the tile;
• determining a lower bound for costs associated with an optimum route connecting any pair of the vertices located on the boundary of the tile divided by an air-line distance of the pair of vertices;
• and
• outputting the determined lower bound.

A system for determining a route from a starting point to a destination on a road network employing an estimation function for a plurality of vertices of the road network, the estimation function providing a lower bound for costs associated with routes connecting a vertex of the road network and the destination, the system comprising:

• a first storage unit containing road network data;
• a second storage unit containing tiling definition data defining a tiling and a resistance value for each tile;
• and
• a processing unit determining an estimation function value for a tile boundary vertex located on a tile boundary in accordance with the resistance values of the tiles of the tiling, where the resistance value of a given tile, contained in the second storage unit, represents costs associated with routes connecting vertices of the road network located on a boundary of the given tile, so that a lower bound for costs associated with the routes connecting vertices located on the boundary of the given tile is derivable using the resistance value of the given tile.

A navigation system, comprising:

• an input function for inputting a destination;
• an output function for outputting a determined route;
• a system for determining a route from a starting point to a destination on a road network employing an estimation function for a plurality of vertices of the road network, the estimation function providing a lower bound for costs associated with routes connecting a vertex of the road network and the destination, the system comprising:
• a first storage unit containing road network data;
• a second storage unit containing tiling definition data defining a tiling and a resistance value for each tile;
• and
• a processing unit determining an estimation function value for a tile boundary vertex located on a tile boundary in accordance with the resistance values of the tiles of the tiling, where the resistance value of a given tile, contained in the second storage unit, represents costs associated with routes connecting vertices of the road network located on a boundary of the given tile, so that a lower bound for costs associated with the routes connecting vertices located on the boundary of the given tile is derivable using the resistance value of the given tile;
• and
• the system coupled to the input function for receiving the destination and to the output function for outputting a determined route.