Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
2000-03-07
2002-02-19
Nguyen, Tan (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
C701S202000, C701S208000, C340S995190
Reexamination Certificate
active
06349261
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a computer system for determining a minimum-cost route from a start location to a target location between which a person travels by walking and using a transportation network, such as a public transportation network.
2. Description of the Related Art
An optimal route is difficult to determine in a complicated traffic network. Further, optimization must be effected in consideration of various factors such as time and cost. Theoretically, a computer can determine an optimal route through calculation performed for all possible combinations. However, when the traffic network becomes complicated, calculation time Increases drastically, even when a high-performance computer is used, so that calculation becomes impossible to complete.
In order to avoid such a problem of calculation becoming impossible to complete, various methods have been proposed. A label determination method—which is used in a computer to determine a shortest route within a traffic network—reduces computer processing time and provides a quick solution. The label determination method is sometimes called the Dijkstra method, after its inventor. Japanese Patent Application Laid-Open (kokal) Nos. 10-275296 (Navigation Method and System), 10-253376 (Method and System for Determining a Minimum-Cost Route), and 11-44547 (Method and System for Determining a Minimum-Cost Route) each disclose a method of determining a route in a traffic network by use of the label determination method.
An exemplary system which is represented by means of a network as shown in
FIG. 1
will be described. Each of black circles in
FIG. 1
corresponds to a specific location and is called a “node.” A line connecting adjacent nodes corresponding to respective locations is called a “link.” Mathematically, a set including the nodes and links is called a “graph.” When the links have orientation, the graph is called a “directed graph,” and when the links have no orientation, the graph is called an “undirected graph.”
FIG. 1
shows an exemplary directed graph. A shortest route problem is a problem of finding a shortest route among routes between a start location node s to a target location node t within a network such as the above-described network.
Here, a shortest route P from node s to node t is represented as follows.
P={s, i, J, . . . , k, t}
In this case, when the route P is divided at a certain node into routes P1 and P2, each of the routes P1 and P2 represents the shortest route within a corresponding set. This is called the principle of optimality. The label determination method is an algorithm for mathematically determining the shortest route by use of the principle. That is, the label determination method starts with an empty set. Each node is labeled with a temporary label, and nodes which constitute the shortest route are determined node-by-node in order to expand a shortest-route subset. Finally, all the nodes are labeled with permanent labels. Thus, the shortest route is determined. The following is an algorithm used for programming computers.
When a set of all nodes present between node s and node t is represented by V, the length of the shortest route from node s to node j is represented by d(j), a set of nodes for the shortest route (hereinafter referred to as a “shortest route node set”) is represented by S1, and its complementary set is represented by S2 (=V−S), the shortest route is determined as follows.
(1) The following initialization is performed.
S1←0 (empty set), S2←V,
d(s)←0, d(i)←∞
Here, i represents a node in the complementary set S2, and X←Y represents an operation of replacing X with Y.
(2) If S1=V, then calculation is ended.
(3) If S1≠V, then
the shortest route length d(i) is selected, and
replacement v←i is effected.
Since the length d(v) represents the length of the shortest route from node s to node v, node v is included in the shortest route node set S1, and is excluded from the complementary set S2.
(4) For each node i which is contained in the complementary set S2 and to which a link extending from node V (outgoing link) reaches next, the following calculation is performed.
d′(i)←d(v)+avi
If d(i)>d′(i), then
d(i)←d′(i) and p(i)←v.
Here, avi represents the length of a link from node v to node i, and d(i) and d′(i) each represent the length of a route from the start location s to node i. The value d(i) at this point represents the shortest route length which is formed by nodes within the shortest route node set S1. There is a possibility that the complementary set S2 includes a node that provides a shorter route. However, such a shorter route would be found during repeated calculation.
(5) Processing returns to step (2) above.
When the thus-obtained p(i) is followed in reverse order from the final node t on the basis of p(t), the shortest route from the start node s is obtained. For example, when the above-described algorithm is applied to the example shown in
FIG. 1
, the following is obtained.
d(1) = 0
d(2) = 50
d(3) = 70
d(4) = 65
d(5) = 85
p(2) = 1
p(3) = 2
p(4) = 2
p(5) = 3
Since s=1 and t=5, node 3 is determined to precede node 5, because p(5)=3; node 2 is determined to precede node 3, because p(3)=2; and node 1 is determined to precede node 2, because p(2)=1, so that the start location s is reached. That is, the shortest route is 1→2→3→5, and the length thereof is 85 (=d(5)). Further, the route (1→2→4) from node 1 to node 4 also has a short route length d(4).
When determination of the route of
FIG. 1
is actually simulated by use of the above-described algorithm, it is found that calculation of the length d′(4) from node 3 to node 4 is not required. That is, the label determination method involves a drastic reduction in the amount of calculation as compared with a case in which the shortest route is calculated through use of all combinations.
The above-described label determination method can be applied to determination of a route from a certain station to a target station within a public transportation network. In this case, the shortest route is determined in consideration of not only distance but also time and fare, which are generally referred to as cost.
The label determination method realizes high-speed processing when performed by use of a computer. Especially, when a start location and a target location are predetermined, the label determination method starts route determination from the start location in order to successively find nodes that minimize cost, and determines the route that reaches the target location with minimum cost. The cost to be considered is time or distance, and therefore, “travel time” or “travel distance” is evaluated.
In many navigation systems manufactured to date, the label determination method is frequently used when route determination is performed with an objective of attaining to minimum cost. Examples of such minimum-cost-route determination include a system for determining a minimum-cost route in a railroad network and a system for determining a minimum-cost route in a road network.
However, no conventional navigation system can determine a route along which a person travels by walking and using a transportation network. For example, a navigation system designed for a railroad network does not take into consideration a station to which a person walks from a start location (a station where the person enters the railroad network, hereinafter called an “entrance station”) or how long the person takes to reach a target location from a station where the person exits the railroad network (hereinafter called an “exit station”). Therefore, such a navigation system starts route determination after a person designates the station closest to the start location and the station closet to the target location. Therefore, the navigation sys
Kikuchi Shin
Ohnishi Keisuke
Navitime Japan Co., Ltd.
Nguyen Tan
Oblon & Spivak, McClelland, Maier & Neustadt P.C.
Tran Dalena
LandOfFree
Method and apparatus for determining route within traffic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for determining route within traffic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for determining route within traffic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2944998