JPH0783675A - Vehicle route guidance device - Google Patents

Abstract

(57) [Summary] [Purpose] After setting the destination, promptly search for the optimum route and start guiding the passengers. [Configuration] Vehicle stop detection means 2 for detecting a substantially stopped state of a vehicle
03, a first route searching means 204 for searching the road map data of the road map storage means 200 to search for an optimum route from the current position to each intersection around the vehicle when the substantially stopped state of the vehicle is detected, A data selection unit 205 that selects data that satisfies a preset condition from the searched search data, a search result storage unit 206 that stores the selected search data, and a setting unit 201 set a destination. And a second route searching means 207 that searches the stored search data and road map data for an optimum route from the destination to the present location, and an optimum route to the destination searched on the road map. And display means 202 for displaying the current location of the vehicle.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a vehicle route guide device for searching an optimum route to a destination and guiding an occupant.

[0002]

[Prior art and its problems] For a vehicle that sets a destination, searches for an optimal route from the current location to the destination, displays the optimal route and the current location of the vehicle on a road map, and guides an occupant to the destination. Route guidance devices are known. The search for the optimum route to this destination is performed by searching a huge amount of intersection network data and selecting from among the numerous routes to the destination, for example, the route with the minimum journey or the route with the minimum required travel time. Selected as a route.

However, in the conventional route guidance device for a vehicle, since the occupant sets the destination and then starts the search for the optimum route, the route guidance is not performed until the search is completed, and the occupant is kept waiting. There's a problem.

In order to solve this problem, Japanese Patent Laid-Open No. 2-1
The search algorithm is improved as disclosed in JP-A-84998, the search target area is limited as disclosed in JP-A-2-306400, and the disclosure is disclosed in JP-A-2-56591. Although it has been proposed to shorten the search time by making the intersection network data into a hierarchical structure as described above, the optimum route search still requires several minutes.

It is an object of the present invention to provide a vehicle route guidance device for promptly searching for an optimum route and starting guidance of an occupant after setting a destination.

[0006]

The present invention will be described with reference to FIG. 1 which is a claim correspondence diagram. The invention of claim 1 is a road map storage means 200 for storing road map data.
A road map is read out from the road map storage means 200 and setting means 201 for setting a destination, and the optimum route to the destination set by the setting means 201 on the road map and the current location of the vehicle are displayed. It is applied to a vehicle route guidance device that includes a display unit 202 that displays a. Then, the vehicle stop detection means 203 for detecting the substantially stopped state of the vehicle, and the vehicle stop detection means 2
When the vehicle substantially stopped state is detected by 03, the first route search means 204 for searching the road map data of the road map storage means 200 to search for the optimum route from the current position to each intersection in the vicinity, and A data selection unit 205 that selects data satisfying a preset condition from the search data searched by the first route search unit 204, and a search result storage that stores the search data selected by the data selection unit 205. When the destination is set by the means 206 and the setting means 201, the search data stored in the search result storage means 206 and the road map data in the road map storage means 200 are searched to find the destination to the present location. The second route searching means 207 for searching for the optimum route is provided, thereby achieving the above object. The vehicle route guiding apparatus according to claim 2 includes a power supply unit 208 that continues to supply power to the vehicle route guiding apparatus for a preset time even after the ignition is turned off, and a search result storage unit 206A.
Auxiliary power source 209 even after power supply is stopped by
While receiving the power supply from the
The first route searching means 204A searches for the optimum route while the power is being supplied from the power supply means 208 after the ignition is turned off. The vehicle route guiding device according to claim 3 is the first route searching means 2
04B searches the route of the minimum distance from the current position to each intersection, and the data selection means 205A selects the search data regarding the intersection where the distance from the current position reaches a preset value. In the vehicle route guidance device according to the fourth aspect, the first route searching means 204C searches for a route of the minimum distance from the current position to each intersection, and the data selecting means 205.
By B, the search data relating to the intersection where the journey from the current position has reached at least the first value and the second value larger than the preset value are selected. In the vehicle route guidance device according to claim 5, the search result storage unit 206B stores the search data regarding all the intersections until the distance from the current position reaches the first value, and when the first value is exceeded, the data is stored. Sorting means 2
The search data relating to the intersection where the distance from the current position selected by 05B has reached at least the second value is stored.

[0007]

According to the vehicle route guiding apparatus of claim 1, when the vehicle is stopped, the road map data is searched to search for the optimum route from the current position to each intersection around the current position, and the searched data is searched. Data that satisfies a preset condition is selected and stored. And when the destination is set,
The stored search data and road map data are searched to find the optimum route from the destination to the current location. This allows
In the route search from the destination to the current location after the destination is set, the route search to the intersection around the current location where the optimum route has already been searched is simplified, and the entire route search time is shortened accordingly. , You can promptly display the optimum route on the road map and start guiding the occupants. Further, since the search data is selected and stored, the search result storage means 206
The storage capacity of can be reduced. According to another aspect of the vehicle route guidance device of the present invention, an optimum route from the current position to each intersection around the current position is searched while the power is supplied after the ignition is turned off, and a preset condition is selected from the searched data. The data to be filled is selected and stored in the search result storage unit 206A driven by the auxiliary power source 209 even after the power supply is stopped. Then, when the destination after the ignition is turned on is set, the stored search data and road map data are searched to search for the optimum route from the destination to the current position.
As a result, the route search result around the current location is retained even if the power supply is stopped, and even if the destination is set immediately after the ignition is turned on, the search result storage unit 206A is provided.
The optimum route from the destination to the current location can be quickly calculated by reading the search result around the current location from. In the vehicle route guidance device according to the third aspect, the route from the current location is used as the search data selection condition, and the search data regarding the intersection at which the route reaches the set value is selected. In the vehicle route guidance device according to the fourth aspect, the route from the current position is used as the search data selection condition, and the search data regarding the intersection at which the route reaches at least the first and second set values is selected. As a result, the search data to be selected are hierarchized on a substantially concentric circle centered on the current location, and a wide range of search data can be stored with a small storage capacity. In the vehicle route guidance device according to claim 5, all the search data are stored until the distance from the current position to the intersection reaches the first set value, and thereafter, the distance from the current position becomes at least the second set value. The search data regarding the reached intersection is stored. As a result, after the destination is set, a detailed optimum route around the current position among the optimum routes from the destination to the current position can be quickly calculated, and route guidance can be started earlier.

