# US 12,601,602 B2 · Systems and methods for multi-destination contraction hierarchy path search

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 12,601,602 B2
- Document ID: US12601602B2
- Status: Granted
- Kind: B2
- Application number: 18/503,550
- Filed: 2023-11-07
- Published: 2025-05-08
- Granted: 2026-04-14
- Earliest claimed: 2023-11-07
- Assignees: Verizon Patent and Licensing Inc.
- Applicants: Verizon Patent and Licensing Inc.
- Inventors: David P. Manning
- Web page: https://patentgrep.com/patent/US12601602B2

## CPC

- G01C 21/3446: {Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes}
- G01C 21/3453: {Special cost functions, i.e. other than distance or default speed limit of road segments}
- G01C 21/343: {Calculating itineraries (travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047)}
- G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S)

## Abstract

A system described herein may efficiently perform a multi-destination backward search, which may be a part of performing a bidirectional search in a node map that implements contraction hierarchy techniques. Lowest cost paths to each node reachable to each destination node of a set of destination nodes may be computed. A queue may be initialized with the set of destination nodes. For each particular node in the queue, the system may add higher priority neighbors of the particular node to the queue, identify costs of outgoing links from the particular node to the higher priority neighbors, compute lowest cost paths associated with the set of destination nodes based on the identified costs of outgoing links from the particular node to the higher priority neighbors and any previously computed lowest cost paths associated with the set of destination nodes, and increment to a next node in the queue.

## Claims

### Claim 1

A device, comprising:
one or more processors configured to:
receive a node map that includes a set of nodes and respective links between nodes, wherein each node is associated with a respective measure of priority and wherein each link is associated with a respective cost;
identify a set of destination nodes in the node map;
initialize a queue by adding the set of destination nodes to the queue;
compute lowest cost paths to each node reachable to each destination node of the set of destination nodes,
wherein a first iteration of the computing includes, for a first node in the queue:
adding higher priority neighbors of the first node, which are not in the queue, to the queue;
loading, to a memory device, information indicating costs of outgoing links from the first node to the higher priority neighbors of the first node; and
performing a first iteration of computing lowest cost paths associated with the set of destination nodes based on:
the costs of the outgoing links from the first node to the higher priority neighbors of the first node, and
any previously computed lowest cost paths associated with the set of destination nodes,
wherein a second iteration of the computing includes, for a second node that is a next node in the queue with respect to the first node:
loading, to the memory device, information indicating costs of outgoing links from the second node to higher priority neighbors of the second node, without loading the information indicating the costs of outgoing links from the first node to the higher priority neighbors of the first node; and
performing a second iteration of computing lowest cost paths associated with the set of destination nodes based on:
the costs of the outgoing links from the second node to the higher priority neighbors of the second node, and
any previously computed lowest cost paths associated with the set of destination nodes, including one or more lowest cost paths computed when performing the first iteration of computing the lowest cost paths;
receive a navigation request for a route between a particular starting node in the node map and a particular destination node of the set of destination nodes;
generate the requested route based on a particular computed lowest cost path associated with the particular destination node; and
output, in response to the navigation request, the generated route.

### Claim 2 (depends on 1)

The device of claim 1, wherein computing the lowest cost paths associated with a particular destination node of the set of destination nodes includes traversing the node map in ascending order of priority.

### Claim 3 (depends on 1)

The device of claim 1,
wherein the first iteration of computing lowest cost paths associated with the set of destination nodes includes identifying a first lowest cost path associated with a particular destination node based on a first set of identified costs of outgoing links from the first node to a first set of higher priority neighbors of the first node, and
wherein the second iteration of computing lowest cost paths associated with the set of destination nodes includes identifying a second lowest cost path associated with the particular destination node, that is a lower cost than the first lowest cost path, based on a second set of identified costs of outgoing links from the second node to a second set of higher priority neighbors of the second node.

### Claim 4 (depends on 3)

The device of claim 3, wherein the second iteration of computing lowest cost paths associated with the set of destination nodes further includes identifying the second lowest cost path associated with the particular destination node based on the first lowest cost path.

### Claim 5 (depends on 1)

