System and method for the calculation and use of travel times in search and other applications

• US 10,317,219 B1
• Filed: 05/07/2018
• Issued: 06/11/2019
• 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: Borgerson, Bo, Kawaguchi, Kenshi, Lerner, Matthew R., Herst, Josh
• Primary Examiner(s): Le, Hung D
• Application Number:
  US15/973,355
• Time in Patent Office: 400 Days
• Field of Search: None
• 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 which are reachable from a given address or location within a specified travel time by utilizing a specified mode of transport (e.g. driving, biking, walking, public transportation, etc.). Techniques are disclosed for enabling the rapid calculations of travel times. In one embodiment, the rapid generation of travel times and associated travel sheds may be enabled by performing a number of pre-processing steps (e.g. downsampling, progressive road type removal, etc.) on road graph data. The pre-processing steps reduce the size of the road graph while still preserving enough of the road graph 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 system comprising:

a non-transitory data store including data representing a road graph including a plurality of nodes and a plurality of edges, wherein;

each node of the plurality of nodes represents a location within a geographic region,

each edge represents a travel route between two locations within the geographic region, which two locations are represented by different nodes of the plurality of nodes, and

each edge indicates a distance of the travel route represented by the edge; and

one or more processors in communication with the non-transitory data store and configured with specific computer-executable instructions that, when executed by the processors, cause the system to at least;

obtain an indication of a particular location within the geographic region, a threshold period of time, and a mode of transport;

traverse the road graph to determine, based at least partly on a subset of the plurality of edges of the road graph, at least a first reachable node and a second reachable node in the road graph, wherein;

the first reachable node represents a first location within the geographic region expected to be reachable from the particular location within the threshold period of time using the mode of transport, and

the second reachable node represents a second location with the geographic region expected to be reachable from the particular location within the threshold period of time using the mode of transport;

combine information regarding the first reachable node and the second reachable node to form a travel shed indicating an area within the geographic region expected to be reachable from the particular location within the threshold period of time using the mode of transport, wherein the area indicated by the travel shed represents a combination of a first area associated with the first location and a second area associated with the second location; and

generate an indication of the travel shed.

2. The system of claim 1, wherein a request for the travel shed is input via a graphical user interface displayed on a computing device, and wherein execution of the computer-executable instructions further causes the system to transmit the indication of the travel shed to the computing device for display within the graphical user interface.

3. The system of claim 2, wherein the travel shed is displayed via the graphical user interface as a series of geometric shapes that collectively depict the at least one area within the geographic region that is expected to be reachable within the threshold period of time using the mode of transport.

4. The system of claim 1, wherein the road graph data represents a plurality of road graphs, each road graph of the plurality of road graphs corresponding to a particular mode of transport of a plurality of modes of transport, and wherein the computer-executable instructions, when executed by the processors, further cause the system to at least select the road graph from the plurality of road graphs based at least partly on the mode of transport within the obtained indication.

5. The system of claim 4, wherein the computer-executable instructions, when executed by the processors, further cause the system to generate the plurality of road graphs, and wherein, to generate at least one road graph of the plurality of road graphs, the computer-executable instructions cause the computing system to pre-process the at least one road graph according to the particular mode of transport corresponding to the at least one road graph.

6. A computer-implemented method comprising:

obtaining road graph data representing a road graph that includes a plurality of nodes and a plurality of edges, wherein;

each node of the plurality of nodes represents a location within a geographic region,

each edge represents a travel route between two locations within the geographic region, which two locations are represented by different nodes of the plurality of nodes, and

each edge indicates a distance of the travel route that is represented by the edge; and

obtaining an indication of a particular location within the geographic region, a threshold period of time, and a mode of transport;

traversing the road graph to determine, based at least partly on a subset of the plurality of edges of the road graph, at least a first reachable node and a second reachable node in the road graph, wherein;

the first reachable node represents a first location within the geographic region expected to be reachable from the particular location within the threshold period of time using the mode of transport, and

the second reachable node represents a second location with the geographic region expected to be reachable from the particular location within the threshold period of time using the mode of transport;

combining information regarding the first reachable node and the second reachable node to form a travel shed indicating an area within the geographic region expected to be reachable from the particular location within the threshold period of time using the mode of transport, wherein the area indicated by the travel shed represents a combination of a first area associated with the first location and a second area associated with the second location; and

generating an indication of the travel shed.

