Collective vehicle traffic routing

• US 10,429,201 B2
• Filed: 07/31/2017
• Issued: 10/01/2019
• Est. Priority Date: 04/09/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Barth, David M.
• Primary Examiner(s): Cheung, Calvin
• Application Number:
  US15/664,070
• Publication Number:
  US 20170363434A1
• Time in Patent Office: 792 Days
• 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/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: G01C 21/3655 Timing of guidance instructions
• CPC Class Codes: G01C 21/3658 Lane guidance
• CPC Class Codes: G01C 21/3667 Display of a road map G01C21/3614 takes precedence; guidance using 3D or perspective road maps G01C21/3635
• CPC Class Codes: G01C 21/3691 Retrieval, searching and output of information related to real-time traffic, weather, or environmental conditions arrangements for giving variable traffic instructions G08G1/09
• CPC Class Codes: G01C 21/3694 Output thereof on a road map
• CPC Class Codes: G01S 19/42 Determining position
• CPC Class Codes: G08G 1/0133 for classifying traffic situation

Abstract

A system and method provides a route and turn-by-turn directions based on estimates of current and future traffic along the route. A client device may request turn-by-turn directions between an initial and a final location. A server may identify a plurality of routes between the locations. Each route of the plurality of routes may be divided into route segments. For each route segment of a particular route, the server may estimate a travel time. The travel time may be based on estimated vehicle volume data generated from information received from other users vehicle Based on the estimated travel time for each route segment of a particular route, the server may estimate a total travel time for the particular route. The server may repeat this estimate for each of the plurality of routes between the locations and select the route with the lowest estimated travel time. Based on the selected route, the server may generate turn-by-turn directions and transmit the directions to the client device for display.

Claims

1. A computer-implemented method for providing directions, the method comprising:

receiving, by one or more computing devices, a request for turn-by-turn directions;

determining, by the one or more computing devices, at least one route associated with the turn-by-turn directions, wherein the at least one route is associated with a plurality of route segments;

estimating, by the one or more computing devices, a travel time for the route, wherein the travel time is based on vehicle data associated with a lane of at least one route segment, wherein the vehicle data comprises an estimated speed associated with the lane based, at least in part, on an estimated number of vehicles traveling on the lane;

generating, by the one or more computing devices, the turn-by-turn directions based on the travel time for the route, wherein the turn-by-turn directions include instructions indicating a fastest lane of travel along the route; and

transmitting, by the one or more computing devices to a first client device, the turn-by-turn directions.

2. The computer-implemented method of claim 1, wherein the vehicle data comprises estimates of a present volume of traffic and a future volume of traffic along the at least one route segment.

3. The computer-implemented method of claim 2, further comprising:

estimating, by the one or more computing devices, a time period during which the first client device will be located along the route; and

updating, by the one or more computing devices, the future volume of traffic based on the time period.

4. The computer-implemented method of claim 3, wherein the turn-by-turn directions comprise a map.

5. The computer-implemented method of claim 1, wherein the vehicle data is based on a plurality of requests for directions received from a plurality of second client devices.

6. The computer-implemented method of claim 1, wherein the client device is a portable device.

7. The computer-implemented method of claim 1, wherein the vehicle data comprises a capacity index indicative of a capacity of a route segment relative to other route segments.

8. The computer-implemented method of claim 7, wherein the capacity index correlates a traffic speed associated with a particular route segment with a number of vehicles on the particular route segment.

9. A computing device comprising:

memory for storing route segments, wherein each route segment is associated with vehicle volume data; and

one or more processors configured to;

receive, a request for turn-by-turn directions;

determine at least one route for the turn-by-turn directions, wherein the at least one route is associated with a plurality of route segments;

estimate a travel time for the route, wherein the travel time is based on vehicle data associated with a lane of at least one route segment, wherein the vehicle data comprises an estimated speed associated with the lane based, at least in part, on an estimated number of vehicles traveling on the lane;

generate the turn-by-turn directions based on the travel time for the route, wherein the turn-by-turn directions include instructions indicating a fastest lane of travel along the at least one route; and

transmit, to a first client device, the turn-by-turn directions.

10. The computing device of claim 9, wherein the vehicle data comprises estimates of a present volume of traffic and a future volume of traffic along the at least route segment.

11. The computing device of claim 9, wherein the processors are further configured to:

estimate a time period during which the first client device will be located along the at least one route; and

update the future volume of traffic based on the time period.

12. The computing device of claim 9, wherein turn-by-turn directions comprise a map.

13. The computing device of claim 9, wherein the vehicle data is based on a plurality of requests for directions received from a plurality of second client devices.

14. The computing device of claim 9, wherein the client device is a mobile phone.

15. A non-transitory computer-readable medium having instructions stored thereon for operating a vehicle routing system, the instructions, when executed by one or more computing devices, cause the one or more computing devices to perform a method comprising:

receiving, a request for turn-by-turn directions;

determining at least one route associated with the turn-by-turn directions, wherein the at least one route is associated with a plurality of route segments;

estimating a travel time for the route, wherein the travel time is based on vehicle data associated with a lane of at least one route segment, wherein the vehicle data comprises an estimated speed associated with the lane based, at least in part, on an estimated number of vehicles traveling on the lane;

generating the turn-by-turn directions based on the travel time for the at least one route, wherein the turn-by-turn directions include instructions indicating a fastest lane of travel along the at least one route; and

transmitting, to a first client device, the turn-by-turn directions.

16. The computing device of non-transitory computer-readable medium of claim 15, wherein the vehicle data comprises an estimated speed of the vehicles traveling in the lane.

17. The computing device of non-transitory computer-readable medium of claim 15, wherein the vehicle data comprises estimates of a present volume of traffic and a future volume of traffic along the at least route segment.

18. The computing device of non-transitory computer-readable medium of claim 15, wherein the processors are further configured to:

estimating a time period during which the first client device will be located along the at least one route; and

updating the future volume of traffic based on the time period.

19. The computing device of non-transitory computer-readable medium of claim 15, wherein the turn-by-turn directions comprise a map.

20. The computing device of non-transitory computer-readable medium of claim 15, wherein the vehicle data is based on a plurality of requests for directions received from a plurality of second client devices.