Travel time determination

• US 8,036,822 B2
• Filed: 09/12/2006
• Issued: 10/11/2011
• Est. Priority Date: 09/12/2006
• Status: Expired due to Fees

• Current Assignee: DDS Wireless International Incorporated (Ghai Investments Ltd)
• Original Assignee: DDS Wireless International Incorporated (Ghai Investments Ltd)
• Inventors: Ho, William P. C.
• Primary Examiner(s): Hellner; Mark
• Assistant Examiner(s): Mawari; Redhwan K
• Application Number:
  US11/520,088
• Publication Number:
  US 20080065318A1
• Time in Patent Office: 1,855 Days
• Field of Search: 701/117, 701/118, 701/201, 701/209, 340/995.13, 340/988, 340/994, 340/990, 340/995.12, 340/995.1, 455/456.1
• US Class Current: 701/201
• CPC Class Codes: G01C 21/3407 specially adapted for specific applications

Abstract

The present invention relates to travel time determination, for example, determining a predicted travel time between locations based on historical data. One aspect of the invention is directed toward a method for determining a predicted amount of time required to travel from one location to another that includes dividing a region into multiple grid portions and designating each grid portion that contains at least one address of interest as a departure grid, a destination grid, or both. The method can further include generating a searchable data arrangement that includes travel times associated with traveling from selected departure grids to selected destination grids, and updating the travel times using historical data.

Claims

1. A method in a computer system, the computer system comprising a database, for determining a predicted amount of time required to travel from one location to another, the method comprising:

maintaining an indexed lookup table, in the database, that includes approximate travel times associated with traveling from within selected departure grid portions to within selected destination grid portions, each selected departure grid portion and each selected destination grid portion being associated with at least one address of interest in a region, the grid portion derived to represent geographical regions whose traversal time relates to a predetermined amount of time wherein the grid portions represented in the indexed lookup table have been sized so that each grid portion is expected to have a traversal time based on a predetermined amount of time, the address representative of a physical location within the geographical region;

updating the travel times with historical data that includes actual amounts of time that have been required to travel from selected departure grid portions to selected destination grid portions; and

searching the indexed lookup table to predict an approximate travel time from a first location to a second location.

2. The method of claim 1 wherein the indexed lookup table comprises a searchable three-dimensional data arrangement that includes travel times associated with traveling from selected departure grid portions to selected destination grid portions during selected time periods.

3. The method of claim 1 wherein updating the travel times with historical data includes:

filtering the collected data to exclude data collected under abnormal circumstances; and

updating the travel times using the filtered data.

4. The method of claim 1 wherein the selected departure grid portions and the selected destination grid portions (a) are expected to require no more than a selected amount of time to transit, (b) include a special condition, or (c) both (a) and (b).

5. The method of claim 1, further comprising:

receiving a command to search the indexed lookup table to determine a predicted travel time from a first address of interest to a second address of interest;

determining a selected departure grid portion in which the first address is located;

determining a selected destination grid portion in which the second address of interest is located; and

determining the travel time associated with the selected departure grid portion and the selected destination grid portion.

6. The method of claim 2, further comprising:

receiving a command to search the three-dimensional data arrangement to determine a predicted travel time from a first address of interest to a second address of interest during a selected time period;

determining a selected departure grid portion in which the first address is located;

determining a selected destination grid portion in which the second address of interest is located; and

determining the travel time associated with the selected departure grid portion, the selected destination grid portion, and the selected time period.

7. The method of claim 1, further comprising:

receiving a command to search the indexed lookup table to determine a predicted travel time from a first address of interest to a second address of interest;

determining a selected departure grid portion in which the first address is located;

determining a selected destination grid portion in which the second address of interest is located; and

determining the travel time associated with the selected departure grid portion and the selected destination grid portion, wherein determining the travel time associated with the selected departure grid portion and the selected destination grid portion includes adjusting the travel time by an operational factor.

8. The method of claim 1, further comprising:

determining if the transit time within or through at least one departure grid portion is less than or equal to a selected amount of time and if so combining the at least one departure grid portion with another departure grid portion to form a single departure grid portion.

9. The method of claim 1, further comprising:

determining a time relation, the time relation relating transit time within or through a grid portion to a selected amount of time; and

performing an action on the grid portion based on the time relation.

10. The method of claim 9, wherein the grid portion is selected from a group consisting of a departure grid portion and a destination grid portion.

11. The method of claim 9, wherein the action is selected from a group consisting of combining the grid portion with another grid portion and dividing the grid portions into multiple new grid portions.

12. The method of claim 9, wherein the time relation is selected from a group consisting of the transit time within or through the grid portion is less than the selected amount of time, the transit time within or through the grid portion is equal to the selected amount of time, and the transit time within or through the grid portion is greater than the selected amount of time.

13. The method of claim 1, wherein searching the indexed lookup table comprises conducting a log N search.