JP2001074482A - Route searching apparatus - Google Patents

Abstract

PROBLEM TO BE SOLVED: To enable route search at a high speed without degrading precision, by searching a route between a present place and a destination, on the basis of main road route data and each data of respective rectangular divided areas containing the present place and the destination. SOLUTION: If data of a present place P is inputted for example, data of a rectangular divided area (K 32515 for example) containing the place P is read, and link costs from the present position P to search start nodes N 32515-2 to 4 of K 32515 are computed. When this data is inputted when a destination is point Q for example near to a national road B3, data of a rectangular divided area containing position Q is read, and a link cost from point Q in this area to search start node is computed. In the case of route search for a national road, data containing routes near intersections of the national route is read out from a main adjacent node list in respective rectangular divided areas containing the present place P and the destination Q. A minimum cost between each intersection and the next is found and summed up, and a route of the smallest link cost is set for a guide route.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a route search device for searching for an optimum route to a destination and displaying the searched route on a map showing a current position in a navigation device used for an automobile or the like.

[0002]

2. Description of the Related Art In a navigation device, a DVD is used.
A drive device for driving a map data storage medium such as a ROM and a CD-ROM, a display device, a vehicle movement detecting device for detecting a current position and a current heading direction of the vehicle such as a GPS, a gyro, and a vehicle speed sensor. Based on the map data including the current position of the vehicle, a map image around the vehicle position is drawn on the display device, and the vehicle position mark is displayed on the display screen in a superimposed manner, and the map is displayed in accordance with the movement of the vehicle. By scrolling the image and fixing the map image on the screen and moving the vehicle position mark, it is possible to see at a glance where the vehicle is currently traveling.

[0003] In addition, usually, the on-vehicle navigation device is provided with a route guidance function that enables a driver to easily travel to a desired destination without making a mistake on a road. According to this route guidance function, a route with the lowest cost connecting the departure point and the destination is automatically searched using the map data, and the searched route is stored as guidance route data. The guidance route is drawn on the screen with a different color from the other roads and drawn thicker on the screen, and when the vehicle approaches within a certain distance the intersection where the route on the guidance route should be changed, the route on the map image is displayed. By drawing an arrow indicating the course at the intersection to be changed and displaying an enlarged view of the intersection on the screen, the driver can reliably and easily grasp the optimal route to the destination, and Various types of traveling are guided by voices and the like, so that the driver can safely travel by route guidance.

In order to perform the above route guidance, a DVD
-Map data as shown in FIG. 9 is recorded on a recording medium such as a ROM. That is, the map data includes a disc label 1, drawing parameters 2, figure management information 3, figures (map data) 4, index data 5, route data 6, and the like. The map leaf 4 stores character data, background data, road data, and the like, as will be described later, and stores, for example, data for each unit map obtained by dividing a topographical map of the whole of Japan by latitude and longitude. There are two types of maps, one roughly showing a wide area and the other showing a narrow area in detail.
B and C. The map display levels A, B, and C are shown in detail in this order. Each of the map display levels A, B, and C is composed of map display level management information 7 and a plurality of units 8 indicating each divided area obtained by dividing each map display level area into four, nine, and the like. Each unit has a unit header 10, a character layer 11, a background layer 12, a road layer 13, an option layer 14, and the like.

[0005] As shown in FIG. 10, a road layer 13 includes a node data NDDT20, a road link data RLDT2.
1. The road link data RLDT21 provides attribute information of the road link. The road link data RLDT21 includes the total number of nodes forming the link and the node data NDDT of each node forming the link.
20 is composed of data such as the number, road name, road type such as national highway and prefectural road, and road width. Further, the intersection data CRDT22 is a set of numbers on the node data NDDT20 of nodes closest to the intersection on the link connected to the intersection (each intersection node) for each intersection on the map. The node data NDDT 20 is a list of all nodes on the map, and includes coordinate information (longitude and latitude) for each node, an intersection identification flag indicating whether or not the node is an intersection, and indicates an intersection if an intersection. If not, it is composed of a pointer or the like pointing to the road link to which the node belongs.