[0008]

2 and 3 are block diagrams showing the structure of an embodiment. As shown in the figure, the vehicle route guidance device 100 is mainly composed of a microcomputer including a CPU 1 and its peripheral components. The CPU 1 exchanges data with various devices via the system bus 2, executes a control program described later to calculate the current position of the vehicle, and searches for an optimum route from the current position to the destination. Direction sensor 3
Is a sensor that detects the traveling direction of the vehicle, and is connected to the system bus 2 via the amplifier 4, the A / D converter 5, and the I / O controller 6. The vehicle speed sensor 7 is attached to, for example, a transmission and generates a predetermined number of pulse signals per one rotation of the speedometer pinion. This vehicle speed sensor 7 is an I / O controller 6
Is connected to the system bus 2 via. The CPU 1 detects the traveling speed of the vehicle by detecting the number of pulses per unit time or the pulse cycle output from the vehicle speed sensor 7, and detects the traveling distance of the vehicle by counting the number of pulses. The key 8 is an operation member for inputting various commands and data such as a destination to the device, and is connected to the system bus 2 via the I / O controller 9. The audio output speaker 10 is connected to the system bus 2 via the sound generator 11 and the I / O controller 9. GPS receiver 12
Receives a GPS signal transmitted from a satellite and performs GPS positioning calculation to detect the current position and heading of the vehicle.

In FIG. 3, a CD-ROM 16 is a storage device for storing road map data including intersection network data, and is connected to the system bus 2 via an interface SCSI controller 17. C
The RT 18 is a display that functions as a VDT (Visual Display Terminal), and is connected to the system bus 2 via the graphic controller 19. This CR
A road map around the current position of the vehicle is displayed at T18, and the optimum route to the current position and the destination of the vehicle is displayed on the road map. The system bus 2 has a CRT 1
8 V-RAM 20 for image storage, ROM 21 for storing control programs described later, D-RAM 22 for storing the route search result from the destination to the current location, Kanji ROM 2
3. When the ignition is turned off, the S-RAM 24 for storing the route search result around the current position and the current position is connected.

FIG. 4 shows the route guiding device 10 shown in FIGS.
It is a power supply system diagram of 0. Route guidance device 10 of this embodiment
0 to the battery 101 via the key switch 102
Power is supplied from. The key switch 102 is closed when an ignition key (not shown) is in any one of the ACC, ON, and START positions, and is opened when it is in the OFF position. Therefore, the ignition key is OF
Unless set to the F position, the route guiding apparatus 100 is supplied with power from the battery 101. Note that S-
The RAM 24 is equipped with two power supply systems and is usually a CP
Power is supplied from the battery 101 similarly to the devices such as the U1, the ROM 21, and the D-ROM 22, but even if the supply of the normal power is stopped, the power is supplied from the auxiliary battery 27 to retain the stored contents. The auxiliary battery 27 is connected to the battery 101 and can be constantly charged.

The timer 26 closes its contact when power is supplied to the route guiding device 100 by the key switch 102, and holds the closed state of the contact for a preset time when the supply of power is stopped. After that, it opens. Therefore, even if the ignition key is set to the OFF position and the key switch 102 is turned off, the battery 101 is supplied to the route guidance device 100 via the timer 26 for the set time.
The power continues to be supplied from. When the set time has elapsed, the timer 26 opens and the supply of power to the route guiding device 100 is stopped. That is, even if the occupant stops the vehicle and sets the ignition key to the OFF position, power is continuously supplied to the route guiding device 100 for the set time of the timer 26, and the CPU 1 causes the optimum route to reach the current position and each intersection around the current position. Can be searched.

FIG. 5 is a diagram for explaining an optimum route searching method according to an embodiment. In this embodiment, while the battery power is being supplied by the timer 26 after the ignition is turned off, the current position of the vehicle is calculated, and the route h to the intersection is calculated from a plurality of routes from the current position to any intersection. Search for the smallest route. Here, an outline of a method of searching for the optimum route around the present location will be described. A road map database including intersection network data and a memory for storing search results are prepared. This search result memory is stored in the memory h for each intersection from the departure intersection h.
And the immediately preceding intersection A in front of each intersection on the optimum route from the departure intersection to each intersection. The departure intersection is an intersection that satisfies a predetermined condition among the intersections near the current location and is specified as the departure intersection. In addition, hereinafter, the intersection searched for performing the route calculation is referred to as a central intersection, and the intersection adjacent to the central intersection is referred to as an adjacent intersection.

First, 0 is set to the path h at the departure intersection,
A constant equivalent to infinity is set for the path h of another intersection, and the departure intersection is set as the central intersection to start the route search. The distance h0 from the departure intersection to the adjacent intersection is calculated by adding the distance h0 from the departure intersection stored in the distance of the central intersection and the distance from the central intersection to the adjacent intersection.
1 is calculated and compared with the route h2 from the departure intersection which is already stored in the route of the adjacent intersection. When the distance h1 calculated this time is smaller than h2, the distance h2 of the adjacent intersection is changed to h1 and the central intersection is set to the intersection A immediately before the adjacent intersection. When the above processing is completed for all the adjacent intersections adjacent to the central intersection, the intersection with the smallest distance h from the departure intersection is selected as the next new center from among all the intersections except the intersection already selected as the central intersection. Set at the intersection. Less than,
The above-described processing is performed on the intersections adjacent to this new central intersection. In this way, a route is searched for by setting new central intersections in order of increasing distance from the departure intersection. At the intersection where the route search is completed, the intersection is reached immediately before the intersection to reach the starting intersection. The route is the optimum route with the minimum distance from the departure intersection to the intersection.

After the ignition is turned on, when the destination of the vehicle is set, the optimum route from the destination to the present location is searched. Here, the optimum route from the destination to the current position is the route with the smallest distance. In the search for the optimum route from the destination to the present location, an intersection satisfying a predetermined condition is specified as an intersection among the intersections near the destination, and the search is started from the intersection around the intersection. Further, in the storage memory of the search results, the distance g from the target intersection for each intersection, the immediately preceding intersection B before each intersection on the optimum route from the target intersection to each intersection, and the intersection from each intersection to the starting intersection Memorize the estimated path h '. In this embodiment, the straight line distance from each intersection to the current location is calculated based on the road map data, and the calculated straight line distance h'is set.