7. The computer-implementing method of claim 6, wherein at least one travel route represented by an edge within the road graph comprises at least one of a motorway, a motorway link, a trunk road, a primary road, a secondary road, a tertiary road, a residential road, footpath, a cycleway, a path, a trail, a subway route, a train route, a bus route, or a ferry route.

8. The computer-implementing method of claim 6, wherein the mode of transport comprises at least one of walking, driving, biking, or public transportation.

9. The computer-implementing method of claim 6 further comprising at least one of transmitting the indication of the travel shed to a computing device or displaying the travel set within a graphical user interface.

10. The computer-implementing method of claim 6, wherein the mode of transport comprises a combination of at least two different modes of transport.

11. The computer-implementing method of claim 6, wherein the road graph data represents a plurality of road graphs, each road graph of the plurality of road graphs corresponding to a particular mode of transport of a plurality of modes of transport, and wherein the method further comprises selecting the road graph from the plurality of road graphs based at least partly on the mode of transport within the obtained indication.

12. The computer-implementing method of claim 6 wherein the road graph data comprises a first array of the nodes within the road graph and a second array of the edges within the road graph, wherein the second array is indexed according to the nodes.

13. The computer-implementing method of claim 12, wherein traversing the road graph to determine the first reachable node and the second reachable node comprises:

generating a directed graph from the first array of the nodes and the second array of the edges; and

traversing the directed graph to generate a point cost matrix, wherein the point cost matrix includes at least an expected travel time between the particular location and the first location represented by the first reachable node and an expected travel time between the particular location and the second location represented by the second reachable node.

14. The computer-implementing method of claim 13, wherein traversing the directed graph comprises searching the directed graph according to a breadth-first traversal algorithm.

15. Non-transitory computer-readable storage media including computer-executable instructions that, when executed by a computing system, cause the computing system to at least:

obtain road graph data, representing a road graph that includes a plurality of nodes and a plurality of edges, wherein;

each node of the plurality of nodes represents a location within a geographic region,

each edge represents a travel route between two locations within the geographic region, which two locations are represented by different nodes of the plurality of nodes, and

each edge indicates a distance of the travel route that is represented by the edge; and

obtain an indication of a particular location within the geographic region, a threshold period of time, and a mode of transport;

traverse the road graph to determine, based at least partly on a subset of the plurality of edges of the road graph, at least a first reachable node and a second reachable node in the road graph, wherein;

the first reachable node represents a first location within the geographic region expected to be reachable from the particular location within the threshold period of time using the mode of transport, and

the second reachable node represents a second location with the geographic region expected to be reachable from the particular location within the threshold period of time using the mode of transport;

combine information regarding the first reachable node and the second reachable node to form a travel shed indicating an area within the geographic region expected to be reachable from the particular location within the threshold period of time using the mode of transport, wherein the area indicated by the travel shed represents a combination of a first area associated with the first location and a second area associated with the second location; and

generate an indication of the travel shed.

16. The non-transitory computer-readable storage media of claim 15, wherein at least some of the edges within the road graph are weighted according to at least one of an effect of weather, traffic, priority lanes, toll roads, or hills on travel along the travel routes indicated by respective edges of the at least some edges, and wherein the first reachable node and the second reachable node are determined based at least in part on weightings of the at least some edges within the road graph.

17. The non-transitory computer-readable storage media of claim 15, wherein the computer-executable instructions further cause the computing system to obtain client travel data indicative of travel along a travel route represented by an edge of the road graph, and to modify the road graph using the client travel data.

18. The non-transitory computer-readable storage media of claim 15, wherein the road graph data represents a plurality of road graphs, each road graph of the plurality of road graphs corresponding to a particular mode of transport of a plurality of modes of transport, and wherein the computer-executable instructions further cause the computing system to select the road graph from the plurality of road graphs based at least partly on the mode of transport within the obtained indication.

19. The non-transitory computer-readable storage media of claim 18, wherein the computer-executable instructions further cause the computing system to generate the plurality of road graphs, and wherein, to generate at least one road graph of the plurality of road graphs, the computer-executable instructions cause the computing system to pre-process the at least one road graph according to the particular mode of transport corresponding to the at least one road graph.

20. The non-transitory computer-readable storage media of claim 19, wherein the computer-executable instructions further cause the computing system to store the plurality of road graphs in a geohash directory structure.