Verizon Patent and Licensing Inc.

Nathan M Robinson

Jefferson Ray Tan Hidayat

Hayden Sean White

Mykhaylo Tyuryutikov

Hughan J Ross

A system described herein may provide a technique for the generation of a node map using contraction hierarchy techniques in a manner that accounts for multi-link constraints. Multi-link constraints may include a sequence of two or more links through the node map, and paths that include such multi-link constraints may be associated with an additional cost based on such inclusion. Shortcut links that represent paths through nodes contracted out of the node map may be associated with portions of multi-link constraints. Paths through such shortcut links, where such paths include the remainder of the multi-link constraint, may be considered as including the multi-link constraint, and the cost of such paths may be calculated accordingly. The costs of links and/or paths, including paths that include multi-link constraints, may be used in determining a path from a source node to a target node of the node map.

Systems and methods for optimal path determination using contraction hierarchies with multi-link constraints

A system may perform a search from a source node of a node map to a target node of the node map. Performing the search may include identifying a first path, starting at the source node, that enters a particular constraint region, and identifying a second path, starting at the source node, that does not enter the particular constraint region. The system may select the second path as a path from the source node to the target node, based on identifying that the first path enters the particular constraint region and that the second path does not enter the particular constraint region. The system may cease exploring nodes via the first path when the second path is identified as reaching the target node, and not including a constraint associated with the particular constraint region.

Conditional region-based costing in contraction hierarchies

A system described herein may provide a technique for a determination of a path through a node map using one or more searches. The nodes may be associated with respective priorities. A first search may be performed from a first node in ascending order of priority. A second search may be performed from a second node in ascending order of priority, until a third node, traversed during the first search is reached. A third search may be performed from the third node, in descending order of priority, until the first node is reached. The third search may be restricted only to nodes traversed during the first search. A path that is based on the second and third searches may be provided in response to a navigation request from a starting point associated with the second node to a destination associated with the first node.

Systems and methods for cost-based forward search based on precomputed bidirectional search

A system described herein may provide a technique for selectively adding or forgoing adding shortcut links to a node map using contraction hierarchy techniques based on turn costs. 'Useful' turn pairs for a given path through a shortcut link may include a turn into a first node of the shortcut link and a turn out of a second node of the shortcut link, where no alternative lower cost paths (including such “useful” turn pairs) from the first node to the second node are available. The useful turn pairs for a shortcut link may be used to evaluate super shortcut links that includes the shortcut link with identified useful turn pairs. For example, a search for alternative lower cost paths may need not be performed for paths, associated with the super shortcut link, which do not include a turn from the useful turn pairs of the component shortcut link.

Systems and methods for optimal path determination using contraction hierarchies with turn costs

A system described herein may provide a technique for the generation of a node map using contraction hierarchy techniques in a manner that accounts for constraints that apply to nodes or links between nodes in the node map. Candidate shortcut links, that represent paths through multiple links in the node map, may be evaluated to determine whether such candidate shortcut links are less restrictive than less costly paths having the same starting and ending nodes as the candidate shortcut links. Candidate shortcut links may be added to the node map in situations where less costly paths are available, but are more restrictive than the shortcut links. At query time, the shortcut links may apply to certain queries having parameters that violate constraints associated with the less costly paths but do not violate any applicable constraints of the shortcut links.

Systems and methods for optimal path determination using contraction hierarchies with link constraints

A route planning platform can identify a plurality of nodes interconnected by a plurality of paths in a road network, can divide the road network into a plurality of partitions, and can generate a respective contraction hierarchy for each partition of the plurality of partitions. The route planning platform can generate, based on the contraction hierarchies of the plurality of partitions, an overlay network and can generate a contraction hierarchy for the overlay network. The route planning platform can obtain information relating to an origination point and a destination point associated with the road network and can identify a first partition associated with the origination point and a second partition associated with the destination point. The route planning platform can determine a route from the origination point to the destination point based on the respective contraction hierarchies of the first partition, the second partition, and the overlay network.

Using partitioned contraction hierarchies to determine a route from an origination point to a destination point

A system described herein may provide a technique for selectively adding or forgoing adding shortcut links to a node map using contraction hierarchy techniques based on turn costs. 'Useful' turn pairs for a given path through a shortcut link may include a turn into a first node of the shortcut link and a turn out of a second node of the shortcut link, where no alternative lower cost paths (including such 'useful' turn pairs) from the first node to the second node are available. The useful turn pairs for a shortcut link may be used to evaluate super shortcut links that includes the shortcut link with identified useful turn pairs. For example, a search for alternative lower cost paths may need not be performed for paths, associated with the super shortcut link, which do not include a turn from the useful turn pairs of the component shortcut link.

Growing community of inventors

Christchurch, New Zealand

Nathan M Robinson