Transportation routing

• US 9,778,055 B2
• Filed: 01/31/2017
• Issued: 10/03/2017
• Est. Priority Date: 12/31/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Rowley, Henry, Baluja, Shumeet
• Primary Examiner(s): To, Tuan C.
• Application Number:
  US15/420,331
• Publication Number:
  US 20170138754A1
• Time in Patent Office: 245 Days
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles
• 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/3605 Destination input or retrieval
• CPC Class Codes: G01C 21/3617 using user history, behaviour, conditions or preferences, e.g. predicted or inferred from previous use or current movement
• CPC Class Codes: G06Q 30/0261 based on user location
• CPC Class Codes: G06Q 30/0267 Wireless devices
• CPC Class Codes: G06Q 30/0269 based on user profile or attribute
• CPC Class Codes: G08G 1/096811 where the route is computed offboard
• 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/096883 where input information is obtained using a mobile device, e.g. a mobile phone, a PDA
• CPC Class Codes: G08G 1/096888 where input information is obtained using learning systems, e.g. history databases

Abstract

A computer-implemented method of providing personalized route information involves gathering a plurality of past location indicators over time for a wireless client device, determining a future driving objective using the plurality of previously-gathered location indicators, obtaining real-time traffic data for an area proximate to the determined driving objective, and generating a suggested route for the driving objective using the near real-time traffic data.

Claims

1. A computer-implemented method to perform predictive routing, the method comprising:

collecting, by one or more computing devices, travel route data descriptive of a plurality of travel routes taken by a user over time;

identifying, by the one or more computing devices, a plurality of trip patterns based at least in part on the travel route data, wherein identifying, by the one or more computing devices, the plurality of trip patterns based at least in part on the travel route data comprises correlating, by the one or more computing devices, the plurality of travel routes with a time of day;

determining, by the one or more computing devices, a predicted trip for the user based at least in part on the plurality of trip patterns and based at least in part on a current time of day or a current day of the week, wherein determining, by the one or more computing devices, the predicted trip for the user based at least in part on the plurality of trip patterns and based at least in part on a current time of day or a current day of the week comprises;

determining, by the one or more computing devices, the current time of day; and

identifying, by the one or more computing devices, at least one of the plurality of trip patterns that is correlated with the current time of day as the predicted trip for the user; and

providing, by the one or more computing devices, a suggested route associated with the predicted trip.

2. The computer-implemented method of claim 1, wherein providing, by the one or more computing devices, the suggested route associated with the predicted trip comprises:

identifying, by the one or more computing devices, a typical route associated with the predicted trip;

accessing, by the one or more computing devices, real-time traffic information associated with the typical route;

automatically detecting, by the one or more computing devices, that an alternative route to the typical route should be suggested based at least in part on the real-time traffic information associated with the typical route; and

providing, by the one or more computing devices, the alternative route as the suggested route.

3. The computer-implemented method of claim 1, wherein:

identifying, by the one or more computing devices, the plurality of trip patterns based at least in part on the travel route data comprises correlating, by the one or more computing devices, the plurality of travel routes with a day of the week; and

determining, by the one or more computing devices, the predicted trip for the user based at least in part on the plurality of trip patterns and based at least in part on a current time of day or a current day of the week comprises;

determining, by the one or more computing devices, the current day of the week; and

identifying, by the one or more computing devices, at least one of the plurality of trip patterns that is correlated with the current day of the week as the predicted trip for the user.

4. The computer-implemented method of claim 1, wherein:

identifying, by the one or more computing devices, the plurality of trip patterns based at least in part on the travel route data comprises;

identifying, by the one or more computing devices, a plurality of frequent start locations based at least in part on the travel route data;

associating, by the one or more computing devices, each of the plurality of frequent start locations with at least one of a time of day and a day of the week; and

determining, by the one or more computing devices, the predicted trip for the user based at least in part on the plurality of trip patterns and based at least in part on a current time of day or a current day of the week comprises;

determining, by the one or more computing devices, the current time of day or the current day of the week; and

identifying, by the one or more computing devices as the predicted trip for the user, at least one of the plurality of frequent start locations that is associated with the current time of day or the current day of the week.

5. The computer-implemented method of claim 1, wherein:

identifying, by the one or more computing devices, the plurality of trip patterns based at least in part on the travel route data comprises;

identifying, by the one or more computing devices, a plurality of frequent end locations based at least in part on the travel route data;

associating, by the one or more computing devices, each of the plurality of frequent end locations with at least one of a time of day and a day of the week; and

determining, by the one or more computing devices, the predicted trip for the user based at least in part on the plurality of trip patterns and based at least in part on a current time of day or a current day of the week comprises;

determining, by the one or more computing devices, the current time of day or the current day of the week; and

identifying, by the one or more computing devices as the predicted trip for the user, at least one of the plurality of frequent end locations that is associated with the current time of day or the current day of the week.

6. The computer-implemented method of claim 1, wherein identifying, by the one or more computing devices, the plurality of trip patterns based at least in part on the travel route data comprises:

identifying, by the one or more computing devices, a plurality of navigation points through which the user is likely to pass based at least in part on the travel route data; and