First, 0 is set to the path g of the target intersection,
A constant of infinity is set for the path g of another intersection, and the destination intersection is set as the central intersection, and the route search from the destination is started. The route g0 from the target intersection to the adjacent intersection is added to the route g0 from the target intersection stored in the route of the central intersection to obtain the route g1 from the target intersection to the adjacent intersection, and the route g1 is already stored in the route of the adjacent intersection. Compared with the traveled distance g2 from the target intersection.
When the calculated route g1 is smaller than g2, the route g2 of the adjacent intersection is changed to g1 and the central intersection is set to the intersection B immediately before the adjacent intersection.
Further, the estimated path h ′ from the adjacent intersection to the departure intersection is calculated and stored. When the above processing is completed for all the adjacent intersections adjacent to the central intersection, from the intersections other than the intersections already selected as the central intersections, the journey g from the destination intersection and the estimated journey h'from the destination intersection to each other The intersection with the smallest sum (g + h ') of and is set to the next new central intersection. Hereinafter, the above-described processing is performed on the intersections adjacent to the new central intersection.

In this way, a new central intersection is set in descending order of the sum (g + h ') of the route g from the destination intersection and the estimated route h'to the departure intersection, and the route is searched from the destination. During the search, if the adjacent intersection reaches the intersection where the route search from the current location is completed, that is, the intersection where the optimum route of the route h from the departure intersection is searched, the purpose of the adjacent intersection is The sum of the distance g from the intersection and the distance h from the departure intersection (g +
h), that is, the distance (g + h) from the starting intersection to the destination intersection of the route passing through the adjacent intersection.

Comparing the route search around the present location and the route search around the destination, the former is omnidirectional route search, while the latter is directional route search. The former searches for intersections in ascending order of the distance h from the departure intersection to each intersection, while the latter searches for the distance g from the destination intersection to each intersection and the estimated distance h'from those intersections to the departure intersection. Sum of (g +
Search for intersections in ascending order of h '). Therefore, comparing the time required for both route searches under the same condition, in the latter case where the directional route search is performed, the amount of calculation is small, so the search can be performed in about 1/5 of the time in the former case. it can. Therefore, while the battery power is supplied after the ignition is turned off, an omnidirectional route search around the current location is performed as much as possible, and the search result is stored in the S-RAM 24. When the destination is set after the ignition is turned on, the route search result around the current location is read from the S-RAM 24, and the route search having the directivity from the destination toward the current location is performed. Then, when the latter route search reaches the formerly searched region 1, the optimum route from the current position to the destination is selected using the former search result. As shown in FIG. 5, since the optimum route has already been searched for at the intersection of the area 2B in the latter search area 2,
The calculation time for the area 2B is unnecessary, and the entire route search time can be shortened accordingly. When the route search area 1 around the current location is wide and the destination is set in the former search area 1, the route search from the current location to the destination is almost instantly completed.

As described above, the wider the search range for the optimum route to each intersection around the present location is, the shorter the search time for the optimum route from the destination after the destination is set to the present location is. After setting, the optimum route can be promptly displayed to start guiding the occupant. However, as the route search range around the current location is wider, the amount of data of the search result increases, and a memory having a large storage capacity for storing the data is required. The optimum route data as a result of this search needs to be stored even after the ignition is turned off, so it must be stored in the nonvolatile S-RAM 24. However,
The S-RAM 24 is expensive, and the auxiliary battery 2 is always used.
Since the power must be supplied by means of 7, it is necessary to reduce the usage amount of the S-RAM 24 as much as possible.

Therefore, in the vehicle route guidance device of the present invention, the memory size of the S-RAM 24 is made as small as possible, and the route search results around the wide range of the present location are stored while solving the above problems of cost and power consumption. To do. The outline of the method will be described below. In the search for the optimum route to each intersection around the current location, the central intersection expands starting from the departure intersection as shown in FIG. FIG. 6 shows a state in which a search has been performed up to a range in which the distance h from the departure intersection of the central intersection exceeds a preset value H1, and the black circle marks in the figure are the outermost intersections. Continue to explore further,
FIG. 7 shows a state in which the search is performed up to a range in which the distance h of the central intersection exceeds a preset value H2. In FIG.
The black circle mark indicates the outermost intersection in the range of the above-mentioned central intersection route h = H1, and the double circle mark indicates the current route h =
The outermost intersection in the range of H2 is shown.

FIG. 8 is a diagram schematically showing the outermost intersections of the search results on the concentric circles by repeating such a search process. In reality, the outermost intersections do not line up concentrically. Here, the distance h = H at the central intersection
The range of 1 is referred to as the first layer, the range of the route h = H2 is referred to as the second layer, the range of the route h = H3 is referred to as the third layer, and the range of the route h = Hn is referred to as the nth layer. In the figure, the outermost intersections on the third layer and below are omitted. Set value Hn (n = 1, 2, ...
., N) is a set value that determines the size of the search area of each layer, and is proportional to the radius of the concentric circles shown in FIG.

When the ignition is turned off, the CPU 1 starts searching for an optimum route from the departure intersection to each of the surrounding intersections. Here, the route search data around the departure intersection is stored in the D-RAM 22, but the data satisfying the following conditions in the search data is stored in the S-RAM 24. The D-RAM 22 has a large memory size and a sufficient storage capacity. Generally, the D-RAM is inexpensive, and even if it is used in a large amount, the cost burden is small, but when the power supply is stopped, the stored contents are erased.
In order to retain the stored contents, power must be supplied at all times, and the power consumption is large.
When the distance h of the central intersection reaches the set value H1, the central intersection is set as the outermost intersection of the first layer, the outermost intersection information, the distance h from the departure intersection of those outermost intersections, and the departure. The intersection and the S-RAM 24 are stored.
After that, when the distance h of the central intersection reaches the set value H2, the central intersection is set as the outermost intersection of the second layer, and the outermost intersection information and the optimum route from the outermost intersection to the departure intersection are set. In the S-RAM 24, the outermost intersections of the first layer existing in 1) and the route h to reach the departure intersection via these optimum routes are stored.

