Route planning
AssigneeGoogle Inc.
InventorRobert Geisberger
Life of this patent
Estimating the term…
Abstract
A computer-implemented route planning method comprises determining source and destination nodes in a graph data structure based on a route planning query, executing an initial graph search on the graph data structure using graph costs based on real-time traffic data, wherein the initial graph search starts at the source node and settles nodes until it stops, and computing one or more routes to the destination node from one or more of said settled nodes using precomputed data based on traffic prediction data, thereby to determine a route from the source node to the destination node via one of said settled nodes.
Claims10
A computer-implemented route planning method, comprising:
- determining, by one or more computing devices, source and destination nodes in a graph data structure based on a route planning query, wherein the graph data structure represents a road network;
- executing, by the one or more computing devices, an initial graph search on the graph data structure using graph costs based on real-time traffic data, wherein the initial graph search starts at the source node and settles nodes until it stops upon locating one or more nodes that are more than a predetermined travel time from the source node;
- computing, by the one or more computing devices, one or more routes to the destination node from one or more of said settled nodes using precomputed data based on traffic prediction data, thereby to determine a route from the source node to the destination node via one of said settled nodes, wherein the initial graph search comprises a blending phase between the real-time traffic data and the traffic prediction data such that costs on the graph for the initial graph search are modified so that there is a continuous transition between real-time traffic data and traffic prediction data;
- and
- providing, by the one or more computing devices, the route to a device for display to a user.
A system, comprising:
- one or more processors and one or more memory devices storing computer-readable instructions that when executed by the one or more processors cause the one or more processors to perform operations comprising:
- communicating with one or more client devices,
- generating a graph data structure based on map data, wherein the graph data structure represents a road network;
- determining source and destination nodes in the graph data structure based on a route planning query, wherein the determining comprises:
- executing an initial graph search on the graph data structure using graph costs based on real-time traffic data, wherein the initial graph search starts at the source node and settles nodes until it stops upon locating one or more nodes that are more than a predetermined travel time from the source node;
- and
- computing one or more routes to the destination node from one or more of said settled nodes using precomputed data based on traffic prediction data, thereby to determine a route from the source node to the destination node via one of said settled nodes, wherein the initial graph search comprises a blending phase between the real-time traffic data and the traffic prediction data such that costs on the graph for the initial graph search are modified so that there is a continuous transition between real-time traffic data and traffic prediction data;
- providing the route to a device for display to a user.
Dependencies are inferred from the claim text.