# US 2014/0207376 A1 · Computer-implemented systems and methods for planning a route

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

- Number: US 2014/0207376 A1
- Document ID: US20140207376A1
- Status: Published application
- Kind: A1
- Application number: 14/223,954
- Filed: 2014-03-24
- Published: 2014-07-24
- Earliest claimed: 2009-12-31
- Assignees: MapQuest, Inc.
- Applicants: MapQuest, Inc.
- Inventors: David W. NESBITT; Leonard B. Jansen
- Web page: https://patentgrep.com/patent/US20140207376A1

## CPC

- H04L 45/00: Routing or path finding of packets in data switching networks (routing or path finding in wireless networks H04W40/00)
- G01C 21/34: Route searching; Route guidance
- H04L 45/12: Shortest path evaluation
- H04L 45/126: {minimising geographical or physical path length}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- 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

Systems and methods are disclosed for determining shortest route(s) or path(s) to one or more destination nodes from one or more origin nodes. In accordance with one implementation, a computer-implemented method is provided that includes identifying a plurality of origin nodes associated with a route based on a threshold distance from at least one destination node, the origin nodes being options for a departure from the route to the at least one destination node. Further, the method may include calculating, using a processor, a cost associated with travelling from each of the origin nodes to at least one common intermediate node between the route and the at least one destination node, and determining a path to the at least one destination node based on the origin node having the lowest calculated cost.

## Claims

### Claim at position 1

1-19. (canceled)

### Claim 20

A computer-implemented method, the method comprising the following operations performed by at least one processor:
obtaining information identifying origin nodes disposed along a travel route, the origin nodes providing options for departing from the travel route to a destination node;
computing first costs for travelling between the origin nodes and the destination node through at least one intermediate node;
identifying a corresponding one of the origin nodes associated with a minimum of the computed first costs; and
determining a path between the corresponding origin node and the destination node, the determined path comprising the at least one intermediate node.

### Claim 21 (depends on 20)

The method of claim 20, wherein:
the travel route comprises a route traversed in a geographic region;
the destination node comprises a point of interest in the geographic region; and
the determined path comprises one or more roads in the geographic region.

### Claim 22 (depends on 20)

The method of claim 20, further comprising generating one or more electronic instructions to transmit information identifying the determined path to a communications device associated with a user.

### Claim 23 (depends on 20)

The method of claim 20, wherein:
the method further comprises identifying one or more of the origin nodes disposed within a threshold distance of the travel route; and
the computing comprises computing the first costs for travelling between the identified origin nodes and the destination node through the at least one intermediate node.

### Claim 24 (depends on 20)

The method of claim 20, wherein determining the path comprises determining a shortest path from the travel route to the destination node, the shortest path comprising the corresponding origin node and the intermediate node.

### Claim 25 (depends on 24)

The method of claim 24, wherein determining the shortest path comprises applying Dijkstra's algorithm to at least the corresponding origin node, the intermediate node, and the destination node to determine the shortest path.

### Claim 26 (depends on 20)

The method of claim 20, further comprising obtaining information identifying a plurality of destination nodes, the destination nodes being disposed within a threshold distance of the travel route.

### Claim 27 (depends on 26)

The method of claim 26, further comprising:
computing second costs for travelling between the origin nodes and the destination nodes through the at least one intermediate node; and
identifying, for the destination nodes, corresponding origin nodes associated with a minimum of the computed second costs; and
determining shortest paths between the corresponding origin nodes and the destination nodes, the shortest paths comprising the at least one intermediate node.

### Claim 28 (depends on 20)

The method of claim 20, further comprising obtaining information identifying a plurality of intermediate nodes disposed between the travel route and the destination node.

### Claim 29 (depends on 28)

The method of claim 28, wherein the computing comprises computing the first costs for travelling between the origin nodes and the destination node through corresponding subsets of the intermediate nodes.

### Claim 30

An apparatus, comprising:
a storage device that stores a set of instructions; and
at least one processor coupled to the storage device and operative with the set of instructions to:
obtain information identifying origin nodes disposed along a travel route, the origin nodes providing options for departing from the travel route to a destination node;
compute first costs for travelling between the origin nodes and the destination node through at least one intermediate node;
identify a corresponding one of the origin nodes associated with a minimum of the computed first costs; and
determine a path between the corresponding origin node and the destination node, the determined path comprising the at least one intermediate node.

### Claim 31

The apparatus of 30, wherein:
the travel route comprises a route traversed in a geographic region;
the destination node comprises a point of interest in the geographic region; and
the determined path comprises one or more roads in the geographic region.

### Claim 32 (depends on 30)

The apparatus of claim 30, wherein the at least one processor is further operative to generate one or more electronic instructions to transmit information identifying the determined path to a communications device associated with a user.

### Claim 33 (depends on 30)

The apparatus of claim 30, wherein the at least one processor is further operative to:
identify one or more of the origin nodes disposed within a threshold distance of the travel route; and
compute the first costs for travelling between the identified origin nodes and the destination node through the at least one intermediate node.

### Claim 34 (depends on 30)

The apparatus of claim 30, wherein the at least one processor is further operative to determine a shortest path from the travel route to the destination node, the shortest path comprising the corresponding origin node and the intermediate node.

### Claim 35 (depends on 34)

The apparatus of claim 34, wherein the at least one processor is further operative to apply Dijkstra's algorithm to at least the corresponding origin node, the intermediate node, and the destination node to determine the shortest path.

### Claim 36 (depends on 30)

The apparatus of claim 30, wherein the at least one processor is further operative to obtain information identifying a plurality of destination nodes, the destination nodes being disposed within a threshold distance of the travel route.

### Claim 37 (depends on 36)

The apparatus of claim 36, wherein the at east one processor is further operative to:
compute second costs for travelling between the origin nodes and the destination nodes through the at least one intermediate node; and
identify, for the destination nodes, corresponding origin nodes associated with a minimum of the computed second costs; and
determine shortest paths between the corresponding origin nodes and the destination nodes, the shortest paths comprising the at least one intermediate node.

### Claim 38 (depends on 30)

The apparatus of claim 30, wherein the at least one processor is further operative to;
obtain information identifying a plurality of intermediate nodes disposed between the travel route and the destination node; and
compute the first costs for travelling between the origin nodes and the destination node through corresponding subsets of the intermediate nodes.

### Claim 39

A tangible, non-transitory computer-readable medium storing instructions that, when executed by at least one processor, cause the at least one processor to perform a method comprising:
obtaining information identifying origin nodes disposed along a travel route, the origin nodes providing options for departing from the travel route to a destination node;
computing costs for travelling between the origin nodes and the destination node through at least one intermediate node;
identifying a corresponding one of the origin nodes associated with a minimum of the computed first costs; and
determining a path between the corresponding origin node and the destination node, the determined path comprising the at least one intermediate node.