That is, the distance h of the central intersection is Hn (n =
1, 2, ..., N), the central intersection is defined as the outermost intersection of the nth layer, and the outermost intersection information,
The outermost intersections of the (n-1) th layer existing on the optimal route from those outermost intersections to the departure intersections (hereinafter,
The parent intersection) and the route h to the departure intersection via these optimum routes are stored in the S-RAM 24. The parent intersection of the first layer is the departure intersection. S-RAM
The storage of the search data in 24 is continued until the storage capacity of the S-RAM 24 becomes full, and when the storage capacity of the S-RAM 24 becomes full, the route search around the current location is ended. In addition, the timer 26 described above has an S-RA.
Sufficient time is set until M24 is filled with route search data.

When the destination is set after the ignition is turned on, the optimum route from the destination intersection to the departure intersection is searched as described above. When the searched adjacent intersection reaches the outermost intersection of the largest layer (nth layer) stored in the S-RAM 24 during the route search from the destination, the optimum route from the adjacent intersection to the departure intersection Since the route h of is searched, the route h is used in place of the above-described estimated route h ′, and the route with the smallest (g + h) is sequentially set as the central intersection. Then, when the central intersection reaches the outermost intersection of the maximum layer (nth layer), the search is terminated. FIG. 9 shows the relationship between the search area from the current location and the search area from the destination at this point. When the search ends at the time when the adjacent intersection reaches the outermost intersection, these search areas become as shown in FIG. 10, and since all the routes from the destination intersection to the departure intersection have not been searched, it is not the selected route. However, there may be an optimal route from the destination to the current location. However, comparing the search area 2A shown in FIG. 9 with the search area 2B shown in FIG. 10, it is clear that the search area 2B shown in FIG. 10 is narrower, and the number of intersections to be searched decreases accordingly, and the search time becomes shorter. Therefore, the search may be terminated when the adjacent intersection reaches the outermost intersection.