On the other hand, as shown in FIG. 11, for example, the route search data 6 shown in FIG.
Search data is recorded for each layer from to a wide layer m. The search data of each hierarchy includes node connection data 16,
Link cost data 1 indicating the estimated transit time for each link
7. It is composed of route display data 18. The node connection data 16 includes, as shown in FIG.
g, P, and Q are data indicating which node is connected. As shown in FIG. 12, the link cost data 17 indicates the link cost of the link between the nodes. For example, the link cost of the link between the node a and the node b is 10, Node a and Node P
This indicates that the link cost between is 13.
The link cost is obtained from [link cost = link distance × road width coefficient × road type coefficient × hierarchy coefficient], where the road width coefficient is a coefficient set for the size of the road width. Yes, the road type coefficient is
The coefficient is set according to the type of road such as a toll road.
The route cost from the departure point to each node is calculated as the sum of the individual route costs between them. The route display data 18 is data for displaying the route selected by the route search on the map of the image display device.

[0007] In a conventional navigation device, the basic idea of performing a route search based on data recorded on a recording medium such as a DVD-ROM as described above is as shown in FIG. The link costs of all the routes from P to the destination node Q are added, and the route with the lowest link cost is selected. In the case of FIG. 3, P-be- dfg-Q
This route is selected as the guide route because the total of the link costs is the smallest at 30.

In the actual guidance route search, first, a departure node and a destination node closest to the departure place and the destination are selected. In the example shown in FIG. 12, it is shown that the node P is selected as the departure node and the node Q is selected as the destination node. Next, route search data including the departure node P is read, and a route search on the departure point side is performed. As described above, this route search selects the route with the lowest total link cost. Next, as a result of the route search, it is determined whether or not connection has been made to the target node. If the distance from the departure point to the destination is relatively short, for example, if the destination node is also present in the most detailed level of the level 0 shown in FIG. 11, a guide route to the destination node is selected using only the data of this level. Is done.

On the other hand, when the destination is far from the departure point, it is not determined that the vehicle is connected to the destination node. Therefore, the route search data including the destination node Q is read from the recording medium, and the route search on the destination side is performed. Do. If the route selected by the route search on the destination side is not connected to the search route on the departure side, the rank of the search hierarchy is raised. Hereinafter, various methods have been proposed for searching for the optimum route between the departure node and the destination node by increasing the rank of the search hierarchy. For example, there is a method as shown in FIG. That is, at the level 0 displayed to the municipal road level, the route search data A including the departure node P is checked, and when the destination node Q does not exist, the level 1 route search data L displayed to the prefectural road level is read. , Where the destination node Q
It is checked whether or not exists, and if it exists, the optimal route is calculated there. In the case where it does not exist there as in the illustrated example, candidate nodes to the target node side in the route search data L are listed in order of link cost.
Note that only a part of the route search data of the hierarchy 0 is extracted from the nodes of the route search data of the hierarchy 1, and as a result, in the example of FIG. Similarly, only the road indicated by the thick line link in the hierarchy 1 exists in the hierarchy 2, and in the upper hierarchy, a route search is performed in the nodes and link data in the range.

Similarly, the route search data B of the hierarchy level 1 on the side of the route search data B of the hierarchy 0 where the target node Q exists exists.
Is read, and it is checked whether or not the departure node P exists. If the departure node does not exist as shown in the illustrated example, candidate nodes to the destination node in the route search data M are listed in order of link cost. I do. By repeating this operation, no matter how many hierarchies exist, or even if the starting node and the destination node are far apart, there will eventually be hierarchical data including both candidate nodes. An optimal route with the lowest link cost between the departure node and the destination node is set. In the example of FIG. 13, both nodes are connected in the route search data S of the hierarchy 2, and an optimum route between the two using the national road is searched in consideration of the search route in the lower hierarchy. When a user instructs a highway priority search at the time of searching for a route, the route search data H of the highway network at the hierarchy 3 is used. A route search to is performed. At this time, a search for sequentially switching the hierarchy as described above is performed in order to find the nearest interchange.

