Routing Method For Calculating A Route

• US 20090234569A1
• Filed: 03/09/2009
• Published: 09/17/2009
• Est. Priority Date: 03/11/2008
• Status: Abandoned Application

• Current Assignee: Navigon AG (Garmin Limited)
• Original Assignee: Navigon AG (Garmin Limited)
• Inventors: Kortge, Harald, Jansen, Ralph
• Application Number:
  US12/400,657
• Publication Number:
  US 20090234569A1
• Time in Patent Office: Days
• US Class Current: 701/200
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

A routing method for calculating a route between a first route endpoint (03), particularly a starting point, and a second route endpoint (04), particularly a destination, utilizes an electronically stored road map. The method includes the following steps:

• • a) defining a starting point (03) on a tile (02a);
  • b) calculating the travel cost value for all routes from the starting point (03) to all boundary elements (06) of the tile (02a) with a route calculation module, wherein the travel costs between the starting point (03) and each boundary element (06) are exactly determined during the travel cost calculation;
  • c) calculating a travel cost estimation for all boundary elements (06) of the tile (02a) with a distance evaluation module, wherein the travel costs from a boundary element (06) of the tile (02a) to one of the two route endpoints (04) are evaluated in an estimative fashion during the travel cost estimation based on the distance between the boundary element (06) and the route endpoint (04);
  • d) determining a combined value for all boundary elements (06) of the tile (02a) in a combined evaluation module, wherein the exactly calculated travel costs within the tile (02a) and the estimated travel costs outside the tile (02b) are evaluated in a combined fashion during the combined evaluation;
  • e) determining the next tile (02b) for continuing the route calculation in dependence on the combined evaluation; and
  • f) repeating steps a) to e) until an abort condition is fulfilled.

Claims

1. A routing method for calculating a route between a first route endpoint (03), particularly a starting point, and a second route endpoint (04), particularly a destination, by utilizing an electronically stored road map that describes the road network of a certain geographic area (01) consisting of roads and intersections by means of datasets stored in a database, wherein the road map is divided into several sections, namely tiles (02), that are stored in the database in the form of individual groups of datasets, wherein the tiles (02) collectively form the complete road map, and wherein the road network merges in boundary elements (06) particularly boundary roads, boundary intersections and/or boundary points, on the boundary lines (05) between adjacent tiles (02), with said method comprising the following steps:

a) defining a starting point (03) on a tile (02a);

b) calculating the travel cost value for all routes from the starting point (03) to all boundary elements (06) of the tile (02a) with a route calculation module, wherein the travel costs between the starting point (03) and each boundary element (06) are exactly determined during the travel cost calculation;

c) calculating a travel cost estimation for all boundary elements (06) of the tile (02a) with a distance evaluation module, wherein the travel costs from a boundary element (06) of the tile (02a) to one of the two route endpoints (04) are evaluated in an estimative fashion during the travel cost estimation based on the distance between the boundary element (06) and the route endpoint (04);

d) determining a combined value for all boundary elements (06) of the tile (02a) in a combined evaluation module, wherein the exactly calculated travel costs within the tile (02a) and the estimated travel costs outside the tile (02b) are evaluated in a combined fashion during the combined evaluation;

e) determining the next tile (02b) for continuing the route calculation in dependence on the combined evaluation; and

f) repeating steps a) to e) until an abort condition is fulfilled.

2. The routing method according to claim 1, in which a first route endpoint (03) is set as starting point in step a) at the beginning of the route calculation.

3. The routing method according to claim 1, in which the abort condition is fulfilled once at least one route between the two route endpoints has been determined.

4. The routing method according to claim 1, in which the exactly calculated travel costs within the tile (02a) are multiplied with a first correction value and/or the estimated travel costs outside the tile (02a) are multiplied with a second correction value during the determination of the combination value for the boundary elements (06) of the tile (02a) in the combined evaluation module.

5. The routing method according to claim 4, in which the first correction value and/or the second correction value can be changed in dependence on a route parameter, particularly in dependence on the distance between the two route endpoints (03, 04).

6. The routing method according to claim 1, in which the route calculation is continued in step e) with the next directly adjacent tile (02b), whose boundary line (05) with the preceding tile (02a) contains the boundary element (06e) with the best combined evaluation, wherein the boundary element (06e) with the best combined evaluation is set as starting point in step a) of the next calculation step.

