JPH08261771A - Route-searching apparatus - Google Patents

Abstract

PURPOSE: To realize a highly practical search for routes by properly performing weighting reflected to a running speed on roads. CONSTITUTION: A route set through an input part 13a from a starting point, to a target, point is searched for by combining roads so that a relay point set at a starting point-setting part 35 is passed and the route cost becomes minimum. The route cost, is reflected on weighting when the route is searched for by extracting road inclinations or an attribute of a road is an expressway or urban highway, etc., from data included in a map data 12a.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a route search device which can be used as a function of a navigation system for guiding a user to a destination by displaying a map and the position of a vehicle on a display.

[0002]

2. Description of the Related Art As a vehicle-mounted navigator device, for example, the prior art disclosed in Japanese Unexamined Patent Publication No. 1-134209 determines whether or not the vehicle position is on a traveling route that is also set by using altitude information. The configuration for determining is disclosed. By receiving radio waves from a plurality of GPS satellites and detecting phase differences and the like, not only the position of the own vehicle can be detected two-dimensionally, but also altitude information can be detected together. By using such altitude information, it is possible to distinguish an elevated road from a road passing thereunder.

Reference data for comparing altitude information, which is also detected when detecting the position of the vehicle, is extracted from the data related to the altitude included in the map data along the traveling route of the vehicle. As a basic method for searching a route,
The Dijkstra method is known and is a method for searching for a mathematical shortest path. In this method, a combination of a link that is a road and a node that is an intersection is selected from the start point node that is the starting point to the end point node that is the destination, and the combination that results in the shortest route cost corresponding to the length of the node is selected. Ask for.

The purpose of searching for a route is often to minimize the arrival time, and depending on road conditions, it may take time even if the distance is short. Therefore, the route cost is calculated using the road attribute as shown in the first equation.

Cost = g (atr) * h (wid) * len + i (ang) (1) Here, Cost is a route cost, atr is a road type, and g (atr) is a weight for the road type. This is the function to be calculated, wid is the road width, and h (wid)
Is a function for obtaining a weight for a road width, ang is a turning angle, and i (ang) is a function for obtaining a weight for a turning angle. In the first expression, g (atr) * h
If (wid) is the reciprocal of speed and i (ang) is time, Cost is the estimated time required from the road attribute, and the shortest time route can be obtained by the route search using the first expression.

[0006]

DISCLOSURE OF THE INVENTION Problems to be Solved by the Invention
The prior art of Japanese Patent No. 9 does not use altitude information at the time of route search. However, the traveling speed of the vehicle is greatly influenced by not only the type of road, the width and the angle of the corner, but also the gradient. In the first expression, the same route cost will be calculated regardless of the road gradient. In reality, the larger the gradient is, the longer it takes.

An object of the present invention is to provide a route search device capable of evaluating the influence of a gradient when calculating a route cost and realizing a route search function having higher practicality.

[0008]

SUMMARY OF THE INVENTION The present invention is an apparatus for searching a combination of roads having a minimum route cost between two points as a route by referring to previously recorded road map data. It is characterized by including gradient extraction means for extracting gradient information of roads forming a route, and weight setting means for weighting route costs at the time of route search according to the gradient information extracted by the gradient extraction means for each road. Is a route search device. Further, the gradient extracting means of the present invention is characterized in that gradient information of each road is extracted from an altitude difference and a distance between both ends of each road. Further, the simulation setting means of the present invention is characterized in that weighting is performed so that the steeper the gradient of the road extracted by the gradient extracting means, the greater the route cost. Further, the weight setting means of the present invention is characterized by performing weighting so that the route cost becomes higher when the road gradient is ascending than when it is descending. Furthermore, the present invention refers to pre-recorded road map data, and in a device that searches for a combination of roads that minimizes the route cost between two points as a route, the roads that form the route from the road map data are highways. Attribute extraction means for extracting an attribute indicating that there is a toll road or an elevated road, and for each road, when the attribute extracted by the attribute extraction means represents a toll road and an elevated road, and the attribute is high speed A route search device characterized by including weight setting means for performing similar weighting when representing a road. Further, when the attribute extracting means of the present invention extracts an attribute indicating that it is an urban expressway or is an expressway and an elevated road, the weight detecting means performs weighting as an urban expressway. And

[0009]

According to the present invention, the gradient extracting means extracts the road gradient information from the road map data for each road. The weight setting means weights the road cost at the time of route search according to the road gradient information extracted by the gradient extracting means. Since the route search is performed based on the route cost weighted according to the gradient information, it is possible to perform a highly practical route search by reflecting the road gradient.

According to the invention, the gradient extracting means extracts the gradient information of each road from the altitude difference and the distance between both ends of each road. Thereby, the road gradient information can be extracted even by using the road data that does not include the gradient information for each road.