[0011]

In the above route search method in the case where the departure node and the destination node do not exist in one route search data in the hierarchy 0, the operation is performed by increasing the hierarchy one by one until the two are connected. In order to repeat the route search data, a part of lower nodes disappears every time the hierarchy is moved up by one level. Therefore, in order to perform an accurate route search, the route search data in the hierarchy 0 provided with as detailed data as possible. Is preferably read out in a wide range, and an optimum route between the two is searched for. However, such a route search method has a problem in that although the accuracy is improved, the route search data becomes large, so that it takes much time to calculate the link cost.

As a countermeasure, for example, in the example shown in FIG. 13 described above, it is also proposed that, immediately after the route search processing based on the route search data of the minimum range at the hierarchy 0, the route is raised to the hierarchy 2 and the route search is performed here. ing. However, if such a method is used, the search path must be rough, and many of the nodes in the hierarchy 0 are in the hierarchy 2
, Nodes may not be properly connected between the two layers.

As described above, when the route search data of different hierarchies is used to perform the route search by switching the hierarchies as appropriate, it is necessary to switch the hierarchies at an appropriate timing and use them. The use of an upper-layer network lowers the accuracy of a search route, and the route search in a lower-layer network having a large data density requires a lot of time. Also, when creating a search start link around the departure node and the destination node, if the route search in the lower hierarchy is performed widely, many candidate nodes are generated, and the subsequent route search takes a lot of time. If the network on the hierarchy is used at an early stage, the accuracy of the search route is reduced.

SUMMARY OF THE INVENTION Accordingly, an object of the present invention is to provide a route search apparatus having a new route search data structure capable of searching a route at a high speed without deteriorating the accuracy of the route search.

[0015]

SUMMARY OF THE INVENTION In order to solve the above-mentioned problems, the present invention provides, for each rectangular divided area obtained by dividing a map area into arbitrary rectangles, route data in the rectangular divided area and an area adjacent to each rectangular divided area. And the main road access route data up to the intersection of the expressway and the intersection of the main general road, and the main road route between the expressway interchanges and the main general road intersection common to all rectangular divided areas. Data, and a route between the current location and the destination based on the data of the rectangular divided area including the current location and the rectangular divided area including the destination and the main road route data. This is a route search device that performs

According to a second aspect of the present invention, at the time of inputting a highway-priority search instruction, road data in the rectangular divided area, main road access route data up to an interchange of an expressway close to each rectangular divided area, 2. The route search device according to claim 1, wherein a route between a current position and a destination is searched for based on main road route data between interchanges of expressways common to all rectangular divided areas.

According to a third aspect of the present invention, when a general road priority search instruction is input, the road data in the rectangular divided area and the main road access route data up to the intersection of the main general road close to each rectangular divided area are stored. A route search apparatus according to claim 1, wherein a route between a current position and a destination is searched for based on main road route data between intersections of main general roads common to all rectangular divided areas.

According to a fourth aspect of the present invention, there is provided the route search apparatus according to the first aspect, wherein a plurality of the main road access route data are provided for each of an expressway and a main general road.

According to a fifth aspect of the present invention, there is provided the route search apparatus according to the first aspect, wherein the rectangular divided areas are set so that each rectangular divided area includes only one intersection.

[0020]

Embodiments of the present invention will be described with reference to the drawings. FIG. 1A shows an example in which a map area, which is a basic concept in route search data used in a route search device according to the present invention, is divided into rectangular divided areas, and FIG. 3) shows an enlarged view of a rectangular divided area including the current position P in FIG. The map data used in the present invention is the same as the conventional one shown in FIG. 9 except that the data structure of the route search data 6 is different. That is, in the conventional device shown in FIG. 9, the route search data is made into a multilayer hierarchy of layers 0 to m as shown in FIG. 11, and node connection data 16, link cost data 17, In contrast to the structure having various data such as the route display data 18, the present invention includes only the most detailed lowest level data in the conventional example. The inside is subdivided by a rectangular division area obtained by dividing the inside into an arbitrary rectangle. However, it is the same in that data is configured by nodes and links connecting the nodes as route information.

