SYSTEM AND METHOD FOR THE CALCULATION AND USE OF TRAVEL TIMES IN SEARCH AND OTHER APPLICATIONS

• US 20130046795A1
• Filed: 08/16/2012
• Published: 02/21/2013
• Est. Priority Date: 08/16/2011
• Status: Active Grant

• Current Assignee: Walk Score Management LLC (Redfin Corporation)
• Original Assignee: Walk Score Management LLC (Redfin Corporation)
• Inventors: Lerner, Matthew, Borgerson, Bo, Kawaguchi, Kenshi, Herst, Josh
• Granted Patent: US 9,195,953 B2
• Time in Patent Office: Days
• US Class Current: 707/798
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling

Abstract

A system and method are provided for generating travel sheds which show the area reachable in a given amount of time by different modes of transport. A travel shed may consist of a series of polygons or other geometric shapes showing areas reachable from a given address or location within a specified travel time utilizing a specified mode of transport (e.g. driving, biking, walking, public transportation, etc.). Techniques are disclosed for enabling rapid calculations of travel times. In one embodiment, rapid generation of travel times and associated travel sheds may be enabled by performing pre-processing steps (e.g. downsampling, progressive road type removal, etc.) on road graph data. The pre-processing steps reduce the road graph while still preserving enough to generate accurate travel sheds. One example use of travel sheds is to enable searching for points of interest (e.g. homes, apartments, hotels, restaurants, schools, parks, etc.) according to specified travel times.

Claims

1. A computer implemented method of processing road graph data for use in determining travel times, comprising:

obtaining, with a computer, road graph data regarding a geographic area to be evaluated;

processing, with the computer, the road graph data utilizing a set of criteria related to a first mode of transport, the set of criteria being utilized to determine a lower priority portion of the road graph data that is considered to have a lower priority for use when calculating travel times for the first mode of transport as compared to a higher priority portion of the road graph data that is considered to have a higher priority for use when calculating travel times for the first mode of transport; and

storing, with the computer, the processed road graph data as a set of optimized road graph data to be utilized for calculating travel times for the first mode of transport, the set of optimized road graph data not including the lower priority portion of the road graph data.

2. The computer-implemented method of claim 1, wherein the set of criteria is utilized during the processing to continue to increase the lower priority portion of the road graph data until the remaining higher priority portion of the road graph data is smaller than a specified threshold.

3. The computer-implemented method of claim 1, wherein the set of criteria relates to a set of road type priorities for the first mode of transport.

4. The computer-implemented method of claim 1, wherein additional enhancing data is stored in conjunction with the road graph data for enhancing the calculations of travel times, including at least one of elevation data, rush-hour data, priority lanes, user generated feedback, and personalized speeds.

5. The computer-implemented method of claim 4, wherein the road map data comprises nodes and edges, and at least some nodes with distances to neighboring nodes that are below a specified threshold are not saved with the optimized road map data.

6. The computer-implemented method of claim 1, wherein the set of optimized road graph data is stored as an array of nodes and an array of edges that index into the nodes, the edges containing at least one of distance or travel time between nodes.

7. The computer-implemented method of claim 1, further comprising:

processing, with the computer, the road graph data utilizing a set of criteria related to a second mode of transport, the set of criteria being utilized to determine a lower priority portion of the road graph data that is considered to have a lower priority for use when calculating travel times for the second mode of transport as compared to a higher priority portion of the road graph data that is considered to have a higher priority for use when calculating travel times for the second mode of transport; and

storing, with the computer, the processed road graph data as a set of optimized road graph data to be utilized for calculating travel times for the second mode of transport, the set of optimized road graph data not including the lower priority portion of the road graph data, the set of optimized road graph data for the second mode of transport being different than the set of optimized road graph data for the first mode of transport.

8. The computer-implemented method of claim 7, wherein the first and second modes of transport each comprise a different one of driving, biking, walking or public transportation.

9. The computer-implemented method of claim 8, wherein in the related sets of criteria, large roads are given the highest priority for driving, small roads are given the highest priority for walking, and mid-sized roads are given the highest priority for biking.

10. A computing system comprising:

a memory for storing a sequence of program instructions;

a processor that is configured to execute the sequence of instructions to process road graph data, by;

processing, with the computer, the road graph data utilizing a set of criteria related to a first mode of transport, the set of criteria being utilized to determine a lower priority portion of the road graph data that is considered to have a lower priority for use when calculating travel times for the first mode of transport as compared to a higher priority portion of the road graph data that is considered to have a higher priority for use when calculating travel times for the first mode of transport; and

