JPH05240652A - Guiding path searching method of vehicle-mounted navigator - Google Patents

Abstract

PURPOSE:To select a desired path easily and readily by obtaining a plurality of opti mum paths with different conditions by one search processing. CONSTITUTION:When a path from a starting point to a target one is searched by an optimum guiding path searching part 15f using Dijkstra method by referring to an intersection net list, an accumulation distance is obtained for a certain intersection. When an intersection which is ahead by one at a targeted path is registered as a set with information to be specified, a priority accumulated distance for each type which is obtained while performing weighting according to the type of road and another set of information specifying an intersection which is ahead by one in a path to be focused are registered separately, and then registration is made by performing replacement with a smaller path data of the accumulated distance for a simple accumulated distance and the priority accumulated distance for each type separately when a data in a different path has already been registered for a certain intersection. When processing ends to a destination intersection, the shortest guiding path which is viewed by the priority accumulated distance for each type is obtained in addition to the shortest navigation path viewed from the simple accumulated distance and then both are stored in a navigation path storage part 15g.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a navigation route search method for an in-vehicle navigator, and more particularly to an in-vehicle navigator navigation in which an optimal route connecting a starting point to a destination is searched by using a crossing netlist by the Dijkstra method. The present invention relates to a route search method.

[0002]

2. Description of the Related Art An in-vehicle navigator has a mass storage device such as a CD-ROM for storing a large amount of map data, a display device, and a vehicle position detection device for detecting the current position of a vehicle. CD-R corresponding map data
The map is read from the OM, the map is drawn on the display screen based on the map data, the vehicle position mark (location cursor) is fixed at a fixed position (for example, the center of the screen) on the display screen, and the map is scrolled according to the movement of the vehicle. By displaying or fixing the map on the screen and moving and displaying the vehicle position mark, it is possible to see at a glance where the vehicle is currently traveling.

The map stored in the CD-ROM is divided into a longitude width and a latitude width of an appropriate size according to the scale level, and roads and the like are vertices (nodes) expressed in latitude and longitude.
, Which is represented by a coordinate set of, and these drawing is performed by connecting each node in order by a straight line. It should be noted that a road is composed of two or more nodes, and a part connecting two nodes is called a link. The map data includes (1) a road layer including a road list, a node table, an intersection constituent node list, and an intersection net list, (2) a background layer for displaying roads, buildings, rivers, etc. on the map screen,
(3) It is composed of a character layer for displaying the names of cities, towns and villages, road names, and the like.

Of these, the road layer has the structure shown in FIG. The road list RDLT is classified by road into road types (0; national roads, 1; highways, 2; general roads, 3; other roads), the total number of nodes that make up the road, and a node table NDTB of nodes that make up the road. Position and width to the next node (0; 1.5m or more and less than 2.5m, 1; 2.5m or more
Less than 5.5m, 2; 5.5m or more and less than 11.0m, 3; 11.0m or more)
It is composed of data such as. The intersection constituent node list CRLT is a set of positions on the node table NDTB of the other end node of the link (referred to as an intersection constituent node) for each intersection on the map. The node table NDTB is a list of all nodes on the map. Position information (longitude, latitude) for each node, an intersection identification flag indicating whether or not the node is an intersection, and if the intersection is an intersection, the node configuration node list is displayed. It is composed of a pointer or the like that points to the position and points to the position of the road to which the node belongs on the road list if it is not an intersection.

The intersection netlist CRNL is (1) intersection sequential number (2) map leaf number of map including the intersection node (3) data unit code above, intersection node ID (4) intersection constituent node, for each intersection node Number (5) Sequential number of each adjacent intersection (6) Distance to each adjacent intersection (7) Road attributes (road type, width) to each adjacent intersection.

By the way, the in-vehicle navigator has a route guidance function of searching an optimum route from the starting point to the destination point, for example, tracing the shortest distance, displaying the guidance route on the screen, and guiding the driver. When driving, the driver's purpose is to distinguish the road from other roads by displaying the guide route in a bold color or to display a guide mark that moves along the guide route in front of the vehicle position mark. It is ready to reach the ground.

A method called Dijkstra's method has been proposed as a method for obtaining an optimum route from a starting point to a destination point. This Dijkstra method considers all the intersections existing in a region whose radius is a straight line connecting the starting point and the destination, or in a region larger than the region, and calculates the shortest route from the starting point to the destination as the intersection netlist CRNL. It refers to and searches. FIG. 10 is a schematic explanatory diagram of the Dijkstra method, in which a road is a straight line and intersections are graphed as intersections of straight lines. Distances between the intersections are known, STP is a departure point (intersection), and DSP is a destination. (Intersection).

In the Dijkstra method, the intersection net
While referring to the list CRNL, go to the departure point STP
Intersection A adjacent to the road₁~ A_FourLooking for each cross
Point A ₁~ A_FourFor each of the following intersections (departure
The total distance from the ground intersection) is calculated, and each intersection A₁~ A_Four
Sequencing that identifies the previous intersection in correspondence with
Stored in memory together with the file number. Then, at each intersection A
₁~ A_FourIntersection B adjacent to each other along the road_ijSearch for
Then, at the intersection, go through the corresponding preceding intersection
Calculate the cumulative distance from the departure point and check each intersection B_ijCorresponding to
Sequential number that identifies the previous intersection
It is stored in the memory together with. For example, at intersection A₁Against
For three intersections B₁₁, B₁₂, B₁₃Headline each of these
Corresponding to the intersection, B₁₁: Intersection A₁Cumulative distance Bd from the place of departure via₁₁ B₁₂: Intersection A₁Cumulative distance Bd from the place of departure via₁₂ B₁₃: Intersection A₁Cumulative distance Bd from the place of departure via₁₃ .. (A) corresponds to intersection A₁With the sequential number of
I remember. Also, at intersection A ₂For three intersections
B_{twenty one}, B_{twenty two}, B_{twenty three}Is obtained, and each intersection B_{twenty one}, B_{twenty two}, B _{twenty three}
Corresponding to, B_{twenty one}: Intersection A₂Cumulative distance Bd from the place of departure via_{twenty one} .. (B) B_{twenty two}: Intersection A₂Cumulative distance Bd from the place of departure via_{twenty two} B_{twenty three}: Intersection A₂Cumulative distance Bd from the place of departure via_{twenty three} The corresponding intersection A₂Memorize with. Other intersection A
₃, A_FourSimilarly, search for an adjacent intersection and
Data. By the way, at intersection B₁₃And B_{twenty one}Are the same
It is an intersection. Thus, the intersection where the data should be stored
Have already overlapped, and already accumulated on different routes for the intersection.
When the distance data is stored, the total distance from the point of departure
Separation Bd₁₃And Bd_{twenty one}Of the smaller data
Memorize only. For example, Bd₁₃> Bd_{twenty one}If so,
Difference point B₁₃(= B_{twenty one}) The cumulative distance shown in (b) as data
Separation Bd_{twenty one}Intersection A just before, which corresponds to₂Sequence of
The card number is finally stored.

