Generating travel time data

• US 9,250,075 B2
• Filed: 12/21/2012
• Issued: 02/02/2016
• Est. Priority Date: 12/23/2011
• Status: Active Grant

• Current Assignee: iGeolise Limited
• Original Assignee: Charles Linfield Davies, Peter Robert John Lilley
• Inventors: Davies, Charles Linfield, Lilley, Peter Robert John
• Primary Examiner(s): Dager, Jonathan M
• Application Number:
  US13/723,928
• Publication Number:
  US 20130166204A1
• Time in Patent Office: 1,138 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G01C 21/34 Route searching; Route 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/3697 Output of additional, non-guidance related information, e.g. low fuel level G01C21/3679 takes precedence

Abstract

The generation of travel time data is disclosed in which coordinates are received for a starting location (1901). A maximum travel time is received (1903) and processed graph data is read that includes nodes representing pre-filtered map features and edges representing travel times between nodes. A temporary graph is built (1907) of selected nodes that can be reached via selected edges within the maximum travel time. Candidate destinations are received (1908) and the travel time to these candidate destinations is tested (1909) with reference to the temporary graph.

Claims

1. A method of generating travel time data, comprising the steps of:

receiving coordinates for a starting location;

receiving a maximum travel time;

reading processed graph data comprising nodes representing pre-filtered map features and edges representing travel times between said nodes;

building a temporary graph of selected nodes that can be reached via selected edges within said maximum travel time;

receiving candidate destinations; and

testing the travel time to said candidate destinations with reference to said temporary graph,

wherein coordinates of each candidate destination are transformed to a modified destination at the location of a node in said processed graph data,

wherein coordinates of each candidate destination are transformed with reference to a binary space partitioning tree data structure produced by dividing a region of interest repeatedly until each sub-region contains only one of said graph nodes.

2. The method of claim 1, wherein said edges represent variable travel times between adjacent nodes that are dependent upon a temporal component derived from non-exclusively one or more of the following, comprising:

time of day, day of the week, time of the year and special activity periods; and

said temporary graph is built with reference to a time of travel so as to account for said temporal component.

3. The method of claim 1, wherein coordinates of an actual starting location are transformed to a modified origin at the location of a node in said processed graph data.

4. The method of claim 1, wherein each candidate destination is transformed upon arrival, in preference to said building step, thereby reducing the building of said temporary graph to a background process.

5. The method of claim 1, wherein a candidate destination is rejected if it has a location that is displaced from a starting location by a first predetermined distance.

6. The method of claim 1, wherein a candidate destination is rejected if it has a location that is displaced from a nearest node by a second predetermined distance.

7. The method of claim 1, wherein said processed graph data is produced by processing map data to remove features that are not travel related.

8. The method of claim 1, wherein said map data is processed a plurality of times to produce a plurality of processed graph data sets, applicable to respective modes of transport.

9. The method of claim 1, wherein a travel time for each selected node is calculated by subtracting travel times between nodes from said maximum travel time.

10. The method of claim 1, wherein said testing step identifies destinations that can be reached within said maximum travel time and returns data that identifies each candidate with an indication of travel time.

11. The method of claim 10, wherein said identified candidates are ranked in terms of travel time.