Generating Travel Time Data

• US 20130166204A1
• Filed: 12/21/2012
• Published: 06/27/2013
• 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
• Granted Patent: US 9,250,075 B2
• Time in Patent Office: Days
• US Class Current: 701/533
• 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.

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 coordinates of each candidate destination are transformed to a modified destination at the location of a node in said processed graph data.

5. The method of claim 4, 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.

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

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

8. The method of claim 4, 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.

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

10. 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.

11. 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.

12. 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.

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

14. A server computer configured to generate travel time data, 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;

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

receive candidate destinations; and

test the travel time to said candidate destinations with reference to said temporary graph.

15. The server computer of claim 14, 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

test each candidate location upon arrival with reference to said two dimensional binary space partitioning tree.

16. The server computer of claim 14, including a cache, wherein said cache is configured to store a previously built temporary graph to facilitate repeated searches from the same starting location but for different candidate destinations.

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

18. The mobile device of claim 17, 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 stating location.

19. A data structure, comprising selected nodes that can be reached via selected edges within a specified maximum journey time, wherein:

said data structure is built from processed graph data; and

said processed graph data comprises nodes that represent pre-filtered map features and edges related to travel times between nodes.

20. The data structure of claim 19, built dynamically in response to a search request, wherein said travel times between nodes are time and event sensitive.