JPH0429013A - Path search device - Google Patents

Abstract

PURPOSE:To perform a search process fast with a small amount of memory by dividing road network data into plural specific ranges and storing them and searching the shortest distance paths or optimum paths within the specific ranges. CONSTITUTION:The positions of the start place and destination place for searching the paths are inputted and stored in a spot storage means 101. A map data storage means 102 is stored with the road network data required for the path search previously while the data are divided by the specific ranges. A search result storage means 103 is stored with search result data corresponding to points (nodes) on the road network of maps by the specific ranges according to the road network data by the specific ranges which are divided by the means 102. A search means 104 inputs the start place and destination place stored in the means 101 and searches for the shortest distance path or optimum path starting at the start place or destination place, so that the search result is stored in the means 103. Then the search result of the means 104 is outputted to an output means 105.

Description

DETAILED DESCRIPTION OF THE INVENTION Field of Industrial Application The present invention (L) relates to a route searching device used by a vehicle driver to know the route from a starting point or current point to a destination; In the route search device, as a device for searching a route for a vehicle to travel, for example, Japanese Patent Application Laid-Open No. 62-601
There is a vehicle route guide device disclosed in Japanese Patent No. 00. This vehicular route guidance device prints an X corresponding to each intersection number on a holding board without duplicating intersection numbers for all intersections on the road network.

It memorizes Y coordinate information, route information, etc., and searches for a route in order from the starting intersection to the connecting intersections to the destination using data corresponding to all intersections. However, when the road network used for route searching becomes wide-area, such as when searching for long-distance routes, the size of the road network data to be read becomes large and the amount of memory used increases. In view of the problems of conventional route searching devices, when the road network used for route searching covers a wide area, such as when searching for long-distance routes, it is necessary to increase the amount of memory used. It is an object of the present invention to provide a route searching device that can perform route searching with a small amount of memory without having to use a large amount of memory. A point storage means for storing the location of a land, a map data storage means for storing road network data divided into each specific range, a search result storage means for storing search results for each specific range, and a starting point or a destination. A route search device consisting of a search means for searching for the shortest route or an optimal route in one or more specific ranges using a starting point as a starting point, and an output means for outputting the search results. It is a route search device characterized by storing divided road network data and road connection data with adjacent specific ranges at divided boundaries, and the map data storage means have different details. Divide and store multiple road network data for each specific range.
The search means is a route search device characterized in that it searches for each specific range using road network data of different details and stores the search result data in the search result storage means.

Operation According to the above-described configuration, the present invention performs a route search by reading road network data of a specific range that has been divided and stored in advance when searching for a route from a starting point to a destination point. The order of the search is from the starting point or destination, or from the destination point or both, and the search is repeated for each specific area.The search results for each search are stored in the search result storage means, and the search When the search is completed, the search results are read out from the search result storage means and output.4 Since the route search is performed using the road network data for each specific range that has been divided and stored in advance, there is no need to read a large amount of road network data at once. Embodiment 1 A first embodiment of the present invention will be described. FIG. 1 shows the present invention. 101 is a point storage means for storing the positions of a departure point and a destination; 102 is a map data storage means for storing road network data divided into specific ranges; FIG. , 103 is a search result storage means, such as a RAM, for storing search result data corresponding to points (nodes) on the road network of the map for each specific range.
Reference numeral 104 denotes a search means, which uses, for example, a CPU to search for the shortest distance route or optimal route in one or more specific ranges using the starting point or the destination as a starting point.Road network data for each specific range The search result data corresponding to the nodes on the road network for each specific range may be stored in the search result storage means 103.
Reference numeral 5 denotes an output means that outputs the search results of the search means 104. Specifically, it may be a tear screen, such as a display, or it may be an output device that outputs the search results in audio form (- or the current location). The route searching device of the first embodiment configured as described above may be combined with a visual or audio guidance device that indicates search results at an appropriate time or place. Explain the operation.

The location storage means 101 inputs and stores the locations of the starting point and destination for route search. Map data storage means 10
2 is to collect the road network data necessary for route searching in advance for each specific range.
For example, the search result storage means 103 may be divided and stored based on the longitude/latitude or the size of the road network data. The search result data of the search means 104 corresponding to the nodes on the road network, for example, the distance traveled from the departure point to each node and the previous route to each node corresponding to each node on the road network. Remember nodes. The search means 104 is the point storage means 101
For example, when searching for the shortest distance route or optimal route using the starting point or destination as the starting point, the starting point and destination stored in the memory are searched manually. reads the road network data of one specific range (one area) that includes the departure point from the road network data of the specific range from the map data storage means 102.
If the search result data corresponding to the nodes on the road network in the read specific range is stored in the search result storage means 103, this data is also read in (a). If there is a route from the departure point to each node on the road network within one page of road network data that takes the shortest distance from the starting point to each node on the road network than the distance recorded in the search result data, then The search result data (the distance traveled from the starting point and the previous node on the route) is updated. When the route search for one page is completed, if the searched route has not reached the destination, the updated search result data is stored in the search result storage means 103, and the read road network data and search result data of the specific range are stored. Instead, the unexplored specific range that touches the boundary of the specific range reached in the shortest distance from the starting point,
For example, the road network data of this specific range and the search result data corresponding to the nodes on the road network are selected from the longitude and latitude of the boundary, and are read from the map data storage means 102 and the search result storage means 103, and the boundary of the searched specific range is selected. Select a route or a connected node from the position of the upper node, transfer the search result data corresponding to the node on the boundary of the searched specific range to the search result data corresponding to this connected node, and then The route search continues as before from the connected point, and the operation of moving the specific range to be searched is repeated until the searched route reaches the destination. The output means 105 outputs the search results of the search means 104.

