Live Traffic Routing

Patent metadata

Field	Value
Publication number	US-2018052002-A1
Application number	US-201615239678-A
Country	US
Kind code	A1
Filing date	Aug 17, 2016
Priority date	Aug 17, 2016
Publication date	Feb 22, 2018
Grant date	—

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:
for routes between a source and a destination in a location-based navigation application, computing which routes qualify as alternate minimum cost routes based on static costs of travel; for via nodes associated with the alternate minimum cost routes, determining which via nodes are likely to provide best cost paths of travel based on dynamic costs of travel; and ranking each via node determined likely to provide best cost paths of travel in a best cost order characterized by their association with alternate minimum cost routes having any one or more of:
a least static cost, a least dynamic cost, a shortest distance, local optimality based on the dynamic costs of travel, and a least amount of overlap with other routes.

2 . The method of claim 1 , further comprising determining which alternate minimum cost routes have local optimality based on dynamic costs of travel, including quantifying a local optimality of one or more segments of the alternate minimum cost routes based on dynamic costs of travel.

3 . The computer-implemented method as in claim 2 , wherein quantifying the local optimality of one or more segments of the alternate minimum cost routes based on dynamic costs of travel includes:
breaking a route into the one or more segments based on any one or more of the static cost associated with a path followed by the route and intersections along the path; determining whether a segment exceeds a minimum acceptable traffic cost based on live traffic data; adding a path restriction for each segment of the route that exceeds the minimum acceptable traffic cost; and accumulating a total number of path restrictions added for the route.

4 . The method of claim 3 , wherein determining whether 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 the minimum acceptable traffic cost.

5 . The method of claim 1 , further comprising computing an amount of overlap between the via node's associated route and other alternate minimum cost routes, wherein determining which via nodes are likely to provide best cost paths of travel includes determining which via nodes are associated with routes having 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 the via node's associated route and a current route being followed in the location-based navigation application, wherein determining which via nodes are likely to provide best cost paths of travel based on dynamic costs of travel includes determining which via nodes are associated with routes having a least amount of overlap with the current route.

7 . The computer-implemented method as in claim 1 , wherein the costs upon which the best cost path order is based 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 which routes between a source and a destination in a location-based navigation application qualify as alternate minimum cost routes based on static costs of travel; determine which via nodes associated with the alternate minimum cost routes are likely to provide best cost paths of travel based on dynamic costs of travel; rank each via node determined likely to provide best cost paths of travel in a best cost order characterized by their association with alternate minimum cost routes having any one or more of:
a least static cost, a least dynamic cost, a shortest distance, local optimality based on the dynamic costs of travel, and a least amount of overlap with other routes; and
transmit the via nodes ranked in the best cost order to a location-aware device operating the location-based navigation application.

9 . The system as in claim 8 , the processor further configured to determine which alternate minimum cost routes have local optimality based on dynamic costs of travel, including to quantify a local optimality of one or more segments of the alternate minimum cost routes based on dynamic costs of travel.

10 . The system as in claim 2 , wherein to quantify the local optimality of one or more segments of the alternate minimum cost routes based on dynamic costs of travel the processor is further configured to:
break a route into the one or more segments based on any one or more of the static cost associated with a path followed by the route and intersections along the path; determine whether a segment exceeds a minimum acceptable traffic cost based on live traffic data; add a path restriction for each segment of the route that exceeds the minimum acceptable traffic cost; and accumulate a total number of path restrictions added for the route.

11 . The system as in claim 10 , wherein to determine whether 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 the minimum acceptable traffic cost.

12 . The system as in claim 8 , wherein the processor is further configured to compute an amount of overlap between the via node's associated route and other alternate minimum cost routes, and further wherein to determine which via nodes are likely to provide best cost paths of travel, the processor is further configured to determine which via nodes are associated with routes having 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 via node's associated route and a current route being followed in the location-based navigation application, wherein to determine which via nodes are likely to provide best cost paths of travel based on dynamic costs of travel, the processor is further configured to determine which via nodes are associated with routes having a least amount of overlap with the current route.

14 . The system as in claim 8 , wherein the costs upon which the best cost path order is based 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:
for routes between a source and a destination in a location-based navigation application, compute which routes qualify as alternate minimum cost routes based on static costs of travel; for via nodes associated with the alternate minim

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