System for determining a route and presenting navigational instructions therefor

• US 6,480,785 B1
• Filed: 09/06/2000
• Issued: 11/12/2002
• Est. Priority Date: 09/06/2000
• Status: Expired due to Term

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Vindigo, Inc. (Forside Co., Ltd.)
• Inventors: Joerg, David S., McAuliffe, Jon D.
• Primary Examiner(s): NGUYEN, TAN QUANG
• Application Number:
  US09/655,818
• Time in Patent Office: 797 Days
• Field of Search: 701/209, 701/201, 701/202, 701/204, 701/205, 701/210, 701/211, 340/990, 340/995
• US Class Current: 701/209
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

A system for determining a route and presenting navigational instructions therefor preferably includes a plurality of map records including a plurality of business records each identifying a business, a plurality of street records each identifying a street, and a plurality of node records each identifying a node. The system preferably further includes a computation module adapted to execute an algorithm for determining a route between a source location and a destination location using at least one of the map records. The algorithm is preferably adapted to manipulate a graph representation having vertices and edges, wherein each of the vertices corresponds to a respective one of the streets, each of the streets corresponds to exactly one of the vertices, each node corresponds to at least one of the edges, and each edge corresponds to exactly one node.

Claims

1. A system for determining a route, comprising a computation module adapted to:

a) receive source location information and use said source location information to identify a source location and a source street associated with said source location;

b) receive destination location information and use said destination location information to identify a destination location and a destination street associated with said destination location; and

c) execute an algorithm for determining a route between said source location and said destination location, said route comprising a desired solution path;

wherein;

i) when at least two of a plurality of possible routes between said source location and said destination location require an identical minimum number of street changes, said algorithm is biased toward determining said route as a shortest route of said at least two of said routes;

d) wherein said algorithm manipulates a graph representation having a plurality of vertices and a plurality of edges;

e) each of said edges represents an adjacency between two of said vertices;

f) said algorithm initially;

i) designates a source vertex from said vertices, said source vertex representing a beginning street, said beginning street being one of said source street and said destination street,

ii) designates a destination vertex from said vertices, said destination vertex representing an ending street, said ending street being the other of said source street and said destination street,

iii) designates said source vertex as seen,

iv) designates each remaining vertex as unseen, and

v) places said source vertex in a head position of a first-in-first-out queue;

g) said algorithm thereafter executes a loop while said destination vertex is designated as unseen and said queue is not empty, in which said algorithm;

i) when all vertices adjacent to said head-positioned vertex are seen;

1) removes said head-positioned vertex from said queue, and

2) when a next vertex is next in said queue, places said next vertex in said head position;

ii) when at least one vertex adjacent to said head-positioned vertex is designated as unseen;

1) considers in a consideration order each unseen vertex adjacent to said head-positioned vertex, and

2) after all of said unseen vertices adjacent to said head-positioned vertex have been considered;

a) removes said head-positioned vertex from said queue, and

b) when a next vertex is next in said queue, places said next vertex

in said head position;

h) each of said vertices cannot be simultaneously designated as both seen and unseen; and

i) said consideration order biases said algorithm toward determining said.

2. The system of claim 1, wherein said consideration of each unseen vertex adjacent to said head-positioned vertex comprises in the alternate and thereafter terminates:

a) when said vertex under consideration is said destination vertex;

i) designating said head-positioned vertex as a predecessor of said destination vertex,

ii) determining a ratio of a distance along a candidate route between said source location and said destination location, said candidate route comprising a current candidate solution path between said beginning street and said ending street, to a distance along a straight line route between said source location and said destination location, and

iii) when said ratio is lower than a desired ratio;

(1) designating said current candidate solution path as said desired solution path, and

(2) designating said destination vertex as seen; and

b) when said vertex under consideration is not said destination vertex;

i) designating said vertex under consideration as seen after said vertex under consideration has been considered,

ii) designating said head-positioned vertex as a predecessor of said vertex under consideration, and

iii) placing said vertex under consideration in a tail position of said queue after said head-positioned vertex has been designated as said predecessor.

3. The system of claim 2, wherein said desired ratio is approximately 2:

1.

4. The system of claim 1, wherein said consideration of each unseen vertex adjacent to said head-positioned vertex comprises in the alternate and terminates otherwise:

a) when said vertex under consideration is said destination vertex and a previous candidate solution path between said beginning street and said ending street has not been designated;

i) designating said head-positioned vertex as a predecessor of said destination vertex,

ii) designating a current candidate solution path between said beginning street and said ending street as said previous candidate solution path, and

iii) terminating consideration of said vertex under consideration;

b) when said vertex under consideration is said destination vertex and said previous candidate solution path has been designated, comparing a distance along another current candidate solution path between said beginning street and said ending street with a distance along said previous candidate solution path, and terminating consideration of said vertex under consideration when not;

i) when said distance along said other current candidate solution path is shorter than said distance along said previous candidate solution path, comparing a number of vertices in said other current candidate solution path with a number of vertices in said previous candidate solution path, and performing in the alternate and otherwise terminating consideration of said vertex under consideration;

(1) when said number of vertices in said other current candidate solution path equals said number of vertices in said previous candidate solution path;

