Live traffic routing

• US 10,018,476 B2
• Filed: 08/17/2016
• Issued: 07/10/2018
• Est. Priority Date: 08/17/2016
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Delling, Daniel, Maitra, Supratik, Schieferdecker, Dennis, Sommer, Christian
• Primary Examiner(s): BUTLER, RODNEY ALLEN
• Application Number:
  US15/239,678
• Publication Number:
  US 20180052002A1
• Time in Patent Office: 692 Days
• 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/096838 where the user preferences are taken into account or the user selects one route out of a plurality
• CPC Class Codes: G08G 1/096844 where the complete route is dynamically recomputed based on new data
• CPC Class Codes: G08G 1/096877 where the input to the navigation device is provided by a suitable I/O arrangement details of I/O arrangements for onboard navigation computers G01C21/36; I/O arrangements for general purpose computers G06F3/00

Abstract

Live traffic routing in a mobile navigation system generates alternate routes based on the user'"'"'s current location, live traffic conditions and estimated time of arrival at certain locations along the route. Live traffic routing re-ranks alternate routes taking into account which routes offer the best cost path to the user'"'"'s destination.

Claims

1. A computer-implemented method for generating a route in a location-based navigation application, the method comprising:

computing a plurality of alternate minimum cost routes between a source and a destination in a location-based navigation application based on static costs of traveling one or more segments of the alternate minimum cost routes without traffic;

computing dynamic costs of traveling the one or more segments of the alternate minimum cost routes with traffic; and

ranking the alternate minimum cost routes between the source and the destination based on a comparison of the dynamic costs of traveling the one or more segments with traffic to the static costs of traveling the one or more segments without traffic.

2. The method of claim 1, further comprising quantifying a local optimality of the one or more segments of the alternate minimum cost routes based on whether the dynamic costs of traveling the one or more segments exceeds a minimum acceptable traffic cost based on live traffic data.

3. The computer-implemented method as in claim 2, wherein quantifying the local optimality of the one or more segments of the alternate minimum cost routes includes:

breaking the alternate minimum cost route into the one or more segments;

determining, for each segment, whether the dynamic costs of traveling the segment exceeds the minimum acceptable traffic cost based on live traffic data;

adding a path restriction for each segment that exceeds the minimum acceptable traffic cost; and

accumulating a total number of path restrictions added for each of the alternate minimum cost routes.

4. The method of claim 3, wherein determining whether the dynamic costs of traveling the segment exceeds the minimum acceptable traffic cost based on live traffic data includes:

computing a difference between the dynamic costs of traveling the segment and the static costs of traveling the segment; and

determining whether the difference exceeds a threshold amount.

5. The method of claim 1, further comprising computing an amount of overlap between each of the alternate minimum cost routes, wherein ranking the alternate minimum cost routes includes determining which alternate minimum cost routes have a least amount of overlap with other alternate minimum cost routes.

6. The method of claim 1, further comprising computing an amount of overlap between a current route being followed in the location-based navigation application and each of the alternate minimum cost routes, wherein ranking the alternate minimum cost routes includes determining which alternate minimum cost routes have a least amount of overlap with the current route.

7. The computer-implemented method as in claim 1, wherein the costs of traveling the one or more segments include any one or more of travel time, tolls encountered, and penalties associated with a type of roadway, the type of roadway including any one or more of highways, restricted access roads, restricted speed roads, primary roads, bypasses, local roads, paved roads and unpaved roads.

8. A system for generating a route in a location-based navigation application, the system comprising:

a server operating a navigation service in communication with location-aware devices operating a location-based navigation application, the server having access to static and dynamic costs of travel, and further having a processor configured to;

compute a plurality of alternate minimum cost routes between a source and a destination in the location-based navigation application based on static costs of traveling one or more segments of the alternate minimum cost routes without traffic;

compute dynamic costs of traveling the one or more segments of the alternate minimum cost routes with traffic;

rank the alternate minimum cost routes between the source and the destination based on a comparison of the dynamic costs of traveling the one or more segments with traffic to the static costs of traveling the one or more segments without traffic; and

transmit the ranked alternate minimum cost routes to a location-aware device operating the location-based navigation application.

