System and method of generating a route across an electronic map

• US 9,506,764 B2
• Filed: 10/22/2012
• Issued: 11/29/2016
• Est. Priority Date: 04/21/2010
• Status: Active Grant

• Current Assignee: TomTom Navigation B.V (TomTom NV)
• Original Assignee: TomTom Navigation B.V (TomTom NV)
• Inventors: Serbanescu, Alexandru, Schilling, Heiko, Gawrilow, Ewgenij, Hilger, Moritz, Profous, Andreas, Werber, Jrgen
• Primary Examiner(s): Do, Truc M
• Application Number:
  US13/656,894
• Publication Number:
  US 20130046465A1
• Time in Patent Office: 1,499 Days
• Field of Search: 701/117, 701/118, 701/413, 701/414, 701/423, 701/489
• US Class Current: 1/1
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G08G 1/096827 where the route is computed onboard

Abstract

A computerized method of generating a route 1000 from an origin position F1 to a destination position 706 across an electronic map 700 comprising a plurality of vectors representing segments of a navigable route in the area covered by the electronic map 700, the method comprising: (1) obtaining delay data indicating delays on vectors within the area covered by the electronic map 700; (2) calculating a first portion 1002 of a route from origin position toward the destination position 706 using a first routing method up to a predetermined threshold 1006 from the origin position F1, such that the first routing method uses the delay data so that the first portion 1002 of the route takes into account delays; and (3) calculating a second portion 1004 of the route beyond the predetermined threshold 1006 to the destination position 706 using a second routing method to further calculate the route to the destination position 1006.

Claims

1. A computerised method of generating a route from an origin position to a destination position across an electronic map comprising a plurality of vectors representing segments of a navigable route in an area covered by the electronic map, the method comprising:

obtaining delay data indicating delays on vectors within an area covered by the electronic map;

calculating a first portion of a route, from an origin position toward the destination position, using a first routing method up to a predetermined threshold from the origin position, such that the first routing method uses the delay data so that the first portion of the route takes into account delays;

calculating a second portion of the route beyond the predetermined threshold to the destination position using a second routing method to further calculate the route to the destination position, wherein the second routing method uses routing acceleration data which indicates vectors within the electronic map which form part of a lowest cost route according to a predetermined cost function; and

providing instructions to navigate the route based on the calculated first and second portions of the route.

2. The method according to claim 1 wherein the second routing method does not use delay data.

3. The method according to claim 1 comprising setting the predetermined threshold up to which delay data is considered at the distance that can be traveled within a predetermined driving time.

4. The method according to claim 1 comprising using a predetermined shape to determine the area in which the delay data is obtained.

5. The method according to claim 4 wherein the predetermined shape is an ellipse, and wherein the origin position is at a first focus of the ellipse.

6. The method according to claim 5 comprising arranging the dimensions of the ellipse such that the distance from the first focus, through the second focus, to the boundary of the ellipse is equal in distance to the distance that a vehicle could travel within a predetermined driving time.

7. The method according to claim 4 comprising subsequently fitting a shape that can be tessellated around the predetermined shape.

8. The method according to claim 7 wherein the shape that can be tessellated is a rectangle.

9. The method according to claim 7 comprising forming a shape around areas covered by delays, and subsequently determining whether the shape around a delay intersects the shape formed around the predetermined shape, and utilising delay data relating to any incident in which an intersection occurs.

10. The method according to claim 1 wherein an A * method is used as the first routing method.

11. The method according to claim 1 comprising recalculating the route if parameters used to generate the original route should change.

18. A non-transitory machine readable medium containing instructions which when read onto at least one machine cause that machine to perform the method according to claim 1.

12. A navigation device which is arranged to generate a route from an origin position to a destination position across an electronic map accessible thereby and comprising a plurality of vectors representing segments of a navigable route in an area covered by the electronic map wherein the device is arranged to:

obtain delay data indicating delays on vectors within an area covered by the electronic map;

calculate a first portion of a route from the origin position toward the destination position using a first routing method up to a predetermined threshold from the origin position wherein the first routing method uses the delay data so that the first portion of the route takes into account delays identified by the delay data; and

calculate a second portion of the route beyond the predetermined threshold to the destination position using a second routing method to further calculate the route to the destination position, wherein the second routing method uses routing acceleration data which indicates vectors within the electronic map which form part of a lowest cost route according to a predetermined cost function.

13. A navigation device according to claim 12 which is a Portable Navigation Device (PND).

14. A navigation device according to claim 12 in which the second routing method does not use delay data, wherein the method may set the predetermined threshold up to which delay data is considered at the distance that can be traveled within a predetermined driving time.

15. The navigation device according to claim 12 wherein the second routing method does not use delay data.

16. The navigation device according to claim 12 wherein the device is arranged to set the predetermined threshold up to which delay data is considered at the distance that can be traveled within a predetermined driving time.

17. A system arranged to generate a route from an origin position to a destination position across an electronic map comprising a plurality of vectors representing segments of a navigable route in the area covered by the electronic map, wherein the system comprises:

at least one server arranged to generate delay data indicating delays on vectors within the area covered by the electronic map; and

at least one navigation device according to claim 12 arranged to receive the delay data for an area covered by the map.

19. The navigation device of claim 12 wherein each of the of vectors is a bit vector.

20. The navigation device of claim 12 wherein each of the plurality of vectors is pre-processed.

21. The navigation device of claim 12 wherein the area covered by the electronic map is divided into a plurality of regions and the routing acceleration data indicates vectors within each region whether the vector forms part of a lowest cost route to any other regions.