Thereafter, in the same manner, each intersection B_ijabout
Adjacent intersection C_ijFor each intersection C _ijTo correspond
Obtain the cumulative distance from the departure point via the intersection just before
Therefore, with the sequential number of the intersection before this one
In the intersection netlist,
For adjacent intersections, find the
From the departure point via the corresponding intersection
Calculate the total distance and the sequential number of the intersection before you
If you memorize it together with the number, you will finally reach the destination (intersection)
Reach the DSP.

When the destination DSP is reached, the destination (m
The intersection before the one stored in association with the next intersection), the intersection before the one stored in association with the intersection, ... The route that is sequentially connected to the side is the shortest optimal route. As described above, the intersection netlist CRNL is stored in advance in the CD-ROM as a part of the road layer, and is not stored in the CD-ROM. It may be created using road layer information (road list RDLT, intersection configuration node list CRLT, node table NDTB, etc.). Alternatively, a route search may be performed from the destination intersection to the departure intersection. Similarly, the optimum route can be obtained.

As described above, according to the Dijkstra method, the optimum route can be obtained using the shortest distance as an index in graph theory. Therefore, the optimum route can be displayed together with the vehicle position mark in the map image on the screen, and the driver can be guided to the desired destination.

[0012]

However, the optimum route displayed on the screen may include a section that is closed on the way, such as construction, or a section that is expected to be congested. , If you want to drive on another route, you must change the route search conditions such as highway priority or road priority with large width, set the destination etc. again and start the route search, Since the operation is complicated and it currently takes several tens of seconds to several minutes to finish searching for one optimal route, it is necessary to wait a long time until the desired optimal route is obtained. There was a problem.

From the above, it is an object of the present invention to obtain a plurality of optimum routes under different conditions with a single search process.
It is an object of the present invention to provide a guide route search method for an in-vehicle navigator that allows a desired route to be selected easily and quickly.

[0014]

According to the present invention, the above-mentioned problems are, for each intersection, information for specifying the intersection, information for specifying an adjacent intersection along the road from the intersection, and information for specifying the intersection from the intersection. In an in-vehicle navigator having an optimum route searching means for searching an optimum route connecting a departure point to a destination by the Dijkstra method with reference to a predetermined intersection netlist including distance information to the intersection, in the optimum route searching means, When calculating a simple cumulative distance for each intersection and newly registering it as a pair with the information that identifies the previous intersection on the route of interest, depending on the type of road connecting the intersection and the previous intersection , Priority classification cumulative distance obtained by multiplying the distance information of the intersection netlist by a predetermined coefficient and weighting, and specify the previous intersection on the route of interest According to the set of information and the width of the road connecting the intersection and the previous intersection, the width information of the intersection netlist is multiplied by a predetermined coefficient and weighted to obtain the width-first cumulative distance and the route of interest. Either one of the sets of information that identifies the previous intersection at, or
A means for registering both separately, and a set of information for identifying a type priority cumulative distance and an intersection before one on the route of interest for a certain intersection, or a width prior priority cumulative distance and one for the route of interest When attempting to register a set of information that identifies the intersection, if the same content on different routes has already been registered for the intersection, the type priority cumulative distance or width priority cumulative distance A means for registering the same contents by replacing the same contents in a set of information specifying the type-based cumulative total distance and the intersection before this, or a set of information specifying the total cumulative prioritized type and the intersection before one, and a purpose When processing is completed up to the ground intersection (or the departure intersection), in addition to the shortest guide route as seen in the simple cumulative distance, the destination intersection (or the departure intersection), the destination intersection (or the departure intersection) ) One before the intersection of the type priority total distance registered for one before the intersection, - according to the type priority total distance registered for the intersection
.., The shortest guide route that is seen by sorting the departure point intersections (or destination intersections) in reverse order (or normal order)
At the destination intersection (or departure intersection), the intersection immediately before the intersection width registered for the destination intersection (or departure intersection), the accumulated width priority accumulated distance for the intersection The intersection just before this one ...
.. This is achieved by providing a means for determining either or both of the shortest guide route in which the departure point intersection (or the destination intersection) is arranged in the reverse order (or the normal order) in the priority order of the width.

[0015]

According to the present invention, while searching for the optimum route connecting the starting point to the destination by the Dijkstra method, the simple cumulative distance is calculated for each intersection and the 1
When newly registering as a pair with the information specifying the previous intersection, the distance information in the intersection netlist is multiplied by a predetermined coefficient and weighted according to the type of the road connecting the intersection and the previous intersection. However, the distance information of the intersection netlist is determined according to the type priority cumulative distance obtained and the information set that identifies the previous intersection on the route of interest, and the width of the road connecting the intersection and the previous intersection. To the width-first cumulative distance obtained while multiplying with a predetermined coefficient and weighting, and either one of the set of information for specifying the preceding intersection on the route of interest, or both are registered separately, For each intersection, register the type priority cumulative distance and a set of information that specifies the previous intersection on the route of interest, or the width priority cumulative distance and a set of information that specifies the previous intersection on the route of interest. When Utosuru already when with respect to the intersection, the same contents of the different routes are registered,
A set of information that identifies the type-preferred cumulative distance and the previous intersection on the route with the smaller type-preferred cumulative distance or the width-preferred cumulative distance, or information that identifies the type-preferred cumulative distance and the previous intersection When the same contents are replaced and registered in the set of, and the processing is completed up to the destination intersection (or the departure intersection), in addition to the shortest guide route seen by the simple cumulative distance, the destination intersection (or the departure intersection) , The previous intersection related to the type priority cumulative distance registered to the destination intersection (or the departure intersection), the previous intersection related to the type priority cumulative distance registered to the intersection,
..., the shortest guide route when the departure intersections (or destination intersections) are arranged in reverse order (or ascending order) in priority order, destination intersections (or departure intersections), destination intersections (or departures) An intersection before the width-first accumulated total distance registered for the intersection, a previous intersection for the width-first accumulated distance registered for the intersection,
.. Either or both of the shortest guide route in which the departure crossing (or the destination crossing) is arranged in the reverse order (or the normal order) and the width is prioritized. As a result, the driver only needs to perform one operation such as destination setting to search for the optimum route, and in addition to the shortest guide route seen from the simple cumulative distance, the shortest guide route under type priority. And either one or both of the shortest guide routes under the priority of width can be obtained together, and two or three conditions with mutually different conditions can be used while sharing the part that refers to the intersection netlist. Since the guide route can be obtained by parallel processing, the route search can be completed without much time difference from obtaining only one guide route under one condition.

[0016]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Overall Configuration FIG. 1 is an overall configuration diagram of an in-vehicle navigator according to an embodiment of the present invention. In the figure, 11 is a CD storing map data
-ROM (map information storage unit). The map data is composed of a road layer, a background layer, a character layer, and the like. Reference numeral 12 is a display device (CRT) that draws a map image and a vehicle position mark according to the current position of the vehicle, a guide route searched by the optimum route search, and 13 is a vehicle based on the traveling distance and the direction of the traveling vehicle. Is a vehicle position detection unit that calculates the current position of the vehicle. Although not shown, the vehicle position detection unit 13 calculates a position sensor that detects a traveling direction of the vehicle, a distance sensor that detects a traveling distance, and a current position (longitude, latitude) of the vehicle based on the direction and the traveling distance. CP for
Have U.

