JPH08128843A - Path searching device - Google Patents

Abstract

PURPOSE: To provide a path searching device which can reduce the time required for searching a path and enable the reduction of a memory capacity. CONSTITUTION: A central processing unit 3 of a navigation device 1 reads map data from a CD-ROM device 8 where map data with a plurality of types of scales are stored in a hierarchy with one point and the other point as a starting point and ending point, respectively, based on the coordinate data of two points by specifying two points so that the scale is the smallest near the starting and the ending points and the scale increases as the distance from the starting to ending point increases. The path from the starting to ending point is searched based on the map data which are read out and a path selected by path search is displayed on a display 10 via a display drive circuit 9.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention is suitably applied to a so-called navigation device capable of displaying a vehicle position and a destination position on a map screen, and for searching a route from a current position to a destination. The present invention relates to a route search device used.

[0002]

2. Description of the Related Art The navigation device is a device mounted on an automobile, displaying the automobile position together on a map screen, and updating the display as the automobile travels.
Further, in recent years, in this navigation device, by inputting the current position and the destination or waypoint, the route having the shortest distance from the current position to the destination or waypoint is calculated and displayed as a recommended route. Such a route search function is being added.

The map data, which is the basis of the map screen, is roughly composed of topographical data such as land, sea and river, and road data. In addition, the road data is configured to include node data representing an intersection and link data connecting the respective node data.

The map data constructed in this way is a CD
-When performing a route search, the searching means that is stored in the ROM device and that performs the route search sequentially reads the map data of the area required for the route search from the CD-ROM device and stores it in the memory provided in the searching means. Perform route search while capturing.

[0005]

In the above-mentioned prior art,
In general, when performing a route search from a starting point for starting the route search to an ending point for ending the route search, map data of a single scale is used as the map data used for the route search. Therefore, when the scale of the map data used for route search is small, for example, when the distance between the start point and the end point is large, the amount of information of the map data read from the CD-ROM device is large, and as a result, the route is The amount of information to be calculated for the search increases, and the time required to determine the recommended route to select increases. Further, it is necessary to increase the storage capacity of the memory provided in the search means, which increases the manufacturing cost of the device.

An object of the present invention is to provide a route search device which can reduce the time required for route search and reduce the memory storage capacity.

[0007]

SUMMARY OF THE INVENTION The present invention is designated 2
In a route search device for searching a route between points based on map data stored in advance, a storage means for storing map data of a plurality of kinds of scales and a route search for one of the two points. The starting point is the starting point, the other point is the ending point for ending the route search, the map data is read from the storage means, and the route search is performed based on the map data having a small scale in the vicinity of the starting point and the ending point. And a map screen is displayed on the basis of the map data read from the storage means and a search means for performing a route search based on map data having a larger scale as the distance increases, and the search is performed on the displayed map screen. Display means for displaying the route searched by the means. Further, the searching means of the present invention is characterized in that, according to a predetermined rule, one of two designated points is a starting point and the other point is an ending point. Further, according to the present invention, in a route search device for searching for a route between two designated points based on map data including node data representing an intersection and link data connecting each node, Storage means for hierarchically storing map data of a plurality of types of scales in each area, setting operation in which one of the two points is the starting point and the other is the ending point, and in the vicinity of the starting point A first read operation of reading the map data having the smallest scale from the storage means and reading the map data from the storage means such that the scale increases as the distance from the start point increases, and the map data having the smallest scale near the end point. From the storage means, and a second read operation for reading the map data from the storage means such that the scale becomes larger as the distance from the end point becomes larger; And a search means for performing a first search operation for performing a route search from a start point to an end point based on the map data of a plurality of layers with different scales read by the second read operation, and based on the map data read from the storage means. And a display unit for displaying a route searched by the first searching operation by the searching unit on the displayed map screen. Further, the searching means of the present invention, in the first and second reading operations, a starting point and a starting point for selecting map data of a predetermined area of a predetermined scale to be read from the map data stored in the storage means. A second search operation is performed in which a route search is performed starting from the end point, and at the time of the second search operation, the hierarchy to which the search point belongs along with the movement of the search point indicating the end point of the search route for which the route search is being performed. When the map data of a predetermined area belonging to the same level as or one level above is read and the search route reaches one level by a predetermined number set for each level,
The second search operation is terminated when the reading of new map data belonging to a layer below one layer is completed and the predetermined number of search routes reach the uppermost layer. In addition, according to the present invention, the node data of the map data of each layer is 1
An upper node that can move to a corresponding node in a layer one level above and a lower node that can move to a corresponding node in a layer one level below are included, and the searching means includes a first search. In the operation, when searching for a route that goes up from the start point to the top layer and a route that goes down from the top layer to the end layer, the route search is performed based on the map data read by the first and second read operations. When the search route moves from one layer to another layer, the upper node moves to the upper layer and the lower node moves to the lower layer. Further, the searching means of the present invention, in the first search operation, when performing a route search from the map data of the uppermost layer read by the first reading operation to the map data of the uppermost layer read by the second reading operation. Is characterized in that the first search operation is performed while reading only the map data belonging to the uppermost hierarchy from the storage means. Further, the searching means of the present invention, when the new map data is read in the second searching operation, has already been read belonging to a layer one level above or below the layer to which the new map data belongs. Maps that belong to the lower layer of the two map data that have been collated by comparing the map data with new map data, detecting multiple nodes that correspond to each other, and performing the second search operation starting from the start point. The node detected in the data is set as an upper node connected to the upper layer, and when the second search operation is performed starting from the end point, the node detected in the map data belonging to the upper layer is set as the lower node connected to the lower layer. It is characterized by setting. The searching means of the present invention is the second
In the search operation, the difference in the route cost per unit distance between roads of different types is smaller than that in the first search operation. Further, when the map data includes the display drawing data, the display character data and the road data as a group, the search means of the present invention extracts and retains only the data necessary for the route search. Is characterized by.