9. The system as in claim 8, the processor further configured to quantify a local optimality of the one or more segments of the alternate minimum cost routes based on whether the dynamic costs of traveling the one or more segments exceeds a minimum acceptable traffic cost based on live traffic data.

10. The system as in claim 9, wherein to quantify the local optimality of the one or more segments of the alternate minimum cost routes the processor is further configured to:

break the alternate minimum cost routes into the one or more segments;

determine, for each segment, whether the dynamic costs of traveling the segment exceeds the minimum acceptable traffic cost based on live traffic data;

add a path restriction for each segment that exceeds the minimum acceptable traffic cost; and

accumulate a total number of path restrictions added for each of the alternate minimum cost routes.

11. The system as in claim 10, wherein to determine whether the dynamic costs of traveling the segment exceeds the minimum acceptable traffic cost based on live traffic data the processor is further configured to:

compute a difference between the dynamic costs of traveling the segment and the static costs of traveling the segment; and

determine whether the difference exceeds a threshold amount.

12. The system as in claim 8, wherein the processor is further configured to compute an amount of overlap between each of the alternate minimum cost routes, and wherein the processor is further configured to determine which alternate minimum cost routes have a least amount of overlap with other alternate minimum cost routes.

13. The system as in claim 8, wherein the processor is further configured to compute an amount of overlap between the current route being followed in the location-based navigation application and each of the alternate minimum cost routes, and wherein the processor is further configured to determine which alternate minimum cost routes have a least amount of overlap with the current route.

14. The system as in claim 8, wherein the costs of traveling the one or more segments include any one or more of travel time, tolls encountered, and penalties associated with a type of roadway, the type of roadway including any one or more of highways, restricted access roads, restricted speed roads, primary roads, bypasses, local roads, paved roads and unpaved roads.

15. At least one computer-readable non-transitory storage medium including instructions that, when executed on a processor, cause the processor to:

compute a plurality of alternate minimum cost routes between a source and a destination in a location-based navigation application based on static costs of traveling one or more segments of the alternate minimum cost routes without traffic;

compute dynamic costs of traveling the one or more segments of the alternate minimum cost routes with traffic; and

rank the alternate minimum cost routes between the source and the destination based on a comparison of the dynamic costs of traveling the one or more segments with traffic to the static costs of traveling the one or more segments without traffic.

16. The at least one computer-readable medium of claim 15, the instructions further causing the processor to quantify a local optimality of the one or more segments of the alternate minimum cost routes based on whether the dynamic costs of traveling the one or more segments exceeds a minimum acceptable traffic cost based on live traffic data.

17. The at least one computer-readable medium of claim 16, wherein to quantify the local optimality of the one or more segments of the alternate minimum cost routes, the instructions further cause the processor to:

break the alternate minimum cost routes into the one or more segments;

determine, for each segment, whether a segment exceeds a minimum acceptable traffic cost based on live traffic data;

add a path restriction for each segment that exceeds the minimum acceptable traffic cost; and

accumulate a total number of path restrictions added for each of the alternate minimum cost routes.

18. The at least one computer-readable medium of claim 17, wherein to determine whether the dynamic costs of traveling the segment exceeds the minimum acceptable traffic cost based on live traffic data, the instructions further causing the processor to:

compute a difference between the dynamic costs of traveling the segment and the static costs of traveling the segment; and

determine whether the difference exceeds a threshold amount.

19. The at least one computer-readable medium of claim 15, the instructions further causing the processor to compute an amount of overlap between each of the alternate minimum cost routes, wherein ranking the alternate minimum cost routes includes determining which alternate minimum cost routes are associated with routes having a least amount of overlap with other alternate minimum cost routes.

20. The at least one computer-readable medium of claim 15, the instructions further causing the processor to compute an amount of overlap between a current route being followed in the location-based navigation application and each of the alternate minimum cost routes, wherein ranking the alternate minimum cost routes includes determining which alternate minimum cost routes have a least amount of overlap with the current route.

21. The at least one computer-readable medium of claim 15, wherein the costs of traveling the one or more segments include any one or more of travel time, tolls encountered, and penalties associated with a type of roadway, the type of roadway including any one or more of highways, restricted access roads, restricted speed roads, primary roads, bypasses, local roads, paved roads and unpaved roads.