Further, according to the present invention, the weight setting means performs the weighting so that the route cost increases as the gradient of the road becomes steeper, so that it is possible to perform an appropriate route search sufficiently considering the gradient of the road. it can. That is, the steeper the slope, the greater the load on the engine and the lower the speed. Also, the steeper the downhill slope, the stronger the brakes will have to be operated and the vehicle will have to travel at a lower speed for safety. A more appropriate route search can be performed by reflecting such circumstances.

Further, according to the present invention, weighting is performed so that the route cost is higher when the gradient is ascending than when it is descending. Since it is particularly difficult to increase the speed on an uphill slope, it is possible to perform a route search that appropriately reflects this situation.

Further, according to the present invention, the highway or the toll road and the elevated road are regarded as the highway, and the weighting is similarly performed. From the viewpoint of the shortest time route, it is necessary to search the route for the expressway so as to pass through as much as possible.
Even for road map data that does not have a highway as an attribute of road information, if it has the attributes of a toll road and an elevated road, it will become relatively straightforward in recent years and as close as possible to a straight line. Is determined to be a road constructed in
It is possible to obtain a more appropriate route search result by judging it as a highway.

Further, according to the present invention, when the attribute extraction means extracts an attribute indicating that it is a highway and an elevated road,
The weight setting means weights the city expressway.
The weight setting means naturally weights the city expressway when the attribute extracting means extracts the attribute representing the city expressway. Even if road map data that does not have road attributes as an urban expressway is used, it is possible to search for a route by giving appropriate weights as an urban expressway.

[0015]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS FIG. 1 shows a schematic electrical structure of a navigation device which is a vehicle route guidance device according to an embodiment of the present invention. The route search guidance device 10 includes a vehicle position detection device 1
Data indicating the vehicle position from 1 and road map data from the recording device 12 are given. From the input device 13,
A starting point, a destination point of the vehicle, an intermediate point on the way, and a guidance point for further guidance are set.
From the output device 14, along the route searched by the route search guide device 10, a road map formed by referring to the recording device 12, a guide by image display, and a guide by voice output are provided.

A CPU 20 is included in the route search guidance device 10, and refers to the main memory 21 to perform an operation for assisting a driver of a vehicle according to a preset program. The main memory 21 includes RAM and ROM, and CP
It is used as a work area or program memory when the U20 performs a program operation. The recording device 12 is
For example, it is a recording medium or a recording device such as a CD-ROM, an IC card, or a hard disk, and mainly stores road map data for display.

The vehicle position detecting device 11 includes a GPS receiving device 22, a distance sensor 23, an azimuth sensor 24 and the like. The GPS receiver 22 receives radio waves from GPS satellites 25, and uses the Global Positioning System (Global Positioning System).
ng System) to detect the current position of the vehicle as a whole. The distance sensor 23 and the direction sensor 24 are used to relatively detect a change from the starting position to the current position of the vehicle. As for the current position of the vehicle detected by such a method, an error is unavoidable due to various factors, and the vehicle position with higher accuracy is obtained by performing map matching with the road map information recorded in the recording device 12. May be modified as.

In the output device 14, a cathode ray tube (CRT)
An image display device 26 including a display device such as a liquid crystal display element (LCD) and a sound reproducing device 27 for guiding a guidance point by voice are included.

In the vehicle position detecting device 11, the GPS receiving device 22 can also observe the Doppler shift of the radio waves from the GPS satellites 25 to obtain the moving distance and direction of the vehicle. Further, as the distance sensor 23, the traveling distance can be obtained by integrating the traveling speed of the vehicle detected by the vehicle speed sensor. The orientation sensor 24 is realized by any one of a geomagnetic sensor, a vibration gyro, an optical fiber gyro, a gas rate sensor, or a combination thereof.

FIG. 2 shows the functions realized by the electrical configuration of FIG. The route search guidance device 10 in FIG. 1 functions as a route search device 30 and a route guidance device 31.
The route search device 30 includes a point setting unit 35, a route search unit 36, and a search result output unit 37. The route search device 30 is provided with input data such as a departure point, a destination point, and a guidance point of the vehicle from the input unit 13a realized by the input device 13 of FIG. 1 before the vehicle travels. The input guide point is set in the point setting unit 35 in the route search device 30. The route search unit 36 refers to the map data 12a recorded in the recording device 12 of FIG. 1 to search for a travel route including the guide point. The searched search result is derived from the search result output unit 37 and displayed by the output unit 14a realized by the recording device 12 of FIG.