[0008]

According to the present invention, when two points are designated by the operator, the search means sequentially reads the map data required for the route search from the storage means and performs the route search based on the read map data. The route searched by the search means is displayed by the display means.

The map data used by the search means for the route search has a reduced scale near the start point where the route search is started and the end point where the route search is ended, and the scale is increased as the distance from the start point and the end point increases. It is supposed to be.

Therefore, near the start point and the end point, the route search is performed based on the map data having a small scale, and as the distance from the start point and the end point increases, the route search is performed based on the map data having a large scale. The amount of information in the map data used for route search is smaller than that in the case where route search is performed based on small scale map data from the entire route to the end point, and as a result, the time required for route search is reduced. be able to. Further, since the amount of information of the map data used is small, the storage capacity of the memory for temporarily storing the map data read from the storage means can be reduced, and as a result, the manufacturing cost of the route search device can be reduced. The cost can be reduced.

In addition, since a route search is performed near the start point and the end point based on map data having a small scale, for example, even when the start point or the end point is far from the main highway, the scale including detailed road data is included. You can search for a suitable route based on the small map data of.

According to the invention, the search means sets the start point and the end point based on the two points designated by the operator, based on the coordinate data of the two points included in the map data. According to a predetermined rule, one of the two designated points is the starting point,
The other point is the end point.

Therefore, for example, when searching for a round-trip route between two points, the same point is set as the start point and the end point when searching for the outward path and when searching for the return path. A route search is performed in a direction, and it is possible to prevent a large difference between the searched outbound route and the inbound route due to the difference in the route search direction, and as a result, to search for similar or identical outbound and inbound routes. be able to.

Further, according to the invention, when two points are designated by the operator, the searching means performs a setting operation with one of the two points as a starting point and the other point as an ending point, Following the operation, the first read operation of reading the map data from the storage means having the smallest scale in the vicinity of the start point and the map data from the storage means such that the scale becomes larger as the distance from the start point increases, and the end point. In the vicinity of, the map data having the smallest scale is read from the storage means, and the map data is read from the storage means such that the scale becomes larger as the distance from the end point becomes larger. After the 2nd read operation, a first search for performing a route search from a start point to an end point based on map data of a plurality of layers with different scales read in the first and second read operations Perform the operation.

Further, according to the invention, the searching means in the above-mentioned first and second reading operations, map data of a predetermined area of a predetermined scale to be read out from the map data stored in the storage means. The second search operation for selecting is performed. In the second search operation, a route search starting from the start point and the end point is performed, and the search point indicating the end point of the search route for which the route search is being performed is a peripheral portion adjacent to the area where the map data has not been read yet. When it reaches, the map data of the area is read from the storage means. The second search operation is
The map data of a predetermined area belonging to the same hierarchy as the search point belongs to, or one hierarchy higher than the hierarchy to which the search point belongs is read along with the movement of the search point.
When the search route reaches one layer by a predetermined number set for each layer, the reading of new map data belonging to a layer below the one layer is completed. The route search is further performed, and when the predetermined number of search routes reach the uppermost layer, the second search operation is ended. The search point in the second search operation gradually moves from the lower layer to the upper layer as the search progresses, that is, as the distance from the start point and the end point generally increases.

Therefore, in the first and second read operations, the map data to be read from the storage means is determined by the second search operation, so that the map data is separated from the start point and the end point so that the scale becomes small near the start point and the end point. The map data can be efficiently read so that the scale becomes larger as it goes.

According to the invention, in the first search operation, when the search means searches for a route ascending from the starting point to the uppermost layer and a route descending from the uppermost layer to the end layer, Based on the map data read by the first and second read operations, a route search is performed without reading new map data.

In the node data of the map data of each layer,
It includes an upper node that can move to the corresponding node in the next higher layer and a lower node that can move to the corresponding node in the next lower layer. However, when moving from one layer to another layer, it moves from the upper node to the upper layer and from the lower node to the lower layer.

Therefore, in the first search operation for searching the route from the start point to the end point, in the search operation of the route going up the hierarchy from the start point to the top layer and the path going down the layer from the top layer to the end point, Since the route search is performed based on the map data read by the first and second read operations, it is possible to prevent the search route by the first search operation from unnecessarily expanding in a lower hierarchy of a small scale.
As a result, the time required for the route search by the first search operation can be reduced. Further, the storage capacity of the memory for temporarily storing the map data read from the storage means can be reduced.

According to the invention, in the first search operation, a route search is performed from the map data of the highest hierarchy read by the first read operation to the map data of the highest hierarchy read by the second read operation. In this case, the search means performs the route search while reading only the map data belonging to the highest hierarchy from the storage means.

Therefore, in the area separated from the start point and the end point by a predetermined distance or more, the route search by the first search operation is performed based on the map data belonging to the uppermost layer.
The information amount of the map data read from the storage means can be reduced, and the time required for the route search by the first search operation can be reduced. Further, the storage capacity of the memory for temporarily storing the map data read from the storage means can be reduced.

For example, when the distance between the start point and the end point is large, by performing the route search by the first search operation based on the map data of the top layer having a large scale,
It is possible to efficiently search for a main trunk road to be selected which connects the starting point or the surrounding area of the starting point and the ending point or the surrounding area of the ending point.

According to the invention, the second means by the search means
In the search operation, when new map data is read, the already read map data belonging to the layer one level above or below the layer to which the new map data belongs is compared with the new map data. , A plurality of nodes corresponding to each other are detected. When the second search operation is performed starting from the starting point, the node detected in the map data belonging to the lower layer of the two collated map data is set as the upper node connected to the upper layer, and the end point is set. When the second search operation is performed as the starting point, the node detected in the map data belonging to the upper layer is set as the lower node connected to the lower layer.

