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

• US 9,964,410 B2
• Filed: 11/23/2015
• Issued: 05/08/2018
• 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, Herst, Josh
• Primary Examiner(s): LE, HUNG D
• Application Number:
  US14/949,672
• Publication Number:
  US 20160216122A1
• Time in Patent Office: 897 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 for providing a travel shed indicating areas within a geographic region expected to be reachable from a specified location within a threshold period of time using a mode of transport, the system comprising:

a non-transitory data store including road graph data, the road graph data indicating locations within a geographic region as nodes of a road graph and travel routes between the locations as edges of the road graph, wherein edges of the road graph are weighted based at least partly on distances between the nodes; and

one or more processors configured with specific computer-executable instructions that, when executed, cause the one or more processors to at least;

remove a set of nodes from the road graph to generate a reduced road graph that has a node density of under a threshold value, the node density representing a proportion of the nodes within the reduced road graph to a size of the geographic region;

obtain a request for the travel shed, the request indicating the specified location, the threshold period of time, and the mode of transport;

traverse the reduced road graph to determine, from at least weightings of the edges within the reduced road graph, a set of nodes, within the reduced road graph, that represent locations within the geographic area expected to be reachable from the specified location within the threshold period of time using the mode of transport;

combine information regarding the set of nodes within reduced road graph to form the travel shed indicating areas within the geographic region expected to be reachable from the specified location within the threshold period of time using the mode of transport; and

generate an indication of the travel shed.

2. The system of claim 1, wherein the request for the travel shed is input via a graphical user interface, and wherein the travel shed is displayed on the graphical user interface.

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

4. The system of claim 1, wherein individual edges in the road graph correspond to at least one travel route type of a plurality of travel route types, and wherein the specific computer-executable instructions cause the one or more processors to remove the set of nodes at least partly by:

determining a priority of the travel route types; and

progressively removing edges from the road graph according to the priority of the travel route types until the road graph has a node density under the threshold value.

5. The system of claim 1, wherein the specific computer-executable instructions cause the one or more processors to remove the set of nodes at least partly by removing one or more nodes within a threshold distance of another node.

6. A computer-implementing method comprising:

obtaining road graph data, the road graph data indicating locations within a geographic region as nodes of a road graph and travel routes between the locations as edges of the road graph;

removing a portion of the nodes from the road graph to result in a reduced road graph with a node density under a threshold value, wherein edges within the reduced road graph are weighted based at least partly on distances between nodes of the reduced road graph;

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

traversing the reduced road graph to determine, at least from weightings of edges within the reduced road graph data, a set of nodes within the reduced road graph that represent locations within the geographic region expected to be reachable from the indicated location within the threshold period of time using the mode of transport;

combine information regarding the set of nodes to form a travel shed indicating areas within the geographic region expected to be reachable from the specified location within the threshold period of time using the mode of transport; and

generating an indication of the travel shed.

7. The computer-implementing method of claim 6, wherein a travel route 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 individual edges in the road graph correspond to at least one of a plurality of travel route types, and wherein removing the set of nodes from the road graph comprises:

determining a priority of the travel route types; and

progressively removing edges from the road graph according to the priority of the travel route types until the road graph has a node density under the threshold value.

11. The computer-implementing method of claim 6, wherein removing the set of nodes from the road graph comprises removing one or more non-branching nodes.

12. The computer-implementing method of claim 6 further comprising storing the reduced road graph data as an array of nodes within the reduced road graph, and an array of edges within the reduced road graph that are indexed according to the nodes.

13. The computer-implementing method of claim 12, wherein traversing the reduced road graph to determine a set of nodes within the reduced road graph that represent locations within the geographic region expected to be reachable from the indicated location within the threshold period of time using the mode of transport comprises:

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

traversing the directed graph to generate a point cost matrix, wherein the point cost matrix includes expected travel times between the indicated location and locations represented by nodes within the directed graph.

14. The computer-implementing method of claim 13, wherein searching 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:

obtain road graph data, the road graph data indicating locations within a geographic region as nodes of a road graph and travel routes between the locations as edges of the road graph;

remove a portion of the nodes from the road graph to result in a reduced road graph, wherein edges within the reduced road graph are weighted based at least partly on distances between nodes of the reduced road graph data;

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

traverse the reduced road graph to determine from at least weightings of edges within the reduced road graph data, a set of nodes within the reduced road graph that represent locations within the geographic region expected to be reachable from the indicated location within the threshold period of time using the mode of transport;

combine information regarding the determined set of nodes to form a travel shed indicating areas within the geographic region expected to be reachable from the specified location within the threshold period of time using the mode of transport; and

generate an indication of the travel shed.

16. The non-transitory computer-readable storage media of claim 15, wherein the edges within the reduced road graph are further 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 the edges.

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 the travel routes, and to modify the reduced road graph using the client travel data.

18. The non-transitory computer-readable storage media of claim 15, wherein individual edges in the road graph correspond to at least one of a plurality of travel route types, and wherein the computer-executable instructions cause the computing system to remove the set of nodes from the road graph at least partly by:

determining a priority of the travel route types; and

progressively removing edges from the road graph according to the priority of the travel route types until the road graph has a node density under the threshold value.

19. The non-transitory computer-readable storage media of claim 15, wherein the computer-executable instructions cause the computing system to remove the set of nodes at least partly by at least one of removing one or more non-branching nodes or removing one or more nodes within a threshold distance of another node.

20. A system comprising:

a non-transitory data store including data representing a road graph, the road graph indicating locations within a geographic region as nodes of a road graph and travel routes between the locations as edges of the road graph, wherein edges within the road graph are weighted based at least partly on distances between nodes of the road graph; and

one or more processors configured with specific computer-executable instructions that, when executed, cause the one or more processors to;

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

traverse the road graph to determine, at least from at least weightings of edges within the road graph, a set of nodes within the road graph that represent locations within the region expected to be reachable from the indicated location within the threshold period of time using the mode of transport;

combine information regarding the set of nodes to form a travel shed indicating areas within the geographic region expected to be reachable from the specified location within the threshold period of time using the mode of transport; and

generate an indication of the travel shed.

21. The system of claim 20, wherein distances between the nodes are represented according to a least one of travel time along a travel route or length of the travel route.

22. The system of claim 20, wherein the specific computer-executable instructions further cause the computing system to generate the road graph from a second road graph at least partly by:

determining a priority of the travel route types; and

progressively removing edges from the second road graph according to the priority of the travel route types until the second road graph has a node density under the threshold value.

23. The system of claim 20, wherein the specific computer-executable instructions further cause the computing system to generate the road graph from a second road graph at least partly by at least one of removing one or more non-branching nodes or removing one or more nodes within a threshold distance of another node from the second road graph.

24. The system of claim 20, wherein the specific computer-executable instructions further cause the computing system to assign weights to edges within the road graph based at least in part on at least one of lengths of travel routes indicated by the edges, travel speeds of travel routes indicated by the edges, or an effect of weather, traffic, priority lanes, toll roads, or hills on travel along the travel routes indicated by the edges.

25. The system of claim 20, wherein the reduced road graph is stored as an array of the nodes and an array of the edges, wherein the edges in the array of edges are indexed according to associated nodes, and wherein the specific computer-executable instructions further cause the computing system to traverse the road graph to determine the set of nodes within the road graph that represent locations within the geographic region expected to be reachable from the indicated location within the threshold period of time using the mode of transport at least partly by:

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

traversing the directed graph to generate a point cost matrix, wherein the point cost matrix includes expected travel times between the indicated location and locations represented by nodes within the directed graph.