Optimum route determination with tiling

• US 9,279,692 B2
• Filed: 06/02/2011
• Issued: 03/08/2016
• 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): Kiswanto, Nicholas
• Application Number:
  US13/152,145
• Publication Number:
  US 20110301837A1
• Time in Patent Office: 1,741 Days
• Field of Search: 701/400, 701/409
• US Class Current: 1/1
• 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 system for optimum route determination, comprising:

a first storage unit containing road segment data;

a second storage unit containing rank information data;

a working memory unit for storing a subset of the road segment data; and

a processing unit coupled to the working memory unit and adapted to determine an optimum route from a start point to a destination based on the rank information data, the rank information data for a road segment respectively being independent of a destination of the optimum route determination and indicating whether the road segment is contained in an optimum route having a start point located in a first tile of a tiling, the first tile having at least a distance defined by the rank information data.

2. The system for optimum route determination of claim 1 where the system includes an additional processing unit adapted to manage the data stored in the working memory unit based on the rank information data.

3. The system for optimum route determination of claim 1, where the system includes a third storage unit containing tiling definition data.

4. The system for optimum route determination claim 1 where the working memory unit has a storage capacity sufficient to store a subset of the road segment data required for optimum route determination.

5. A system for optimum route determination, comprising:

a first storage unit containing road segment data;

a second storage unit containing rank information data;

a working memory unit for storing a subset of the road segment data; and

a processing unit coupled to the working memory unit and adapted to determine an optimum route from a start point to a destination based on the rank information data, the rank information data for a road segment stored in the second storage unit respectively being independent of a destination of the optimum route determination and indicating whether the road segment is contained in an optimum route having a start point located in a first tile of a tiling, the first tile being different from a tile of the tiling in which the road segment is located and the first tile having at least a distance defined by the rank information data from the tile of the tiling in which the road segment is located.

6. The system of claim 5 where the subset of the road segment data stored by the working memory unit is selected as a function of the rank information value.

7. The system of claim 5 where the rank information value for a road segment respectively indicates whether the road segment is contained in an optimum route having a start point located in a first tile and a destination point located in a second tile, the first tile being different from the tile in which the road segment is located and the second tile being different from the tile in which the road segment is located.

8. A navigation system for use in providing guidance on a suitable route for a vehicle comprising:

an output unit;

a position detection unit;

a system for computing an optimum route from a start point to a destination through a use of a tiling applied to a network of road segments, the system for computing an optimum route utilizing a rank information value for a road segment, which rank information value is stored in a storage unit and is independent of a destination of the optimum route determination and indicates whether the road segment is contained in an optimum route having a start point located in a first tile of a tiling, the first tile being different from a tile of the tiling in which the road segment is located, and the first tile having at least a distance defined by the rank information value.

9. The navigation system of claim 8 where the position detection unit is adapted to provide a set of data sufficient to define a current position of the navigation system to be used as the start point.

10. The navigation system of claim 8 where the rank information value for a road segment respectively indicates whether the road segment is contained in an optimum route having a start point located in a first tile and a destination point located in a second tile, the first tile being different from the tile in which the road segment is located and the second tile being different from the tile in which the road segment is located.