With the upper node and the lower node thus set, when the search point of the search route reaches the upper node or the lower node during the first search operation, the search point passes through the upper node or the lower node. And move one level up or down.

Therefore, the search means collates the map data between different layers and reads the map data from the storage means while setting the upper node and the lower node.
Even if the map data stored in the storage means does not include data relating to the upper node and the lower node, and the correspondence between the nodes in different layers is unknown,
A route search can be performed using the map data.

Further, according to the present invention, in the second search operation, the difference in route cost per unit distance between roads of different types is set smaller than in the first search operation. This prevents the searched route searched by the second search operation from concentrating on an expressway having a smaller route cost than an ordinary road, for example. Therefore, it is possible to prevent the upper node or the lower node from concentrating along the expressway, and it is possible to set the upper node or the lower node with appropriate variation. as a result,
An appropriate route can be searched in the first search operation.

Further, according to the present invention, when the map data includes the display drawing data, the display character data and the road data as a group, the searching means reads the map data from the storage means. , Extracts and retains only the data required for route search. Therefore, the search means extracts and holds only the data necessary for route search,
It is possible to reduce the storage capacity of the memory that stores the map data read from the storage means.

[0028]

1 is a block diagram showing the electrical construction of a navigation device 1 in which a route search device according to an embodiment of the present invention is used. The navigation device 1 is mounted on an automobile to display a current position and display route guidance to a destination, and is useful for determining a driver's course.

Therefore, roughly, in this navigation device 1, in response to an input operation to the operation keys 2, the central processing unit 3 realized by a microcomputer or the like is provided with the CD-ROM device 5 via the communication bus 4. Instruct to read the map data of the desired area. In response to the instruction, the processing circuit 6 causes the CD-ROM via the decoder 7.
The map data of the corresponding area is read from the map data recorded on the disk 8. In this way, corresponding to the map data input from the processing circuit 6 via the communication bus 4,
The central processing unit 3 drives the display device 10, which is realized by a liquid crystal display device or the like, through the display drive circuit 9 to display the map screen of the desired area.

Further, the navigation device 1 has a G
A PS (Global Positioning System) receiver 11 is provided, and the GPS receiver 11 performs triangulation based on a signal from a positioning satellite that orbits the earth, which is received by a GPS antenna 12, to perform triangulation. Latitude, longitude, altitude, running speed, etc. are calculated, and the calculation result is output to the central processing unit 3 via the communication bus 4.

Furthermore, the navigation device 1 is provided with a geomagnetic sensor 13, a gyro sensor 14, and a wheel speed sensor 15. The geomagnetic sensor 13 detects the traveling direction of the vehicle, the gyro sensor 14 detects a change in the posture of the vehicle, and the wheel speed sensor 15 detects the vehicle speed. The detection results of the sensors 13 and 14 are converted into digital values by the analog / digital converters 16 and 17 and input to the processing circuit 19. In addition, the wheel speed sensor 15
The vehicle speed pulse from is counted by the pulse counter 18 and input to the processing circuit 19. At this time, when the reverse position detector 25 detects that the gear position of the transmission is in the reverse position, the count value is set to a negative value.

Data relating to the position of the vehicle or the like input by the operation keys 2 from the central processing unit 3 is input to the processing circuit 19, which causes the processing circuit 19 to detect the current detection result of each of the sensors 13-15. The position of the vehicle is estimated and calculated, and the calculation result is output to the central processing unit 3. In this way, the vehicle position can be accurately measured by so-called dead reckoning even at a point where the GPS receiver 11 cannot accurately measure the vehicle position, for example, in the shadow of a building, under the overpass, or in a tunnel. it can.

Furthermore, a memory 20 is provided in association with the central processing unit 3. As will be described later, the memory 20 stores destinations and transit points of the selected route, and is used by the central processing unit 3 for route search read from the CD-ROM disk 8 via the processing circuit 6. The map data for is stored.

FIG. 2 is a functional block diagram for explaining the route guidance operation of the navigation device 1 configured as described above. When the current position and the destination or waypoint are input from the input unit 31 such as the operation keys 2, the GPS receiver 11 and the processing circuit 19, the point setting unit 33 of the route search unit 32, before starting the search, In relation to the input point, a search point which should be a point to start the search or a point to end the search is initialized.

Between the set search points, the search unit 34
Map data is read from the D-ROM device 5 or the like as indicated by reference numeral 35, a route is searched by following links, and the search result 36 is given to the route guidance unit 37,
The data management unit 38 in the route search unit 32 causes the memory 2
Stored at 0.

On the other hand, the map data 35 is also given to the own vehicle position detecting section 39, and this own vehicle position detecting section 3
Reference numeral 9 performs map matching between the outputs from the GPS receiver 11 and the processing circuit 19 and the map data 35 to calculate an accurate own vehicle position and gives it to the route guide unit 37, and the display drive circuit. 9 and display device 1
It is given to the output unit 40 realized by 0 or the like. The output unit 40 is also provided with data regarding the selected route from the route guide unit 37, and thus the route guide unit 3 is provided.
The own vehicle position measured by the own vehicle position detection unit 39 is also displayed on the route created by 7, so that route guidance can be provided.

The operation of the navigation device 1 at the time of route search will be roughly described. When the point indicating the current position and the point indicating the destination or the waypoint are input from the input unit 31, the point setting unit 33 determines in advance, as will be described later, in relation to the two input points. According to the rule set, one of the two points is set as the point where the route search should be started, and the other point is set as the end point where the route search should be ended, that is, the direction of the route search is set. To do.

When the sorting operation is performed, the scale is minimized in the vicinity of the start point and the distance from the start point is increased prior to the first search operation for searching the set route from the start point to the end point. The first read operation of reading the map data so that the scale becomes larger as
Following the read operation, a second read operation is performed in which the map data is read such that the scale is the smallest near the end point and the scale increases as the distance from the end point increases. As a result, the map data used in the first search operation is determined in advance in the peripheral part of the start point and the peripheral part of the end point.