Reference numeral 14 is an operation unit equipped with a map search key, an enlargement / reduction key, a map scroll key, a route guidance mode key, a route change key, and the like, and 15 is a map display control device. And a vehicle position mark and a guide route image are generated.

In the map display control device 15, 15a reads out map data (for example, 9 screens of map data) in a range wider than the screen display range around the current position from the CD-ROM 11 based on the vehicle position data, and stores the map data in the map data. It is a map image drawing unit that generates a dot image map image based on the map image.

Reference numeral 15b is a guide route drawing section for generating a guide route image based on one of the three guide route data connecting the starting point to the destination obtained by the optimum route searching process. A video RAM 15c stores a map image and a guide route image. Map image drawing unit 1
In 5a, the display range of the display screen is the video RAM 15
In order not to exceed the image range of c, as the vehicle runs,
The video RAM 15c is rewritten at any time, and the guide route drawing unit 15b also generates a guide route image according to the traveling of the vehicle and stores it in the video RAM 15c.

Reference numeral 15d is a read-out control section for reading out one screen of map image from the video RAM 15c so that the current position of the vehicle is located at the center of the display screen. The read-out position is designated by the map image drawing section 15a. 15
e is a vehicle position mark generation unit for displaying a vehicle position mark in the center of the display screen, and 15f is an optimum route search unit, which is a road included in the map data when the departure point and the destination are input in the route guidance mode. Optimal route (shortest route) that connects the departure point to the destination based on the layer information
Is calculated under three conditions (shortest in simple cumulative distance, shortest in type priority, shortest in width priority). Reference numeral 15g is a guide route storage unit that stores, as guide route data, a node sequence that forms an optimum route connecting a starting point to a destination. As shown in FIG. 2, simple guide route data, type priority guide route data, width priority The three guide route data of the guide route data are stored separately.

Reference numeral 15h is a combining unit, which is a video RAM 15
c, the map image, the guide route image, and the vehicle position mark image respectively read from the vehicle position mark generation unit 15e are combined and output to the display device 12 for image display.

The road layer included in the road layer map data has the same data structure as in FIG. 9, and includes a road list RDLT, an intersection node list CRLT, a node table NDTB, and an intersection net prepared for each intersection node. The list CRNL and the like are included. However, intersection netlist CRNL
Is configured as shown in FIG.
DA includes (1) intersection sequential number (information for identifying the intersection) (2) map leaf number of the map including the intersection node (3) data unit code, intersection node ID (4) number of intersection constituent nodes (5) ) Sequential number of each adjacent intersection (6) Distance to each adjacent intersection (7) Attribute of road to each adjacent intersection (road type, width), etc. Up to seven adjacent intersection data are stored in one intersection netlist. The road type data is represented by numerical values of 0 to 3, and is 0; national roads, 1; expressways, 2; general roads, 3; other roads. The width data is also represented by a numerical value of 0 to 3, 0; 1.5 m or more 2.
Less than 5m, 1; 2.5m or more and less than 5.5m, 2; 5.5m or more and less than 11.0m, 3; 11.0m or more.