In setting the rectangular divided area, in principle, only one intersection node is set in one rectangular divided area, and the rectangular divided area having no intersection is divided such that at least one road exists. Is preferred. However, at this time, it is not preferable that there are too many nodes and links connecting the nodes in each rectangular divided area. If the number of nodes is likely to increase, a rectangular divided area obtained by subdividing the number is set. .

In the illustrated embodiment, a rectangular divided area K32515 shown in the central part of FIG. 1A (added to a rectangular divided area divided into an appropriate size and shape based on nationwide detailed map data). FIG. 1 shows an example of a serial number)
(B) is an enlarged view, and as is apparent from this figure, this rectangular divided area K32515 is an intersection node N32515-1 (node number No. in the rectangular divided area K32515) which is a T-shaped intersection. 1 is shown), and is a rectangular divided area set to an arbitrary size with the center at the center. There are no other intersection nodes or the like in this rectangular divided area, and the rectangular divided area K32515
In addition to the intersection node N32515-1, a link L32515-1 (a rectangular divided area
Link number No. in K32515. 1), a connection node N32515-2 to which the link L32515-3 is connected, and a connection node N32515-4 to which the link L32515-3 is connected. In the illustrated embodiment, the links L32515-1 and L32515-2 are shown as part of a city road.

In the above embodiment, the rectangular division area K3
2515, the current position P exists as described above, and when performing a route search from the current position P to a destination Q, which will be described later, there are three links from the rectangular divided region K32515 to other rectangular divided regions. Then, link costs for searching for a route to the destination Q from the connection node corresponding to each link are calculated. Therefore, each connection node becomes a “search start node” when performing a route search from a point in the rectangular divided area to another rectangular divided area.