When the first and second read operations are performed,
The first search operation is performed based on the map data read by the first and second read operations, and the route from the start point to the end point is selected.

During the first and second read operations, the CD
A route search is started from a start point and an end point in order to select and read out map data of a predetermined area of a predetermined scale out of the map data stored in the CD-ROM disk 8 of the ROM device 5; Two search operations are performed respectively. At the time of the second search operation, with the movement of the search point indicating the end point of the search route for which the route search is being performed, a predetermined area belonging to the same hierarchy as the search point The map data of is read.

Before describing the sorting operation for setting the start point and the end point of the route search, a conventional method of setting the start point and the end point will be described with reference to FIG. In the Dijkstra method that is generally used as a basic method for route search, when performing a route search between two points, it is necessary to set the direction of the route search. Conventionally, the point indicating the current position and the point indicating the destination are When input, the point indicating the current position is set as the start point for starting the route search, and the point indicating the destination is set as the end point for ending the route search, and the route search is performed from the current position toward the destination. .

In the structure for performing the route search in the direction from the current position to the destination, the route search is performed when the current position and the destination are exchanged and when the current position and the destination are exchanged. In some cases, the directions in which the route search is performed are opposite to each other, and even when the route search is performed under the same conditions, routes that are significantly different from each other may be selected depending on the characteristics of the route search.

For example, as shown in FIG. 3 (1), when searching for a round-trip route between a point A and a point B, a search is made for a route with the point A as the current position and the point B as the destination. There is a case where the going route R1 and the returning route R2 are greatly different from each other depending on whether the route B1 is the current position and the point A is the destination. . In general, in the case of a round-trip route, it is rare that the optimal route for going and the optimal route for returning are significantly different, and it is unnatural that the route R1 for going is greatly different from the route R2 for returning.

One of the causes of the difference between the going route R1 and the returning route R2 as described above is the search range of the route search set when the going route shown in FIG. 3B is searched. C1 and return route R shown in FIG. 3 (3)
The search range C2 set when searching 2 is different from each other.

The route search is performed in a preset search range, for example, a region within the search ranges C1 and C2.
As shown in FIG. 3 (2), the search range is set so as to include points A and B at which the route search is performed, and the shape of the search range is generally different between the periphery of the start point and the periphery of the end point. Differently, for example, the peripheral portion of the end point B is set to be wider than the peripheral portion of the start point A.

For this reason, as shown in FIG. 3 (2), with the points A and B as the starting point and the ending point, respectively, when searching for the going route, the route R1 having a wide road width and a high moving speed, and the road R Route R2 with narrow width and slow moving speed
When and are selectable as recommended routes, it is assumed that the route R1 having a wide road width and a high moving speed is finally selected as the recommended route even if the distance is long. In contrast, Fig. 3 (3)
As shown in, when searching for the return route with the points B and A as the start point and the end point, respectively, the route R1 searched as the outgoing route is out of the search range C2, so the route R2 is the return route. It will be searched as a route.

In order to solve the above-mentioned point, the present invention performs a sort operation for determining the direction in which the route search is performed according to a predetermined rule. This sorting operation is performed based on the coordinate data included in the map data indicating the latitude and longitude of each point on the map.

The sorting operation will be described by taking as an example the case of searching for a round-trip route between the point A and the point B shown in FIG. When the latitude of the point A is XA, the longitude is YA, the latitude of the point B is XB, and the longitude is YB, XA,
The relation between YA and XB, YB is XA <XB, or XA =
When XB and YA <YB, the point A is set as the start point and the point B is set as the end point. Conversely, XA> XB, or X
When A = XB and YA> YB, the point A is the end point and the point B is the start point. By setting the start point and the end point in this way, for example, the longitude of the point A is changed to the point B.
If it is smaller than the longitude of, the point A is always set as the start point and the point B is set as the end point.

When actually performing a route search, in the case of a forward search in which the traveling direction and the search direction of the route in which the point A is the current position and the point B is the destination are the same, the route search is performed as it is. It suffices to carry out, but in the case of a reverse search in which the traveling direction and the search direction of the route in which the point A is the destination and the point B is the current position are opposite directions, the actual traveling direction of the car Since the directions in which the route search is performed and the directions in which the route search is performed are opposite to each other, it is necessary to change the calculation of the route cost between the one-way inversion and the right turn and the left turn when performing the route search.

In such a reverse route search, when the route under search reaches a one-way section, the direction of one-way passage in that section is reversed, and the route under search turns right at an intersection or the like. When a left turn is made, the calculated value of the route cost is different between the right turn and the left turn. Therefore, the route search is performed while replacing the right turn with the left turn and the left turn with the right turn. By performing the route search in the reverse direction in this manner, the route search in the direction opposite to the actual traveling direction of the vehicle is appropriately performed.

In this embodiment, by performing the sorting operation, for example, the route search is performed in the same direction when searching for the going route and when returning, so that the directions of the route searching are opposite to each other. Thus, it is possible to prevent the route going back and the route going back from being greatly differently searched.

FIG. 4 is a diagram for explaining the first and second read operations. When the start point S and the end point G are set by the sort operation described above, map data is read from the CD-ROM disk 8 by the first and second read operations. At the time of the first read operation, the second search operation starting from the start point S is performed, and the map data is moved as the search point indicating the end point of the search route searched by the second search operation moves. Is read out, and during the second read operation, the second search operation starting from the end point G is performed, and as the search point indicating the end point of the search path searched by the second search operation moves. Map data is read out.

In the CD-ROM disk 8, the map data of each area of a plurality of different scales is hierarchically stored for each scale and is stored in the CD-ROM disk 8 in association with the second search operation. Of the existing map data, map data of a predetermined area and a predetermined scale is sequentially read.