FIG. 3 shows the contents of data recorded as the map data 12a in FIG. FIG. 3 (1) shows a state in which data is expanded and displayed, and FIG. 3 (2) shows a recorded data structure. The digital road map shown in FIG. 4 (1) expresses the road as a combination of nodes and links as shown in FIG. 4 (2). Figure 3 (1)
The nodes 30 to 37 and the links 40 to 45 configuring the digital road map of No. 3 have the node attributes and the link attributes shown in FIG. 3B, respectively. As a node attribute,
"Number of connections", which is the number of links to connect, "Intersection name",
The contents of "traffic regulation" and "altitude" are included. The link attributes include "link length", "road type", "width", "traffic regulation", "road gradient", "overpass flag" indicating an elevated road, and a toll road "Pay flag" etc. are included. The road gradient is also stored in the digital road map as one of the link attributes and is read together with other road attributes such as the link length and the road type at the time of route search.

The following second equation is a relational equation for calculating the route cost by adding the function j (x) for obtaining the weight for the road gradient to the above-mentioned first equation.

Cost = g (atr) * h (wid) * j (ang2) * len + i (ang1) (2) Here, ang1 indicates a bending angle like ang in the first equation, and ang2 indicates a road gradient. Shown in angles. In the second equation, g
If (atr) * h (wid) * j (ang2) is the reciprocal of the speed, Cost is the time required for estimation. If you choose a route that minimizes the time required for this estimation,
The shortest route search is performed.

FIG. 4 shows an example of the function j (ang2). When the gradient is 0 to the downward gradient, the same weight is used, but in the upward direction, the larger the gradient, the greater the weight. If this is applied to the second equation, the route cost will increase as the uphill gradient increases.

When the road gradient is not stored in the link attribute shown in FIG. 3B or when the road gradient is not included in the link attribute of FIG. 3B from the beginning, the altitude of the node attribute is set. If (elevation) data is stored, the road gradient can be obtained using it. When performing positioning using GPS, the altitude for the area indicated by the road data may be stored as a node attribute for error correction during two-dimensional positioning.

FIG. 5 shows the concept of calculating the road gradient using the altitude data in the node attributes. Using the altitude difference, which is the difference in altitude data between the start point node and the end point node of the link whose route cost is considered, and the link length, the road gradient θ is calculated as in the following third formula. be able to.

[0027]

[Equation 1]

Assuming that the altitude difference is positive (+) for uphill and negative (-) for downhill, if the direction of the route to be obtained is from the start point node to the end point node, altitude difference = end point node-start point node (4) When the direction of the route to be obtained is from the end point node to the start point node, the altitude difference is: start point node-end point node (5).

FIG. 6 shows a second embodiment of the present invention shown in FIG.
The operation when the route search device 30 described above performs weighting in consideration of road attributes. Here, the "highway" has a speed limit of 80 to 80, such as "Tomei Expressway" and "Meishin Expressway".
The expressway is 100 km, and the "city expressway" is a motorway with a speed limit of less than 60 km, such as "capital expressway" or "Hanshin expressway". And toll roads.
If there is no data format corresponding to "Expressway" or "Urban Expressway" as the road type on the digital road map, when calculating the route cost by weighting with the road type, Such problems occur. If the highway is regarded as a toll road, the route cost will be greatly calculated. If the urban expressway is regarded as a toll road, the route cost will be greatly calculated.

FIG. 6 shows a process of weighting by using the elevated flag and the toll flag in the link attributes of FIG. 3 (2) as if they were “highways”. The elevated flag is 0
A normal road is shown when, and an elevated road is shown when 1. The toll flag indicates that the toll road is free when it is 0, and indicates that it is a toll road when it is 1.

The operation starts from step a1 in FIG. 6, and in step a2, the link attribute in FIG. 3 (2) is read. The value of the pay flag is substituted for the parameter a, the value of the elevated flag is substituted for the parameter b, and the parameter len
Substitutes the value of the link length. In step a3, a = 1
It is judged whether or not the pay is indicated by and the overpass is indicated by b = 1. When the condition is satisfied, the process proceeds to step a4, and the value of 2 representing the expressway is substituted for the parameter a. When step a4 ends, or step a
When it is determined that the condition is not satisfied in step 3, the process proceeds to step a5, the route cost C is set to the weighting function f (a), and the link length le is set.
Substitute the value obtained by multiplying n. When the route cost C is calculated in step a5, the process ends in step a6. The weighting function f is expressed as the following sixth equation.

If w = f (x), then if x = high speed then w = K / 80 if x = paid then w = K / 40 (6) if x = other then w = K / 30 FIG. The processing when the road attributes are further finely classified and weighted as compared with FIG. 6 will be described. When there is no data format corresponding to "city expressway" in the road type of the digital road map as shown in FIG. 3 (2), when the route search for calculating the route cost by the road type is performed, the following problems occur. Occurs. If the "city highway" is regarded as a "highway", the route cost will be calculated small. If the "city expressway" is regarded as a "toll road", the route cost will be greatly calculated.

