Optimum route determination employing an estimation function
First Claim
1. A method for determining a route from a starting point to a destination on a road network of a navigation system employing an estimation function for a plurality of vertices of the road network, the estimation function providing a lower bound for costs associated with any route connecting a vertex of the road network and the destination, the method comprising:
- defining a tiling covering an area where at least a portion of the road network is contained;
providing a resistance value of each tile of the tiling, anddetermining an estimation function value for a tile boundary vertex located on a tile boundary in dependence on the resistance values of tiles of the tiling, where the resistance value of a given tile represents costs associated with mutes 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.
1 Assignment
0 Petitions
Accused Products
Abstract
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.
-
Citations
39 Claims
-
1. A method for determining a route from a starting point to a destination on a road network of a navigation system employing an estimation function for a plurality of vertices of the road network, the estimation function providing a lower bound for costs associated with any route connecting a vertex of the road network and the destination, the method comprising:
-
defining a tiling covering an area where at least a portion of the road network is contained; providing a resistance value of each tile of the tiling, and determining an estimation function value for a tile boundary vertex located on a tile boundary in dependence on the resistance values of tiles of the tiling, where the resistance value of a given tile represents costs associated with mutes 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22)
-
-
23. 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.
-
-
24. 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. - View Dependent Claims (25, 26)
-
-
27. 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. - View Dependent Claims (28, 29, 30, 31, 32, 33, 34, 35)
-
-
36. 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. - View Dependent Claims (37, 38, 39)
-
Specification