The second search operation is a route search in which the search routes being searched between map data having different scales can be changed from each other. As will be described later with reference to FIGS. 6 and 7, the start point S and the end point on the map data Ma1 and Ma2 belonging to the lowest hierarchy Ma, which has the smallest scale including the start point S and the end point G respectively, that is, the lowest hierarchy Ma. When the second search operation starts from G,
As the route search progresses, the search point moves to the upper level,
The map data of the upper hierarchy is sequentially read. When the route search progresses and the search points of the search route under search starting from the start point S and the end point G reach the highest scale Mc, which is the highest scale, that is, the first and the first and second scales. 2 The reading of the map data by the reading operation is completed.

In this embodiment, the CD-ROM disk 8 has map data of three types of reduced scales in three levels of layers Ma and M.
b and Mc are stored. Also the first and second
By the second search operation starting from the start point S and the end point G in the read operation, the map data Ma1 and Ma2 are read from the lowest hierarchy Ma, respectively, and the middle hierarchy M is read.
The map data Mb1 and Mb2 are read from b, and the map data Mc1 and Mc2 are read from the uppermost layer Mc.
Are read respectively.

By the first and second read operations as described above, when searching for a route that goes up the hierarchy from the starting point S of the lowest hierarchy Ma to the highest hierarchy Mc in the first search operation described later, and from the highest hierarchy Mc The map data used when searching for the route down the hierarchy to the end point G of the lower hierarchy Ma is determined in advance.

FIG. 5 is a diagram for explaining the setting operation for setting the upper node and the lower node which is performed in association with the second search operation described above. The map data stored in the CD-ROM disk 8 includes node data representing intersections and link data connecting each node, and the connection state of each road is determined by the node data and the link data. Is represented.

If the map data stored in the CD-ROM disc 8 does not include data representing node data corresponding to each other between map data belonging to different layers, a first search operation described later. In order to carry out a route search that changes between different layers in, the map data read from the CD-ROM disk 8 and belonging to different layers should have coordinate data included in the node data and a link connected to the node. It is necessary to collate the nodes based on the number and the like and detect the corresponding node data in advance.

In the second search operation, for example, one hierarchy Ib shown in FIG. 5 (2) above one hierarchy Ia shown in FIG. 5 (1) to which the search point of the search route under search belongs.
When the map data Ib1 belonging to is read, the already read map data Ia1 to Ia3 belonging to the hierarchy Ia,
Map data I belonging to the newly read layer Ib one above
By collating with b1, the node data included in the map data Ib1 corresponding to the node data included in the map data Ia1 to Ia3 is detected.

When the corresponding node data is detected, when all or part of the detected nodes are performing the second corresponding operation with the start point as the starting point, the upper node U is added to the map data Ia1 to Ia3. It is set to the included node data, and when the second search operation is performed starting from the end point, it is set to the node data included in the map data Ib1 as the subordinate node D. When the search point of the search route being searched in the first search operation reaches the upper node U, the upper node U can move the search point to the node of the map data belonging to the layer one level higher than the upper node U. It is a node. When the search point of the search route being searched in the first search operation reaches the lower node D, the lower node D may move from the lower node D to the corresponding node of the map data belonging to the next lower layer. It is a possible node.

In this embodiment, when the search point reaches the upper node in the first search operation, the search point is set to move to the node belonging to the layer one level higher through the upper node. When reaching the lower node, the search point is set to move to the node belonging to the next lower layer through the lower node.

The map data I shown in FIG. 5 (1) is used.
a4 is map data that has not yet been read because reading is prohibited.

FIG. 6 is a flow chart for explaining the second search operation starting from the starting point. When the start point and the end point are set by the sort operation described above, step a
At 1, the map data of the area including the starting point is read from the map data of the lowermost layer, and at step a2, the second search operation starting from the starting point is started based on the map data read at step a1.

From step a2 to step a3, it is determined whether or not the search point, which is the end point of the search route being searched by the second search operation, has reached the peripheral portion of the map data to which the search point belongs. If it is determined that it has arrived, the process proceeds to step a4, and if it is determined that the contact is not made, the process proceeds to step a9. Here, the peripheral portion of the map data refers to a portion of the area covered by the map data of one area, which is adjacent to the area covered by the other map data. In step a4, it is determined whether or not the reading of the map data of the area adjacent to the map data where the search point is located is prohibited. If it is prohibited, the process proceeds to step a9, and if it is not prohibited. To move to step a5.

At step a5, the map data of the area adjacent to the peripheral portion where the search point is located is read out, and step a5
It moves to step 6, and it is judged whether or not the map data belonging to the next higher layer corresponding to the area of the map data read in step a5 has already been read. If already read, the process moves to step a8 and reads. If not, the process proceeds to step a7. At step a7, the map data belonging to the next higher layer corresponding to the area of the map data read at step a5 is read, and the process proceeds to step a8.

At step a8, the layer to which the search point belongs has already been read out, or the map data newly read at step a5 and the layer one level above the layer to which the search point belongs have already been read out or step a7. Then, the new map data read out is collated, and the upper node as shown in FIG. 5A is set on the map data of the layer to which the search point belongs. The upper node setting operation of step a8 is performed when new map data is read in step a5 or step a7.

The process moves from step a8 to step a9. At step a9, the search point of the route under search reaches the upper node set at step a8 by the route search carried out at step a2, and the next higher layer is reached. If it is determined that the shift has been made, the process proceeds to step a10, and if it is determined that the shift has not been made, the process returns to step a2.

At step a10, the number of times the searched route being searched for has reached each layer is counted for each layer, and the process proceeds to step a11. In step a11, each count value counted in step a10 is compared with each predetermined value preset for each layer, and any one of the count values corresponding to each layer becomes equal to or larger than the corresponding predetermined value. It is determined whether or not the result is satisfied. If it is determined that the condition is satisfied, the process proceeds to step a12, and if not, the process returns to step a2.