FIG. 2 shows a schematic flowchart when the operation of the first embodiment is realized by software. First of all, Process 2
(corresponding to point storage means 101), process 202 to input and memorize the positions of the starting point and destination of the route to be searched in step 01).
Search for the shortest route or optimal route using the starting point or destination as the starting point (map data storage means 102,
(corresponds to search result storage means 103 and search means 104)
In step 203, the search result obtained in step 202 is output (corresponding to output means 105).

Next, the search process 202 will be explained in more detail using the flowchart of FIG. 3, taking as an example the case of searching for the shortest distance route. The locations of the starting point and destination stored in step 201 are input in step 301, and in step 302 road network data of a specific range including the starting point is stored in the map data storage means 1.
Read from 02 a Process 303 to find the shortest route for one page of road network data in a specific range that has been read
Process 304 stores search result data corresponding to nodes on the road network in the specific range searched for the route in process 303 in the search result storage means 103, and in judgment 305, the route searched in process 303 leads to the destination. It is determined whether or not the distance has been reached using the shortest distance searched so far, and if the distance has been reached using the shortest distance searched so far, the limit distance of the search range for route searching is set to this shortest distance in process 306. 3
If the route searched in step 05 has not been reached by the shortest distance so far, do not perform process 306 ('Io Next, process 307
In step 303, the search result data obtained in step 303 is examined to create search result data corresponding to the nodes on the road network in the adjacent specific range that are connected to the nodes that the searched route connects to on the boundaries of the specific range. This specific range to be connected is then set as the search target range for the next route search. Process 308 selects the road network within the specific range that is the search target range in process 307 and that is reached by the shortest distance from the starting point, and the distance reached in this selected specific range is set in process 306. It is determined in step 309 whether the distance is within the search limit distance, and if it is within the search limit distance, one page of road network data in the selected specific range is processed in step 310 instead of the road network data in the specific range for which the route search was performed in step 303. Read the search result data corresponding to the nodes on the road network in the selected specific range in process 311 and proceed to process 303
Return to Step 3. If the distance at which the selected specific range is reached in judgment 309 is outside the search limit distance, processing 202 is terminated.

Next, the specific range search process 303 will be explained in more detail using the flowchart in FIG. 4. Process 401
is the departure point or the searched route based on the road network data of the specific range read in process 302 or process 310 and the departure point input in process 301 or the search result data of the specific range stored in process 307 and read in process 311. The node connected to is set as the search target node, and it is determined in step 402 whether or not this search target node remains.Here, if the search target art remains, the shortest distance from the starting point among the search target nodes is determined. The node that has been reached is searched for and used as a reference point for route search in step 403. A node that connects to this reference point through the road network is searched for in one page of the read road network data of a specific range in step 404. Then, it collects the search result data and determines whether the node to be connected has been reached by the shortest distance from the departure point 40
5, if the distance is the shortest so far, the reference point and the distance reached from the starting point are stored in the search result data corresponding to the node to be connected in step 406, and the node to be connected is added to the search target node in step 407. . Also, in judgment 405, if it has not been reached by the shortest distance so far, process 406
And processing 407 is not performed. Next, in judgment 408, it is determined whether all the nodes connected to the reference point have been examined. If the reference point has been examined, in process 409, the reference point is deleted from the nodes to be searched, and the process returns to judgment 402. Maf, Judgment 408
If all nodes connected to the reference point have not been checked, the process returns to step 404. In addition, if there are no search target nodes remaining in judgment 402, search within specific range processing 3
End 03.

Next, an example of the data format used in the search process 202 and the specific range search process 303 and an example of the process 203 will be explained using FIGS. 5 and 6. 4. Associating a number with each node on the road network , if the road network data in which the connections between nodes and their distances are stored is a road network as shown in Fig. 5, the search result data is stored as shown in Fig. 6, and 4 601 stores the nodes on the road network. A node number storage area 602 stores the node number of the reference point corresponding to each node number in the node number storage area 601. A reference point number storage area 603 stores the shortest distance from the starting point to the node number. For example, for a squad whose starting point is node number 1, enter O in the reference point number storage area 602 corresponding to the node number 1 in the node number storage area 601, and then store the shortest distance. 0 (m) is stored in area 603. Furthermore, as shown in Figure 5 &
Suppose that the node numbers to connect from minode number 1 are 2 and 3, and the reachable distance from the starting point is node number 2, reachable distance is 30 (m), and node number is 3.
, when the reachable distance is 50 (m), the reference point number 1 is stored in the reference point number storage area 602 corresponding to the node number 2 in the node number storage area 601, and the reachable distance 30 is stored in the shortest distance storage area 603. In addition, the reference point number 1 is stored in the reference point number storage area 602 corresponding to the node number 3 in the node number storage area 601, and the reachable distance 50 (m) is stored in the shortest distance storage area 603. Then, set node numbers 2 and 3 as search target nodes.

When we have finished investigating the nodes connected to node number l, we select the node that can be reached by the shortest distance from the starting point (node number 1) among the search target nodes as the next reference point for the search.The current search target node are node numbers 2 and 3,
The values in the shortest distance storage area 603 corresponding to node numbers 2 and 3 in the node number storage area 601 are 30 (m) and 50 (m).
Node number 2, which is 0(m), is selected. In this way, nodes connected to node number 2, which is the reference point, are investigated from the connection information between the nodes, and search result data is created. After completing the search process 202, in process 203, the node number of the destination is searched from the node number storage area 601, and the reference point number corresponding to this node number is read from the reference point storage area 602. Then, the read reference point number is searched from the node number storage area 601, and the reference point number of this node number is read again from the reference point storage area 602 until the node number of the departure point is reached, and the read node number is By storing them in order, you can find the shortest distance route as a string of nodes.For example, if you want to display the shortest distance route on a display, you can use this string of nodes to display the shortest distance path on the display, by displaying the location of each node on the map. By examining these and connecting them with lines etc. in the order of the node columns, the shortest distance route can be output. do. 701 is the location Wt of the departure point, 702 is the boundary line of the map divided into specific ranges, 703 is the location of the specific range including the departure point 701 divided by the border line 702, and 704 is recorded on the map 703 of the specific range. The road map 705 is a connection node between the road network 704 and the map 705 of the specific range that is connected to the road network 704. Search processing 303
When performing the process 303, the map 703 of the specific range is
A route search is performed from a departure point 701 according to a road network 703, and search result data corresponding to each node on the road network of a map 704 of a specific range is created.

Next, a process 307 searches the map 705 of a specific range connected by the road network 703 to find a connection node 706.
The search result data of the corresponding connection node 706 is selected from the search result data, and the current within-specific range search process 303 is performed.
The search result data of the connection node 706 has been rewritten.For each map 705 of the specific range to be connected, search result data corresponding to the nodes on the road network of the map 705 of the specific range to be connected are created and stored, and the data is connected. The map 705 of the specific range to be searched is set as the next search target range. Process 308 selects the node that can be reached by the shortest distance from the starting point 701 from among the connection nodes 706 of the map 705 of the specific range to be connected that became the search target range in process 307, and selects the node that can be reached at the shortest distance from the starting point 701, and selects the node that can be reached by the shortest distance from the starting point 701. The map data storage means 102 selects one of the maps 705 and deletes the map of the selected specific range from the next search target range. A process of selecting nodes connected by a route from the location of the route, latitude, etc. of the node on the boundary of the searched specific range using a map data storage means that stores road connection data with adjacent specific ranges. This road connection data can be used to select the nodes connected by the route without performing GQ.
As described above, according to the first embodiment (2) In order to perform a route search by reading road network data for each specific range of road network data, a memory for reading a large amount of road network data at a time and using it for route searching. Route searching can be performed with a small amount of memory without increasing the amount of memory.

Next, a second embodiment of the present invention will be described.The present invention is useful when the road network used for route searching is wide area, such as when searching for long distance routes. A second embodiment of the present invention is aimed at providing a route search device that can search for a route in terms of quantity and can reduce the search time compared to the first embodiment. The block diagram of the route search device in FIG. 1 is the same as that shown in FIG. The difference from the configuration of the first embodiment is that the search means 104 uses the road network data of a plurality of specific ranges to find the shortest distance route or the optimal route using the departure point or destination as the starting point. When searching, convert two or more specific ranges of road network data into the same data structure as one specific range of road network data, and search for each converted road network data.
The point is that search result data corresponding to the converted nodes on the road network for each of two or more specific ranges is stored in the search result storage means 103.

Next, the operation of the route search device of the second embodiment configured as described above will be explained below. A correspondence is made for each set of 3 or more specific ranges. Then, the starting point and destination stored in the point storage means 101 are input, and the shortest distance route or the optimal route is searched using this starting point or destination as a starting point.

For example, when searching for the shortest route using the starting point as the starting point, this can be done using two or more specific ranges to which the road network data of a specific range including the starting point belongs from among the road network data for each specific range. A set of road network data is read from the map data storage means 102 and converted into the same data structure as the road network data of one specific range.At this time, the search result data corresponding to the nodes on the converted road network are stored in the search result memory. If stored in the means 103, this data is also read in.Here, according to the road network spreading from the starting point, in the converted road network data, from the starting point to each node on the road network, the shortest distance than the search result data is read. If there is a route that can be reached by distance, the search result data corresponding to that node is updated.And when the route search in the converted road network data is finished, if the searched route has not reached the destination, the search result data is updated. The search result storage means 103 stores, in place of the converted road network data, a corresponding set of road network data that includes the adjacent specific range that the searched road connects to on the boundary with the converted specific range. Map data storage means 102
Load the road network data from the search result storage means 103 and read the search result data corresponding to the nodes on the converted road network from the search result storage means 103 Search for the shortest distance route from the departure point to the nodes to which the road connects. If the searched route or destination has been reached, the shortest distance from the starting point to the destination is set as the limit distance for searching, and if all the routes being searched exceed this limit distance, the search is continued. When it ends, the search result storage means 103 is the search means 104.
The search result data corresponding to the nodes on the road network for each of two or more specific ranges is stored.

A case where the operation of the second embodiment is realized by software will be explained below.

The general flowchart is the same as that in FIG. 2, and processing 201 and processing 203 perform the same operations as in the first embodiment. The difference from the first embodiment is that in process 202, the shortest distance route or the optimal route is searched using the departure point or destination as the starting point. The point is that the route search is performed by converting the data structure to the same data structure as the network data (map data storage means 1
02, corresponding to the search result storage means 103 and search means 104).

Next, the search process 202 will be explained in more detail using the flowchart of FIG.
Corresponding phases are performed so as to form groups for each of three or more specific ranges. Then, in process 301, the locations of the departure point and destination are manually determined.
In process 802, a set of road network data of two or more specific ranges corresponding to each other in process 801 including the starting point is read from the map data storage means 102 at once.In process 803, this road network data of one specific range is read. Although it is converted into the same data structure as the road network data, this converted data is processed in the same manner as the road network data of a newly configured specific range.
3 to judgment 309 are performed in the same manner as in FIG. 3 of the first embodiment. Then, in judgment 309, if the specific range selected in process 308 is within the search limit distance set in process 306, a route search is performed in process 804 using the road network data of a set of two or more specific ranges that includes this selected specific range. The loaded road network data is converted into the same data structure as the road network data of one specific range in process 805, and the search result data corresponding to the nodes on this converted road network is read. is read in step 311 and the process returns to step 303.

Next, an example of the operation of the search process 202 in the second embodiment will be explained using FIG. It is a map of two or more specific ranges, for example 4
Map boundary line for each range 903 is the starting point @
904 is a road alignment on the map. 905 is a specific range of land 11fl that includes the starting point 903 and is divided by the boundary line 901.
906 is a map of four ranges that form a pair with the map 905 that corresponds to the boundary line 902; 907 is a specific range of locations connected to the starting point by the shortest distance when a route search is performed from the starting point 903; and 908 is a map to be connected. When performing a route search from the starting point 903, all four range maps 906 forming a set with the map 905 are read when the map 905 including the starting point 903 is loaded. Load. Then, after converting the map 906 of the four ranges forming the set into the same data structure as the road network data of one specific range and searching at once, the search result data is stored together. Next, for example, if the searched route connects to the map 907 of the specific range at the shortest distance from the departure point 903 to the map 906 of the four searched ranges, then the map 907 of the specific range
Load all four ranges of maps 908 that form a pair with the four ranges of maps 908 that are read based on the search result data of nodes connected from the searched four ranges of maps 905 as one specific range of road network data. Route search is performed after converting to the same data structure. By expanding the range of route search in this way until the destination is reached, starting point 903
You can find the shortest route from to the destination.

As described above, according to this embodiment, by searching the road network data of two or more specific ranges at once, when the road network data of one specific range is searched, the next location for which the search has been completed is It is possible to reduce the number of times a map of a specific range that has been searched is re-searched because the range search result data is rewritten. There is no need to read a large amount of road network data each time, and routes can be created with a small amount of memory. Next, a third embodiment of the present invention will be described, in which the search can be performed and the search time can be shortened compared to the first embodiment.

The present invention is useful when the road network used for route searching covers a wide area, such as when searching for long-distance routes. It is an object of the present invention to provide a route searching device that can be shortened compared to the first embodiment.

The block diagram of the route search device according to the third embodiment of the present invention is the same as that shown in FIG. 1, and will be explained using this figure. The structure is similar to that of the first embodiment, but the difference from the structure of the first embodiment is the map data storage means 102.
Divide multiple pieces of road network data with different details into specific ranges in the same region on the same map, and generate data indicating that the common points on the road network are the same among the road network data with different details. The search means 104 uses, for example, a CPU to store the road network data at one level of detail, using a CPU as a starting point, and converts the road network data into a predetermined range of road network data, for example, a specific range of a specific number of images. A route search is performed on the road network data for each specific range, and the search result data corresponding to the nodes on the road network is stored in the search result data storage means 103, and a plurality of road networks with different details are searched for on the road network. The shortest distance route or the optimal route is determined by switching the road network data to be searched using the common parts.

Next, the operation of the route searching device of the third embodiment configured as described above will be explained below.

The map data storage means 102 divides in advance a plurality of road network data of different details in the same region into each specific area, for example, based on longitude and latitude or the size of the road network data, and divides the less detailed maps into detailed maps. It is also possible to divide and store a wider range than the same range as a specific range.
The search means 104 inputs the departure point and destination stored in the point storage means 101 and searches for the shortest distance route or the optimal route using this departure point or destination as a starting point.
For example, when searching for the shortest route using the starting point as the starting point, for example, one page of map data is stored that includes road network data for a specific range that includes the starting point from among the most detailed road network data for a specific range. Read from means 102. Then, according to the road network that spreads from the departure point, the shortest route from the departure point to each node on the road network is searched using one page of this road network data, and when the route search for one page is completed, the destination is reached. If the searched route has not been reached, the search result data is stored in the search result storage means 103, and the road network in the adjacent specific range where the searched roads are connected on the boundary line of the specific range using road network data of the same detail is stored. Explore your data. When the specific number of images predetermined here has been searched, the route search range must not have reached the destination position (2. Instead of the road network data from which the route was searched, a road network whose details are less than the route search data is used). Load the road network data for a specific range that covers the specific area searched using the road network data. Then, based on the common parts on the road network, for example, the longitude and latitude positions of the nodes, it is possible to search for detailed nodes on the road network. Compare nodes on an unfamiliar road network, select nodes with the same location and define them as common nodes, and match the search result data of these common nodes to common nodes on an unfamiliar road network. 4. Based on this newly created search result data, a predetermined number of road network data in a specific range is created again using the loaded unfamiliar road network. If a route search is not performed within a specific range that includes the location of the destination, the route search will be performed using road network data that is even less detailed than the searched road network data. If you are searching for a route within a specific area that includes a map, search for a specific number of predetermined images of the specific area that includes the location of the destination and the adjacent specific area to be connected on a road network that is more detailed than the searched map, and then search for this specific number of images on the road network. Create search result data using nodes common to 1.%, search within a specific number of images, and repeat the above operation until the destination is reached.

A case where the operation of the third embodiment is realized by software will be explained below.

The general flowchart is the same as that in FIG. 2, and processing 201 and processing 203 perform the same operations as in the first embodiment. What is different from the first embodiment is that in process 202, a route search is performed using a predetermined number of specific ranges of road network data on a map with one level of detail, using the starting point or destination as the starting point, and searching for roads with different levels of detail. Route search is performed using common nodes on the road network between networks. The detail of the road network data is switched, and two or more road network data with different details are searched to find the shortest distance route or the optimal route. It is (
(corresponds to map data storage means 102, search result storage means 103, and search means 104).

Next, the search process 202 will be explained in more detail using the flowchart of FIG. 10. Processes 301 to 304 perform the same operations as in FIG. 3 of the first embodiment. Then, in judgment 1001, it is determined whether the search for the road network data in a specific range with a predetermined number of images has been completed, and if the specific number of images has not been searched yet, processing 307;
Processing 308, processing 310, and processing 311 are performed in the same manner as in FIG. 3 of the first embodiment, and the process returns to processing 303. Also
If the search for a specific number of images has been completed in judgment 1001, judge whether the searched route has reached the destination or not.
Judging by 02, if the destination has been reached, search process 2
End 02 If you have not yet reached your destination,
It is determined in step 1003 whether the search range includes the destination position, and if the search range does not include the location of the destination, then in response to road network data of a road network that is even less detailed than the searched road network,
The search result storage means 203 selects common nodes on the road network from among the searched nodes within the specific range of the specific number of searched images, creates search result data corresponding to nodes on the road network in the specific range that are not detailed. In step 1005, all search target candidates for the road network in the specific range are set to the specific range of the road network data that is not detailed, and the route search is switched from the detailed road network data to the road network data that is not detailed, and the process moves to step 308. Also, if the search range includes the location of the destination in judgment 1003, search result data of a specific number of specific ranges searched in process 1006 is retrieved.Road network data stored in a more detailed road network than the searched road network Select common nodes on the road network in a specific range of a predetermined number of images near the destination location, create search result data corresponding to nodes on the road network in a detailed specific range, and store the search results. In step 1007, all search target candidates for the road network in a specific range are set to a specific range of detailed road network data, and the route search is switched from less detailed road network data to detailed road network data, and the process proceeds to step 308. Next, an outline of the operation of the third embodiment will be explained using FIG. 11. 1101 is a map with the most detailed road network data divided into specific ranges 1102 is a map 110 is a place with less detailed road network data @ 1103 is a map 11
Road network data location efl that is even less detailed than 02
1104 is the starting point position + 105 is the destination position 1i! r
, 1106 is a common node on the road network between map 1101 and map 1102 on the departure point 1104 side, 1107
is an arrow 1108 indicating the direction in which search result data is transferred when switching the details of the searched road network data from the map 1101 to the map 1102 using a common node 1106.
is a common node on the road network between map 1102 and map 1103 on the departure point 1104 side, and 1109 is a search result when switching the detail of the road network designer to search from map 1102 to map 1103 using common node 1108. Arrow Ell 1110 indicates the direction of data transfer, and 1110 indicates a common node on the road network between map 1103 and map 1102 on the destination 1105 side, and 1111 indicates a common node 111.
Arrow 1112 is the destination 110.
On the 5 side, a common node t 1113 on the road network between the map 1102 and the map 1101 uses the common node 1112 to transfer the search result data when switching the details of the road network data to be searched from the map 1102 to the map 1101. An arrow 1114 indicating a direction is an example of a route determined by search.

In the vicinity of the starting point 1104 and the destination 1105 in each map, for example, if it is decided to search for road network data in four specific ranges before proceeding with the search, then in the map 1101, roads in four specific ranges including the starting point 1104 are searched. Search the network data and move the search result data corresponding to the node 1106 common to the map 1102 in the direction of 1107 to switch the detail of the road network data to be searched.Next, the map 1102
4 Search the road network data in a specific range, and search result data corresponding to the node 1108 common to the map 1103 as 1
You can also change the detail of the road network data to be searched by moving in the direction of 109. Here, when searching for road network data in 4 specific ranges on map 1103, the location of destination 1105 was included in the range for which the route was searched. 8. The search result data corresponding to the node 1110 that is common to the four specific ranges near the destination on the map 1102 is moved in the direction of 1111 to create the map 1102.
You can also switch the road network to be searched for. If the road network data of four specific ranges are searched on the map 1102 and the searched route does not reach the destination 1105, the search result corresponding to the node 1112 that is common to the map 1101 is displayed. data 11
13, change the details of the road network data to be searched, search for road network data in 4 specific ranges on the map 1101, connect the searched route to the destination 1105, and move from the departure point 1104 to the destination. The shortest route 1114 to the ground 1105 can be found using tQ as described above.
According to this embodiment, a plurality of pieces of road network data with different details are stored, and in order to expand the search range using the road network data of a specific range with different details, it is possible to search for small roads other than those near the departure point and destination. It is possible to shorten the search time compared to the first embodiment without searching, and to create a route using a small amount of memory without increasing the amount of memory used for route searching by reading a large amount of road network data at once. You can explore.

Next, a fourth embodiment of the present invention will be described.The present invention is suitable for long-distance route searches, etc. when the road network used for route searching covers a wide area. A route search device that can perform a route search in a manner that reduces the search time compared to the first embodiment, and uses less road network data in a specific range than the third embodiment. The block diagram of the route searching device according to the fourth embodiment of the present invention is the same as that shown in FIG. 1. The location storage means 101, the map data storage means 102, the search result storage means 103, and the output means 105 have the same configuration as in the third embodiment.

The configuration differs from that of the third embodiment (i) The search means 104 uses, for example, a CPU to search for a predetermined distance from both the departure point and destination location using road network data of one level of detail. For example, a specific number of road network data in a specific range may be searched for routes for each specific range, and search result data corresponding to nodes on the road network for each specific range may be stored in the search result data storage means 103, and a plurality of details may be stored. The point is to find the shortest distance route or the optimal route from the departure point to the destination while switching the road network data to be searched between different road networks using common parts of the road network, such as the longitude and latitude of nodes. Next, the operation of the route searching device of the fourth embodiment configured as described above will be explained below.

The search means 104 inputs the departure point and destination stored in the point storage means 101, and searches for the shortest distance route or the optimal route using both the departure point position and the destination position as starting points. When searching for the shortest distance route, select one of the most detailed road networks. First, read one page of road network data for a specific range that includes the starting point from the map data storage means 102. A road network that extends from the starting point. The shortest route from the departure point to each node on the road network is searched within the specified range read according to the specified range, and the search result data is stored in the search result storage means 103. A specific range is similarly searched up to a specific number of images.

Next, search the road network data of a specific range that includes the destination within the road network of the same level of detail, in the same way as the departure point, up to a specific range with a predetermined number of images, and then search for both the departure point and the destination. If the route searched from is not connected, then instead of the road network with the level of detail at which the route was searched, we will use road network data that is less detailed than the road network data of this level of detail for the specific range on the departure and destination sides. From the search result data, select search result data corresponding to common parts on the road network, for example, common nodes on the road network, and create search result data corresponding to nodes on the road network that are unfamiliar to you. A route search is performed in the same manner as above using road network data of a specific range of a road network that is not detailed on both the destination side and the created search result data. Also, if the route from the departure point and the route searched from the destination are connected, the route from the departure point to the connected node and the route from the destination to the connected node can be connected to find the shortest distance from the departure point to the destination. A case where the operation of the fourth embodiment configured as a route or an optimal route is realized by software will be described below.

The general flowchart is the same as that in FIG. 2, and the process 201
, processing 203 performs the same operation as in the first and third embodiments. What is different from the first and third embodiments?
In 02, on a map with one level of detail, a route search is performed using a predetermined number of predetermined number of road network data in a specific range using both the starting point and destination position as the starting point, and searching between road networks with different levels of detail. By switching the detail of the road network data searched using common parts of the network, such as common nodes on the road network, searching for two or more road network data with different details to find the shortest route or the optimal route. Next, regarding finding a route, the search process 202 will be explained in more detail using the flowchart in FIG. In process 1201, a specific range of road network data including the starting point in one level of road network data is set as a search target for route searching, and in process 1202, a specific number of images predetermined by the starting point that is the search target is searched. Route search is performed using road network data in a specific range of road network data with the same level of detail searched at the starting point.
In step 3, road network data in a specific range including the destination is set as a search target for route searching, and in process 1202, a specific number of road network data in a specific range predetermined on the destination side as the search target is searched for a route. Determine whether the route on the departure side and the route on the destination side searched here are not connected 1204
If there is a connection, the process 202 is terminated.If there is no connection, the search result data on the departure point side is compared to a road network with less detail than the searched road network. Select a node, create search result data corresponding to a node on an unfamiliar road network in process 1205, switch the details of the road network to be searched, and select the specific range for which the search result data on the departure point side was created. In process 1206, the route is searched for road network data within a specific range of a predetermined number on the departure point side, which is set as the search target in process 1202. Also, the search is switched on the destination side as well as on the departure point side. Select common nodes on the road network for road network data of the same detail, create search result data corresponding to nodes on the road network that are less detailed in process 1207, and switch the detail of the road network to be searched. Then, in step 1208, a specific range on the destination side is searched, and in step 1202, a predetermined number of road network data within the specific range is searched for on the destination side, and then in judgment 1204. Next, the specific number search process 1202 will be explained in more detail using the flowchart in FIG. 13. Process 13
01 searches for a specific range with the shortest reachable distance from the departure point on the departure point side from among the road network data of the specific range searched for in processing 1201, processing 1203, processing 1206, and processing 1208. Search for a specific range with the shortest reachable distance from the road and read the road network data for that specific range. Process 1302 reads search result data corresponding to nodes on the road network in the specific range read in process 1301. A route is searched for one page of the road network data of the specific range read here in process 303, and the search result data within the searched specific range is stored in process 304. Next, it is determined in judgment 1303 whether or not the specific range of a predetermined number of images has been searched, and if the search has been completed, processing 1202 is ended. If the search is not finished, process 3
The search result data of the adjacent specific range connected on the boundary of the specific range to the road network of the specific range searched in step 07 is created and stored from the search result data, and the specific range reached by the shortest distance is selected in process 1304. Then, the road network data of the selected specific range is read in process 310. The search result data corresponding to the nodes on the road network of the selected specific range is processed 3.
11 and returns to process 303.Next, the outline of the operation of the fourth embodiment will be explained using FIG. El 1403 is a map 1 of the road network data that I am not familiar with.
Road network data location a1 that is even less detailed than 402
404 is the place of departure 11405 is the place of destination WjL 1
406 is the departure point 1404 side, map 1401 and map 140
A common node on the road network between the two, 1407 is a common node 1406 used to convert the map 1401 to the map 140.
Arrow 1408 indicating the direction in which search result data is transferred when switching the details of road network data to be searched for is a common node on the road network between map 1401 and map 1402 on the destination 1405 side, and 1409 is a common node. node 140
Arrow Ell 1410 indicates the direction in which the search result data is transferred when switching the details of the road network data to be searched from the map 1401 to the map 1402 using 8.
4 side is a common node on the road network between map 1402 and map 1403, and 1411 is a common node 1410 that is used to transfer search result data when switching the detail of the searched road network data from map 1402 to map 1403. The arrow Ell 1412 indicating the direction is a common node node on the road network between the map 1402 and the map 1403 on the destination 1405 side. The arrow El11414 indicating the direction in which the search result data is transferred when switching is the boundary line where the search range on the departure point 1404 side and the search range on the destination 1405 side are connected 14
15 is an example of a route obtained through a search. When it is determined that in each map, near the starting point 1404 and the destination 1405, the road network data of a specific range of four pages is to be searched before moving on to the search, map 1401 Search road network data for 4 specific ranges including departure point 1404 and destination 1
Search for road network data in four specific ranges including 405.Here, in order to switch the details of the road network data to be searched for, go to the map 1402.On the starting point 1404 side, search result data corresponding to the common node 1406 is searched in the direction 1407. Move to 4 to search for road network data in a specific range, and select Destination 14.
On the 05 side, the search result data corresponding to the common node 1408 is moved in the direction of 1409 to search for road network data in 4 specific ranges, but then the starting point is moved to the map 1403 to switch the details of the road network data to be searched On the 1404 side, the search result data corresponding to the common node 1410 is moved in the direction of 1411 to search for road network data in 4 specific ranges, and on the destination I405 side, the search result data corresponding to the common node 1412 is moved in the direction of 1413. Move the map 140 to search for road network data in a specific range.
3, the route 1415 is connected at the boundary line 1414 where both the search ranges on the departure point 1404 side and the destination 1405 side are connected.
04 to the destination 1405 to find the shortest distance route or the optimal route.According to this embodiment, when searching and moving between road networks in a specific range with different details. The search time is reduced compared to the first embodiment by changing the detail of the road network data to be searched by transferring the search result data using only the range in which the route was searched using both the departure point and destination as the starting point. The search result data is not transferred to a node where the road network is not connected to the starting point or the destination. The road network data used for the search can be reduced compared to the third embodiment. , and it is not possible to perform route searching with a small amount of memory without having a large capacity memory to read a large amount of road network data at once. First, second, third and fourth implementations In the example,
Instead of searching by distance, the optimal route can be found as the shortest travel time route based on the average travel time between nodes on the road network.Also, when searching for a route, the starting point position is set to the current location. You can also search for a route using other methods other than those described above.Also, in the first embodiment, the road network data of a specific range and the road network of a map of a specific range are used as much as the memory allows. You may also save the time required to read and store data by retaining the search result data corresponding to the nodes above (also see the third section).
In the embodiment, the map data storage means is used to store in advance data indicating that common nodes on the road network between a plurality of pieces of road network data having different details are the same. , by using it when transferring search result data corresponding to common nodes on the road network, the time to select common nodes can be shortened. When transferring search result data corresponding to common roads on a road network using a map data storage means in which data indicating that common parts of roads between network data are the same is stored in advance. By using this, you can reduce the time it takes to select common parts of roads.
In addition, in the third and fourth embodiments, when switching the detail of the road network data to be searched after searching a specific range of a predetermined number of images, roads to be searched after searching a range of a predetermined search distance. The detail of the network data can be changed.As explained in detail, according to the present invention, the road network data for each specific range is read and a route search is performed, so a large amount of road network data is generated at once. There is no need to read the information, and the route search can be performed with a small amount of memory without requiring a large capacity memory, and the search process can be performed at high speed.

[Brief explanation of the drawing]

Figure 1 shows the blocks of the route search device according to the first embodiment of the present invention, Figure 2 is a schematic flowchart showing the operation of the first embodiment, and Figure 3 shows an example of the search process of the first embodiment. FIG. 4 is a flowchart showing an example of the search process within a specific range according to the first embodiment. FIG. 5 is an explanatory diagram showing an example of the road network used for the search. Data configuration diagram FIG. 7 is an explanatory diagram of the operation of the same device. FIG. 8 is a flowchart showing an example of the search processing of the route searching device of the second embodiment of the present invention. FIG. 9 is an explanation of the operation of the same device. @ Fig. 10 is a flowchart showing an example of the search process of the route searching device according to the third embodiment of the present invention, Fig. 11 is an explanatory diagram showing an overview of the operation of the same device, and Fig. 12 is a flowchart showing an example of the search process of the route searching device according to the third embodiment of the present invention. FIG. 13 is a flowchart showing an example of the search process of the route search device of the embodiment, FIG. 13 is a flowchart showing an example of the specific number of sheets search process of the fourth embodiment, and FIG. Am 101...Point storage means, 102...Map data storage means, +03...Search result memory half-dead 104...
・Search means, 105...Name of output agent Shigetaka Awano Haka 1 name Figure Figure Figure ■ Figure Figure Figure 13

Claims (8)

[Claims] (1) A point storage means that stores the positions of the departure point and the destination, and road network data that is divided into a plurality of specific ranges and stored;
A map data storage means for storing connection relationship data of each divided specific range road network data, and a map data storage means for storing connection relationship data of each divided specific range road network data, and a shortest distance route or an optimal route within one or more specific ranges with the starting point or destination as a starting point. A route characterized by comprising a search means for searching in the search means, a search result storage means for storing the search results by the search means, and an output means for reading out the search results from the search result storage means and outputting them. Exploration device. (2) When searching for the shortest distance route or the optimal route in at least one specific range, the search means searches for each specific range using road network data for each specific range, and stores this search result data in the search result storage means. 2. The route search device according to claim 1, wherein the route search device stores the information in the route search device. (3) The route search device according to claim 1 or 2, wherein the connection relation data is road connection data with a specific range adjacent to the divided boundary. (4) The search means converts each of two or more specific ranges of road network data into the same data structure as one specific range of road network data, searches for each of the converted road network data, and searches for the search result data. 4. The route search device according to claim 1, 2 or 3, wherein the search result storage means stores the search result storage means. (5) The map data storage means stores a plurality of road network data having different details divided into respective specific ranges,
5. The route search device according to claim 1, wherein the search means searches for each specific range using road network data with different details, and stores the search result data in the search result storage means. . (6) The map data storage means stores a plurality of road network data with different details divided into specific ranges, and also stores common points on the road network between the road network data with different details. The search means uses this data to switch searches between road network data of different details, and stores the results in the search result storage means. The route searching device according to claim 5. (7) The map data storage means stores a plurality of road network data with different details divided into specific ranges, and also stores the road network data with different details in which the common parts of roads are the same. The search means uses this data to switch the search between the road network data having different details, and stores the search result data in the search result storage means. The route searching device according to claim 5. (8) The search means searches the road network data for each specific range from both the location of the departure point and the location of the destination, and uses two or more pieces of road network data with different details to find the shortest route or 6. The route searching device according to claim 5, further comprising searching for an optimal route and storing the search result in search result storage means.