Therefore, the process is started from step b1,
In step b2, the link characteristics are read, and the road type, the elevated flag, and the link length are assigned to the parameters a, b, and len, respectively. In step b3, it is determined whether or not the road type of a is a highway and the elevated flag of b is 1 indicating that it is an elevated road. When the condition is satisfied, the process proceeds to step b4, and the data indicating that the road type is "city highway" is substituted. When step b4 ends, or when the condition is not satisfied in step b3, the process moves to step b5 and the route cost C
Is calculated, and the process ends in step b6. Step b
The weighting function f with respect to the road type of 5 is expressed as the following seventh expression.

When w = f (x), if x = high speed then w = K / 80 if x = urban high speed then w = K / 60 if x = toll then w = K / 40 (7) if x = National road then w = K / 30 if x = Prefectural road then w = K / 30 if x = Other then thew = K / 20 A more practical route search will be performed by weighting according to the detailed road type as shown in Formula 7. be able to.

If the weighting by the road gradient represented by the second equation is further added to the processing of FIG. 6 or FIG. 7, it is possible to carry out the route search which is more effective as the shortest time.

[0036]

As described above, according to the present invention, the route cost can be calculated in consideration of the gradient of the road, and the route can be searched so as to minimize the route cost. As a result, a more appropriate route search result can be obtained.

Further, according to the present invention, the gradient extracting means can extract road gradient information from road data having no road gradient information based on the altitude difference between both ends and the distance.

Further, according to the present invention, since the route cost is calculated by weighting so that the weight becomes larger as the gradient of the road becomes steeper, it is possible to search for a more practical route.

Further, according to the present invention, since the route search is performed with a greater weight when the road gradient is ascending than when it is descending, a more practical search result can be obtained.

Further, according to the present invention, even if road map data having no highway attribute is used, a road having a toll attribute and an elevated attribute is determined to be a highway, and weighting similar to that having a highway attribute is performed. And more appropriate search results can be obtained.

Further, according to the present invention, even if the road map data having no urban expressway attribute is used, the road having the toll attribute and the elevated attribute is determined to be the urban expressway, and the route cost is weighted. An appropriate route search result can be obtained.

[Brief description of drawings]

FIG. 1 is a block diagram showing a schematic electrical configuration of an embodiment of the present invention.

FIG. 2 is a block diagram showing a functional configuration of the embodiment shown in FIG.

3A and 3B are a schematic diagram and a data structure diagram showing the contents of a digital road map recorded as the map data 12a in FIG.

FIG. 4 is a graph showing an example of a weighting function for a road gradient.

FIG. 5 is a schematic diagram showing the concept of performing gradient calculation using altitude data.

FIG. 6 is a flowchart showing the operation of the route search device according to another embodiment of the present invention.

FIG. 7 is a flowchart showing an operation of a route search device according to still another embodiment of the present invention.

[Explanation of symbols]

 10 Route Search Guide Device 11 Vehicle Position Detecting Device 12 Recording Device 12a Map Data 13 Input Device 14 Output Device 20 CPU 21 Main Memory 22 GPS Receiver 23 Distance Sensor 24 Direction Sensor 25 GPS Satellite 26 Image Display Device 30-37 Node 40 ~ 45 links

Claims (6)

[Claims] 1. An apparatus for searching a combination of roads having a minimum route cost between two points as a route by referring to pre-recorded road map data, and gradient information of roads constituting the route from the road map data. And a weight setting means for weighting the route cost at the time of route search according to the gradient information extracted by the gradient extraction means for each road. 2. The route search device according to claim 1, wherein the gradient extraction means extracts gradient information of each road from an altitude difference and a distance between both ends of each road. 3. The route search according to claim 1, wherein the simulation setting unit weights the route cost so that the steeper the gradient of the road extracted by the gradient extracting unit, the greater the route cost. apparatus. 4. The weight setting means performs the weighting so that the route cost is higher when the road slope is uphill than when it is downhill.
3. The route search device according to any one of 3 above. 5. An apparatus for searching a combination of roads having a minimum route cost between two points as a route with reference to pre-recorded road map data, wherein roads forming a route from the road map data are highways. Or an attribute extraction unit that extracts an attribute that indicates that the road is a toll road and an elevated road, and for each road, when the attribute extracted by the attribute extraction unit represents a toll road and an elevated road, and A route search device comprising weight setting means for performing similar weighting when representing an expressway. 6. When the attribute extracting means extracts an attribute representing that it is an urban highway or is an expressway and an elevated road, the weight detecting means performs weighting as an urban highway. The route search device according to claim 5, which is characterized in that.