AUTOMATED ROUTE DETERMINATION

• US 20140129141A1
• Filed: 01/13/2014
• Published: 05/08/2014
• Est. Priority Date: 08/29/2002
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: MapQuest, Inc. (Apollo Global Management, Inc.)
• Inventors: NESBITT, David W.
• Granted Patent: US 10,551,203 B2
• Time in Patent Office: Days
• US Class Current: 701/533
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• 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/3453 Special cost functions, i.e. other than distance or default speed limit of road segments

Abstract

A preferred route may be determined from an origin location to a destination location. The determination is made by processing directed links (e.g., one-way edges) in a graph that includes one or more links and two or more nodes. The determination of a preferred route may include an estimate of the time required at one or more intersections along alternative. Individual routing preferences, such as a preference of a rural over an urban route, also may be considered. Techniques are described that may help reduce the time required to identify a preferred route, including the identification and removal of no outlet routes before processing the directed links and techniques using particular data formats.

Claims

1-39. -39. (canceled)

40. A computer system for determining a recommended route, the system comprising:

a memory having processor-readable instructions stored therein; and

a processor configured to access the memory and execute the processor-readable instructions, which when executed by the processor configures the processor to perform a plurality of functions, including functions to;

access an origin and a destination in a routing graph representing a network of roads, the routing graph including a plurality of links, each link joining two nodes,

identify a link, among the plurality of links, that leads to a no-outlet region,

determine a recommended route from the origin to the destination based on excluding routing graph, the link that leads to the no-outlet region from the, and

communicate the recommended route to a user.

41. The computer system of claim 40, wherein the recommended route is a route for driving a vehicle from the origin to the destination.

42. The computer system of claim 40, wherein the recommended route is a route for walking from the origin to the destination.

43. The computer system of claim 40, wherein the computer system comprises a routing system provided through a network.

44. The computer system of claim 43, wherein the processor is further configured to communicate the recommended route over a network.

45. The computer system of claim 40, wherein the no-outlet region is a dead-end.

46. The computer system of claim 40, wherein the processor is further configured to determine a waiting time required at one or more intersections along alternative routes.

47. The computer system of claim 40, wherein the processor is further configured to process routing preferences received from a user.

48. The computer system of claim 47, wherein the routing preferences comprise avoiding an urban route or an rural route.

49. The computer system of claim 40, wherein the processor is further configured to calculate a cost associated with travelling along each of the plurality of links.

50. The computer system of claim 49, wherein a link having a left exit has a higher cost than a link having a right exit.

51. The computer system of claim 40, wherein the recommended route is based on shortest travel time.

52. A computer system for determining a preferred route, the system comprising:

a memory having processor-readable instructions stored therein; and

a processor configured to access the memory and execute the processor-readable instructions, which when executed by the processor configures the processor to perform a plurality of functions, including functions to;

utilize a routing system to access an origin and a destination in a routing graph representing a network of roads and including two or more nodes and one or more links,

determine that a first link is included among a set of multiple links in a no-outlet region, wherein the set of multiple links can be exited only by traversing the first link used to enter the set of multiple links,

utilize the routing system to determine a preferred route from the origin to the destination, wherein the routing system excludes the first link based on the determination that the first link is included among the set of multiple links which can be exited only by traversing the first link used to enter the set of multiple links, and

communicate the preferred route from the routing system to a user.

53. The computer system of claim 52, wherein the processor is further configured to access the routing system through a network.

54. The computer system of claim 53, wherein the processor is further configured to communicate the preferred route over the network.

55. The computer system of claim 52, wherein the no-outlet region is a dead-end.

56. The computer system of claim 52, wherein the processor is further configured to determine a waiting time required at one or more intersections along alternative routes.

57. The computer system of claim 52, wherein the processor is further configured to process routing preferences received from a user

58. A computer-implemented method for determining a recommended route, the method comprising:

accessing an origin and a destination in a routing graph representing a network of roads, the routing graph including a plurality of links, each link joining two nodes;

receiving route preference input from a user;

identifying a link, among the plurality of links, that leads to a no-outlet region;

determining a recommended route from the origin to the destination based on excluding the link that leads to the no-outlet region from the routing graph; and

communicating the recommended route to the user.

59. The computer-implemented method of claim 58, further comprising calculated a cost associated with each of the plurality of links.