Computer-implemented systems and methods for planning a route

• US 9,557,182 B2
• Filed: 03/24/2014
• Issued: 01/31/2017
• Est. Priority Date: 12/31/2009
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: MapQuest, Inc. (System1 LLC)
• Inventors: Nesbitt, David W., Jansen, Leonard B.
• Primary Examiner(s): Sam, Phirin
• Application Number:
  US14/223,954
• Publication Number:
  US 20140207376A1
• Time in Patent Office: 1,044 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/126 minimising geographical or physical path length

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

1. 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 located off the travel route, the travel route comprising a route traversed by a user in a geographic region;

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 and one or more roads in the geographic region.

2. The method of claim 1, wherein:

the destination node comprises a point of interest in the geographic region.

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

4. The method of claim 1, 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.

5. The method of claim 1, 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.

6. The method of claim 5, 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.

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

8. The method of claim 7, further comprising:

computing second costs for travelling between the origin nodes and the destination nodes through the at least one intermediate node;

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.

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

10. The method of claim 9, 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.

11. 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 located off the travel route, the travel route comprising a route traversed by a user in a geographic region;

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, and one or more roads in the geographic region.

13. The apparatus of claim 11, 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.

14. The apparatus of claim 11, 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.

15. The apparatus of claim 11, 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.

16. The apparatus of claim 15, 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.

17. The apparatus of claim 11, 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 away from the travel route.

18. The apparatus of claim 17, wherein the at least 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;

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.

19. The apparatus of claim 11, 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.

12. The apparatus of 11, wherein:

the destination node comprises a point of interest in the geographic region.

20. 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 located off the travel route, the travel route comprising a route traversed by a user in a geographic region;

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 and one or more roads in the geographic region.