At step a12, it is determined whether or not the count value determined to be equal to or larger than the predetermined value at step a11 is the count value corresponding to the top layer, and it is determined that the count value corresponds to the top layer. If it is determined that the count value corresponding to the uppermost layer is not reached, the process proceeds to step a14, and the second search operation starting from the starting point is terminated. The new reading of the map data belonging to the layer below the layer corresponding to the counted value is prohibited, and the process returns to step a2.

Thus, from step a2 to step a
By repeating step 13, the map data is sequentially read from the CD-ROM disk 8. Appropriate values are set as the predetermined values set in advance for each layer, depending on the scale of each layer, the size of the area covered by one map data belonging to each layer, and the like.

FIG. 7 is a flow chart for explaining the second search operation starting from the end point. In the flowchart of FIG. 7, steps corresponding to the steps of FIG. 6 described above are designated by the same reference numerals, and description thereof will be omitted. Figure 7
The second search operation starting from the end point shown in FIG. 6 is similar to the second search operation starting from the start point shown in FIG.
The difference from the second search operation of FIG. 6 is that the map data belonging to the lowest hierarchy of the area including the end point is read in step b1, and that the lower node, not the upper node in FIG. The points are set as shown, and the operations of the other steps are almost the same. However, in the second search operation performed in step a2 of FIG.
A route search is performed in the direction of the starting point starting from the ending point.

Similarly to the case of the second search operation starting from the starting point in FIG. 6, in the second search operation starting from the end point in FIG. 7 as well, after the map data belonging to the lowest hierarchy is read in step b1. , The map data are sequentially read by repeating the steps from a2 to a13.

When the second search operation starting from the start point and the end point shown in FIGS. 6 and 7 is performed, the map data in a wider range than necessary is not read except for a predetermined area. Reading of map data in the area is prohibited. This prohibition of reading the map data is determined in step a4 in FIGS. 6 and 7.

In the second search operation starting from the end point, when the search point being searched for reaches a node corresponding to a lower node in a hierarchy one level higher than the hierarchy to which the search point belongs, the search point corresponds to the node. From the node to be performed to the upper node in the next higher layer.

In the second search operation shown in FIGS. 6 and 7, when the route search progresses and the search point under search reaches the peripheral portion of the map data of one area belonging to one hierarchy, it is adjacent to the peripheral portion. The map data of the area to be read is read, and along with this, the map data of the area that belongs to the next higher layer corresponding to the read map data of the area is read. As described above, in the second search operation, as the route search progresses, that is, as the distance between the start point and the end point and the search point being searched increases, the map data of a higher hierarchical scale is sequentially read out. To be done.

In the second search operation of FIGS. 6 and 7,
The difference between the route costs per unit distance between the roads of different types is set smaller than that in the first search operation described later, and the route search is performed. In a normal route search such as a first search operation described later, for example, a highway having a high moving speed is set to have a smaller route cost per unit distance than an ordinary road and the route search is performed. Under this setting, the route search is performed so that the route with the smallest sum of the route costs of all routes is selected, so there is a high probability that a highway with a low route cost will be selected as the recommended route. Become. In a normal route search, an appropriate route can be searched by setting the route cost in this way. Here, the route cost represents the time taken for the vehicle to actually move along the route.

However, if the second search operation is performed under such a setting, the probability that the above-mentioned upper node and lower node will be set along an expressway having a low route cost will increase, and the route cost will increase. The probability that the map data will be read along a small route increases, and the set upper and lower nodes and the set map data will be biased.

When the upper node and the lower node and the read map data are biased, when a route search is performed by a first search operation described later, a roundabout route that is larger than a route to be selected may be selected. It will cause. Therefore, in the second search operation, in order to prevent such bias of the upper node and the lower node and the read map data, the difference in the route cost per unit distance between roads of different types is set small. Has been done.

When the first and second read operations, in which the second search operation is performed, are completed, the first search operation for searching the entire route from the start point to the end point is performed. Referring to FIG. 4, the first
The search operation is performed in the first search section from the start point S belonging to the lowermost layer Ma to the uppermost layer Mc and the second search section in the uppermost layer Mc.
It is composed of a search section and a third search section from the uppermost layer Mc to the end point G belonging to the lowermost layer Ma.

In the first and third search sections, the route search is performed only on the basis of the map data read by the first and second read operations, and the second search section is the uppermost layer Mc.
The route search is performed while reading only the map data belonging to.

When the first search operation starts from the starting point S and the search point of the search route under search reaches the upper node U1 on the map data Ma1 belonging to the lowest hierarchy Ma, the upper node U1 changes the upper node. 1 corresponding to U1
The process moves to the node N1 on the map data Mb1 of the upper hierarchy Mb. When the route search is further continued and the search point reaches the upper node U2 on the map data Mb1, the upper node U2
The search point moves to the node N2 belonging to the uppermost layer Mc, which is the next higher layer corresponding to. When the search point reaches the highest hierarchy Mc in this way, the search operation shifts from the search operation in the first search section to the search operation in the second search section.

In the search operation of the second search section, the map data belonging to the highest hierarchy Mc is CD- as the route search progresses.
A route search is performed while being read from the ROM disk 8. When the search operation in the second search section progresses and the search point being searched reaches the map data Mc2 belonging to the uppermost layer Mc read by the second read operation, the search operation in the second search section ends and the third search section. Shift to the search operation in.

In the search operation in the third search section, when the search point being searched for reaches the lower node D1 set on the map data Mc2 belonging to the uppermost layer Mc, the search point becomes
The process moves from the lower node D1 to the node N3 on the map data Mb2 belonging to the next lower layer Mb corresponding to the lower node D1. Further, when the search point reaches the lower node D2 on the map data Mb2, the search point moves to the node N4 on the map data Ma2 belonging to the lowermost layer Ma, which is the next lower layer, and the route search is continued and the search is continued. When the inner search point reaches the end point G, the first search operation is ended.

