Optimum route determination with tiling

• US 7,957,894 B2
• Filed: 11/09/2006
• Issued: 06/07/2011
• Est. Priority Date: 11/09/2005
• Status: Active Grant

• Current Assignee: Harman Becker Automotive Systems GmbH (Samsung Electronics Co. Ltd.)
• Original Assignee: Harman Becker Automotive Systems GmbH (Samsung Electronics Co. Ltd.)
• Inventors: Wellmann, Harald
• Primary Examiner(s): Tran; Khoi
• Assistant Examiner(s): Kiswanto; Nicholas
• Application Number:
  US11/595,802
• Publication Number:
  US 20070129885A1
• Time in Patent Office: 1,671 Days
• Field of Search: 340/995.1, 340/995.14, 340/995.18, 340/995.27, 340 1- 9, 340 11- 14, 340 17- 19, 340/21, 340/22, 340/25, 340/26
• US Class Current: 701/209
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G08G 1/0968 Systems involving transmission of navigation instructions to the vehicle
• CPC Class Codes: G08G 1/096827 where the route is computed onboard
• CPC Class Codes: G08G 1/09685 where the complete route is computed only once and not updated

Abstract

An optimum route search may be conducted through the use of a tiling overlay on the network of road segments. Overlaying the tiling (grid) over the road segments allows for a reduction of the number of road segments considered for an optimum path as road segments can be evaluated on whether the road segment is part of an optimal path to the borders of a first tile and then successively larger frames of tiles around the initial tile. By reducing the number of road segments considered for the optimum route search to road segments that are part of optimal routes to various tile boundary edges, the computation of the optimum route for the route of interest may be quicker and less resource intensive than efforts to determine optimum routes through other methods.

Claims

1. A computer-implemented method for pre-processing road segment data for optimum route determination, comprising the steps of:

using a computer-based pre-processing system for;

providing the road segment data;

defining a tiling covering an area where the road segments are contained by dividing the area into a plurality of tiles, each tile containing at least one road segment;

determining a rank information for a road segment, including determining a tile containing the road segment, selecting a first tile having at least a given tile distance from the tile containing the road segment, and determining whether the road segment is contained in an optimum route having a start road segment located in the first tile; and

determining a maximum of the given tile distance for which the road segment is contained in an optimum route, and where the rank information is based on the tiling and quantifies the relevance of the road segment for optimum routes connecting tiles of the tiling.

2. The method for pre-processing road segment data of claim 1 where the rank information quantifies the relevance of a road segment for optimum routes connecting points located on tile borders.

3. The method for pre-processing road segment data of claim 1 where a combination of the definition of tiling and the definition of road segments is defined such that each one of the road segments is contained in at most one tile of the tiling and that the rank information is determined in dependence on the tiling.

4. The method for pre-processing road segment data of claim 1 where a vertex of the start road segment is located on a border of the first tile.

5. The method for pre-processing road segment data of claim 1 where determining the rank information includes the step of selecting a second tile having at least the given tile distance from the tile containing the road segment, with a destination road segment of the optimum route being located in the second tile.

6. The method for pre-processing road segment data of claim 5 where a vertex of the destination road segment is located on a border of the second tile.

7. The method for pre-processing road segment data of claim 1 where the step of determining the rank information is performed recursively for increasing values of the given tile distance.

8. The method for pre-processing road segment data of claim 1 where providing road segment data includes providing road segment weighting factors, and determining the rank information is at least partially based on the road segment weighting factors.

9. The method for pre-processing road segment data of claim 1 where the step of determining the rank information is performed for each one of the road segments.

10. The method for pre-processing road segment data of claim 1 where the tiles of the tiling are rectangular in shape.

11. The method for pre-processing road segment data of claim 1 where a tile distance between two tiles is defined as the minimum number of tile borders traversed on a path connecting the two tiles.

12. The method for pre-processing road segment data of claim 1 that includes the step of outputting the determined rank information.

13. The method for pre-processing road segment data of claim 1 where the road network is an arbitrary graph and each road segment is an edge of the graph.