Method for Determining Correction Values for a Route Calculation Algorithm

摘要

A predefined area is divided into a plurality of tiles, a respective one of the tiles of the area being determined as a starting tile and the respective remaining tiles being determined as reference tiles, and special nodes, being predefined that are arranged in the starting tile or in the respective reference tile. For the respective starting tile, a correction value is determined, in each case in relation to one of the reference tiles, such that a respective cost ratio is determined for each special node of the respective starting tile in relation to each special node of the reference tile on the basis of the edge costs of the connections that are situated between the respective special node of the starting tile and the respective special node of the reference tile. The cost ratio is also determined on the basis of a heuristic value of the respective special node of the starting tile in relation to the respective special node of the reference tile. A mean value is determined on the basis of the determined cost ratios. The mean value is taken as a basis for determining the correction value of the starting tile in relation to the respective reference tile.

主权项

1. A method for determining correction values for a route calculation algorithm based on digital map data for a route network and/or a path network in a predefined area, the digital map data comprising:
respective nodes in the predefined area and connections between the respective nodes in the predefined area, and respective edge costs for the respective connections between the nodes, the method comprising the acts of: subdividing the predefined area, in a predefined manner, into a plurality of tiles, for which the correction values are determined, determining one of the tiles in the area respectively as a starting tile and the respective remaining tiles as reference tiles, first special nodes being predefined, which first special nodes are arranged in the starting tile and form a true or artificial subset of all nodes in the starting tile, and second special nodes being predefined, which second special nodes are arranged in the respective reference tile and form a true or artificial subset of all nodes in the respective reference tile, determining the correction value for the respective starting tile with respect to one of the reference tiles in each case in such a manner that:
a cost ratio is respectively determined for each first special node in the respective starting tile with respect to each second special node in the respective reference tile based on: (i) the edge costs of the connections, which lie between the respective first special node in the starting tile and the respective second special node in the respective reference tile and represent an optimum route between the first respective special node in the starting tile and the respective second special node in the respective reference tile, and (ii) a heuristic value for the respective first special node in the starting tile with respect to the respective second special node in the respective reference tile,a mean value is determined based on the determined cost ratios, andthe correction value for the starting tile is determined with respect to the respective reference tile based on of the mean value.