The device of claim 1, wherein the one or more processors are further configured to:
perform a bidirectional search of the node map that includes a forward search from the particular starting node and a backward search from the set of destination nodes, wherein the backward search from the set of destination nodes includes the computing of the lowest cost paths to each node reachable to each destination node of the set of destination nodes.

### Claim 6 (depends on 1)

The device of claim 1, wherein adding higher priority neighbors of the first node, which are not in the queue, to the queue includes adding the higher priority neighbors of the first node, which are not in the queue, to the queue in order of ascending priority.

### Claim 7 (depends on 6)

The device of claim 6, wherein the one or more processors are further configured to:
add the second node to the queue;
identify, after adding the second node to the queue and prior to adding the first node to the queue, that the first node is associated with a lower priority than the second node; and
add the first node to the queue, wherein adding the first node to the queue includes placing the first node ahead of the second node in the queue based on identifying that the first node is associated with the lower priority than the second node.

### Claim 8

A non-transitory computer-readable medium, storing a plurality of processor-executable instructions to:
receive a node map that includes a set of nodes and respective links between nodes, wherein each node is associated with a respective measure of priority and wherein each link is associated with a respective cost;
identify a set of destination nodes in the node map;
initialize a queue by adding the set of destination nodes to the queue;
compute lowest cost paths to each node reachable to each destination node of the set of destination nodes,
wherein a first iteration of the computing includes, for a first node in the queue:
adding higher priority neighbors of the first node, which are not in the queue, to the queue;
loading, to a memory device, information indicating costs of outgoing links from the first node to the higher priority neighbors of the first node; and
performing a first iteration of computing lowest cost paths associated with the set of destination nodes based on:
the costs of the outgoing links from the first node to the higher priority neighbors of the first node, and
any previously computed lowest cost paths associated with the set of destination nodes,
wherein a second iteration of the computing includes, for a second node that is a next node in the queue with respect to the first node:
loading, to the memory device, information indicating costs of outgoing links from the second node to higher priority neighbors of the second node, without loading the information indicating the costs of outgoing links from the first node to the higher priority neighbors of the first node; and
performing a second iteration of computing lowest cost paths associated with the set of destination nodes based on:
the costs of the outgoing links from the second node to the higher priority neighbors of the second node, and
any previously computed lowest cost paths associated with the set of destination nodes, including one or more lowest cost paths computed when performing the first iteration of computing the lowest cost paths;
receive a navigation request for a route between a particular starting node in the node map and a particular destination node of the set of destination nodes;
generate the requested route based on a particular computed lowest cost path associated with the particular destination node; and
output, in response to the navigation request, the generated route.

### Claim 9 (depends on 8)

The non-transitory computer-readable medium of claim 8, wherein computing the lowest cost paths associated with a particular destination node of the set of destination nodes includes traversing the node map in ascending order of priority.

### Claim 10 (depends on 8)

The non-transitory computer-readable medium of claim 8,
wherein the first iteration of computing lowest cost paths associated with the set of destination nodes includes identifying a first lowest cost path associated with a particular destination node based on a first set of identified costs of outgoing links from the first node to a first set of higher priority neighbors of the first node, and
wherein the second iteration of computing lowest cost paths associated with the set of destination nodes includes identifying a second lowest cost path associated with the particular destination node, that is a lower cost than the first lowest cost path, based on a second set of identified costs of outgoing links from the second node to a second set of higher priority neighbors of the second node.

### Claim 11 (depends on 10)

The non-transitory computer-readable medium of claim 10, wherein the second iteration of computing lowest cost paths associated with the set of destination nodes further includes identifying the second lowest cost path associated with the particular destination node based on the first lowest cost path.

### Claim 12 (depends on 8)

The non-transitory computer-readable medium of claim 8, wherein the plurality of processor-executable instructions further include processor-executable instructions to:
perform a bidirectional search of the node map that includes a forward search from the particular starting node and a backward search from the set of destination nodes, wherein the backward search from the set of destination nodes includes the computing of the lowest cost paths to each node reachable to each destination node of the set of destination nodes.

