Method for finding shortest path to destination in traffic network using Dijkstra algorithm or Floyd-warshall algorithm

• US 6,564,145 B2
• Filed: 12/27/2000
• Issued: 05/13/2003
• Est. Priority Date: 12/11/2000
• Status: Active Grant

• Current Assignee: Korea Telecom (KT Corporation)
• Original Assignee: Korea Telecom (KT Corporation)
• Inventors: Lee, Jong-Hyun, Jeong, Youn-Suk, Kim, Hong-Soo
• Primary Examiner(s): NGUYEN, THU V
• Application Number:
  US09/752,324
• Publication Number:
  US 20020059025A1
• Time in Patent Office: 867 Days
• Field of Search: 701/200-203, 701/206, 701/208-210, 340/988-990, 340/995
• US Class Current: 701/209
• 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

Abstract

A method is presented for finding a shortest path from a starting place to a destination place in a traffic network including one or more turn restrictions, one or more U-turns and one or more P-turns using a Dijkstra algorithm. The method as sets a virtual arc between nodes, and assigns a virtual arc value. A smallest travel time value is selected out of total travel time values for all nodes except for the starting node, by considering existing arcs between nodes and the virtual arc and assigning the smallest travel time value to a permanent label node. The shortest path is determined by tracing the permanent nodes starting from the destination node.

Claims

1. A method for finding a shortest path from a starting place to a destination place in a traffic network including one or more turn restrictions, one or more U-turns and one or more P-turns using a Dijkstra algorithm, the method comprising the steps of:

a) selecting a starting node and a destination node in the traffic network, wherein the starting node indicates the starting place and the destination node indicates the destination place;

b) setting a virtual arc between nodes in order to do the U-turn and the P-turn, and assigning a virtual arc value to the virtual arc;

c) selecting a smallest travel time value out of total travel time values for temporary label nodes, which are all nodes except for the starting node, by considering existing arcs between nodes and the virtual arc and assigning the smallest travel time value to a permanent label node which is a node having the smallest travel time value among the temporary label nodes, wherein an existing arc of the turn restriction is excluded from a shortest path; and

d) determining the shortest path by tracing the permanent nodes starting from the destination node.

2. The method as recited in claim 1, wherein the step b) includes the steps of:

b1) when an existing arc, which connects the starting node and the destination node, having an existing arc value already exists in the traffic network, if the virtual arc value is less than the existing arc value, utilizing the virtual arc value for finding the shortest path; and

b2) if the virtual arc value is larger than the existing arc value, utilizing the existing arc value for finding the shortest path.

3. The method as recited in claim 2, wherein the step c) includes the steps of:

c1) assigning a travel time value d_1j from a node 1 to a temporary label node j, wherein the node 1 is the starting node and the temporary label node is a node adjacent to the node 1, to a travel time value π

_j^b from the starting node to the node j;

c2) assigning an infinite value (∞

) as the travel time value d_1j from a node b to the node j if there exists no arc between the node b and the node j, wherein the node b is a previous permanent node of the node j and the starting node is initially assigned as the previous permanent node;

c3) assigning 0 as the travel time value d_1j from the node 1 to a total travel time π

₁* from the starting node to the node 1;

c4) selecting a node i having a shortest travel time value out of all π

_j^b;

assigning a permanent label to the node i;

assigning the π

_j^b to a total time value from the starting node to the permanent label node i π

_i*; and

determining if there exists any temporary label;

c5) if there exists no temporary label, going to the step d);

c6) if there exists any temporary label, modifying travel time value of all temporary label nodes adjacent to the permanent node i;

c7) if a path along nodes b-i-j is the turn-restriction path, excluding the b-i-j path from a candidate shortest path;

c8) if the path along nodes b-i-j is not the turn-restriction path, comparing the π

_j^b with a sum of the π

_i* and a d_ij and selecting the less one of the π

_j^b and the sum, to thereby assign the less one to the π

_j^b, wherein the d_ij represents a travel time value from the permanent node i to a temporary node j adjacent to the i; and

c9) determining whether the π

_j^b is larger than the sum of the π

_i* and the d_ij.

4. The method as recited in claim 3, wherein the step c9) includes the steps of:

c9-1) if the π

_j^b is larger than the sum of the π

_i* and the d_ij, assigning the current permanent node i to the previous permanent node b of the π

_j^b, going to the step c4); and

c9-2) if the π

_j^b is not larger than the sum of the π

_i* and the d_ij, going to the step d).

5. A computer-readable record media storing instructions for performing a method for finding a shortest path from a starting place to a destination place in a traffic network including one or more turn restrictions, one or more U-turns and one or more P-turns using a Dijkstra algorithm, the method comprising the steps of:

a) selecting a starting node and a destination node in the traffic network, wherein the starting node indicates the starting place and the destination node indicates the destination place;

b) setting a virtual arc between nodes in order to do the U-turn and the P-turn, and assigning a virtual arc value to the virtual arc;

c) selecting a smallest travel time value out of total travel time values for temporary label nodes, which are all nodes except for the starting node, by considering existing arcs between nodes and the virtual arc arid assigning the smallest travel time value to a permanent label node which is a node having the smallest travel time value among the temporary label nodes, wherein an existing arc of the turn restriction is excluded from a shortest path; and

d) determining the shortest path by tracing the permanent nodes starting from the destination node.