Generating alternative routes

• US 9,459,106 B2
• Filed: 06/28/2013
• Issued: 10/04/2016
• Est. Priority Date: 06/29/2012
• Status: Active Grant

• Current Assignee: TomTom Navigation B.V (TomTom NV)
• Original Assignee: TomTom Development Germany GmbH (TomTom NV)
• Inventors: Knig, Felix Godafoss
• Primary Examiner(s): FREJD, RUSSELL WARREN
• Application Number:
  US14/411,625
• Publication Number:
  US 20150160025A1
• Time in Patent Office: 1,194 Days
• US Class Current: 1/1
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G08G 1/096816 where the complete route is transmitted to the vehicle at once
• CPC Class Codes: G08G 1/096822 where the segments of the route are transmitted to the vehicle at different locations and times
• CPC Class Codes: G08G 1/096827 where the route is computed onboard
• CPC Class Codes: G08G 1/096833 where different aspects are considered when computing the route
• CPC Class Codes: G08G 1/096844 where the complete route is dynamically recomputed based on new data

Abstract

A method of generating routes in an area covered by an electronic map is described. The map comprises a plurality of segments representing navigable segments in the area covered by the electronic map, each segment being associated with jam probability data representative of a likelihood of a jam on the segment. The method involves generating a first route between an origin and a destination in the area, and generating at least one alternative route between the origin and destination using the jam probability data associated with the segments in the area. In embodiments jam and non-jam travel time data is used with the jam probability for a segment to obtain a measure of reliability of the segment under given traffic conditions, which is used to generate the alternate route(s).

Claims

1. A method of generating a route in an area covered by an electronic map, the map comprising a plurality of segments representing navigable segments in the area covered by the electronic map, each segment being associated with jam probability data representative of a likelihood of a jam on the segment, the method comprising:

exploring routes between an origin and a destination in the area to determine a minimum cost route, wherein the cost of each of a plurality of segments is determined using a cost function such that the cost for a segment is based at least on a reliability measure indicative of an expected reliability of the segment under a theoretical traffic condition, said reliability measure being obtained using the jam probability data associated with the segment, and wherein the theoretical traffic condition is selected from a plurality of predefined traffic severity levels; and

outputting said determined minimum cost route as the route between the origin and the destination.

2. The method of claim 1, wherein the jam probability data associated with a segment is in respect of a given time period, optionally wherein each segment is associated with data indicative of a plurality of jam probabilities, each being in respect of a different given time period.

3. The method of claim 1, where each segment of the electronic map is further associated with:

jam travel time data representative of the time to traverse that segment when it is considered jammed; and

non-jam travel time data representative of the time to traverse that segment when it is not considered jammed, and wherein the reliability measure is further obtained using the jam travel time data and the non-jam travel time data, such that said reliability measure is representative of an expected time to traverse the segment under the theoretical traffic condition.

4. The method of claim 3, wherein the jam travel time data and non-jam travel time data is in respect of a given time period, optionally wherein each segment is associated with data indicative of a plurality of jam travel times and data indicative of a plurality of non-jam travel times, each of the plurality of jam travel times and the plurality of non-jam travel times being in respect of a different given time period.

5. The method of claim 1, wherein the reliability measure for a segment is further obtained based on the likelihood of a jam on the segment relative to the likelihood of a jam on other segments in the area.

6. The method of claim 1, wherein the theoretical traffic condition is specified by a user.

7. The method of claim 1, further comprising obtaining a plurality of reliability measures for each of the plurality of segments, wherein each reliability measure is indicative of an expected reliability of the segment under a different theoretical traffic condition, and generating a route between the origin and the destination for a set of traffic conditions using reliability measures for different segments determined with respect to different theoretical traffic conditions.

8. The method of claim 1, further comprising obtaining a plurality of reliability measures for each of the plurality of segments, wherein each of the plurality of reliability measures is indicative of an expected reliability of the segment under a different theoretical traffic condition, and generating a plurality of routes between the origin and the destination, wherein each of the plurality of routes is generated using a different one of the plurality of reliability measures for the plurality of segments.

9. The method of claim 1, further comprising displaying the generated route to a user.

10. The method of claim 1, further comprising providing a set of navigation instructions for guiding a user along the generated route.

11. The method of claim 1, wherein the generated route between the origin and the destination is an alternative route to a first route between a first route origin and a first route destination in the area, said method further including generating the first route, and wherein the origin of the alternative route is the first route origin or a location on the first route, and the destination of the alternative route is the first route destination or a location on the first route.

12. A non-transitory computer readable medium comprising computer readable instructions which, when executed by a computer, cause the computer to perform the method of claim 1.

13. A system for generating a route in an area covered by an electronic map, the map comprising a plurality of segments representing navigable segments in the area covered by the electronic map, each segment being associated with jam probability data representative of a likelihood of a jam on the segment, the system comprising:

one or more processors operable to;

explore routes between an origin and a destination in the area to determine a minimum cost route, wherein the cost of each of a plurality of segments is determined using a cost function such that the cost for a segment is based at least on a reliability measure indicative of an expected reliability of the segment under a theoretical traffic condition, said reliability measure being obtained using the jam probability data associated with the segment, and wherein the theoretical traffic condition is selected from a plurality of predefined traffic severity levels; and

output said determined minimum cost route as the route between the origin and the destination.

14. The system of claim 13, where each segment of the electronic map is further associated with:

jam travel time data representative of the time to traverse that segment when it is considered jammed; and

non-jam travel time data representative of the time to traverse that segment when it is not considered jammed, and wherein the reliability measure is further obtained using the jam travel time data and the non-jam travel time data.

15. The system of claim 13, wherein the system is a portable navigation device or a server.