Similarly to the above-mentioned rectangular divided area K32515, for example, the intersection node C361- at which the city road intersects with the prefectural road C361 (means the prefectural road of No. 361 which is a serial number assigned to prefectural roads nationwide). A rectangular division area formed by an arbitrary rectangle centered at 65 (a node number that is a serial number assigned to a node constituting the prefectural road C361, which means the node of No. 65)
K32519 is formed. Similarly, the prefectural road C361 is an expressway
Intersects with A4 (meaning the highway No. 4 which is a serial number assigned to all highways nationwide) and the interchange (I
A rectangular division area K32513 is formed by an arbitrary rectangle centered on the intersection node A4-26 (which means the interchange of No. 26, which is a serial number assigned to the interchange of the highway A4). ing. Also, the connection node N32515-4 of the rectangular division area K32515 in which the current location P exists
The intersection node B6-126 (the serial number is assigned to the nodes constituting the national highway B6) where the road extending from the intersection with the national highway B6 (means the national highway No. 6 which is serially numbered to the national highway) (Meaning the node of No. 126 attached) is a rectangular divided area K32512. In this manner, an arbitrary rectangular division area is formed around each intersection, and the rectangular division areas K32510, K325
11, K32514, K32516, K32517, K32518, K32520, etc.

In this way, the whole of the country is divided into arbitrary rectangular divided areas, and each rectangular divided area is used as a basic data block. For each rectangular divided area, for example, path data in a rectangular divided area as shown in FIG. 2 is provided as basic data for route search. FIG. 2A is a diagram showing the entire configuration of route data of a rectangular divided area unit forming a rectangle, and includes a unit header (K32515 of the rectangular divided area in the illustrated example) as a header of each rectangle.
Node table that lists the nodes included in the rectangle and also indicates the storage location of the connection node table described later (NT32515)
And a connection node table (CNT32515) that records detailed data of all nodes, a link table (LT32515) that stores detailed data of the link specified by two adjacent nodes, and route data in these rectangular divided areas. In addition to the above, a main neighboring node list (KNL32515) that records route data for accessing a main road from the rectangular divided area is included.

The above node table (NT32515) is shown in FIG.
As shown in (b), node records of N32515-1, N32515-2, N32515-3, and N32515-4, which are all the nodes in the rectangular divided area, are stored, and a connection node table corresponding to each node is stored. The storage location data is also provided. The connection node table (CNT32515) includes, for each node, a. The normalized longitude / latitude of the node, b. A node attribute flag including an intersection node flag indicating whether or not this node is an intersection node, a connection node flag indicating whether this node is a node at a boundary with another rectangular divided area, c. The number of connected nodes indicating the number of nodes forming the other end of each link when there is a link at one end, d. No right turn or U
The number of traffic restrictions, such as turn prohibition, if any; e. Connection node records for the number of links indicating the link number of each link having this node at one end; f. A traffic regulation record indicating the specific content of the traffic regulation corresponding to the number of the traffic regulations, if any, g. If this node is a node at the boundary with another rectangular divided area, a connection node record indicating the position of the corresponding connection node table of the adjacent rectangular divided area; h. When this node is an intersection node, the storage location and size of the corresponding intersection record in the intersection unit are included.

The link table (LT32515) is shown in FIG.
As shown in (d), a plurality of link records in the order of link numbers corresponding to all the links included in the focused rectangular divided area are included. Each of these link records, as shown in FIG. Link No., which is a code assigned to each link mainly for displaying a search route. , B. Node number 1 and node number 2 specifying two nodes located at both ends of the link, c. Link distance, d. The actual time required to travel on this link is a link cost determined for both the forward and reverse directions of each link; e. Road type data indicating a road type such as whether an actual road corresponding to this link is an expressway, a national road, a prefectural road, a municipal road, etc. f. The route number assigned to the road corresponding to this link is included.

Details of the main neighboring node list (KNL32515) in the data of the rectangular divided area unit shown in FIG. 2A are shown in FIG. 3 from a point in each rectangular unit, such as an expressway or a national road. When entering an interchange or intersection on a major road, the data of the nearest interchange or intersection is recorded. In the rectangular divided area (K32515) in the illustrated embodiment, as described with reference to FIG. 1, the interchange 25 (A4) on the highway (A4)
-25) indicates that it has the lowest link cost, followed by interchange 26 (A4-26) on the expressway. Further, the link cost from the rectangular divided area to each of the interchanges (adjacent nodes) is recorded. For example, the total link cost may differ depending on which direction of the expressway the destination is. When there is, an optimal interchange is selected in consideration of the link cost, and a guidance route is set. Further, since the link cost for each route is calculated in advance, this data can be used as it is when searching for a route to be described later, and it is not necessary to calculate the link cost again.

Also, a series of passing nodes to the above-mentioned adjacent node is recorded, and the passing node series displays the guidance route on the map on the display screen after the route search is completed, and further displays the guidance route while the vehicle is running. Used for guidance.
In the example shown in the figure, the interchange (IC; A4-25) of the nearest highway from the rectangular divided area (K32515) includes a rectangular divided area (K32515) as is clear from FIG.
From the search start node (N32515-2), which is the connection node of
A node (C350-25) which is an intersection with a prefectural road (C350) is passed through the connecting node (N32511-2) corresponding to the search start node in the adjacent rectangular divided area (K32511). Via the highway (A
It records the sequence of passing nodes leading to the interchange (A4-25) in 4). Similarly, interchanges (IC; A4-26) with the next lowest link cost include N32515-3 and N32518-
It passes through 1 and records a series of passing nodes through the node (C361-65), which is the intersection with the prefectural road (C361), and finally to the interchange (A4-26).

