Optimum route determination with tiling

• US 20070129885A1
• Filed: 11/09/2006
• Published: 06/07/2007
• Est. Priority Date: 11/09/2005
• Status: Active Grant

• Current Assignee: Harald Wellmann
• Original Assignee: Harald Wellmann
• Inventors: Wellmann, Harald
• Granted Patent: US 7,957,894 B2
• Time in Patent Office: Days
• 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 method for pre-processing road segment data for optimum route determination, comprising the steps of:

providing the road segment data;

defining a tiling covering an area where the road segments are contained; and

determining a rank information for a road segment, where the rank information 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 is determined in dependence on the tiling and 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 3 where the step of determining the rank information for a road segment includes the steps of 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.

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

6. The method for pre-processing road segment data of claim 4 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.

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

8. The method for pre-processing road segment data of claim 4 where determining the rank information includes the step of determining a maximum of the given tile distance for which the road segment is contained in an optimum route.

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

10. The method for pre-processing road segment data of claim 4 where, for a given value of the given tile distance, an optimum route search is performed on a subset of road segments selected based on results obtained for smaller values of the given tile distance.

11. 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.

12. 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.

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

14. 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.

15. The method for pre-processing road segment data of claim 1 that includes a step of combining a road segment sequence contained in one tile into a new road-segment.

16. The method for pre-processing road segment data of claim 1 that includes a step of coarsening the tiling after a predetermined road segment rank information has been determined.

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

18. 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.

19. A method for optimum route determination from a start point to a destination, comprising the steps of:

providing road segment data;

providing rank information for the road segments determined based upon a rank value based upon a tiling applied to the road network; and

determining an optimum route from the start point to the destination based on the road segment data and the rank information data.

20. The method for optimum route determination of claim 19 that includes selecting a subset of road segments based on the rank information, and where determining an optimum route is performed based on the subset of road segments.

21. The method for optimum route determination of claim 19 that includes the step of defining a tiling covering an area wherein the road segments are contained.

22. The method for optimum route determination of claim 21 where the combination of the tiling and the road segments are defined such that each one of the road segments is contained within at most one tile of the tiling.

23. The method for optimum route determination of claim 20 where the step of selecting a subset of road segments comprises the steps of:

determining a start tile containing the start point;

determining a destination tile containing the destination; and

including a road segment into the subset of road segments based on a road segment rank information and a minimum of a tile distance of a tile containing the road segment from the start tile and a tile distance of the tile containing the road segment and the destination tile.

24. The method for optimum route determination of claim 20 where the step of selecting a subset of road segments includes the steps of:

determining a start-destination tile distance from a start tile containing the start point to a destination tile containing the destination;

selecting a minimum rank value based on the start-destination tile distance; and

including all road segments having a rank value equal to or greater than the minimum rank value into the subset of road segments.

25. The method for optimum route determination of claim 19 including the step of providing road segment weighting factors, where the step of determining an optimum route is further based at least partially on the weighting factors.

26. The method for optimum route determination of claim 19 including the steps of:

receiving vehicle position data indicating a vehicle position, and

determining an optimum route from the vehicle position to the destination.

27. The method for optimum route determination of claim 19 where the road network is an arbitrary graph and each road segment is an edge of the graph.

28. A system for pre-processing road segment data, comprising:

a first storage unit containing road segment data;

a second storage unit containing tiling definition data;

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

a processing unit adapted to process data stored in the working memory unit and to determine a rank information of a road segment based on the tiling, where the rank information quantifies the relevance of the road segment for optimum routes connecting tiles of the tiling.

29. The system for pre-processing road segment data of claim 28 where the system is adapted to perform pre-processing road segment data by including utilizing a combination of the tiling and the road segment data defined such that each one of the road segments is contained in at most one tile of the tiling.

30. The system for pre-processing road segment data of claim 28 where the system includes an additional working memory unit coupled to the processing unit and adapted to store a determined rank information.

31. The system for pre-processing road segment data of claim 30 where the processing unit is adapted to process data stored in the additional working memory unit for determining the rank information.

32. The system for pre-processing road segment data of claim 28 where the working memory unit has a storage capacity sufficient to store a subset of road segment data required for an optimum route search for determining the rank information.

33. The system for pre-processing road segment data of claim 28 where the system includes an output unit for outputting a determined rank information.

34. The system for pre-processing road segment data claim 28, where the system includes a third storage unit (30) for storing a determined rank information.

35. The system for pre-processing road segment data claim 28, where the system includes at least one additional processing unit adapted to determine a rank information of a road segment based on the tiling, and where the processing unit and the additional processing unit are adapted to determine road segment rank information in parallel.

36. 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 rank information data;

where in that the rank information data is determined in dependence on the tiling and the rank information quantifies the relevance of a road segment for optimum routes connecting tiles of the tiling.

37. The system for optimum route determination of claim 36 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.

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

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

40. 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 pre-processing step that determines a rank information value for a road segment based on a relevance of that road segment to an optimum route passing through that road segment from a point on a border of a tile in the tiling containing the road segment to another point on the border of the tile in the tiling containing the road segment.

41. The navigation system of claim 40 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.