In the route search by the first search operation, the sum of the route costs from the start point to the search point is calculated while moving the search point which is the end point of the searched route being searched, and the sum of the route costs is the most. Select a smaller search point. Next, it is checked whether there is another route to the selected search point, and if there is another route, the sum of the route costs is the smallest among the plurality of routes to the selected search point. Let the route be a recommended route from the start point to the selected search point.

When the recommended route to the selected search point is established in this way, a new search point is provided on the node adjacent to the selected search point node via one link,
Similarly, the recommended route to the new search point is determined while sequentially moving the new search point.

In this way, the recommended route searched by the route search is determined for each section corresponding to one link between mutually adjacent nodes, and when the sequentially set search points reach the end point, the route search is performed. Is ended. The route search by the second search operation is similarly performed.

In the second search operation and the first search operation having the start point and the end point as the starting points, the route in which the vehicle actually travels and the route in which the route search is performed are opposite to each other. In the case of a search, the route search is performed while reversing one-way traffic and rereading right turn and left turn.

When the search point being searched for reaches the end point during the second search operation starting from the start point in FIG. 6, the second search operation is terminated at that point and the end point in FIG. 7 is set as the start point. The first search operation for performing the route search for all the routes is started without performing the second search operation described above. As a result, the time required for route search can be shortened.

Therefore, in the first search operation for performing the route search of all the routes from the start point to the end point, the scale is minimized near the start point and the end point, and the scale is increased as the distance from the start point and the end point is increased. Since the route search is performed based on the map data read as described above, compared to the conventional case where the route search from the start point to the end point is performed based on a single map data having a small scale, the CD- The information amount of map data read from the ROM disk 8 can be reduced. As a result, the amount of information to be processed is reduced, and the time required for route search can be greatly reduced. Further, the storage capacity of the memory 20 for temporarily storing the read map data can be reduced, and the manufacturing cost of the navigation device 1 can be reduced.

When searching for a route between two designated points, one of the two points is set as the start point and the other point is set as the end point based on the coordinate data of the two points. Since the sorting operation is performed, the search direction is set regardless of the traveling direction of the car, which makes a large difference between the going route and the returning route, for example, when searching for a round-trip route between two points. Can be prevented.

In addition, during the first and second read operations,
Since the map data to be read is determined as the search point of the search route being searched by the second search operation starting from the start point and the end point moves, the scale is reduced near the start point and the end point. , The map data can be efficiently read such that the scale increases as the distance from the start point and the end point increases.

In the first search operation, during the search operation of the first search section from the start point to the top layer and the third search section from the top layer to the end point, the read operation is performed in advance by the first and second read operations. Since the route search is performed based on the map data stored, it is possible to prevent the route being searched by the first search operation from unnecessarily expanding in a lower hierarchy having a small scale. As a result, the first search It is possible to reduce the time required for route search by motion.

In the first search operation, when performing the search operation for the second search section in the uppermost layer, the search operation is performed while reading only the map data belonging to the uppermost layer having a large scale. The amount of information of the map data read from can be reduced, and the time required for the route search by the first search operation can be reduced.

In the second search operation starting from the start point and the end point, the map data is read while referring to the map data between different layers and setting the upper node and the lower node, so that the CD-ROM disk 8 is used. Even if the map data recorded in does not include data related to upper nodes and lower nodes and the correspondence between nodes in different layers is unknown, the map data can be used for route search. .

Further, in the second search operation starting from the start point and the end point, the difference in route cost per unit distance between roads of different types is set smaller than in the first search operation. Therefore, it is possible to prevent the upper node and the lower node and the read map data from being concentrated along the highway with a low route cost, and the upper node and the lower node can be set with appropriate dispersion. . As a result, it is possible to perform an appropriate route search without wrapping around the route in the first search operation.

The central processing unit 3 uses the map data stored in the CD-ROM disk 8 to display drawing data,
If the display character data and the road data are included as a group, the first and second read operations,
When the map data is read from the CD-ROM disk 8 in the first search operation, only the data necessary for the route search is extracted from the read data and stored in the memory 20. Therefore, the storage capacity of the memory 20 can be reduced. Further, since the information amount of the map data to be searched in the memory 20 becomes small, the processing speed can be improved.

In the above-mentioned embodiment, it is assumed that the map data stored in the CD-ROM disk 8 does not include the data related to the upper node and the lower node. If set, the processes of step a8 for setting the upper node and step b8 for setting the lower node in the second search operation starting from the start point and the end point in FIGS. 6 and 7 are omitted.

In the above-described embodiment, the sorting operation is performed based on the coordinate data. However, the sorting operation is performed in the order of Japanese syllabary based on the intersection name and the place name included in the node data corresponding to the designated two points. You may make it set a start point and an end point.

In the above-described embodiment, the first read operation is performed, the second read operation is performed, and the first search operation is further performed. However, the central processing unit 3 can simultaneously perform a plurality of processes. In the case of a processing device capable of possible multi-task processing, the second read operation and the first search operation may be performed in parallel after performing the first read operation. Alternatively, the first search operation is performed from both the start point side and the end point side, the first search operation is performed from the start point side while performing the first read operation, and at the same time, the second search operation is performed from the end point side. Alternatively, the first search operation may be performed.

Further, in the above-described embodiment, in order to prevent the search route by the first search operation from being too wide in the hierarchy below the top hierarchy, prior to the first search operation of searching all the routes, The first and second read-out operations for predetermining the map data to be used for the search are performed.
When performing a route search in the search operation, it is easier to move the route being searched one level up or one level below that in the same level, so that the route below the top level The search path by the first search operation may be prevented from being too wide, and the first and second read operations may be omitted. By omitting the first and second read operations, the time required for route search can be significantly reduced.