In the main neighboring node list of the rectangular unit, as the data leading to the main road, in addition to the route data to the interchange of the expressway as described above, data leading to the national road are also recorded. In the illustrated example, the route with the smallest link cost from the rectangular divided area (K32515) to the national highway is the route to the intersection (B6-126) of the national highway (B6), and the cost there and to the intersection. Are recorded in the same manner as described above. The next route with the lowest link cost is the intersection (B6) of the national road (B6).
Data on the route to -125) is recorded, followed by data on the route to the intersection (B6-127) of the national road (B6) as the route with the lowest link cost. In the example shown in FIG. 3, in addition to these, the route with the lowest link cost to the prefectural road as the main general road and the route with the next lowest link cost are recorded in the same manner as described above. The route to the prefectural road can be omitted as necessary, or if there is a further main city road, the route data to the city road is recorded in other parts of the node list. You can also.

As described above, since one main road access route data is provided for one rectangular divided area,
For example, it is not necessary to record the main road access route data for each connection node in each rectangular divided area, and the amount of data to be recorded can be significantly reduced. In addition, by setting each of the rectangular divided areas to be sufficiently small as described above, the search accuracy does not decrease as compared with the case where each connection node has main road access route data. If the storage capacity of the data recording medium is sufficient, the data of the route to the main road may be created and recorded for each connection node in the same manner as shown in FIG.

The data structure of the route search apparatus according to the present invention, as shown in FIG. 4, is that the route data for each of the rectangular divided regions includes the route data in the rectangular divided region and the route data for main road access. The main road access route data includes the route data to the nearby interchange and the route data to the intersection of the nearby main general road as described above. Also,
As will be described later, common route data is provided for all rectangular divided areas, and includes route data between expressway interchanges and route data between intersections of major general roads.

As the route data common to all the rectangular divided areas, there is provided a matrix-like link cost total list as shown in FIG. In this link cost total list, for example, when looking at an expressway, FIG.
As shown in (a), serial numbers A1 to Am are assigned to all expressways nationwide. In the illustrated embodiment, the Tomei Expressway is A1, the Tohoku Expressway is A2, and the Chuo Expressway is A.
3. The Joban Expressway is designated as A4.
Up to a sequential number. In addition, interchanges are numbered in order for each expressway, and are shown as 1, 2, 3,... N in the figure. For such highways nationwide, the data of the minimum link cost between interchanges is calculated and recorded in advance. The hatched portion indicated by a broken line on the matrix in FIG. 5 is shown as a portion that does not require data input because data overlaps with a portion that is not hatched.

In the matrix shown in FIG. 5, data having the minimum link cost from the interchange of each column to the interchange of each row is recorded in a rectangular portion where each column and each row intersect. For example, as shown in FIG. 6A, A1 which is the first interchange of the Tomei Expressway
When entering the expressway from -1, the link cost at the time of getting off at the interchange of each expressway and the column of the main transit nodes at that time are recorded in the same data format as in FIG. It should be noted that this main passage node sequence is used for guidance along the guidance route, similarly to the data in FIG.
A similar list is recorded for each interchange. For example, as shown in FIG. 6B, data from A3-2, which is the second interchange on the central expressway, is indicated by the broken line in the matrix of FIG. Since the data of the hatched portion is unnecessary, only the data after the third interchange on the Chuo Expressway is recorded. Therefore, for example, data from the second interchange (A3-2) of the Chuo Expressway (A3) to the third interchange (A2-3) of the Tohoku Expressway (A2) is stored in the third interchange (A2-3) of the Tohoku Expressway. ) Is read from the portion recorded as data. In the data relating to the expressway, the nodes recorded as the main transit node sequence are not necessarily all nodes of the expressway network. Data similar to data obtained by normal route search, such as getting off and entering an expressway again, is recorded.

Further, for national roads nationwide, data similar to the above-mentioned expressway interchange is recorded at each intersection of each national road. That is, as shown in FIG. 5 (b), a matrix type data structure similar to that shown in FIG. 5 (a) is formed.
3, B4... Bm national roads are arranged, and intersections are sequentially arranged as 1, 2, 3,. Also in this matrix, the data in the portion indicated by the hatching with broken lines in the figure becomes unnecessary. Also in this case, in the rectangular portion where each column and row intersect, data having the minimum link cost from the intersection of each column to the intersection of each row is recorded, and the data configuration is shown in FIG. Since the data is the same as the data for each expressway interchange shown in FIG.