Further, the intersection netlist CRNL has four rewrite data areas RDA1 to RDA4, and at the time of route search, the simple cumulative distance and 1 are stored in RDA1.
Sequential number of the previous intersection (one less the order), RDA2 type cumulative cumulative distance and sequential number of the previous intersection (one less the order), R
In DA3, the width-first priority distance and the one before (the order of 1
Sequential numbers of intersections can be stored, and the search order can be stored in RDA4.

When obtaining the simple cumulative distance for a certain adjacent intersection, the optimum route searching unit 15f stores the simple total stored in RDA1 of the intersection net list CRNL related to the previous intersection corresponding to the adjacent intersection. The distance information of the adjacent intersection is added to the distance. Further, when obtaining the type-priority cumulative distance, the type-priority cumulative distance stored in the RDA2 of the intersection net list CRNL related to the preceding intersection corresponding to the adjacent intersection is determined according to the road type according to the distance information of the adjacent intersection. The weighted distance is added by multiplying the coefficient q. In this embodiment, as an example, the correspondence between road types and coefficients is as follows. National road (0) ・ ・ ・ q = 1 Highway (1) ・ ・ ・ q = 0.5 General road (2) ・ ・ ・ q = 1 Other roads (3) ・ ・ ・ q = 2 That is, depending on the type of road Considering that there are differences in driving time and driving difficulty, even if the driving distance is the same, it is generally shorter on an expressway, and because driving is considerably easier, it is treated as shorter than the actual distance. On the other hand, on other roads, in general, it takes a long traveling time and requires careful driving, so the road is treated longer than the actual distance.

Further, when obtaining the width-first cumulative distance, the width-first cumulative distance stored in the RDA3 of the intersection net list CRNL relating to the previous intersection corresponding to the adjacent intersection is added to the distance information of the adjacent intersection. The weighted distance is added by multiplying by the coefficient r according to the width. In the present embodiment, as an example, the correspondence between the road width and the coefficient is as follows. 1.5m or more and less than 2.5m (0) ・ ・ ・ r = 4 2.5m or more and less than 5.5m (1) ・ ・ ・ r = 2 5.5m or more and less than 11.0m (2) ・ ・ ・ r = 1 11.0m or more (3・ ・ ・ R = 0.5 In other words, considering that the traveling time and driving difficulty vary depending on the width of the road, even if the traveling distance is the same, if the width is wide, the traveling time is generally relatively short. In addition, because it is relatively easy to drive, it is treated as shorter than the actual distance, and conversely, if the width is narrow, generally, it takes longer traveling time and caution is required in driving, so the distance is treated as longer than the actual distance.

Route Search Process FIGS. 4 to 7 are flowcharts showing the operation of the map display control device 15, and FIG. 8 is an explanatory diagram of route search. The route search process will be described below with reference to these figures. Here, for simplification, it is assumed that the intersection netlist CRNL of any intersection includes the first to fourth adjacent intersections, and the lower adjacent in FIG. 8 is the first adjacent intersection and the right adjacent. Is the second
It is assumed that the adjacent intersection, the upper adjacent one is the third adjacent intersection, and the left adjacent one is the fourth adjacent intersection.

At the time of route search, a route guidance mode is set by using a route guidance key on the operation unit 14. Next, the map search key is operated, and the map image drawing unit 15a is used to
A predetermined map is displayed on the display screen for each destination, and then the vehicle position mark is positioned at the starting point and the destination using the map scroll key, and these starting points and destinations are set (step in FIG. 4). 101).

When the starting point and the destination are set, the optimum route searching unit 15f checks whether the starting point is an intersection (step 102), and if it is an intersection, the starting point intersection STP is set (step 103). After step 105 If it is not an intersection, the nearest intersection is set to the departure point STP.
Then (step 104), the processing from step 105 onward is performed. When the departure point intersection STP is determined, the optimum route search unit 15f checks whether the destination is an intersection (step 10
5) If it is an intersection, it is set as the destination intersection DSP (step 106), and the processing after step 108 is performed. If it is not the intersection, the nearest intersection is set as the destination intersection DSP (step 107), and the processing after step 108 is performed. To do.

Departure intersection STP and destination intersection DS
When P is determined, the optimum route searching unit 15f firstly intersects all the intersections included in a circle centered at the departure point intersection STP and having a radius slightly longer than the distance between the departure point intersection STP and the destination intersection DSP. Netlist CRNL to C
It is read from the map data of the D-ROM 11, and the storage unit 15
It is stored in f-1 (step 108). Then, the search order i is set to 0 (step 109), and the storage unit 15f-
By referring to the intersection net list CRNL related to the i-th intersection stored in No. 1, it is checked whether or not an intersection adjacent to the i-th intersection remains (step 110). The 0th intersection is the starting point intersection STP. Note that step 110
By then, the j-th intersection (j = 0, 1, ...
Excludes items marked i).

Here, since four adjacent intersections remain, the first adjacent intersection A ₁ from the starting intersection STP to the first adjacent intersection A _{1 in the} intersection netlist CRNL related to the starting intersection STP. The distance d ₂ ,
Referring to the road type and width, the simple cumulative distance D from the departure point intersection STP to the adjacent intersection A ₁ , the departure point intersection S
Calculate the type-preferred cumulative distance D ′ weighted according to the road type between the TP and the adjacent intersection A _1, and the width-preferred cumulative distance D ″ weighted according to the road width between the departure point STP and the adjacent intersection A _1. (Steps 111 to 113) D
Let d ₁ be the simple cumulative distance from the departure point intersection STP to the i-th intersection, and it can be obtained by the following equation d ₁ + d ₂ → D. Initially, when i = 0, d ₁ = 0, so D =
It becomes d ₂ .

Further, D'is from the starting point intersection STP to the i-th
If the type-first cumulative distance to the next intersection is d ₁ ′, it can be obtained by the following equation: d ₁ ′ + q · d ₂ → D ′. Initially, when i = 0, d ₁ ′ = 0, so that D ′ = q · d ₂ . q is q when the road type from the starting point intersection STP to the adjacent intersection A ₁ is national road (0).
1, q = 0.5 for the expressway (1), q = 1 for the general road (2), and q = 2 for the other roads (3).
Further, D ″ is obtained by the following equation d ₁ ″ + r · d ₂ → D ″, where d ₁ ″ is the width-first cumulative distance from the starting point intersection STP to the i-th intersection. Initially, when i = 0, d ₁ ″ = 0, so that D ″ = r · d ₂ . r is 4, when the road width from the starting point intersection STP to the adjacent intersection A ₁ is 1.5 m or more and less than 2.5 m (0), r = 4, and r when 2.5 m or more and less than 5.5 m (1)
= 2, 5.5m or more and less than 11.0m (2) r = 1, 11.0m
In the above case (3), r = 0.5.

Then, referring to the rewriting data area RDA4 of the intersection netlist CRNL related to the intersection A ₁ stored in the storage unit 15f-1, whether the search order of the adjacent intersection A ₁ is (i + 1), If you do,
Per intersection A _1, a simple total distance of a different route and 1
It is checked whether the information specifying the previous intersection, the type priority cumulative distance and the information specifying the previous intersection, the width priority cumulative distance and the information specifying the previous intersection have been registered (step 201 in FIG. 5). ), since the NO here, so as to correspond to the adjacent intersection a _1, in the intersection network list CRNL according to the intersection a _1,
Store (a) the sequential number of the 0th intersection STP currently being focused on, (b) the simple cumulative distance D (= Ad ₁ ) from the departure intersection STP to the adjacent intersection A ₁ in the rewriting data area RDA1. , (C) Sequential number of the 0th intersection STP currently being focused on, (d) Type priority cumulative distance D ′ (= Ad ₁ ′) from the departure intersection STP to the adjacent intersection A ₁ , and rewriting data area Stored in RDA2, (e) Sequential number of 0th intersection STP currently focused on, (f) Departure intersection S
The width-first cumulative distance D ″ (= Ad ₁ ″) from TP to the adjacent intersection A ₁ is stored in the rewriting data area RDA3, and (g) (i + 1) = 1 as the search order of the adjacent intersection A ₁ is stored. The data is stored in the rewrite data area RDA4 (step 202). Note that the information (a), (c), and (e) that specify the previous intersection (the 0th-order intersection STP) registered corresponding to the intersection A ₁ are all the same, but will be described later. As described above, there are cases where different information is obtained by rewriting.

Then, returning to step 110 in FIG. 4, the intersection netlist CR for the departure point intersection STP is targeted.
With reference to the NL, it is checked whether or not the intersection adjacent to the 0th-order intersection of interest still remains, and if it remains, the same processing is repeated. As a result, since the adjacent intersections A _{1 to} A ₄ exist in the intersection netlist of the departure point intersection STP,
These are primary intersections, and each data rewriting area of the intersection netlist CRNL related to these primary intersections has one corresponding to the simple cumulative distances Ad _{1 to} Ad ₄ and adjacent intersections A _{1 to} A _4. Sequential number that identifies the front intersection STP, type priority cumulative distance Ad ₁ ′ -A
Sequential number that identifies the previous intersection STP corresponding to d ₄ ′, width-first cumulative distance Ad ₁ ″ -A
A sequential number that specifies the previous intersection STP corresponding to d ₄ ″ is registered.

When the processing is completed for all the adjacent intersections included in the intersection net list CRNL for the departure point intersection STP, the optimum route searching unit 15f determines whether there is a 0th intersection other than the departure point intersection STP. (Fig. 4
Step 110 of FIG. 6, step 301 of FIG. 6) does not exist, so the destination intersection D is reached while the destination intersection DSP is reached, in other words, the destination is the (i + 1) th intersection.
It is judged whether SP is included (302), and if not, i is incremented to 1 (step 30).
3). Then, the process proceeds to step 110 in FIG. 4, and attention is paid to one of the first-order intersections A ₁ , the storage unit 15f−
Intersection netlist C related to intersection A ₁ stored in ₁
With reference to the RNL, it is determined whether or not the adjacent intersections remain except the 0th-order intersection STP.