storing, with the computer, the processed road graph data as a set of optimized road graph data to be utilized for calculating travel times for the first mode of transport, the set of optimized road graph data not including the lower priority portion of the road graph data.

11. The computing system of claim 10, wherein the set of criteria is utilized during the processing to continue to increase the lower priority portion of the road graph data until the remaining higher priority portion of the road graph data is smaller than a specified threshold.

12. The computing system of claim 10, wherein additional enhancing data is stored in conjunction with the road graph data for enhancing the calculations of travel times, including at least one of elevation data, rush-hour data, priority lanes, user generated feedback, and personalized speeds.

13. The computing system of claim 10, further comprising:

processing, with the computer, the road graph data utilizing a set of criteria related to a second mode of transport, the set of criteria being utilized to determine a lower priority portion of the road graph data that is considered to have a lower priority for use when calculating travel times for the second mode of transport as compared to a higher priority portion of the road graph data that is considered to have a higher priority for use when calculating travel times for the second mode of transport; and

storing, with the computer, the processed road graph data as a set of optimized road graph data to be utilized for calculating travel times for the second mode of transport, the set of optimized road graph data not including the lower priority portion of the road graph data, the set of optimized road graph data for the second mode of transport being different than the set of optimized road graph data for the first mode of transport.

14. The computing system of claim 13, wherein the first and second modes of transport each comprise a different one of driving, biking, walking or public transportation.

15. A non-transitory, computer readable media with instructions stored thereon that when executed, cause a processor to process road graph data, by:

processing, with the computer, the road graph data utilizing a set of criteria related to a first mode of transport, the set of criteria being utilized to determine a lower priority portion of the road graph data that is considered to have a lower priority for use when calculating travel times for the first mode of transport as compared to a higher priority portion of the road graph data that is considered to have a higher priority for use when calculating travel times for the first mode of transport; and

storing, with the computer, the processed road graph data as a set of optimized road graph data to be utilized for calculating travel times for the first mode of transport, the set of optimized road graph data not including the lower priority portion of the road graph data.

16. The non-transitory computer readable media of claim 15, wherein the set of criteria is utilized during the processing to continue to increase the lower priority portion of the road graph data until the remaining higher priority portion of the road graph data is smaller than a specified threshold.

17. The non-transitory computer readable media of claim 15, wherein additional enhancing data is added to the road graph data for enhancing the calculations of travel times, including at least one of elevation data, rush-hour data, priority lanes, user generated feedback, and personalized speeds.

18. The non-transitory computer readable media of claim 15, further comprising:

processing, with the computer, the road graph data utilizing a set of criteria related to a second mode of transport, the set of criteria being utilized to determine a lower priority portion of the road graph data that is considered to have a lower priority for use when calculating travel times for the second mode of transport as compared to a higher priority portion of the road graph data that is considered to have a higher priority for use when calculating travel times for the second mode of transport; and

storing, with the computer, the processed road graph data as a set of optimized road graph data to be utilized for calculating travel times for the second mode of transport, the set of optimized road graph data not including the lower priority portion of the road graph data, the set of optimized road graph data for the second mode of transport being different than the set of optimized road graph data for the first mode of transport.

19. The non-transitory computer readable media of claim 18, wherein the first and second mode of transport each comprise a different one of driving, biking, walking or public transportation.

20. A computer implemented method of providing travel sheds utilizing processed road graph data, comprising:

receiving as input a selected mode of transport; and

generating a travel shed for the selected mode of transport, the generation of the travel shed utilizing processed road graph data, the road graph data having been processed to enable determinations of travel times between points in the road graph that are represented in the road graph data, the travel times being determined based on the selected mode of transport and associated rates of travel, the travel times between points also being determined based on selected pathways through the road graph between the points, wherein the selected pathways are determined based on criteria related to the selected mode of transport.

21. The computer implemented method of claim 20, wherein the selected mode of transport is one of a plurality of different modes of transport that are presented on a user interface for selection, the plurality of modes of transport comprising at least two of driving, biking, walking or public transportation.

22. The computer implemented method of claim 21, further comprising providing a user interface with an option for generating a plurality of travel sheds to be displayed on the user interface at the same time, each of the travel sheds having the option for being generated for different modes of transport.

23. The computer implemented method of claim 20, wherein the processing of the road graph data reduces the size of the road graph.

24. The computer implemented method of claim 20, wherein the processing of the road graph data includes producing one or more of a directed graph, a point cost matrix, and a geohash table.

25. The computer implemented method of claim 20, wherein the processing of the road graph data is accomplished utilizing a plurality of computers in parallel.