A lot of data processing is required to create the above data for each intersection on national roads nationwide. However, conventional route search data for a navigation device is used, and data is automatically generated along the above matrix. By setting a program to search the routes in order and automatically storing the searched routes, the above-mentioned series of data can be obtained without extraordinary manpower. It can be used as search data. In this way, the above data can be obtained easily, so the same data is also obtained and recorded for prefectural roads,
This can also be used.

In the route search apparatus of the present invention, since the data configuration is as described above, the route search is performed according to an operation flow as shown in FIG. That is, a route search is started (S1), and the current location is, for example, a point P between the highway A4 and the national highway B6 as shown in FIG. 8, and when the current location data is input to the navigation device (S2), The route search data shown in FIGS. 2 and 3 as data of the rectangular divided area including this point is read from the DVD (S3). When this rectangular divided area is, for example, the rectangular divided area (K32515) shown in FIG. 1, the link cost from the current position P to the search start nodes (N32515-2, N32515-3, N32515-4) of this rectangular divided area is It is calculated and stored (S4).

On the other hand, when the destination is a point Q close to the highway A3 and the national highway B3 shown in FIG. 8, when this data is input to the navigation device (S5), the same as the data reading of the current location is performed. The data of the rectangular divided area including the ground point is read (S6). This rectangular divided area has the same data structure as the rectangular divided area at the current location. Similar to the operation at the current location, the link cost from the destination Q to the search start node of the rectangular divided area is calculated and stored. (S7).

Next, it is determined whether or not an instruction to give priority to the expressway is given in this route search (S8). Here, when the highway priority instruction is given, data recording a route near an expressway interchange is read from the main neighboring node list shown in FIG. 3 in the rectangular divided area where the current location is located. In the embodiment shown in FIG. 3, interchanges A4-25 and A4-2
The link cost to 6 and the passing node sequence are read. Similarly, the link cost to the adjacent interchange and the passing node sequence are read out for the rectangular divided area where the destination exists (S9).

Next, as for the candidates for the interchanges that are close to the rectangular area of the current position and the destination, the minimum link cost between the interchanges is read out as shown in FIG. (S10). The link costs calculated and read out as described above are totaled, and the route with the smallest link cost is set as the guide route (S11).

On the other hand, if it is determined in step S8 whether or not the expressway-prioritized route search has been instructed (S8), and if the expressway-prioritized route search instruction has not been issued, the main proximity shown in FIG. From the node list,
Read the data recording the route near the intersection of national roads. In the embodiment shown in FIG. 3, the intersection B6-12
The link cost to 6, B6-125, and B6-127 and the passing node sequence are read. Similarly, the link cost and the passing node sequence to the intersection of the national road close to the rectangular divided area where the destination exists are read (S12). Next, for the candidate of the intersection of the national road which is close to the rectangular division area of the current location and the destination, the minimum link cost between each intersection is
It is determined by reading data of a list having a data structure similar to that of FIG. 6 (S13). Hereinafter, as in the case of the expressway priority, the link costs are totaled, and the route having the lowest link cost is set as the guidance route (S1)
4).

In the above embodiment, an example of reading the route data to the intersection of the national road when reading the route data to the intersection of the main general road in the rectangular division area of the current location and the destination when the expressway is not prioritized. As shown, when the current location and the destination are relatively close to each other and there is no national road nearby, data of a route to a prefectural road or an intersection of other roads close to each rectangular divided area is provided. Can be used. Also, in the above example,
Although an example in which a plurality of routes from each rectangular divided area to a highway or a national highway is provided, if each rectangular area is sufficiently small or a difference in fine link cost may be ignored,
As a route from each rectangular area to a highway or a national road, only one having a low link cost may be stored, and a route may be searched based on this data.

[0043]