associating, by the one or more computing devices, each of the plurality of navigation points with at least one of a time of day and a day of the week.

7. The computer-implemented method of claim 1, further comprising:

detecting, by the one or more computing devices, a change in at least one of the plurality of trip patterns based on newly collected travel route data; and

updating, by the one or more computing devices, the at least one of the plurality of trip patterns to reflect the newly collected travel route data.

8. A computer system to perform predictive routing, the computer system comprising:

at least one processor; and

at least one tangible, non-transitory computer-readable medium that stores instructions that, when executed by the at least one processor, cause the computer system to perform operations, the operations comprising;

collecting travel route data descriptive of a plurality of travel routes taken by a user over time;

identifying a plurality of trip patterns based at least in part on the travel route data, wherein identifying the plurality of trip patterns based at least in part on the travel route data comprises correlating the plurality of travel routes with a time of day;

determining a predicted trip for the user based at least in part on the plurality of trip patterns and based at least in part on a current time of day or a current day of the week, wherein determining the predicted trip for the user based at least in part on the plurality of trip patterns and based at least in part on a current time of day or a current day of the week comprises;

determining the current time of day; and

identifying at least one of the plurality of trio patterns that is correlated with the current time of day as the predicted trip for the user; and

providing a suggested route associated with the predicted trip.

9. The computer system of claim 8, wherein providing the suggested route associated with the predicted trip comprises:

identifying a typical route associated with the predicted trip;

accessing real-time traffic information associated with the typical route;

automatically detecting that an alternative route to the typical route should be suggested based at least in part on the real-time traffic information associated with the typical route; and

providing the alternative route as the suggested route.

10. The computer system of claim 8, wherein:

identifying the plurality of trip patterns based at least in part on the travel route data comprises correlating the plurality of travel routes with a time of day; and

determining the predicted trip for the user based at least in part on the plurality of trip patterns and based at least in part on a current time of day or a current day of the week comprises;

determining the current time of day; and

identifying at least one of the plurality of trip patterns that is correlated with the current time of day as the predicted trip for the user.

11. The computer system of claim 8, wherein:

identifying the plurality of trip patterns based at least in part on the travel route data comprises;

identifying a plurality of frequent start locations based at least in part on the travel route data;

associating each of the plurality of frequent start locations with at least one of a time of day and a day of the week; and

determining the predicted trip for the user based at least in part on the plurality of trip patterns and based at least in part on a current time of day or a current day of the week comprises;

determining the current time of day or the current day of the week; and

identifying at least one of the plurality of frequent start locations that is associated with the current time of day or the current day of the week as the predicted trip for the user.

12. The computer system of claim 8, wherein:

identifying the plurality of trip patterns based at least in part on the travel route data comprises;

identifying a plurality of frequent end locations based at least in part on the travel route data;

associating each of the plurality of frequent end locations with at least one of a time of day and a day of the week; and

determining the predicted trip for the user based at least in part on the plurality of trip patterns and based at least in part on a current time of day or a current day of the week comprises;

determining the current time of day or the current day of the week; and

identifying at least one of the plurality of frequent end locations that is associated with the current time of day or the current day of the week as the predicted trip for the user.

13. The computer system of claim 8, wherein identifying the plurality of trip patterns based at least in part on the travel route data comprises identifying a plurality of navigation points through which the user is likely to pass based at least in part on the travel route data.

14. The computer system of claim 8, wherein the operations further comprise:

detecting a change in at least one of the plurality of trip patterns based on newly collected travel route data; and

updating the at least one of the plurality of trip patterns to reflect the newly collected travel route data.

15. At least one tangible, non-transitory computer-readable medium that stores instructions that when executed by at least one processor, cause the at least one processor to perform operations, the operations comprising:

gathering travel route data descriptive of a plurality of travel routes taken by a user over time;

correlating the travel route data to a plurality of events;

correlating each of the plurality of events to at least one of a time of day and a day of the week;

determining a predicted trip for the user based at least in part on the plurality of events and based at least in part on a current time of day or a current day of the week; and

providing a suggested route associated with the predicted trip for display to or selection by the user.

16. The at least one tangible, non-transitory computer-readable medium of claim 15, wherein providing the suggested route associated with the predicted trip comprises:

identifying a typical route associated with the predicted trip;

accessing real-time traffic information associated with the typical route;

automatically detecting that an alternative route to the typical route should be suggested based at least in part on the real-time traffic information associated with the typical route; and

providing the alternative route as the suggested route.

17. The at least one tangible, non-transitory computer-readable medium of claim 15, wherein determining the predicted trip for the user based at least in part on the plurality of events and based at least in part on a current time of day or a current day of the week comprises:

determining the current time of day; and

identifying at least one of the plurality of events that is correlated with the current time of day; and

identifying a predicted trip associated with the identified event.

18. The at least one tangible, non-transitory computer-readable medium of claim 15, wherein determining the predicted trip for the user based at least in part on the plurality of events and based at least in part on a current time of day or a current day of the week comprises:

determining the current day of the week;

identifying at least one of the plurality of events that is correlated with the current day of the week; and

identifying a predicted trip associated with the identified event.