7. The routing method according to claim 1, in which an ordered control list is kept, in which two control datasets can be stored for each boundary line (05) between a tile (02) that has already been processed during the route calculation and a directly adjacent tile (02), wherein the first control dataset contains the best combined evaluation determined for the cross-over at the boundary line (05) in one direction, as well as the assigned boundary element (06), and the second control dataset contains the best combined evaluation determined for the cross-over at the boundary line (05) in the opposite direction, as well as the assigned boundary element (06), wherein the route calculation is continued in step e) with the next tile (02), whose boundary line (05) has the control dataset with the best combined evaluation in the control list, and wherein the boundary element (06) stored in this control dataset is set as starting point in step a) of the next calculation step.

8. The routing method according to claim 7, in which, after calculating the combined evaluation in step d), it is respectively checked if a control dataset for this boundary line (05) already exists in the control list, wherein

aa) a new control dataset is generated if no control dataset exists for this boundary line (05) and the current combined evaluation and the assigned boundary element (06) are stored in this new control dataset;

bb) it is respectively checked whether or not the current combined evaluation is superior to the combined evaluation that is already stored in the control dataset if a control dataset already exists for this boundary line (05), wherein the combined evaluation stored in the control dataset and the assigned boundary element (06) are overwritten with the current combined evaluation and the assigned boundary element (06) in this case.

9. The routing method according to claim 7, in which the control dataset, in which the starting point for the next calculation step is stored in step a), is deleted from the control list.

10. The routing method according to claim 7, in which, after finding a first route or subsequent alternative route between the two route endpoints (03, 04), new control datasets are only incorporated into the control list if the combined evaluation of the new control dataset is superior to a threshold value.

11. The routing method according to claim 10, in which the threshold value is dynamically derived from the combined evaluation of the first route or from the combined evaluation of the last alternative route between the two route endpoints.

12. The routing method according to claim 10, in which all existing control datasets, the combined evaluation of which is inferior to the threshold value, are deleted from the control list.

13. The routing method according to claim 10, in which the threshold value is derived in the form of the product of the combined evaluation and a safety factor, wherein the safety factor has a value higher than 1.

14. The routing method according to claim 7, in which, after finding at least one route between the two route endpoints (03, 04), the route calculation for finding alternative routes is not aborted until the control list is empty.

15. The routing method according to claim 1, in which the route calculation is carried out in two search directions from the first route endpoint (03), as well as from the second route endpoint (04).

16. The routing method according to claim 15, in which the abort condition is fulfilled when at least one corresponding road is determined that has been selected in step e) during both route calculations from both search directions.

17. The routing method according to claim 15, in which, during the route calculation in two search directions, the classification of the significance of the road on which a boundary element is located, particularly the classification of the road as an expressway, a highway or a country road, is taken into account in the combined evaluation of the combined evaluation module in addition to the exactly calculated travel costs within a tile (02) and the estimated travel costs outside the tile (02).

18. The routing method according to claim 17, in which boundary elements (06) with the relatively highest road classification are preferably selected.

19. The routing method according to claim 15, in which, during the route calculation in two search directions, the abort condition is fulfilled when one of the two control lists that are respectively kept for both search directions is empty.

20. The routing method according to claim 15, in which an error message indicating an isolated route endpoint is output if the abort condition is fulfilled due to an empty control list.

21. The routing method according to claim 1, in which the tiles (02) respectively cover the same surface of the road map.

22. The routing method according to claim 1, in which the tiles (02) respectively have the same shape, particularly a rectangular shape.

23. The routing method according to claim 1, in which a standard travel cost calculation algorithm, particularly the routing algorithm according to Djikstra or the routing algorithm according to Belmann-Ford, is used in the route calculation module for calculating the exact travel costs within the tile (02).

24. The routing method according to claim 1, in which the distance between a boundary element (06) and the route endpoint (04) is determined along a straight line in the distance evaluation module and this distance along the straight line forms the basis for the travel cost estimation.

25. The routing method according to claim 1, in which the A-Star-Algorithm is used for estimating the travel costs in the distance evaluation module.