As one of the methods for facilitating the movement of the search route being searched to move one level up or one level below that in the same level, the route cost of the route moving up or down by one level is There is a method of setting it smaller than the route cost of the inner route.

As another method for omitting the first and second read operations, in the first search operation, the first search section from the start point to the uppermost layer and the third search section from the uppermost layer to the end layer are searched. There is a method of preliminarily limiting the area of the map data read from the CD-ROM disk 8 for each layer so that the searched route searched by the operation does not spread more than necessary.

[0103]

Therefore, the route search is performed based on the map data having a small scale in the vicinity of the start point and the end point, and the route search is performed based on the map data having a large scale as the distance from the start point and the end point increases. For example, the amount of information in the map data used for the route search is smaller than that in the case where the route search is performed based on small scale map data over the entire route from the start point to the end point, and as a result, the time required for the route search is reduced. Can be made smaller.

Further, since the amount of information of the map data used can be small, the storage capacity of the memory for temporarily storing the map data read from the storage means can be reduced, and as a result, the route search device The manufacturing cost can be reduced.

Further, in the vicinity of the start point and the end point, since the route search is performed based on the map data having a small scale, for example, even when the start point or the end point is far from the main highway, the scale including the detailed road data is included. You can search for a suitable route based on the small map data of.

[Brief description of drawings]

FIG. 1 is a block diagram showing an electrical configuration of a navigation device 1 in which a route search device according to an embodiment of the present invention is used.

FIG. 2 is a functional block diagram illustrating route guidance in navigation 1.

FIG. 3 is a diagram for explaining a conventional route search operation.

FIG. 4 is a diagram for explaining first and second read operations.

FIG. 5 is a diagram for explaining a setting operation for setting an upper node and a lower node.

FIG. 6 is a second diagram in which the starting point in the first read operation is a starting point;
It is a flowchart which shows a search operation.

FIG. 7 shows a second starting point from the end point in the second reading operation.
It is a flowchart which shows a search operation.

[Explanation of symbols]

 1 Navigation Device 2 Operation Keys 3 Central Processing Unit 5 CD-ROM Device 10 Display Device 11 GPS Receiver 13-15 Sensor 19 Processing Circuit 20 Memory

Claims (9)

[Claims] 1. A route search device for searching a route between two designated points based on map data stored in advance, and a storage means for storing map data of a plurality of types of scales; One of the points is used as the starting point for starting the route search, the other point is used as the ending point for ending the route search, and the map data is read from the storage means, and based on the map data with a small scale in the vicinity of the starting point and the ending point. A route search is performed, and a route search is performed based on map data having a large scale as the distance from the start point and the end point increases, and a map screen is displayed based on the map data read from the storage unit, and the display thereof is displayed. And a display unit for displaying the route searched by the searching unit on the displayed map screen. 2. The searching means uses one of two designated points as a starting point and the other point as an ending point according to a predetermined rule.
The route search device described. 3. A route search device that searches a route between two designated points based on map data including node data representing an intersection and link data connecting each node, Storage means for hierarchically storing map data of a plurality of different scales in each area, setting operation in which one of the two points is a start point and the other is an end point, and in the vicinity of the start point A first read operation of reading the map data having the smallest scale from the storage means and reading the map data from the storage means such that the scale increases as the distance from the start point increases, and the map data having the smallest scale near the end point. From the storage means, and a second read operation for reading the map data from the storage means such that the scale increases as the distance from the end point increases, and the first read operation. And a search means for performing a first search operation for performing a route search from a start point to an end point on the basis of the map data of a plurality of layers having different scales read by the second read operation, and based on the map data read from the storage means. A route search device for displaying a map screen and displaying a route searched by the first searching operation by the searching unit on the displayed map screen. 4. The starting point for the search means to select map data of a predetermined area of a predetermined scale to be read from the map data stored in the storage means in the first and second read operations. And a second search operation for performing a route search from the end point as a starting point. At the time of the second search operation,
Along with the movement of the search point indicating the end point of the search route for which the route is being searched, the map data of a predetermined area belonging to the same layer as the search point or one layer above is read, , A predetermined number set for each layer 1
When one layer is reached, reading of new map data belonging to a layer below that one layer is finished, and when a predetermined number of search routes reach the uppermost layer, the second search operation is finished. The route search device according to claim 3. 5. In the node data of the map data of each layer, it is possible to move to an upper node which can be moved to the corresponding node of the upper layer and to be moved to the corresponding node of the lower layer. A lower node is included, the search means, in the first search operation, in the search operation of the path that goes up the hierarchy from the start point to the top hierarchy, and the path that goes down the hierarchy from the top hierarchy to the end point, A route search is performed based on the map data read by the first and second read operations, and when the searched route moves from one layer to another layer, it moves from the upper node to the upper layer and from the lower node to the lower layer. 5. The hierarchy is moved to
The route search device described. 6. The search means, when performing a route search from the map data of the highest hierarchy read by the first read operation to the map data of the highest hierarchy read by the second read operation in the first search operation. 5. The route search device according to claim 4, wherein the first search operation is performed while reading only the map data belonging to the uppermost hierarchy from the storage means. 7. The searching means, when the new map data is read in the second searching operation, has already been read belonging to a layer above or below the layer to which the new map data belongs. Existing map data is collated with new map data, a plurality of nodes corresponding to each other are detected, and when the second search operation is performed with the start point as a starting point, it belongs to the lower layer of the two pieces of collated map data. The node detected in the map data is set as an upper node connected to the upper layer, and when the second search operation is performed starting from the end point, the node detected in the map data belonging to the upper layer is a lower node connected to the lower layer. The route search device according to claim 4, wherein 8. The search means reduces the difference in route cost per unit distance between roads of different types during the second search operation as compared with the case of the first search operation. The route search device according to claim 7. 9. The searching means extracts and retains only data necessary for route search when the map data includes the display drawing data, the display character data, and the road data in a lump. The route search device according to claim 1, wherein: