Route Planning

• US 20140200807A1
• Filed: 01/17/2014
• Published: 07/17/2014
• Est. Priority Date: 01/17/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Geisberger, Robert
• Granted Patent: US 9,175,972 B2
• Time in Patent Office: Days
• US Class Current: 701/533
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G08G 1/096816 where the complete route is transmitted to the vehicle at once
• CPC Class Codes: G08G 1/09685 where the complete route is computed only once and not updated

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.

Claims

1. A computer-implemented route planning method, comprising:

determining 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 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;

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.

2. A computer-implemented route planning method as claimed in claim 1, wherein the initial graph search stops at a predetermined travel time from the source node.

3. A computer-implemented route planning method as claimed in claim 1, wherein the precomputed data based on traffic prediction data is computed in the precomputation phase of a hierarchical speedup technique.

4. A computer-implemented route planning method as claimed in claim 3, wherein the hierarchical speedup technique comprises contraction hierarchies.

5. A computer-implemented route planning method as claimed in claim 3, wherein the hierarchical speedup technique comprises highway hierarchies.

6. A computer-implemented route planning method as claimed in claim 1, where the one or more routes to the destination node are computed based on a many-to-one graph search from a plurality of said settled nodes to the destination node.

7. A computer-implemented route planning method as claimed in claim 1, wherein computing one or more routes to the destination node comprises computing one or more routes to the destination node from one or more settled nodes at which the initial graph search stops, using precomputed data based on traffic prediction data.

8. A computer-implemented route planning method as claimed in claim 1, wherein there is a blending phase between the real-time traffic data and the traffic prediction data.

9. A computer-implemented route planning method as claimed in claim 1, wherein the graph data structure is multi-shaded, and wherein additional nodes are included in one or more shards based on a search space of the initial graph search algorithm.

10. A computer-implemented route planning method as claimed in claim 1, wherein computing one or more routes to the destination node from one or more of said settled nodes comprises a bidirectional graph search.

11. A computer-implemented route planning method as claimed in claim 1, wherein the initial graph search comprises a Dijkstra-based search.

12. An apparatus comprising at least one processor and at least one memory storing instructions Which when executed by the at least one processor cause the at least one processor to perform the method of claim 1.

13. An apparatus as claimed in claim 12, comprising a mobile device.

14. A computer-readable medium comprising a computer program product adapted to perform the steps of claim 1.

15. A system, comprising:

one or more communication modules for communication with one or more client devices,

a precomputation module configured to generate a graph data structure based on map data, wherein the graph data structure represents a road network;

a query processing module configured to determine source and destination nodes in the graph data structure based on a route planning query, wherein, the query processing module comprises;

a first graph search module configured to execute 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

a second graph search module configured to compute 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.