Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
1997-12-15
2001-02-27
Cuchlinski, Jr., William A. (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
C701S023000, C701S201000, C701S206000, C701S210000, C340S988000
Reexamination Certificate
active
06195611
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is directed to a route search method.
2. Background of the Invention
In a route search of an electronic map, that is, in order to find a route from a departure point to a destination point (the route is, hereinafter, referred to as a specific route), Dijkstra's method has been widely used. However, according to this method, search is made in all directions from the departure point including a direction not related to the specific route, which reduces computational efficiency.
On the other hand, there are also well-known techniques for limiting a search area, or for making a directional search so that unnecessary search is omitted and almost the shortest specific route can be found for a short time. The former technique is, for example, adopted into the Japanese Patent Laid-Open Gazette No. 63-20700, while the latter, for example, into the Japanese Patent Laid-Open Gazettes Nos. 4-280287 and 2-260000.
In the route search method for limiting the search area, an area including the departure point and the destination point is set so that only the area is searched excluding an area unlikely to be included in the specific route. In the directional route search, orientation or distance to the destination point are examined whenever the route is branched at a node. Thus, the branch approaching closer to the destination point is always selected to search the specific route.
However, in the route search method for limiting the search area, the route may expand to the outside of the search area and cannot be searched. Such an example is schematically shown in FIG.
20
. Though a departure point S and a destination point E are both included in a limited search area Q, a specific route R goes beyond the search area Q due to the presence of a bay therebetween. Thus, in this route search, it is necessary to set the search area large enough to include any mountains regions or bays between the departure point S and the destination point E. The search of such an area, however, increases the amount of data to be processed, and reduces computational efficiency.
In the directional route search, since the search area is not limited, geographical features between the departure point and the destination point, such as mountains regions and bays, have no influence on the search. However, in this method, the search may end as soon as the first route to the destination point is found without thoroughly reviewing other routes, or the search may take considerably a long time, not easily reaching the destination point.
SUMMARY OF THE INVENTION
A first aspect of the present invention is directed to a route search method for searching a plurality of nodes linked with each other for a specific route from a departure point to a destination point, the plurality of nodes including the departure point and the destination point. The route search method comprises: a judging step of judging which of the plurality of nodes is adopted into the specific route in an search area including the departure point and the destination point, the judging step being repeated when the search area is updated, wherein the search area after updated includes the search area before updated.
Preferably, according to a second aspect of the present invention, in the route search method, the judging step includes the steps of: (a) selecting an expansion node out of the plurality of nodes included in the search area; (b) selecting a node linked with the expansion node as a node ahead of the link, regardless of inside and outside the search area; (c) finding a distance from the departure point via the expansion node to the node ahead of the link; (d) adopting a shorter one of the distances as the accumulated total distance to a first node ahead of the link, when the node ahead of the link obtained by the step (b) is common to the first node ahead of the link with a different expansion node, every time the step (c) is performed on the different expansion node; and (e) finding the specific route by linking the expansion node giving the accumulated total distance adopted in the step (d), wherein at least the steps (a) and (b) is performed on a node which has not been adopted as the expansion node yet.
According to a third aspect of the present invention, in the route search method, the steps (a) and (b) is performed also on a node which has already been adopted as the expansion node.
A fourth aspect of the present invention is related to a route search method for searching a plurality of nodes linked with each other for a specific route from a departure point to a destination point, the plurality of nodes including the departure point and the destination point. The route search method comprises: a judging step of judging which of the plurality of nodes is adopted into the specific route in a search area including the departure point and the destination point, wherein the search area is in the form of an ellipse focusing the departure point and the destination point.
In the route search method of the first aspect, search is at first made in a small limited search area. Thus, a straight specific route connecting the departure point and the destination point, if existing, can be found for a short time, which can complete the process at high speed. Further, even if including geographical features such as mountains regions and bays, the search area can be extended until including the specific route within its range. Thus, the specific route can be found in such a condition. Since the search area is extended only when few node is included between the departure point and the destination point because of, for example, geographical features such as mountains regions and bays, the extension of the search area would hardly increase the amount of data to be processed. Thus, the process can be performed relatively at high speed.
Moreover, since the search area is modified sequentially by the extension in this route search, the shorter route is very likely to be searched, compared to the directional route search in which the search area is not limited.
In the route search method of the second aspect, the distance from the departure point via the expansion node to the first node ahead of the link is found, and the expansion nodes giving the shortest distance are linked with each other to find the specific route. Thus, at least the specific route found by this method cannot be the longest one within the searched range.
In the route search method of the third aspect, if another expansion node further shortening the accumulated total distance is found on the way the expansion nodes are linked with each other from the departure point to find the specific route, the specific route which has already been found is even modified. Thus, the specific route found by this method can be the shortest one at least within the searched range.
In the route search method of the fourth aspect, as long as the search area includes the relay points connecting the departure point and the destination point by straight routes, respectively, even if the relay points are on the opposite side to the destination point viewed from the departure point or on the opposite side to the departure point viewed from the destination point, the sum of the distances of those routes becomes not more than a certain value. That is, the specific route taking the accumulated total distance of not more than a predetermined value can be found by defining the search area as a predetermined size of an ellipse and then searching the area for the route including the relay points.
The object of the present invention is to find the shortest route from the departure point to the destination point for a short processing time.
These and other objects, features, aspects and advantages of the present invention will become more apparent from the following detailed description of the present invention when taken in conjunction with the accompanying drawings.
REFERENCES:
patent: 5475598 (1995-12-01), Fushimi et al.
patent: 5506779 (1996-0
Hayashi Yukio
Sakamoto Tadashi
Arthur Gertrude
Burns Doane , Swecker, Mathis LLP
Cuchlinski Jr. William A.
Mitsubishi Denki & Kabushiki Kaisha
LandOfFree
Route search method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Route search method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Route search method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2579655