Here, B₁₁, B₁₂, B₁₄There exists
Then, first of all, the first adjacent intersection B ₁₁About the intersection
A₁Refer to the intersection netlist CRNL related to
From the starting point intersection STP to the adjacent intersection B₁₁Up to simple
Total distance D, type priority total distance D ', width priority total distance
D ″ is calculated (steps 111 to 113).
The first intersection A that is currently focused on from the difference point STP₁Until
Simple total distance d₁, Type priority cumulative distance d₁′, Width
Destination cumulative distance d₁″ Is stored in the storage unit 15f-1 at the intersection A₁To
RDA1 to RDA3 of the relevant intersection netlist CRNL
To Ad₁, Ad₁′, Ad₁Is stored as
First intersection A₁From the adjacent intersection B₁₁Distance to
₂Is intersection A₁Described in the intersection netlist CRNL related to
Because it ’s remembered, Ad₁+ D₂→ D to the first intersection A from the starting point STP₁Via
Said adjacent intersection B₁₁The simple cumulative distance D to
And Ad₁′ + Q · d₂→ D 'from the starting point intersection STP to the first intersection A₁Via
Said adjacent intersection B₁₁Up to type-based cumulative distance D '
Wanted, Ad₁″ + Q · d₂→ D ″ to start intersection STP to the first intersection A₁Via
Said adjacent intersection B₁₁Up to type priority cumulative distance D ″
I want it.

Next, referring to the rewriting data area RDA4 of the intersection netlist CRNL related to the adjacent intersection B ₁₁ stored in the storage unit 15f-1, it is checked whether the search order of the adjacent intersection B ₁₁ is (i + 1) (see FIG. Step 2 of 5
01), NO here, so the adjacent intersection B ₁₁
In the intersection netlist CRNL relating to the intersection B ₁₁ , (a) the first one which is currently focused.
Sequential number of next intersection A ₁ , (b) Simple cumulative distance D from the departure point intersection STP to the adjacent intersection B ₁₁
(= Bd ₁ ) is stored in the rewriting data area RDA1, (c) the sequential number of the primary intersection A ₁ currently being focused on, (d) the type priority from the departure point intersection STP to the adjacent intersection B ₁₁ concerned Total distance D '(= B
d ₁ ′), is stored in the rewrite data area RDA2,
(E) Rewriting data area for the sequential number of the first intersection A ₁ currently being focused on, (f) the width-first cumulative distance D ″ (= Bd ₁ ″) from the departure point intersection STP to the adjacent intersection B ₁₁ stored in RDA3, stored in the rewrite data area RDA4 the (i + 1) = 2 as (g) search order of the adjacent intersection B ₁₁ (step 202).
Then, returning to step 110 in FIG. 4, the storage unit 15f-1
By referring to the intersection netlist CRNL related to the first-order intersection A ₁ stored in, it is checked whether an intersection adjacent to the currently-selected first-order intersection A ₁ still remains, and if there is, the same processing is performed. repeat.

When the optimum route searching unit 15f returns to step 110, since the adjacent intersections B ₁₂ and B ₁₄ are present, YES.
To judge. Then, these, for the second adjacent intersection B _12, simple total distance D from the departure point intersection STP to the adjacent intersection B _12, type priority total distance D ', after calculating the width preferences total distance D "(step 111 to 113), the data rewriting area RD of the intersection netlist CRNL corresponding to the adjacent intersection B ₁₂ stored in the storage unit 15f-1
By referring to A4, it is checked whether the search order is already 2 (step 201 in FIG. 5), and since it is NO, the sequential number of the first intersection A ₁ and the simple cumulative distance D = Bd ₁₂ in the data rewriting area RDA1. In RDA2, the sequential number of the first intersection A ₁ and the type priority cumulative distance D ′
= Bd ₁₂ ′, RDA 3 has the sequential number of the first intersection A ₁ and the width-first cumulative distance D ″ = Bd ₁₂ ″, RDA 4
The search order 2 is registered in (step 202). And
Returning to step 110 of FIG. 4, the remaining adjacent intersections B ₁₄ stored in the intersection netlist CRNL of the intersection A ₁ are processed in the same manner as described above.

When the processing for B ₁₄ is completed, the optimum route searching unit 15f checks whether or not there is another first-order intersection (step 301 in FIG. 6), and in this case, A ₂ , A
_{Since 3} and A ₄ are present, the processing after step 110 of FIG. 4 is performed by using A ₂ as a new first intersection (step 304).

Intersection netlist CRNL of intersection A ₂
Although the first to fourth adjacent intersection B ₂₁ .about.B ₂₄ is present,
B ₂₄ = 4th adjacent intersection B ₂₄ because it is the starting point intersection STP
Are removed and processed in step 110. And first B
_{For 21} , the optimum route search unit 15f refers to the intersection netlist CRNL of the intersection A ₂ and refers to the departure point S
Adjacent intersection B from TP via the first adjacent intersection A ₂
The simple cumulative distance D up to ₂₁ , the type priority cumulative distance D ′, and the width priority cumulative distance D ″ are calculated (steps 110 to 11).
3).

[0040] Then, the optimum route searching portion 15f is the order of the reference to the intersection network list CRNL of stored in the storage unit 15f-1 adjacent intersection B ₂₁ adjacent intersection B ₂₁ is 2 or check (FIG. 5 Step 201), B ₂₁ = B ₁₂
Since the degree of the adjacent intersection B ₁₂ is already 2, the result is YES. This indicates that the intersection B ₁₂ adjacent to the primary intersection A ₁ has already been processed (the data (a) to (g) has been stored). In this case, first, the adjacent intersection Intersection netlist CRN related to B ₁₂
The simple cumulative distance * D = Bd ₁₂ from the departure point intersection STP stored in the rewriting data area RDA1 of L is compared with the size of the distance D obtained in step 111 this time (step 203).

If D << D, the adjacent intersection B
The sequential number of the i-th intersection A ₁ stored in the rewriting data area RDA1 of the intersection netlist CRNL of ₁₂ (= B ₂₁ ) is the i-th intersection A currently focused on.
_While replacing with the sequential number of ₂ , the simple cumulative distance * D is rewritten with D = Bd ₂₁ (step 20).
4). If D ≧ * D, RDA1 is not rewritten.
Next, the intersection netlist CR relating to the adjacent intersection B ₁₂
Type priority cumulative distance * D '= B from the departure point intersection STP stored in the rewriting data area RDA2 of the NL
d ₁₂ ′ is compared with the size of the distance D ′ found in step 112 this time (step 205). If D '<* D',
Intersection netlist C of the adjacent intersection B ₁₂ (= B ₂₁ ).
The sequential number of the i-th intersection A ₁ stored in the rewriting data area RDA2 of the RNL is replaced with the sequential number of the i-th intersection A ₂ of interest, and the type-first cumulative distance * D ′ is D ′ = It is rewritten with Bd ₂₁ (step 206). If D ′ ≧ * D ′, then R
DA2 is not rewritten.

