Live traffic routing

Patent metadata

Field	Value
Publication number	US-10018476-B2
Application number	US-201615239678-A
Country	US
Kind code	B2
Filing date	Aug 17, 2016
Priority date	Aug 17, 2016
Publication date	Jul 10, 2018
Grant date	Jul 10, 2018

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.

First claim

What is claimed is:

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

Assignees

• Apple Inc

Inventors

• Delling Daniel
• Maitra Supratik
• SCHIEFERDECKER Dennis
• Sommer Christian

Classifications

• G01C21/3492 Primary

  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 title

• G08G1/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) · CPC title

• G08G1/096838

  where the user preferences are taken into account or the user selects one route out of a plurality · CPC title

• G08G1/096844

  where the complete route is dynamically recomputed based on new data · CPC title

• G08G1/096816

  where the complete route is transmitted to the vehicle at once · CPC title