Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
2000-08-07
2001-07-17
Cuchlinski, Jr., William A. (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
C701S208000, C701S210000, C701S211000, C701S212000, C340S988000, C340S990000
Reexamination Certificate
active
06263277
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a method of searching for routes and more particularly to a route searching method used with a navigation apparatus for determining an optimal route leading to a chosen destination.
An on-vehicle navigation apparatus detects the position of the vehicle, reads map data around the vehicle position from a map storage medium such as a DVD, and depicts the map on a display screen with a vehicle position marker superimposed at the vehicle's location on the map. The map can be scrolled as the vehicle moves forward while the vehicle position mark is fixed in a specific position, such as the center of the screen, and the map surrounding the vehicle's position can be viewed at a glance. In such an on-vehicle navigation apparatus, a route searching function may be provided to search out a route to enable travel from a starting point to a destination. It can determine the route, for example, taking the shortest time or the shortest distance, and display the route on the screen, thereby providing the vehicle driver with a driving guide. In such a route guiding function, the particular route is displayed with a thick, colored line during the actual driving, so that it can be distinguished from the other roads, allowing the driver to reach the destination easily. As the methods for searching out the guided route, along which the vehicle travels, from road map data, there are known the Dijkstra method, the A* algorithm, and the like.
The user of a route-searching navigation apparatus is not only concerned with the quality of the route, but also with the time necessary to produce it. An ideal navigation apparatus would be capable of solving a routing problem with faster speed and better quality. However, the quality of the solution and the time required for the search are generally in an inverse relationship. Practically speaking, a solution which is close to the optimum solution, obtained quickly, is more useful than finding the best solution with a longer searching time. The Dijkstra method or the A* algorithm, two commonly known methods, are able to provide an optimum path, but the broad range of the search increases the time that it takes. When the starting point is distant from the destination or the road network is dense, the optimal route searching time becomes even longer, as the number of intersections and links has become larger.
SUMMARY OF THE INVENTION
An object of the present invention is to make the selection of major roads, such as freeways, easier when there is a greater distance to a destination, even if the actual distance traveled is slightly extended.
Another object of the present invention is to make it possible to search for a close to optimal route to a destination in a short time.
A further object of the present invention is to make it possible to search out a close to optimal route to a destination, taking into account the time it takes to cross an intersection.
According to the present invention, the above mentioned objects can be attained by a method of route searching comprising the steps of: (1) producing map information by storing link information, including the nodes on both ends of a link, the link length, the speed limit in the link, and the functional class of the link; (2) in making the route search, correcting the speed limit in the link on the basis of both the straight line distance from the nodes of the examined link to the destination and the functional class of the link; (3) calculating the time for passing through the link with the corrected speed limit and the link length; and, (4) searching out the route required to reach a destination on the basis of the link passage time while minimizing the time required.
According to the present invention, the above mentioned objects can be attained by a method of route searching further comprising the steps of: (1) performing a route search from the starting point towards the destination by using links of the same functional class as the functional class of the link to which the start point belongs until a higher class link is reached; (2) performing a similar route search from the destination towards the starting point by using links of the same functional class as the functional class of the link to which the destination belongs until a higher class link is reached; (3) setting the node of the higher class link reached in the search from the start point as a new starting point and setting the node of the higher class link reached in the search from the destination as a new destination; (4) repeating the search, using the higher class links; and (5) connecting the routes when the two paths meet, thereby forming a guided route.
According to the present invention, the above mentioned objects can be attained by the method of route searching further comprising the steps of: (1) estimating the time for passing through a node by considering the functional class of an intersecting road and the vehicle's own link; and (2) correcting the link passing time by adding in the node passing time.
Other features and advantages of the present invention will be apparent from the following description of the invention, taken in conjunction with the accompanying drawings.
REFERENCES:
patent: 4926336 (1990-05-01), Yamada
patent: 5031104 (1991-07-01), Ikeda et al.
patent: 5036471 (1991-07-01), Tamura et al.
patent: 5638280 (1997-06-01), Nishimura et al.
patent: 6049753 (2000-04-01), Nimura
patent: 6134501 (2000-10-01), Oumi
Endo Koichi
Hayes David
Tanimoto Satoshi
Alpine Electronics Inc.
Arthur Gertrude
Brinks Hofer Gilson & Lione
Cuchlinski Jr. William A.
LandOfFree
Route searching 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 searching method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Route searching method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2493710