Next, the width-first priority cumulative distance from the starting point intersection STP stored in the rewriting data area RDA3 of the intersection netlist CRNL related to the adjacent intersection B ₁₂ *
D ″ = Bd ₁₂ ″ and the distance D ″ obtained in step 113 this time
The size of is compared (step 207). If D ″ <* D ″, the current sequential number of the i-th intersection A ₁ stored in the rewriting data area RDA3 of the intersection netlist CRNL of the adjacent intersection B ₁₂ (= B ₂₁ ) is currently being considered. Replace with the sequential number of the i-th intersection A ₂ and replace the type priority cumulative distance * D ″ with D ″ = B
It is rewritten with d ₂₁ (step 208). If D ″ ≧ * D ″, RDA3 is not rewritten. In general, even if the data is registered at the same adjacent intersection, the cumulative total distance, the type-preferred cumulative distance, and the width-preferred cumulative distance are different from each other, and therefore, as a sequential number that identifies the previous intersection. Different data are registered. After completing these processes, the process returns to step 110 in FIG. 4 and the same process is performed for the next adjacent intersection related to the first intersection A ₂ .

Thereafter, the same processing is sequentially repeated,
In the check in step 302 in FIG. 6, the (i +
1) Destination intersection DSP among all the following intersections
When it is determined to be YES, the destination stored in the rewriting data area RDA1 is first stored in the intersection netlist CRNL related to the destination intersection DSP stored in the storage unit 15f-1. Stored in the rewriting data area RDA1 in the previous (m-1) th intersection corresponding to the intersection DSP (m-th intersection) and the intersection netlist CRNL related to the (m-1) th intersection. In the intersection netlist CRNL relating to the secondary intersection, the (m−2) th previous intersection, which corresponds to the relevant intersection, the primary intersection stored in the rewriting data area RDA1. , A node that connects the departure point intersection STP in the reverse order to determine the shortest optimum route as viewed from the simple cumulative distance, and configures the optimum route from the departure point intersection STP to the destination intersection DSP. The stores the guidance route storage section 15g as a simple guide route data (step 305).

Next, in the intersection netlist CRNL related to the destination intersection DSP stored in the storage unit 15f-1, the destination intersection DSP (mth-order intersection) stored in the rewriting data area RDA2 is set. ) Corresponding to
The previous (m-1) th intersection and the previous (m-1) corresponding to the intersection stored in the rewriting data area RDA2 in the intersection netlist CRNL related to the (m-1) th intersection -2) Next intersection ... In the intersection netlist CRNL relating to the second intersection, the first intersection and the departure intersection STP stored in the rewriting data area RDA2 are connected in reverse order, and the type priority accumulation is performed. The shortest optimum route in terms of distance is determined, and the node sequence forming the optimum route from the departure point intersection STP to the destination intersection DSP is stored in the guide route storage unit 15g as type priority guide route data (step 306). Finally, the storage unit 15f-1
In the intersection netlist CRNL related to the destination intersection DSP stored in, the one (m-) in front of the destination intersection DSP (m-th intersection) stored in the rewriting data area RDA3. 1) The next intersection, the (m
-1) In the intersection netlist CRNL related to the next intersection, the previous (m-2) th intersection corresponding to the intersection stored in the rewriting data area RDA3, ...
In the intersection netlist CRNL related to the secondary intersection, the shortest optimum route viewed from the width-first cumulative distance by connecting the primary intersection and the departure intersection STP stored in the rewriting data area RDA3 in reverse order Is determined and the node sequence forming the optimum route from the departure point intersection STP to the destination intersection DSP is stored in the guide route storage unit 15g as the width priority guide route data, and the route search process is completed (step 307). ).

Here, for the sake of simplicity, the number of adjacent intersections at each intersection has been described as 4. However, even if there are various numbers at each intersection, similarly, a simple guide route, a type priority guide route, Three width-first priority routes are required. In addition, the route search by the Dijkstra method is performed at the destination intersection D
It can also be executed by setting SP as the 0th-order intersection and performing the same processing as described above until the intersection at the departure point STP is reached. In this case, the departure point intersection, the previous intersection that is stored in association with the departure point intersection, the previous intersection that is stored in association with the intersection, ... Connect in order to determine the optimum route.

Upon completion of the search for the route guidance optimum route, the simple mode is first set (step 308), and the map image drawing section 15a inputs the vehicle position data from the vehicle position detecting section 13 (step 30).
9) The map data including the vehicle position is read from the CD-ROM 11 and drawn on the video RAM 15c. On the other hand, based on the vehicle position data, the guide route drawing unit 15b selects a portion within the area drawn in the video RAM 15c from the simple guide route data stored in the guide route storage unit 15g, and sets the guide route in the video RAM 15c. Emphasize a given color in bold.

In response to the read control of the map image drawing unit 15a, the read control unit 15d cuts out a map image of one screen centered on the vehicle position from the map images drawn in the video RAM 15c, and sends it to the combining unit 15h. Output. The vehicle position mark generation unit 15e also generates a predetermined vehicle position mark and outputs it to the synthesizing unit 15h. The synthesizing unit 15h synthesizes the vehicle position mark with the map image including the emphasized guide route, outputs it to the display device 12, and displays it on the screen (step 310). As a result, the guide route with the shortest distance connecting the departure point intersection STP to the destination intersection DSP is displayed on the screen.

Looking at this guide route, if there is no particular problem, if the vehicle continues traveling along the guide route as it is, the vehicle position data output from the vehicle position detection unit 13 changes every time the vehicle travels a certain distance. (Steps 311 to 31 1
3), the map image drawing unit 15a cuts out a map image of one screen centered on the vehicle position from the map images drawn in the video RAM 15c, and outputs it to the synthesizing unit 15h. The vehicle position mark generation unit 15e also generates a predetermined vehicle position mark and outputs it to the synthesizing unit 15h. The synthesizing unit 15h synthesizes the vehicle position mark with the map image including the emphasized guide route, outputs it to the display device 12, and displays it on the screen (step 310). If the cut-out range from the video RAM 15c comes to the end of the map image drawn on the video RAM 15c, the map image drawing unit 15a will display the CD-R.
New map data is read from the OM 11, a map image including the vehicle position in the center is drawn in the video RAM 15c, and the guide route drawing unit 15b stores in the video RAM 15c the simple guide route data stored in the guide route storage unit 15g. Select the part that fits in the drawn area, and select video RAM
The guide route is highlighted in bold in 15c with a predetermined color. As a result, the map image with the vehicle position at the center is always displayed on the screen together with the emphasized guide route (simple guide route) and the vehicle position mark, so that the driver can correctly reach the desired destination.

On the other hand, at first, looking at the guide route displayed on the screen in the simple mode, there is a closed road in the middle, or a busy section of the city is included. When the driver wants to change to, the driver presses the route change key on the operation panel 2. Then, the type priority mode is set (step 311, step 4 in FIG. 7).
01), the map image drawing unit 15a inputs the vehicle position data from the vehicle position detecting unit 13 (step 402), reads the map data including the vehicle position from the CD-ROM 11,
Drawing on the video RAM 15c. On the other hand, the guide route drawing unit 15b determines the guide route storage unit 15 based on the vehicle position data.
From the type-priority guide route data stored in g, a portion that enters the area drawn in the video RAM 15c is selected, and the guide route is highlighted in a thick color in the video RAM 15c with a predetermined color.

