Collective vehicle traffic routing

• US 8,972,171 B1
• Filed: 04/09/2010
• Issued: 03/03/2015
• Est. Priority Date: 04/09/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Barth, David
• Primary Examiner(s): Cheung, Calvin
• Assistant Examiner(s): Jos, Basil T
• Application Number:
  US12/757,178
• Time in Patent Office: 1,789 Days
• Field of Search: 701/201, 701/117, 701/123, 701/200, 701/414, 701/423, 340/995.13
• US Class Current: 701/414
• 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

Systems and methods provide 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 vehicles. 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 method of providing turn-by-turn directions to a first client device on a network, the method comprising:

receiving, from the first client device, a request for turn-by-turn directions including an initial location and a final location;

determining, by a server device, a first plurality of routes between the initial location and the final location, wherein each of the first plurality of routes is associated with a first plurality of route segments;

receiving, by the server device, a second request for turn-by-turn directions from a second client device;

selecting a second route based on the second request, wherein the second route is associated with a second plurality of route segments;

estimating a plurality of time periods during which the second client device will be located along the second plurality of route segments;

estimating for the first client device a travel time for each of the first plurality of route segments,

wherein the estimated travel time for a particular route segment from the first plurality of route segments is based on vehicle volume data associated with the particular route segment that includes;

estimates of the present volume of traffic along the particular route segment, and

future volume of traffic along the particular route segment at a time at which the first client device is estimated to be located along the particular route segment,

wherein the vehicle volume data is updated based on the plurality of time periods during which the second client device will be located along the second plurality of route segments;

selecting a shortest route of the first plurality of routes based on estimated total times of travel for the first plurality of routes based on the estimated travel times for the first plurality of route segments;

generating turn-by-turn directions based on the selected shortest route; and

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

2. The method of claim 1, wherein the vehicle volume data includes estimates of the present volume of traffic and future volume of traffic along the associated route segment for each of a plurality of time periods.

3. The method of claim 1, wherein the vehicle volume data further includes an optimum capacity for the associated route segment.

4. The method of claim 1, wherein the vehicle volume data further includes estimates of the present volume of traffic and future volume of traffic along a particular lane of the associated route segment.

5. The method of claim 1, wherein the client device is a portable computer.

6. The method of claim 1, wherein the client device is a mobile phone.

7. The method of claim 1, wherein the vehicle volume data is updated based on travel information associated with a plurality of second client devices, the travel information including a current location, destination, and route to a destination for each of the plurality of second client devices.

8. The method of claim 7, further comprising identifying the travel information based on requests received from each of the plurality of second client devices.

9. The method of claim 7, further comprising automatically receiving the travel information from each of the plurality of second client devices independent of a request for turn-by-turn directions from each of the plurality of second client devices.

10. The method of claim 1, wherein the vehicle volume data is based on a plurality of requests for turn-by-turn directions received from a plurality of second client devices.

11. The method of claim 1, wherein the future volume of traffic along the particular route segment is estimated based on an estimated arrival of a second client device at the particular route segment at a future time period.

12. The method of claim 11, wherein the future time period begins when a sum of the estimated travel time for each of the first plurality of route segments before the particular route segment elapses from a present time.

13. The method of claim 12, wherein the request is received at the present time.

14. A server device comprising:

memory for storing route segments, wherein each route segment is associated with vehicle volume data, and wherein the vehicle volume data including estimates of the present volume of traffic and future volume of traffic along the associated route segment; and

a processor configured to;

receive, from a first client device, a request for turn-by-turn directions including an initial location and a final location;

determine a first plurality of routes between the initial location and the final location, wherein each of the first plurality of routes is associated with a first plurality of route segments of the stored route segments;

receive, from a second client device, a second request for turn-by-turn directions;

select a second route based on the second request, wherein the second route is associated with a second plurality of route segments;

estimate a plurality of time periods during which the second client device will be located along the second plurality of route segments;

estimate for the first client device a travel time for each of the first plurality of route segments,

wherein the estimated travel time for a particular route segment from the first plurality of route segments is based on the vehicle volume data associated with the particular route segment that includes;

estimates of the present volume of traffic along the particular route segment, and

future volume of traffic along the particular route segment at a time at which the first client device is estimated to be located along the particular route segment,

wherein the vehicle volume data is updated based on the plurality of time periods during which the second client device will be located along the second plurality of route segments;

select a shortest route of the first plurality of routes based on estimated total times of travel for the first plurality of routes based on the estimated travel times for the first plurality of route segments; and

estimate a time period during which the first client device will be located along each of the first plurality of route segments of the selected route; and

update the vehicle volume data based on the time period.

15. The server device of claim 14, wherein the processor is further configured to:

generate turn-by-turn directions based on the selected shortest route; and

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

16. The server device of claim 14, wherein the vehicle volume data includes estimates of the present volume of traffic and future volume of traffic along the associated route segment for each of a plurality of time periods.

17. The server device of claim 14, wherein the vehicle volume data further includes estimates of the present volume of traffic and future volume of traffic along a particular lane of the associated route segment.

18. The server device of claim 14, wherein the vehicle volume data is based on a plurality of requests for turn-by-turn directions received from a plurality of second client devices.

19. A non-transitory computer-readable medium having instructions stored thereon for operating a vehicle routing system, the instructions, when executed by a processor, cause the processor to perform a method comprising:

receiving, from a first client device, a request for turn-by-turn directions including an initial location and a final location;

determining, by a server device, a first plurality of routes between the initial location and the final location, wherein each of the first plurality of routes is associated with a first plurality of route segments;

receiving, by the server device, a second request for turn-by-turn directions from a second client device;

selecting a second route based on the second request, wherein the second route is associated with a second plurality of route segments;

estimating a plurality of time periods during which the second client device will be located along the second plurality of route segments;

estimating for the first client device a travel time for each of the first plurality of route segments,

wherein the estimated travel time for a particular route segment from the first plurality of route segments is based on vehicle volume data associated with the particular route segment that includes;

estimates of the present volume of traffic along the particular route segment, and

future volume of traffic along the particular route segment at a time at which the first client device is estimated to be located along the particular route segment,

wherein the vehicle volume data is updated based on the plurality of time periods during which the second client device will be located along the second plurality of route segments;

selecting a shortest route of the first plurality of routes based on estimated total times of travel for the first plurality of routes based on the estimated travel times for the first plurality of route segments;

generating turn-by-turn directions based on the selected shortest route; and

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

20. The non-transitory computer-readable medium of claim 19, wherein the vehicle volume data includes estimates of the present volume of traffic and future volume of traffic along the associated route segment for each of a plurality of time periods.

21. The non-transitory computer-readable medium of claim 19, wherein the vehicle volume data further includes an optimum capacity for the associated route segment.