Generating travel time data

• US 9,677,904 B2
• Filed: 01/05/2016
• Issued: 06/13/2017
• 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:
  US14/988,242
• Publication Number:
  US 20160146629A1
• Time in Patent Office: 525 Days
• Field of Search: None
• 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 server computer configured to produce a list of destinations, having a processor configured to:

receive co-ordinates for a starting location;

receive a maximum travel time;

read processed graph data comprising nodes representing pre-filtered map features and edges that include representations of travel times between said nodes;

traverse said graph data to identify selected nodes that can be reached from said starting location via edges in said graph data within said maximum travel time;

receive candidate destinations;

for each candidate destination, identify whether it is geographically close to one of said selected nodes, and if so select it; and

output for display a list including said selected candidate destinations.

2. The server computer of claim 1, wherein said processor is also configured to:

divide a geographical region repeatedly so that each divided region includes one exclusive graph node;

create a two dimensional binary space partitioning tree;

translate a starting location to a graph node with reference to said two dimensional binary space partitioning tree; and

carry out said step of identifying identifying whether a candidate destination is geographically close to a selected node by referring to said two dimensional binary space partitioning tree.

3. The server computer of claim 1, including a cache, wherein said cache is configured to store a previously identified set of selected nodes to facilitate repeated searches from the same starting location but for different candidate destinations.

4. An application executable within a mobile device, configured to receive travel time data from the server of claim 1.

5. The mobile device of claim 4, further comprising apparatus for generating location data representing the location of said mobile device, wherein said location data is conveyed to said server computer to identify a starting location.

6. A method of generating travel time data, comprising the steps taken by a processor 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;

traversing said graph data to identify selected nodes that can be reached from said starting location via edges in said graph data within said maximum travel time;

receiving candidate destinations;

for each candidate destination, identifying whether it is geographically close to one of said selected nodes, and if so selecting it; and

outputting for display a list including said selected candidate destinations.

7. The method of claim 6, 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 traversal of said graph data is carried out with reference to a time of travel so as to account for said temporal component.

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

9. The method of claim 6, wherein coordinates of each candidate destination are transformed to a modified destination at the location of a-its geographically close selected node.

10. The method of claim 9, wherein each candidate destination is transformed upon arrival, in preference to said building step, the building of said temporary graph being performed as a background process.

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

12. The method of claim 9, wherein a candidate destination is rejected if it has a location that is displaced from its geographically close selected node by a second predetermined distance.

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

14. The method of claim 6, 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.

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

16. The method of claim 6, wherein said outputted list includes an indication of travel time for each selected candidate destination.

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