In response to the reading control of the map image drawing unit 15a, the reading control unit 15d cuts out a map image of one screen centered on the vehicle position from the map images drawn in the video RAM 15c, and sends it to the synthesizing unit 15h. Output. The vehicle position mark generation unit 15e also generates a predetermined vehicle position mark and outputs it to the synthesizing unit 15h. The synthesizing unit 15h synthesizes the vehicle position mark with the map image including the emphasized guidance route, outputs it to the display device 12, and displays it on the screen (step 403). As a result, the shortest guide route that connects the departure point intersection STP and the destination intersection DSP and is viewed with priority given to the type is displayed on the screen. Since expressways are prioritized for this type priority route,
You can reach your destination quickly and easily
When the driver determines that the route is the desired route, the vehicle may start traveling as it is.

Each time the vehicle travels a certain distance, the vehicle position detection unit 1
Since the vehicle position data output from No. 3 changes (steps 404 to 406), the map image drawing unit 15a cuts out one screen of the map image centered on the vehicle position from the map images drawn in the video RAM 15c. , Synthesis section 15h
Output to. The vehicle position mark generation unit 15e also generates a predetermined vehicle position mark and outputs it to the synthesizing unit 15h.
The synthesizing unit 15h synthesizes the vehicle position mark with the map image including the emphasized guidance route, outputs it to the display device 12, and displays it on the screen (step 403). Young, Video RA
When the cut-out range from M15c comes to the end of the map image drawn in the video RAM 15c, the map image drawing unit 15
a reads the new map data from the CD-ROM 11 and displays the map image including the vehicle position in the center in the video RAM 15
c on the guide route drawing unit 15b.
From the type-priority guidance route data stored in 5g, a portion that falls within the area drawn in the video RAM 15c is selected, and the guidance route is highlighted in bold in a predetermined color in the video RAM 15c. As a result, the map image with the vehicle position in the center is always highlighted on the screen.
Since it is displayed together with the vehicle position mark, the driver can correctly reach the desired destination.

On the other hand, when the type preferential guidance route is displayed on the screen, the driver wants to go to the destination on a route avoiding the expressway because of problems such as cost and wanting to eat during the course. Then, the path change key of the operation panel 2 is pressed again. Then, the width priority mode is set (step 40
4, 407), the map image drawing unit 15a inputs the vehicle position data from the vehicle position detecting unit 13 (step 408),
The map data including the vehicle position is read from the CD-ROM 11 and drawn on the video RAM 15c. On the other hand, the guide route drawing unit 15b selects, based on the vehicle position data, a portion within the area drawn in the video RAM 15c from the width-first guide route data stored in the guide route storage unit 15g, and the guide route is displayed in the video RAM 15c. Is highlighted with a predetermined color thickly.

In response to the reading control of the map image drawing unit 15a, the reading control unit 15d cuts out a map image for one screen centered on the vehicle position from the map images drawn in the video RAM 15c, and sends it to the synthesizing unit 15h. Output. The vehicle position mark generation unit 15e also generates a predetermined vehicle position mark and outputs it to the synthesizing unit 15h. The synthesizing unit 15h synthesizes the vehicle position mark with the map image including the emphasized guidance route, outputs it to the display device 12, and displays it on the screen (step 409). As a result, the shortest guide route viewed from the intersection of the departure point STP to the destination intersection DSP viewed from the width is displayed on the screen. This width-first route does not include highways, but roads with a wide width are prioritized, so you can reach your destination in a relatively short time and with relatively easy driving. The detour can be freely performed, and when the driver determines that the route is the desired route, the vehicle can simply start traveling.

Then, the vehicle position data output from the vehicle position detection unit 13 changes every time the vehicle travels a certain distance (steps 410 to 412), and therefore the map image drawing unit 15a.
Cuts out a map image for one screen centered on the vehicle position from the map image drawn in the video RAM 15c and outputs it to the synthesizing unit 15h. In addition, the vehicle position mark generation unit 15
e also generates a predetermined vehicle position mark and outputs it to the synthesizing unit 15h. The synthesizing unit 15h synthesizes the vehicle position mark with the map image including the emphasized guidance route, outputs it to the display device 12, and displays it on the screen (step 409). If the cut-out range from the video RAM 15c is the video RAM 1
When it comes to the end of the map image drawn in 5c, the map image drawing unit 15a reads new map data from the CD-ROM 11, and the map image including the vehicle position in the center is recorded on the video RA.
Drawing on M15c, the guide route drawing unit 15b selects a portion that enters the area drawn on the video RAM 15c from the width-first guide route data stored in the guide route storage unit 15g and sets the guide route to the video RAM 15c in a predetermined color. To highlight boldly. As a result, the map image with the vehicle position in the center is always displayed on the screen together with the emphasized guide route (width priority guide route) and the vehicle position mark, so that the driver can correctly reach the desired destination. ..

In the above-described embodiment, the maximum number of adjacent intersections that can be stored in the intersection netlist CRNL is set to 7, but it may be set to 8 or more. Further, although the intersection netlist CRNL is configured to include the road type and width information up to the adjacent intersection in advance, the CD-R is not included in the intersection netlist CRNL.
It may be created from the road layer information in the map data stored in the OM1, and the intersection netlist CRNL itself is also included in the map data stored in advance in the CD-ROM 1, and when the route search is started. , The optimum route search unit 15f reads from the CD-ROM 1, and the storage unit 15
However, when the intersection netlist CRNL is not included in the map data of the CD-ROM 1, the optimum route searching unit 15f uses the map data stored in the CD-ROM 1 to find the required intersection. By creating the intersection netlist CRNL and storing the intersection netlist CRNL in the storage unit 15f-1, in the same manner as described above, the three conditions of the simple cumulative distance, the type-preferred cumulative distance, and the width-preferred cumulative distance are complied with.
It is possible to search for one guide route. In addition, although three guide routes are obtained under the three conditions of the simple cumulative distance, the type-preferred cumulative distance, and the width-preferred cumulative distance, two guide routes are obtained under the two conditions of the simple cumulative distance and the type-preferred cumulative distance. May be obtained, or two guide routes may be obtained under the two conditions of the simple total distance and the width-first priority total distance.

[0056]