### Claim 13 (depends on 8)

The non-transitory computer-readable medium of claim 8, wherein adding higher priority neighbors of the first node, which are not in the queue, to the queue includes adding the higher priority neighbors of the first node, which are not in the queue, to the queue in order of ascending priority.

### Claim 14 (depends on 13)

The non-transitory computer-readable medium of claim 13, wherein the plurality of processor-executable instructions further include processor-executable instructions to:
add the second node to the queue;
identify, after adding the second node to the queue and prior to adding the first node to the queue, that the first node is associated with a lower priority than the second node; and
add the first node to the queue, wherein adding the first node to the queue includes placing the first node ahead of the second node in the queue based on identifying that the first node is associated with the lower priority than the second node.

### Claim 15

A method, comprising:
receiving a node map that includes a set of nodes and respective links between nodes, wherein each node is associated with a respective measure of priority and wherein each link is associated with a respective cost;
identifying a set of destination nodes in the node map;
initializing a queue by adding the set of destination nodes to the queue;
computing lowest cost paths to each node reachable to each destination node of the set of destination nodes,
wherein a first iteration of the computing includes, for a first node in the queue:
adding higher priority neighbors of the first node, which are not in the queue, to the queue;
loading, to a memory device, information indicating costs of outgoing links from the first node to the higher priority neighbors of the first node; and
performing a first iteration of computing lowest cost paths associated with the set of destination nodes based on:
the costs of the outgoing links from the first node to the higher priority neighbors of the first node, and
any previously computed lowest cost paths associated with the set of destination nodes,
wherein a second iteration of the computing includes, for a second node that is a next node in the queue with respect to the first node:
loading, to the memory device, information indicating costs of outgoing links from the second node to higher priority neighbors of the second node, without loading the information indicating the costs of outgoing links from the first node to the higher priority neighbors of the first node; and
performing a second iteration of computing lowest cost paths associated with the set of destination nodes based on:
the costs of the outgoing links from the second node to the higher priority neighbors of the second node, and
any previously computed lowest cost paths associated with the set of destination nodes, including one or more lowest cost paths computed when performing the first iteration of computing the lowest cost paths;
receiving a navigation request for a route between a particular starting node in the node map and a particular destination node of the set of destination nodes;
generating the requested route based on a particular computed lowest cost path associated with the particular destination node; and
outputting, in response to the navigation request, the generated route.

### Claim 16 (depends on 15)

The method of claim 15, wherein computing the lowest cost paths associated with a particular destination node of the set of destination nodes includes traversing the node map in ascending order of priority.

### Claim 17 (depends on 15)

The method of claim 15,
wherein the first iteration of computing lowest cost paths associated with the set of destination nodes includes identifying a first lowest cost path associated with a particular destination node based on a first set of identified costs of outgoing links from the first node to a first set of higher priority neighbors of the first node, and
wherein the second iteration of computing lowest cost paths associated with the set of destination nodes includes identifying a second lowest cost path associated with the particular destination node, that is a lower cost than the first lowest cost path, based on:
a second set of identified costs of outgoing links from a second node to a second set of higher priority neighbors of the second node, and
the second lowest cost path associated with the particular destination node based on the first lowest cost path.

### Claim 18 (depends on 15)

The method of claim 15, further comprising:
performing a bidirectional search of the node map that includes a forward search from the particular starting node and a backward search from the set of destination nodes, wherein the backward search from the set of destination nodes includes the computing of the lowest cost paths to each node reachable to each destination node of the set of destination nodes.

### Claim 19 (depends on 15)

The method of claim 15, wherein adding higher priority neighbors of the first node, which are not in the queue, to the queue includes adding the higher priority neighbors of the first node, which are not in the queue, to the queue in order of ascending priority.

### Claim 20 (depends on 19)

The method of claim 19, further comprising:
adding the second node to the queue;
identifying, after adding the second node to the queue and prior to adding the first node to the queue, that the first node is associated with a lower priority than the second node; and
adding the first node to the queue, wherein adding the first node to the queue includes placing the first node ahead of the second node in the queue based on identifying that the first node is associated with the lower priority than the second node.