System and method for the calculation and use of travel times in search and other applications
First Claim
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, andeach 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, andthe 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.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5)
-
-
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. - View Dependent Claims (7, 8, 9, 10, 11, 12, 13, 14)
-
-
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. - View Dependent Claims (16, 17, 18, 19, 20)
-
Specification