As described above, according to the present invention, the simple cumulative distance is calculated for each intersection while searching for the optimum route connecting the starting point to the destination by the Dijkstra method, and the route immediately before the target route is calculated. When newly registering as a pair with the information for identifying an intersection, the distance information of the intersection netlist is multiplied by a predetermined coefficient and weighted according to the type of road connecting the intersection and the previous intersection. According to the type priority cumulative distance and the set of information that identifies the previous intersection on the route of interest, and the width of the road that connects the intersection and the previous intersection, the distance information of the intersection netlist is specified. Either one of the width-first cumulative distance obtained by multiplying by the coefficient and weighting and the information set that identifies the previous intersection on the route of interest, or both are registered separately, and a certain intersection is registered. Type Priority total distance and one short of identifying the intersection information set in the focused path, or,
When trying to register a set of information that specifies the width-first cumulative distance and the previous intersection on the route of interest, when the same content on different routes has already been registered for the intersection, the type A set of information that identifies the type-preferred cumulative distance and the previous intersection on the route with the smaller cumulative total-preferred distance or width-preferred cumulative distance, or a set of information that identifies the type-preferred cumulative distance and the previous intersection. When the same contents are replaced and registered in the group and processing is completed up to the destination intersection (or the departure intersection), in addition to the shortest guide route seen from the simple cumulative distance, the destination intersection (or the departure intersection), An intersection before the type priority cumulative distance registered for the destination intersection (or a departure point intersection), an intersection before the type priority cumulative distance registered for the intersection, ... , The shortest guidance route in which the departure point intersection (or destination intersection) is arranged in reverse order (or normal order) in priority order, the destination intersection (or the departure point intersection), the destination intersection (or the departure point intersection) , The previous intersection related to the width-first cumulative distance registered to the intersection, the previous intersection related to the width-first cumulative distance registered to the intersection, ..., Departure intersection (or destination intersection ) Are arranged in reverse order (or ascending order) to find either or both of the shortest guide routes viewed in the priority order of width, so that the driver can perform optimum route search such as destination setting. By performing the necessary operation only once, in addition to the shortest guide route seen from the simple cumulative distance, either the shortest guide route under type priority or the shortest guide route under width priority, or, Both are requested together In addition, it is possible to obtain two or three guide routes with different conditions by parallel processing while sharing the part that refers to the intersection netlist, so that only one guide route is obtained under one condition. The route search can be completed without much difference in time.

Further, by including the intersection netlist in the map data stored in the map information storage means in advance, the time required to create the intersection netlist can be saved.

Furthermore, the intersection netlist is created in the vehicle-mounted navigator based on the map data stored in the map information storage means, thereby avoiding an increase in the storage capacity of the map information storage means. You can

Further, the intersection netlist includes, for each adjacent intersection, information on either one or both of the type and width of the road connecting the adjacent intersection and the intersection, and referring to the intersection netlist, By storing either one or both of the type priority cumulative distance and the width priority cumulative distance, the road type and the width are stored in the map information storage means in order to obtain the type priority cumulative distance and the width priority cumulative distance. It is possible to eliminate the time required to search from the stored map data.

[Brief description of drawings]

FIG. 1 is an overall configuration diagram of a vehicle-mounted navigator according to an embodiment of the present invention.

FIG. 2 is an explanatory diagram of data stored in a guide route storage unit.

FIG. 3 is an explanatory diagram of an intersection netlist.

FIG. 4 is a first flowchart showing the operation of the map display control device.

FIG. 5 is a second flowchart showing the operation of the map display control device.

FIG. 6 is a third flowchart showing the operation of the map display control device.

FIG. 7 is a fourth flowchart showing the operation of the map display control device.

FIG. 8 is an explanatory diagram of route search.

FIG. 9 is an explanatory diagram showing a data structure of a road layer.

FIG. 10 is an explanatory diagram of a Dijkstra method.

[Explanation of symbols]

 11 map information storage unit (CD-ROM) 12 display device 14 operation unit 15 map display control device 15f optimum route search unit

Claims (4)

[Claims] 1. A predetermined intersection netlist including, for each intersection, information identifying the intersection, information identifying an adjacent intersection along the road from the intersection, and distance information from the intersection to the adjacent intersection. , And refer to the intersection netlist corresponding to the departure point intersection, for each intersection adjacent to the departure point intersection (or destination intersection), simply calculate the distance from the departure point intersection (or destination intersection) Then, referring to the corresponding intersection net list for each intersection for which the simple cumulative distance is obtained, for each intersection adjacent to the intersection, the intersection before the one on the route of interest is registered. The distance between the intersection and the adjacent intersection is added to the registered simple cumulative distance to obtain the simple cumulative distance, which is combined with the information for identifying the preceding intersection on the route of interest. While repeating the process of registering and registering a combination of information that specifies the simple cumulative distance and the previous intersection on the route of interest for a certain intersection, , When the set of information that specifies the simple cumulative distance and the previous intersection on different routes is registered, the simple cumulative distance and the previous intersection on the route with the smaller simple cumulative distance are specified. Register the information by replacing it with a set of information, and when processing is completed up to the destination intersection (or the departure intersection), register for the destination intersection (or the departure intersection) or the destination intersection (or the departure intersection) The intersection before this one, the intersection before this registered for the intersection, ..., Departure intersection (or destination intersection)
In the guide route search method of the in-vehicle navigator by the Dijkstra method that makes the route arranged in reverse order (or ascending order) the shortest guide route, the simple cumulative distance is calculated for each intersection and When newly registering as a pair with the information that identifies the front intersection, the distance information in the intersection netlist is multiplied by a predetermined coefficient and weighted according to the type of the road connecting the intersection and the previous intersection. However, according to the type priority cumulative distance obtained and the set of information that identifies the previous intersection on the route of interest and the width of the road connecting the intersection and the previous intersection, the distance information of the intersection netlist is set. Either one or both of the set of information that specifies the width-first priority cumulative distance obtained by multiplying by a predetermined coefficient and weighting and the previous intersection on the route of interest, or both, separately. A set of information that registers and identifies the type prior cumulative total distance and the previous intersection on the route of interest for a certain intersection, or the information specifying the width prioritized cumulative distance and the previous intersection on the route of interest When the same contents of different routes have already been registered for the intersection when registering the group, the type priority accumulated on the route with the smaller type priority accumulated distance or width priority accumulated distance is registered. Register the destination intersection (or departure point intersection) by replacing the same content with a group of information that specifies the distance and the previous intersection, or a group of information that specifies the type-first cumulative total distance and the previous intersection. When processing is completed, in addition to the shortest guide route seen by simple cumulative distance,
At the destination intersection (or departure point intersection), the intersection before the type priority cumulative distance registered for the destination intersection (or departure point intersection), the type priority cumulative distance registered for the intersection The intersection just before this one ...
.. The shortest guide route that is seen by categorizing the departure point intersection (or destination intersection) in reverse order (or normal order), destination intersection (or departure point intersection), destination intersection (or departure point intersection) ), The previous intersection related to the width-first accumulated total distance, the previous intersection related to the width-first accumulated total distance registered to the intersection, ...
Guidance of an in-vehicle navigator characterized in that either or both of the shortest guidance route in which the departure point intersection (or the destination intersection) is arranged in reverse order (or normal order) in terms of width priority are obtained. Route search method. 2. The guide route search method for an in-vehicle navigator according to claim 1, wherein the intersection netlist is included in the map data stored in the map information storage unit in advance. 3. The intersection netlist is created in the vehicle-mounted navigator based on the map data stored in the map information storage means.
The guidance route search method for the in-vehicle navigator described. 4. The intersection netlist includes, for each adjacent intersection, information on one or both of the type and width of a road connecting the adjacent intersection and the intersection, and referring to the intersection netlist, The guide route search method for an in-vehicle navigator according to claim 1, wherein either or both of the type priority cumulative distance and the width priority cumulative distance are required.