In the invention according to the first aspect of the present invention, unlike the conventional route search device, it is not necessary to switch and use data of different hierarchies when searching for a route. There is no disadvantage such as an increase in search time due to a wide search of a layer having a high density and a deterioration in accuracy of a search path due to a wide search of a layer having a small amount of data. It can be carried out.

Further, in the invention according to the second aspect, when a search instruction is input with highway priority, an appropriate route search can be performed with high accuracy and high speed with highway priority. Further, in the invention according to claim 3, at the time of inputting a general road priority search instruction, an appropriate route search can be performed with high accuracy and high speed with general road priority. In the invention according to claim 4, since a plurality of main road access route data are provided for each expressway and main general road, an optimal route can be searched from a plurality of route candidates. Thus, a more appropriate route search can be performed. Further, in the invention according to claim 5, since the rectangular divided areas are set so as to include only one intersection in each rectangular divided area, the inside of each rectangular divided area and the adjacent main road from each rectangular divided area are set. The data of the access route to the server is simplified, and an appropriate route search can be performed with high accuracy and high speed.

[Brief description of the drawings]

FIG. 1 is a route data diagram showing an example in which a map area according to the present invention is divided by an arbitrary rectangular division area and nodes and links are set, and FIG. 1 (b) is a partially enlarged view of FIG.

FIG. 2 is a configuration diagram of route search data of the present invention.

FIG. 3 is a data configuration diagram showing an example of a main neighboring node list in route search data of the present invention.

FIG. 4 is a basic configuration diagram of route search data of the present invention.

5A and 5B show examples of route data common to all rectangular divided areas according to the present invention, and FIG. 5A is a matrix diagram showing a tally list in which minimum link costs between nationwide and expressway interchanges are tallyed; FIG. 4 is a matrix diagram showing an aggregation list in which minimum link costs between national and national road intersections are aggregated.

FIG. 6 is a data configuration diagram showing an example of a data configuration of a minimum link cost between interchanges on a highway in the matrix of FIG. 5A.

FIG. 7 is an operation flowchart showing the operation of the route search device of the present invention.

FIG. 8 is a map showing an example of a current location / destination, an expressway network, a national road network, and the like when a route search is performed by the route search device of the present invention.

FIG. 9 is a data configuration diagram showing a configuration example of conventional map data.

FIG. 10 is a data configuration diagram showing a configuration example of conventional route search data.

FIG. 11 is a hierarchical diagram of conventional route search data.

FIG. 12 is a diagram showing a node, a list, and a cost used for a conventional route search.

FIG. 13 is an explanatory diagram showing an example of a conventional route search using hierarchical route search data.

[Explanation of symbols]

 1 disk label 2 drawing parameter 3 figure management information 4 figure 5 index data 6 route search data

Claims (5)

[Claims] 1. For each rectangular divided area obtained by dividing a map area into arbitrary rectangles, route data within the rectangular divided area, up to an interchange of an expressway close to each rectangular divided area, and up to an intersection of a main general road. Main road access route data, main road route data between expressway interchanges and main general road intersections common to all rectangular sub-regions, rectangular sub-regions including the current location, and destinations A route search device that searches for a route between a current location and a destination based on the data of the rectangular divided area including the following and the main road route data. 2. When inputting a search instruction for expressway priority, road data in the rectangular divided area, main road access route data up to an interchange of an expressway close to each rectangular divided area, and common data for all rectangular divided areas. 2. The route search device according to claim 1, wherein a route between the current position and the destination is searched based on main road route data between expressway interchanges. 3. When inputting a general road priority search instruction, road data within the rectangular divided area, main road access route data to an intersection of a main general road close to each rectangular divided area, and common data for all rectangular divided areas. 2. The route search device according to claim 1, wherein a route between the current position and the destination is searched based on main road route data between intersections of the main general roads. 4. A plurality of the main road access route data are provided for each of an expressway and a main general road.
The route search device according to the above. 5. The route search device according to claim 1, wherein the rectangular divided areas are set so as to include only one intersection in each rectangular divided area.