(a) designating said head-positioned vertex as a predecessor of said destination vertex,

(b) designating said other current candidate solution path as said previous candidate solution path, and

(c) terminating consideration of said vertex under consideration;

(2) when said number of vertices in said other current candidate solution path is a minimum number of vertices greater than said number of vertices in said previous candidate solution path, determining a ratio of said distance along said other current candidate solution path to said distance along said previous candidate solution path, and terminating consideration of said vertex under consideration when not;

(a) when said ratio is lower than a desired ratio;

(i) designating said head-positioned vertex as a predecessor of said destination vertex,

(ii) designating said other current candidate solution path as said previous candidate solution path, and

(iii)terminating consideration of said vertex under consideration; and

(3) when said number of vertices in said other current candidate solution path is a maximum number of vertices greater than said number of vertices in said previous candidate solution path, designating said previous candidate solution path as said desired solution path, designating said destination vertex as seen and terminating consideration of said vertex under consideration; and

c) when said vertex under consideration is not said destination vertex;

i) designating said vertex under consideration as seen after said vertex under consideration has been considered,

ii) designating said head-positioned vertex as a predecessor of said vertex under consideration,

iii) placing said vertex under consideration in a tail position of said queue after said head-positioned vertex has been designated as said predecessor, and

iv) terminating consideration of said vertex under consideration.

5. The system of claim 4, wherein said minimum number is 1, said maximum number is 2 and said desired ratio is 0.7:

1.

6. The system of claim 1, wherein said consideration of each unseen vertex adjacent to said head-positioned vertex comprises:

a) designating said vertex under consideration as seen,

b) designating said head-positioned vertex as a predecessor of said vertex under consideration,

c) placing said vertex under consideration in a tail position of said queue after said head-positioned vertex has been designated as said predecessor, and

d) terminating consideration of said vertex under consideration.

7. The system of claim 6, wherein said consideration order is established by:

a) each unseen vertex adjacent to said head-positioned vertex having associated therewith a position in a connection order relative to said head-positioned vertex;

b) pairing a first unconsidered vertex of said unseen vertices adjacent to said head-positioned vertex and, when available, a second unconsidered vertex of said unseen vertices adjacent to said head-positioned vertex,

i) said first unconsidered vertex being an unconsidered vertex next in one of increasing connection order position and decreasing connection order position from an entrance connection order position,

ii) said second unconsidered vertex being an unconsidered vertex next in the other of increasing connection order position and decreasing connection order position from the entrance connection order position, and

iii) said entrance connection order position being;

(1) when said head-positioned vertex is said source vertex, a connection order position corresponding to a connection order position, relative to said head-positioned vertex, of a vertex adjacent to said head-positioned vertex; and

(2) when said head-positioned vertex is not said source vertex, a connection order position, relative to said head-positioned vertex, of said predecessor vertex of said head-positioned vertex;

c) ordering according to a preference order said first unconsidered vertex and, when available, said second unconsidered vertex; and

d) enqueing for consideration, according to said preference order, at least one of said first unconsidered vertex and said second unconsidered vertex.

8. The system of claim 7, wherein enqueing comprises enqueing for consideration, according to said preference order, both said first unconsidered vertex and said second unconsidered vertex.

9. The system of claim 7, wherein said preference order is:

a) established by;

i) said head-positioned vertex having associated therewith an entrance intersection, said entrance intersection being intersected by a street represented by said head-positioned vertex;

ii) each of said first unconsidered vertex and, when available, said second unconsidered vertex having associated therewith;

(1) a respective vertex intersection, each of said respective vertex intersections being an intersection of;

(a) a street represented by said respective unconsidered next vertex, and

(b) said street represented by said head-positioned vertex; and

(2) a respective straight line distance from said respective vertex intersection to said entrance intersection; and

b) according to the shorter of said straight line distances.

10. The system of claim 7, wherein said preference order is:

a) established by each of said first unconsidered vertex and, when available, said second unconsidered vertex having associated therewith;

i) a respective vertex intersection, each of said respective vertex intersections being an intersection of;

(1) a street represented by said respective unconsidered next vertex, and

(2) a street represented by said head-positioned vertex; and

ii) a respective straight line distance from said respective vertex intersection to one of;

(1) said source location, when said ending street is said source street, and

(2) said destination location, when said ending street is said destination street; and

b) according to the shorter of said straight line distances.

11. The system of claim 7, wherein said connection order positions are established by:

a) a street represented by said head-positioned vertex having associated therewith a first end and a second end;

b) each vertex adjacent to said head-positioned vertex having associated therewith;

i) a respective vertex intersection, each of said respective vertex intersections being an intersection of;

(1) a street represented by said respective vertex adjacent to said head-positioned vertex and

(2) said street represented by said head-positioned vertex; and

ii) a respective distance from said respective vertex intersection to one of said first end and said second end along said street represented by said head-positioned vertex; and

c) ordering said vertices adjacent to said head-positioned vertex according to increasing said respective distances.

12. The system of claim 11, wherein ordering according to increasing said respective distances comprises assigning a numerical value to each of said connection order positions to indicate a connection order position of each of said vertices adjacent to said head-positioned vertex relative to one another.