Transportation routing

• US 7,908,080 B2
• Filed: 12/31/2004
• Issued: 03/15/2011
• 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): Hellner; Mark
• Assistant Examiner(s): Diacou; Ari M
• Application Number:
  US11/027,769
• Publication Number:
  US 20060149461A1
• Time in Patent Office: 2,265 Days
• Field of Search: 701/209, 340/995.13
• US Class Current: 701/209
• 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 of providing personalized route information, comprising:

obtaining a plurality of past location indicators over time for a wireless client device;

determining a future travel objective from a starting point to a destination for a user of the device using the plurality of previously-gathered location indicators with determining the future travel objective including identifying the starting point and the destination based on long periods of immobility connected by one or more periods of mobility;

obtaining, at a server system remote from the wireless client device, near real-time traffic data for an area proximate to the determined travel objective;

determining estimated total trip times for a plurality of routes from the determined starting point to the determined destination, the estimated total trip times being based at least in part on the near real-time traffic data;

generating at the server system a suggested route for the travel objective using the traffic data based on the determined estimated total trip times; and

providing from the server system to the wireless client device map data formatted to generate a map showing the suggested route on the wireless client device.

2. The method of claim 1, wherein determining the future travel objective further comprises determining one or more stop points for a user of the device using the plurality of previously-gathered location indicators.

3. The method of claim 2, wherein determining the one or more stop points comprises identifying the one or more stop points based on shorter periods of immobility.

4. The method of claim 1, further comprising determining estimated time deviations from the estimated total trip times.

5. The method of claim 4, wherein generating the suggested route further comprises generating the suggested route based on the determined estimated total trip times and the determined estimated time deviations.

6. The method of claim 1, further comprising receiving from a user an indication of an intent to have the client device enter a learn mode, and to gather location indicators only during the learn mode.

7. The method of claim 1, wherein the map data is provided at a predetermined time of day.

8. The method of claim 1, further comprising transmitting information indicative of real-time traffic data to the wireless device.

9. The method of claim 1, further comprising identifying one or more advertisements targeted to locations on the map and providing indicators for the advertisements with the map data, wherein the advertisements are targeted based on a profile of the user.

10. The method of claim 9, wherein the advertisements are further targeted to information in a profile for a user of the wireless client device.

11. The method of claim 9, further comprising charging a business for a location associated with one of the advertisements if a user of the wireless client device interacts with the advertisement.

12. The method of claim 1, wherein each location indicator is gathered as the result of a cell-tower hand-off for the device.

13. The method of claim 1, wherein the location indicators are grouped according to multiple different time periods.

14. The method of claim 1, further comprising generating an updated suggested route based on updated real-time traffic data and position information from the device.

15. The method of claim 1, further comprising a calendar for a user of the wireless client device and generating the suggested route based on a future entry in the calendar.

16. The method of claim 1, further comprising receiving navigation points manually entered by a user of the wireless client device between endpoints of a route, and requiring that the suggested route pass through the navigation points.

17. A computer-implemented navigation system, comprising:

a location generator for a mobile computing device that produces data indicative of a plurality of computing device locations;

a navigation point generator at a server system remote from the computing device that analyzes the data indicative of a plurality of device locations and determines a travel objective from a start to a destination for a user of the device by identifying the starting point and the destination based on long periods of immobility connected by one or more periods of mobility;

a route generator at the server system that;

receives information indicative of near real-time traffic data near the one or more expected navigation points,

determines estimated total trip times for a plurality of routes from the determined starting point to the determined destination, the estimated total trip times being based at least in part on the near real-time traffic data; and

generates data for one or more optimized routes for the travel objective based on the determined estimated total trip times; and

a response formatter at the server system to generate a document for transmission to the computing device, wherein the document includes a map showing the one or more optimized routes.

18. The computer-implemented navigation system of claim 17, wherein the document further includes one or more advertisements targeted to locations on the map.

19. The computer-implemented navigation system of claim 18, further comprising a billing unit to charge a business for a location associated with one of the advertisements if a user of the mobile device interacts with the advertisement.

20. The computer-implemented navigation system of claim 17, wherein the route generator determines estimated time deviations from the estimated total trip times for at least some of the plurality of routes.

21. The computer-implemented navigation system of claim 20, wherein the route generator generates the data for the one or more optimized routes based on the determined estimated total trip times and the determined estimated time deviations.

22. The computer-implemented navigation system of claim 17, wherein the information indicative of traffic data includes real-time traffic data.

23. A computer-implemented navigation system having memory for storing instructions that, when executed:

obtain a plurality of past location indicators over time for a wireless client device;

determine a future travel objective determining a future travel objective from a starting point to a destination for a user of the device using the plurality of previously-gathered location indicators by identifying the starting point and the destination based on long periods of immobility connected by one or more periods of mobility;

obtain, at a server system remote from the wireless client device, near real-time traffic data for an area proximate to the determined travel objective;

determine estimated total trip times for a plurality of routes from the determined starting point to the determined destination, the estimated total trip times being based at least in part on the near real-time traffic data;

for at least some of the plurality of routes, determine estimated time deviations from the estimated total trip times

generate at the server system a suggested route having a reduced travel time for the travel objective using the traffic data based on the determined estimated total trip times and the determined estimated time deviations; and

provide from the server system to the wireless client device map data formatted to generate a map showing the suggested route on the wireless client device.

24. The computer-implemented navigation system of claim 23 further having memory storing instructions that, when executed, generate a location information for use in computing expected navigation points for the device based on past locations for the device.

25. The computer-implemented navigation system of claim 24, wherein the expected navigation points are computed for a time period corresponding to a time period for the past locations for the device.

26. The computer-implemented navigation system of claim 23, wherein the obtaining of information showing a suggested navigation route occurs at a predetermined time of the day.

27. A computer-implemented navigation system, comprising:

a location generator for a moving vehicle that produces data indicative of a plurality of vehicle locations;

a navigation point generator at a server system remote from the vehicle that analyzes the data indicative of a plurality of vehicle locations and generates expected navigation points for the vehicle by identifying a starting point and a destination based on long periods of immobility connected by one or more periods of mobility;

means for generating one or more optimized routes through the expected navigation points based on estimated total trip times for a plurality of routes through the expected navigation points for the plurality of routes; and

means for generating a representation of the one or more optimized routes for transmission from the server system to the vehicle.