As shown in FIG. 11, in the route search from the destination intersection, the route g from the destination intersection to the central intersection
And the estimated route h'from the central intersection to the departure intersection
Since the central intersection is selected in the ascending order of the sum (g + h '), when the central intersection reaches the outermost intersection A of the largest layer (nth layer), it passes through the outermost intersection A from the target intersection. The route to the starting intersection is the optimum route with the minimum distance. The parent intersection of the outermost intersection A is the outermost intersection B of the third layer (the (n-1) th layer), and similarly, the parent intersection of the outermost intersection A of the third layer is the outermost intersection of the second layer. It is C. The outermost intersection of the second layer is the outermost intersection D of the first layer, and the parent intersection of the outermost intersection D of the first layer is the starting intersection as described above. That is,
By following the parent intersection in order from the outermost intersection A stored in the S-RAM 24, the optimum route from the outermost intersection A to the departure intersection can be obtained.

By the way, the intersections in each layer are omitted in the optimum route from the outermost intersection A shown in FIG. 11 to the starting intersection through the outermost intersections in each layer. Therefore, after the route from the outermost intersection A of this maximum layer to the starting intersection is selected, the optimal route of the minimum path from the outermost intersection to the parent intersection is recalculated for each layer, and these are combined to combine the maximum layers. Obtain the optimum route from the outermost intersection A to the departure intersection. At this time, the route calculation for the first layer is executed first, and the CRT is immediately executed after the optimum route for the first layer is calculated.
The route is displayed on 18 and guidance of the occupant is started. After that, the route calculation for the second layer and above is performed, and the remaining calculated route is displayed on the CRT 18. The route search result around the destination is stored in the D-RAM 22.

FIG. 12 is a flow chart showing a main control program executed by the CPU 1, FIGS. 13 to 15 are flow charts showing an optimum route search program to each intersection around the present location, and FIGS. 16 to 18 are optimum from destination to present location. It is a flow chart which shows a route search program.
The operation of the embodiment will be described with reference to these drawings. When the ignition switch 102 is turned on, the route guiding device 100
When the power is turned on, the CPU 1 starts executing the IGN ON program shown in FIG. In step S1 after the execution is started, it is determined whether or not the destination is set by the key 8. If the destination is set, the process proceeds to step S2. If the destination is not set, the execution of the program ends.

When the destination is set, the S-RAM 24
The search data of the optimum route from the to the intersections around the current location is read out. This search data is calculated while the vehicle is stopped and the ignition key 102 is turned off, while the timer 26 continues to supply the battery power to the route guiding device 100. Continuing step S
In step 3, the subroutine shown in FIGS.
The optimum route from the destination to the current location is searched using the route search data around the current location read from the RAM 24.
When the optimum route from the destination to the current position is selected, the process proceeds to step S4, where a road map around the current position is displayed on the CRT 18, and the current position of the vehicle and the optimum route to the destination are displayed on the road map. In addition, as the vehicle moves, the road map is scrolled and the current location is updated.

When the ignition switch 102 is turned off, the CPU 1 starts executing the IGN OFF program shown in FIG. 12 (b). Timer 2 in step S6
6 and proceeds to step S7, where D-RAM 22
The current location of the vehicle is read from. The CPU 1 always calculates the current position of the vehicle when the ignition switch 102 is turned on. That is, the output pulse signal of the vehicle speed sensor 7 is counted to detect the traveling distance of the vehicle, and the traveling locus of the vehicle is calculated based on the detected traveling distance and the traveling azimuth of the vehicle detected by the azimuth sensor 3. Further, map matching is performed based on the calculated traveling locus and the road map stored in the CD-ROM 16, the current position of the vehicle is calculated, and stored in the D-RAM 22. Therefore, when the ignition switch 102 is turned off, the D-RAM
The stop position of the vehicle, that is, the current position is stored in 22 and the stored position is read. At this time, if the correct current position of the vehicle is detected by the GPS receiver 12, the current position calculated by the above map matching is corrected by the current position data obtained by the GPS positioning. Next, in step S8, the subroutine shown in FIGS. 13 to 15 is executed to start the search for the optimum route to each intersection around the current location, and the information about the outermost intersection of each layer is stored in the S-RAM.
24, and the route search ends when the S-RAM 24 is full of search data. In a succeeding step S9, it is determined whether or not the timer 26 has timed out, and when the time is up, the execution of the program is terminated and the power supply to the route guiding apparatus 100 is stopped.

As described above, even if the ignition key is turned off, power is continuously supplied to the route guidance device 100 for a predetermined time, the current location is calculated, and an optimum route to each intersection around the current location is searched for, and a search for each layer is performed. The data is stored in the S-RAM 24 up to the full storage capacity. When the ignition key is turned on again and the destination is set, the optimal route from the destination to the current location is searched using the search result of the optimal route to each intersection around the current location, and the current location is searched on the road map. Guide the occupant by displaying the optimal route to the destination.

Next, with reference to the flow charts shown in FIGS. 13 to 15, the search processing of the optimum route to each intersection around the present location will be described. In steps S100 and S102 of FIG. 13, the following initial processing is performed. (1) The contents stored in the D-RAM 22 and the S-RAM 24 are erased. (2) Specify the departure intersection. This starting intersection is, for example, as disclosed in Japanese Patent Laid-Open No. 62-86499, an intersection that is located outside the circle of a predetermined radius centered on the current location and is closest to the current location from the intersections around the current location. Is selected as the departure intersection. (3) Set departure intersection 1 as the first central intersection. (4) H1 is set to the above-described boundary radius H that determines the size of the search range of the first layer. (5) Set the departure intersection 1 at the parent intersection of the central intersection. (6) 1 is set to the outermost flag of the departure intersection 1. The outermost contour flag is a flag indicating that the intersection is the outermost contour intersection. In the first layer, the parent intersection is the starting intersection 1
And the outermost contour flag of the departure intersection 1 is set to 1. (7) Set 0 for the route h of the departure intersection 1 and
Set ∞ to the path h of all intersections except the departure intersection 1.

In step S104, the distance h of the central intersection
Is the boundary radius H (H1 first, then H2, H3, ...
, Hn), and if so, the process proceeds to step S122 in FIG. 14, and if not, the process proceeds to step S106. If the path h of the central intersection is larger than the boundary radius H, the central intersection is the outermost intersection, and the processing in that case is performed after step S122 of FIG. On the other hand, if the path h of the central intersection is equal to or less than the boundary radius H, the central intersection has not yet reached the outermost portion of the layer, and the process proceeds to step S106. Step S10
In step 6, one of the adjacent intersections adjacent to the central intersection is selected, the process proceeds to step S108, and the route h of the central intersection is selected.
Is added to the distance from the central intersection to the selected adjacent intersection to obtain a calculated value A of the distance to the adjacent intersection.
In the following step S110, it is determined whether or not the calculated value A of the route to the adjacent intersection is smaller than the route h of the adjacent intersection stored in the D-RAM 22, and if it is smaller, the process proceeds to step S112. If so, the process proceeds to step S120.

The calculated value A of the route to the adjacent intersection is D-R
When the distance is smaller than the distance h stored in the AM 22, the distance h of the adjacent intersection in the D-RAM 22 is changed to the calculated value A in step S112, and the parent intersection of the central intersection is added to the parent intersection of the adjacent intersection in step S114. Set the intersection. That is, since the current center intersection is not the outermost intersection, if this center intersection is in the nth layer, the parent intersection of the (n-1) th layer is set to this center intersection. Therefore, the same parent intersection as the central intersection is also set at this adjacent intersection. In step S116, it is determined whether or not the currently selected adjacent intersection exists in the central intersection candidate list. If it is already registered in the central intersection candidate list, the process proceeds to step S120. If it is not registered, the process proceeds to step S118. move on. The central intersection candidate list is a list for registering intersections that can be central intersections. In step S118, the adjacent intersection is additionally registered in the central intersection candidate list. Next, the process proceeds to step S120, it is determined whether or not all the adjacent intersections of the currently set central intersection are searched, and when the above process is completed for all the adjacent intersections, the process proceeds to step S140 of FIG. If not, the process returns to step S106 and the above process is performed on the remaining adjacent intersections.

In step S140 of FIG. 15, D-
It is determined whether or not the central intersection candidate list stored in the RAM 22 is empty. If it is empty, the process proceeds to step S142.
If it is not empty, the process proceeds to step S146. Until the distance h of the central intersection reaches the boundary radius H, the adjacent intersections of the central intersections are additionally registered in the list as the candidate of the central intersections as described above, and the candidate number of the central intersections increases. When H is reached, the adjacent intersection is added to the temporary center intersection candidate list, and the number of intersections in the center intersection candidate list gradually decreases. If the central intersection candidate list is not empty, then in step S146, the intersection having the smallest path h among the intersections registered in the central intersection candidate list is set as a new central intersection, and the flow proceeds to step S148. In step S148, the intersection newly set as the central intersection is deleted from the central intersection candidate list.
Then, in step S150, it is determined whether or not the S-RAM 24 is filled with the search result data, and when it is full, the execution of the program is terminated. If not, the process proceeds to step S104 in FIG.

When the route search is performed in the above loop, the distance h at the central intersection gradually increases and finally becomes larger than the boundary radius H. In step S104 of FIG. 13, when it is determined that the path h of the central intersection is larger than the boundary radius H and the central intersection is the outermost intersection, the central intersection is stored in the S-RAM 24 in step S122 of FIG. The parent intersection and the route h are stored.
In the following step S124, one of the adjacent intersections adjacent to the central intersection is selected, and the process proceeds to step S126. The distance h from the central intersection to the selected adjacent intersection is added to the distance h of the central intersection, and the adjacent intersection is added. Calculate the calculated value A up to. In the following step S128, it is determined whether or not the calculated value A of the route to the adjacent intersection is smaller than the route h of the adjacent intersection stored in the D-RAM 22, and if it is smaller, the process proceeds to step S130. If so, the process proceeds to step S138.

The calculated value A of the route to the adjacent intersection is D-R
When the distance is smaller than the distance h stored in the AM 22, the distance h of the adjacent intersection of the D-RAM 22 is changed to the calculated value A in step S130, and the central intersection is set to the parent intersection of the adjacent intersection in step S132. To do. That is, since the current center intersection is the outermost intersection, if this center intersection is in the nth layer, this adjacent intersection is in the (n + 1) th layer. Therefore, the outermost intersection of the nth layer, that is, the current central intersection is set as the parent intersection of the adjacent intersection. In step S134, it is determined whether or not the currently selected adjacent intersection is present in the temporary center intersection candidate list, and if it is already registered in the temporary center intersection candidate list, the process proceeds to step S138. Proceed to S136. If the central intersection is the outermost intersection, the adjacent intersection is registered in the temporary central intersection candidate list instead of being registered in the central intersection candidate list. In step S136, the adjacent intersection is additionally registered in the temporary center intersection candidate list. Next, in step S138, it is determined whether or not all the adjacent intersections of the currently set central intersection have been searched, and when the above processing is completed for all the adjacent intersections, the process proceeds to step S140 in FIG. If not, the process returns to step S124 and the above process is performed on the remaining adjacent intersections.

When the path h of the central intersection becomes larger than the boundary radius H and the central intersection becomes the outermost intersection, the number of the intersections registered in the central intersection candidate list in step S146 described above is gradually decreased until finally the center intersection is reached. The intersection candidate list is empty. Then, step S14 in FIG.
If 0 is affirmed and it progresses to step S142, it is discriminate | determined whether the temporary center intersection candidate list is empty. This is a CD-RO
It is confirmed whether or not the search for the road map in the predetermined range read from M16 is completed. If the temporary center intersection candidate list is empty, it is determined that the search for the predetermined range of the road map is completed and the program is executed. Otherwise, the process proceeds to step S144, the intersection registered in the temporary center intersection candidate list is moved to the center intersection candidate list, and the boundary radius H is increased to perform the route search of the next layer ( H1 → H2 → H3 → ... → Hn). By repeating the above process, the outermost intersection of each layer is searched and the information is stored in the S-RAM 24.

FIG. 19 is an intersection network diagram for explaining the optimum route searching method. In FIG.
Small circles indicate intersections, and the numbers in the vicinity indicate intersection numbers. Lines connecting intersections indicate roads, and the numbers on each road indicate the distance from the intersection to the intersection. Figure 2
0 to 25 are diagrams showing route search results stored in the D-RAM 22. The D-RAM 22 stores a path h, a parent intersection, a central intersection candidate list, and a temporary central intersection candidate list for each intersection. The outermost contour flag set for each intersection is not shown. Figure 1
Taking the intersection network shown in FIG. 9 as an example, the process of searching for the optimum route to each intersection around the current location will be described. Here, it is assumed that the intersection 1 is specified as the departure intersection.
The data shown in FIG. 20 is stored in the D-RAM 22 after the initialization described above. That is, 0 is set to the journey h of the departure intersection 1, ∞ is set to the journey h of the other intersections, 1 is set to the parent intersection of the departure intersection 1, and 0 is set to the parent intersection of the other intersections. Is set.

Next, the above-mentioned route search is performed for the adjacent intersections 2 to 6 of the departure intersection 1, and the contents stored in the D-RAM 22 are changed as shown in FIG. Intersections 2-6
The respective journeys h are changed, and the departure intersection 1 is set as their parent intersection. Further, intersections 2 to 6, which are adjacent intersections of the departure intersection 1, are registered in the central intersection candidate list. Intersections 2 to 6 registered in the central intersection candidate list
Among them, the intersection 2 of the minimum route h is set as the next central intersection, and the route search is performed to the adjacent intersections 1, 5, 7, 11 of the central intersection 2. As a result, D-RAM2
The stored contents of No. 2 change as shown in FIG. That is,
The path h is changed with respect to the intersections 5, 7, and 11, and the parent intersection 1 of the central intersection 2 is set as the parent intersections thereof. At this time, the intersection 2 set as the central intersection is deleted from the central intersection candidate list, and new intersections 7 and 11 are additionally registered. It should be noted that the intersection 5 is already registered in the central intersection candidate list, and thus is not registered again.

Here, it is assumed that the boundary radius H is set to 9. When the search for the optimum route from the departure intersection to each of the surrounding intersections is continued, as shown in FIG.
When the ten intersections 18 are selected as the central intersections, the distance h of the central intersections becomes larger than 9. Therefore,
The adjacent intersections 19 and 20 are registered in the provisional central intersection candidate list, not in the central intersection candidate list, and the central intersection 18 is set as their parent intersection. This central intersection 18 is the outermost intersection because the distance h exceeds the boundary radius H = 9, and the central intersection number 18 and the distance h
= 10 and parent intersection 1 are stored in the S-RAM 24. When the search is further continued, the central intersection candidate list becomes empty as shown in FIG. At this point intersection 8,
12, 13, 14, 18, 18, 21 and 22 are the outermost intersections of the first layer and are stored in the S-RAM 24. afterwards,
As shown in FIG. 25, the intersections registered in the temporary center intersection candidate list are moved to the center intersection candidate list, the above-described processing is repeated, and the outermost intersection information of each layer is S.
-It is stored in the RAM 24.

Next, the process of searching for the optimum route from the destination to the current position will be described with reference to the flow charts shown in FIGS. First, the target intersection is specified in step S200 of FIG. This destination intersection is, for example, similar to the departure intersection described above, the intersection that is located outside the circle with a predetermined radius centered on the destination and is closest to the destination is selected as the destination intersection. To do. Next, in step S202, the information about the outermost intersection of each layer stored in the S-RAM 24 is read. Step S
In 204, the target intersection is set to the central intersection, and in the subsequent step S206, 0 is set to the route g of the target intersection, and very large values, ∞, are set to the route g of all the intersections other than the target intersection. . Here, the route search result from the destination to the present location is stored in the D-RAM 22. FIG. 26 shows D at the time when the above initial settings are made.
-Indicates the contents stored in the RAM 22. In the figure, the immediately preceding intersection is an intersection in front of each intersection on the optimum route from the target intersection to each intersection. The outermost contour flag is an intersection stored in the S-RAM 24 as the outermost contour intersection of each layer in the route search around the current location described above, and the outermost contour of the outermost contour intersection is read according to the outermost contour intersection information read from the S-RAM 24. Set the flag to 1.

In step S208, it is determined whether or not the outermost contour flag of the central intersection is 1, and if the central intersection is the outermost contour intersection, the process proceeds to step S234 of FIG. 18, otherwise the process proceeds to step S210. In step S210, one of the intersections adjacent to the central intersection is selected and the process proceeds to step S212. The distance g from the central intersection to the selected adjacent intersection is added to the distance g of the central intersection to reach the adjacent intersection. Calculate the calculated value A of the journey. In step S214, it is determined whether or not the calculated value A of the route to the adjacent intersection is smaller than the route g of the adjacent intersection stored in the D-RAM 22, and if it is smaller, the process proceeds to step S216, and if not. It progresses to step S228 of FIG. When the calculated value A of the route to the adjacent intersection is smaller than the route g stored in the D-RAM 22, in step S216, the route g of the adjacent intersection of the D-RAM 22 is changed to the calculated value A, and the subsequent step S
At 218, the central intersection is set to the intersection just before the adjacent intersection.

In step S220 of FIG. 17, it is determined whether or not the currently selected adjacent intersection is present in the central intersection candidate list, and if it is already registered in the central intersection candidate list, the process proceeds to step S228. If not, the process proceeds to step S222. In step S222,
It is determined whether or not the outermost contour flag of the currently selected adjacent intersection is set to 1. If the outermost contour flag is set to 1, the process proceeds to step S226. If not, the process proceeds to step S224. If the adjacent intersection is not the outermost intersection, in step S224, the adjacent intersection is additionally registered in the central intersection candidate list, and the straight line distance from the adjacent intersection to the departure intersection is calculated based on the road map data to estimate the estimated path h '. Set to. The estimated path h'is an estimated value of the path from an arbitrary intersection to the departure intersection, and in this embodiment, the straight line distance from the arbitrary intersection to the departure intersection is the estimated path h '. On the other hand, when the adjacent intersection is the outermost intersection, the adjacent intersection is additionally registered in the center intersection candidate list, and the route h from the departure intersection to the adjacent intersection is calculated. The path h of the adjacent intersection is set to h '. In step S228, it is determined whether or not the above-described processing has been completed for all adjacent intersections, and if completed, the process proceeds to step S230, and if not, step S2 in FIG.
Return to 10.

In step S230, an intersection having the smallest estimated route (g + h ') from the target intersection to the departure intersection is selected from among the intersections registered in the central intersection candidate list as a new central intersection. in this way,
By sequentially searching for intersections with the smallest estimated path from the destination intersection to the departure intersection and conducting a search, it is possible to conduct a route search with directionality from the destination intersection to the departure intersection, and the search area is rationalized. You can search for the optimum route more quickly with a limited number. In the following step S232, the intersection newly selected as the central intersection is deleted from the central intersection candidate list, the process returns to step S208 of FIG. 16, and the above-described processing is repeated.

When it is determined in step S208 in FIG. 16 that the central intersection is the outermost intersection, the process proceeds to step S234 in FIG. When the central intersection is the outermost intersection, the route of the minimum distance g from the destination intersection to the central intersection is fixed, and the route of the minimum distance h from the central intersection to the departure intersection is fixed. This means that the optimum route with the minimum distance (g + h) from the destination intersection to the departure intersection has been searched. In step S234, D-
By referring to the data stored in the RAM 22, the optimum route of the minimum route from the last central intersection to the preceding intersection is traced to the target intersection. In a succeeding step S236, the parent intersection is traced from the last central intersection to obtain the optimum route of the minimum journey to the departure intersection. Then, in step S238, the route from the central intersection to the departure intersection that follows the parent intersection is calculated in detail, and the optimum route from the destination intersection to the departure intersection is calculated.

When the detailed route is calculated by tracing the parent intersection from the central intersection to the departure intersection, the route calculation for the first layer is performed with priority, and the first route is calculated when the route calculation for the first layer is completed. The optimum route in the range of layers is displayed on the CRT 18 and promptly start occupant guidance. In addition, if the setting area H1 that determines the size of the search area of the first layer is made smaller than that of the other layers and the search area of the first layer is made narrower, the route calculation of the first layer will be that much. The S-RAM is shortened and the occupant guidance can be started quickly, and the search area other than the first layer is wide.
24 can store search data in a wide area. Further, all the search data of the first layer is stored in the S-RAM, and only the search data regarding the outermost intersection is stored in the S-RA for the second layer and above.
It may be stored in M. In that case, the recalculation time of the optimum route in the first layer after the destination setting is unnecessary, and the occupant guidance can be started earlier.

In each of the above-described embodiments, the route with the minimum travel distance is the optimal route, but the route with the minimum required travel time may be the optimal route. In this case, the required travel time must be calculated from the distance between the intersections and the traveling speed, but it is difficult to specify the actual traveling speed in advance. The required travel time may be calculated by using this. Further, in this case, the estimated required travel time from the intersection under search in the route search from the destination to the departure intersection is calculated by the straight line distance from the intersection to the departure intersection and the possible maximum speed during that time. This maximum possible speed is the maximum possible travel speed on the possible route from the intersection under search to the departure intersection. For example, 100 on the route
If there is a highway of m / h, the maximum running speed is 100 m / h
And

In the configuration of the above embodiment, the CD-RO
M16 is a road map storage means, key 8 is a setting means, C
RT 18 is a display means, key switch 102 is a vehicle stop detection means, CPU 1 and a control program shown in FIGS. 13 to 15 are a first route search means and a data selection means, SR
The AM 24 uses search result storage means as the CPU 1 and FIGS.
The control program shown in 8 constitutes the second route searching means, the timer 26 constitutes the power supply means, and the auxiliary battery 27 constitutes the auxiliary power source.

[0048]

As described above, according to the first aspect of the invention, when the vehicle is stopped, the road map data is searched to search for the optimum route from the current position to each of the intersections around the current position, and the search is performed. The data that satisfies the preset condition is selected from the stored data and stored, and when the destination is set, the stored search data and road map data are searched to find the optimum route from the destination to the current location. Since the search is made, the route search from the destination to the current position after the destination is set simplifies the route search to the intersection around the current position where the optimum route has already been searched, and the entire The route search time can be shortened, and the optimum route can be promptly displayed on the road map to start occupant guidance. Furthermore, since the search data is sorted and stored, the storage capacity of the search result storage means can be reduced. According to the invention of claim 2,
While the power is being supplied after the ignition is turned off, the optimum route from the current location to each of the surrounding intersections is searched, and the data that meets the preset conditions is selected from the searched data and the power supply is stopped. Stored in the search result storage means that is driven by the auxiliary power supply even after the ignition is turned on, and when the destination after ignition is set, the stored search data and road map data are searched to reach the optimum location from the destination to the current location. Since the route is searched, the route search results around the current location are retained even if the power supply is stopped, and even if the destination is set immediately after the ignition is turned on, the route search results around the current location will be saved even if the destination is set. It is possible to read the search result and quickly calculate the optimum route from the destination to the current location. According to the invention of claim 3, the route from the current position is used as the selection condition for the search data, and the search data relating to the intersection whose route reaches at least the first and second set values is selected. The search data are hierarchically arranged on a substantially concentric circle centered on the current location, and a wide range of search data can be stored in a small storage capacity. According to the invention of claim 4, all the search data are stored until the distance from the current position to the intersection reaches the first set value, and thereafter, the distance from the current position reaches at least the second set value. Since the search data for intersections is stored, after the destination is set, it is possible to quickly calculate the detailed optimal route around the current location among the optimal routes from the destination to the current location, and start route guidance earlier. it can.

[Brief description of drawings]

FIG. 1 is a complaint correspondence diagram.

FIG. 2 is a block diagram showing the configuration of an embodiment.

FIG. 3 is a block diagram showing the configuration of one embodiment following FIG.

FIG. 4 is a power supply system diagram of one embodiment.

FIG. 5 is a diagram illustrating a method of searching for an optimum route according to an embodiment.

FIG. 6 is a diagram illustrating a route search method around a departure intersection.

FIG. 7 is a diagram illustrating a route search method around a departure intersection.

FIG. 8 is a diagram illustrating a route search method around a departure intersection.

FIG. 9 is a diagram illustrating a route search method from a destination.

FIG. 10 is a diagram illustrating a route search method from a destination.

FIG. 11 is a diagram for explaining a route search method from a destination intersection to a departure intersection.

FIG. 12 is a flowchart showing a main control program of a microcomputer.

FIG. 13 is a flowchart showing an optimum route search program to reach each intersection around the current location.

FIG. 14 is a flowchart following FIG. 13, showing an optimum route search program to reach each intersection around the current location.

FIG. 15 is a flowchart showing an optimum route search program following FIG. 14 to reach each intersection around the current location.

FIG. 16 is a flowchart showing an optimal route search program from a destination to the present location.

FIG. 17 is a flowchart showing an optimum route search program following the process shown in FIG. 16 from the destination to the current position.

FIG. 18 is a flowchart following FIG. 17, showing an optimal route search program from the destination to the current location.

FIG. 19 is an intersection network diagram for explaining a method of searching for an optimum route.

FIG. 20 is a diagram showing a route search result around the current location stored in a D-RAM.

FIG. 21 is a diagram showing a route search result around the current location stored in D-RAM.

FIG. 22 is a diagram showing a route search result around the current location stored in D-RAM.

FIG. 23 is a diagram showing a route search result around the current location stored in a D-RAM.

FIG. 24 is a diagram showing a route search result around the current location stored in a D-RAM.

FIG. 25 is a diagram showing a route search result around the present location stored in a D-RAM.

FIG. 26 is a diagram showing a route search result around a departure place stored in a D-RAM.

[Explanation of symbols]

1 CPU 2 System Bus 3 Direction Sensor 4 Amplifier 5 A / D Converter 6,9 I / O Controller 7 Vehicle Speed Sensor 8 Key 10 Speaker 11 Sound Generator 12 GPS Receiver 13 Extended I / O 14 Receiver 15 Antenna 16 CD-ROM 17 SCSI Controller 18 CRT 19 Graphic Controller 20 V-RAM 21 ROM 22 D-RAM 23 Kanji ROM 24 S-RAM 26 Timer 27 Auxiliary Battery 100 Vehicle Route Guidance Device 101 Battery 102 Key Switch 200 Road Map Memory Means 201 Setting Means 202 Display means 203 Stop detection means 204, 204A, 204B, 204C First route search means 205, 205A, 205B Data selection means 206, 206A, 206B Search Result storage means 207 second route search unit 208 power supply unit 209 auxiliary power

Claims (5)

[Claims] 1. A road map storage means for storing road map data, a setting means for setting a destination, a road map read from the road map storage means for display, and the setting means on the road map. A route guide device for a vehicle that includes an optimum route to a set destination and a current position of the vehicle, and guides an occupant to the destination, and a stop detection unit that detects a substantially stopped state of the vehicle. When the substantially stopped state of the vehicle is detected by the vehicle stop detection means, a first route search for searching the road map data of the road map storage means to search for an optimum route from the current position to each intersection around the current position Means, data selecting means for selecting data satisfying a preset condition from the search data searched by the first route searching means, and the data selecting means. Search result storage means for storing the search data selected by the step, and when the destination is set by the setting means, the search data stored in the search result storage means and the road map data of the road map storage means And a second route searching means for searching for an optimum route from the destination to the current position. 2. The vehicle route guiding apparatus according to claim 1, further comprising a power supply unit that continues to supply power to the vehicle route guiding apparatus for a preset time even after ignition is turned off. The means receives power from an auxiliary power source and retains stored contents even after the power supply is stopped, and the first route searching means is powered by the power source after the ignition is turned off. A route guidance device for a vehicle, which searches for an optimum route while the vehicle is in motion. 3. The vehicle route guiding apparatus according to claim 1, wherein the first route searching unit searches for a route having a minimum distance from the current position to each intersection, and the data selecting unit. A route guidance device for a vehicle, wherein search data relating to an intersection whose journey from the current location has reached a preset value is selected. 4. The vehicle route guidance device according to claim 1 or 2, wherein the first route searching means searches for a route having a minimum distance from the current position to each intersection, and the data selecting means. A route guidance device for a vehicle, wherein search data relating to an intersection whose travel distance from a current position has reached at least a first value and a second value larger than the preset value are selected. 5. The vehicle route guiding apparatus according to claim 4, wherein the search result storage means has the first distance from the current position as the first distance.
Search data for all intersections is stored until the value of is reached, and if the first value is exceeded, search data for the intersection where the distance from the current position selected by the data selection means reaches at least the second value. A route guidance device for a vehicle, which stores: