JPH04177289A - Route calculation method and route guidance device using the method - Google Patents

Abstract

PURPOSE:To enable an entire path ranging from a destination location to a starting point to be accurately and rapidly determined by a method wherein a stored path and its link cost are utilized as they are to calculate the path. CONSTITUTION:A starting location and a destination location are set by an initial setting means B. Each of closed links including the starting location and the destination location in a lower stage map and containing a road constituting an upper stage map is specified by a path calculation means C, thereby each of one or a plurality of paths connected to the closed link with each of the starting location and the destination location in the lower stage map being applied as a starting point and a finishing point, respectively. This one or a plurality of paths and their link costs are stored in a memory. Then, path calculation is carried out with one or a plurality of paths being a passage while the link costs stored in the upper stage map being used. With such an arrangement, an accurate path calculation in consideration of the path ranging from the destination location to the starting location can be performed and a path calculation time is reduced.

Description

[Detailed Description of the Invention] <Industrial Application Field> The present invention includes information on a departure point and a destination from road map data stored in a road map memory in accordance with settings such as a destination by a driver. This invention relates to a route calculation method for reading road map data of a range and calculating an optimal route from a departure point to a destination based on this road map data and necessary road regulation information, and a route guidance device using the method. be.

<Prior Art> Conventionally, there are route guidance devices that have been developed to display the location, direction, etc. of a vehicle on a screen to facilitate driving in unfamiliar territory or at night.

The above route guidance device is equipped with a display, a direction sensor, a distance sensor, a road map memory, and a computer on the vehicle, and stores direction data input from the direction sensor, mileage data input from the distance sensor, and road map memory. There is a system that detects the vehicle position based on a match with a road pattern, and displays the vehicle position and destination on a display together with a road map.

In this case, the driver is responsible for determining the driving route from the departure point to the destination.

However, recently, it has been proposed that a computer automatically calculates the route from the departure point to the destination according to the destination point setting input by the driver, and displays the route superimposed on the road map. .

The method for calculating the route from the departure point to the destination is as follows:
There is the so-called Dijkstra method (Development research report on emergency vehicle travel guidance system, Japan Traffic Management Technology Association, March 1986, Dfrck Von Vlle
t, “Improved 5hortest
PathAlgorithm for Transpo
Trans-po
rtat4on Research, Vol, 12.
1978) o This method divides a number of routes to be route calculated, sets the divided points as nodes, routes connecting the nodes as links, and sets the node or link closest to the starting point as the starting point. Assuming a tree of links from the start point to the end point, with the node or link closest to the destination as the end point, the link costs of all routes that make up the tree are sequentially added to find the link with the lowest cost to reach the destination. This is a method of calculating columns. Here, the items to be evaluated when calculating the link cost include travel distance, travel time, use of expressways, number of right and left turns, probability of driving on main roads, avoidance of accident-prone areas, and other factors depending on the driver's preference. There are certain items that have been set.

If you calculate a route using this method, you will definitely reach your destination as long as there is a route from your departure point to your destination.

However, in the Dijkstra method, the calculation time increases exponentially as the number of nodes and links in the area to be calculated increases.

Therefore, as the distance from the departure point to the destination increases, the number of nodes and links increases, and the problem of calculation time becomes more prominent.

Therefore, the present applicant has developed a method for route calculation when calculating a route from a node near the departure point to a node near the destination by reading road map data from the road map memory according to the destination setting. We have proposed an in-vehicle navigator using a route calculation method that makes it possible to shorten the time required (Japanese Patent Application No. 1-88441, Takeo Ikeda et al.
3rd Atpanti Symposium on "Automotive Route Guidance System", sponsored by Vehicle Automation Technology Study Group.

(Reference January 1990).

In this route calculation method, road map data is classified into upper and lower layers and filed, and depending on the length of the straight line distance from the departure point to the destination, the route search area of the lower layer,
Alternatively, if you set up a route search area that spans multiple layers, upper and lower, and the route search area is a lower layer, add the link cost from the node near the departure point to the node near the destination in the lower layer. When a route is calculated, and the route search area spans multiple layers above and below, the road map data is searched for the interlayer nodes that connect the lower and upper layers, and in the lower layers, the nodes near the starting point are searched for. In this method, calculations are made from nodes near the destination to interlayer nodes, and routes between interlayer nodes are calculated in upper layers.

According to this method, if the upper hierarchical map is set with roads consisting only of arterial roads (including expressways), the density of links and nodes can be reduced, so the time required to calculate the route of the upper hierarchical map can be reduced. , which in turn can reduce the time required for all route calculations.

<Problems to be Solved by the Invention> By the way, in the above route calculation method, when the route search area spans multiple layers above and below, the interlayer node connecting the lower layer and the upper layer is fixed, and the In this case, the calculation is performed from the node near the starting point to the interlayer node, and from the node near the destination to the interlayer node, and the route between the interlayer nodes is calculated in the upper layer, so the -intercortical node is fixed. Then, calculation continues on the assumption that the interlayer node is always passed through.

However, you may find that another route that does not pass through the interlayer nodes is more optimal than the optimal route that passes through the interlayer nodes, which is obtained by actually performing route calculations.

Considering why this situation occurs, in the route calculation method described above, multiple interlayer nodes are searched from the road map data of the lower layer to find the interlayer node that connects the lower layer and the upper layer. Search for candidates, fix the interlayer node that can be reached fastest from the starting point or destination, and
- This is because when an intercortical node is fixed, all the history leading up to the determination of that interlayer node is erased, and a new route calculation is started using that interlayer node as the starting point. Although this interlayer node determination process appears to be reasonable, it has the following problems.

The starting point of the vehicle in the lower layer is O1. The interlayer node that can be reached from the starting point O with the least cost is Pl, and in the process of calculating a new route from node Pi in the upper layer, it passes through another interlayer node P2. Suppose there is a route.

In the technology of the above-mentioned prior application, the link cost of the route passing through the starting point 〇 - interlayer node pt - interlayer node P2 is known, but
The link cost of the route directly passing through the interlayer node P2 from the departure point O is not known, and the same route cannot be compared and evaluated.

This is because even if there is a route for which the link cost was calculated in a lower hierarchy from the starting point O to the interlayer node P2, the record is erased at the stage when the route from the starting point O to the interlayer node Pi is determined as the optimal route. Because there should be.

However, depending on the direction in which the destination is located, it is conceivable that the route from the departure point O directly to the interlayer node P2 may ultimately result in lower link costs. This is because when determining the interlayer node Pi, it is determined based on which interlayer node in the upper layer can be reached from the starting point O with the least cost, and at that time, the relative positional relationship with the destination is That's because they hadn't considered it at all.

The present invention has been made in view of the above problems, and reads road map data from a road map memory in accordance with the settings of the destination etc. by the driver, and calculates the optimal route from the departure point to the destination. If the route search area spans multiple layers above and below, the connection point connecting the lower and upper layers is not fixed to one, and the route is calculated while leaving connection point candidates. Accordingly, it is an object of the present invention to provide a route calculation method capable of calculating the most suitable route from a departure point to a destination, and a route guidance device using the same.

Means for Solving the Problems> The route calculation method of the present invention for achieving the above objects is as follows:
Set the departure point and destination, and in the lower layer map,
Identify a closed link consisting of roads that include the starting point and correspond to the roads that constitute the upper layer map, and a closed link that includes the destination and consist of roads that correspond to the roads that constitute the upper layer map. In the map, one or more routes connecting to the closed link are determined with the starting point and destination as the starting point and ending point, respectively, and the link cost of each route is stored, and the above procedure is performed in the upper layer map. In this method, route calculation is performed using each route stored in .

Further, the route guidance device of the present invention, as shown in FIG.
A road map memory A that stores road map data configured by classifying roads into at least two levels, upper and lower, and initial setting means B for setting the departure point, destination, and route calculation conditions desired by the driver. and a route calculation means C that reads road map data from the road map memory A and calculates an optimal route based on this road map data and the route calculation conditions set by the initial setting means B; It has a route display means for superimposing the optimal route and displaying it on the screen, and the route calculation means C includes the starting point in the lower layer map and corresponds to roads forming the upper layer map. Means C1 for setting a route search area surrounded by closed links consisting of roads including a destination, and a route search area including a destination and surrounded by closed links consisting of roads corresponding to roads constituting the upper hierarchical map; In the hierarchical map, means C2 for determining one or more routes connecting to the closed link on each route search area, with the departure point and destination as the starting and ending points, respectively, determined by the means C2. Means C3 for storing the one or more routes and their link costs, respectively, and the upper layer map, use the link costs stored in the means C3 to calculate routes using the one or more routes as passing routes. It includes a means C4 for performing.

According to the route calculation method and route guidance device described above, a starting point and a destination are set, and in a lower hierarchical map, starting from a road that includes the starting point and destination and that corresponds to a road that constitutes the upper hierarchical map. By specifying each closed link, it is possible to determine one or more routes connecting to the closed link in this lower hierarchical map, with the departure point and destination as the starting and ending points, respectively. . The one or more routes and their link costs are then stored.

Next, in the upper layer map, route calculation is performed using the link cost stored in the above procedure and using the above one or more routes as a passing route.

Therefore, the route obtained in the route calculation process on the lower layer map is not necessarily fixed to one, but multiple routes are left.
While using the link cost of each transit route, it is possible to perform accurate route calculations taking into consideration the distance from the destination to the departure point in the upper layer map.

Also, higher-level maps have more links than lower-level maps.
Since the node density is low, the route calculation time is also significantly reduced.

<Embodiments> Hereinafter, embodiments of the present invention will be described in detail based on the accompanying drawings.

The route guidance device implementing the route calculation method of the present invention includes a second
As shown in the figure, a display 1, a console 2, a direction sensor 10, a distance sensor 9, and a road map memo 1J3A that stores road map data consisting of upper layer map data and lower layer map data. , a calculation process memory 3B that stores the route calculation process in the lower layer map, and each memory 3A.

A memory drive 4 that reads stored data from 3B, and a travel distance and direction sensor 1 that is detected by a distance sensor 9.
The amount of change in the running direction detected by 0 is integrated,
A locator 11 detects the vehicle position based on a comparison between this integrated data and the road map data read by the memory drive 4, acquires the calculation process in the lower layer map from the calculation process memory 3B, reads out the road map of a predetermined range, Generation of display data for guiding vehicles, audio output device 1
5 and locator 11 (this processing section 7 functions as a route calculation means), and a main memory that stores display data output from the processing section 7. 8, an output controller 12 that controls the display 1, and an initial setting section 6 that sets initial data input from the console 2.

To explain in more detail, the console 2 consists of a key board (keyboard) that allows you to start and stop the device, move the cursor on the screen, set initial data such as the destination, scroll the road map displayed on the screen, etc. (not shown).

The orientation sensor 10 detects changes in orientation as the vehicle travels, and can use a geomagnetic sensor, a gyro, or the like.

The distance sensor 9 detects the traveling distance based on the speed of the vehicle or the number of rotations of the wheels, and a wheel speed sensor, a vehicle speed sensor, etc. can be used.

The locator 11 calculates travel trajectory data by integrating the distance data detected by the distance sensor 9 and the direction change data detected by the orientation sensor 10, and stores the travel trajectory data and the road map memory 3A. Comparison with road patterns (so-called map matching method,
The vehicle position is detected based on Japanese Unexamined Patent Publication No. 14-58112).

A transparent touch panel 5 is attached to the display 1 on a screen such as a CRT or liquid crystal panel.

Each of the memories 3A and 3B is a CD-1 which is a mass storage medium.
? It consists of memory such as ON, IC memory card, and magnetic tape.

The road map memory 3A divides a road map (including national expressways, expressways, general national roads, major local roads, general prefectural roads, general city roads of designated cities, and other community roads) into mesh shapes. , road map data consisting of a combination of nodes and links in each mesh unit is divided into trunk roads (
High-level maps that include data on national expressways, expressways, private roads, general national roads, and major local roads), as well as arterial roads as well as non-arterial roads such as general prefectural roads, general city roads in designated cities, and other community roads. (hereinafter referred to as "-general roads") are stored separately from lower hierarchical maps that also include data.

Here, a node generally refers to a coordinate position for specifying a branch point or turning point of a road, and a node representing a branch point is called a turning point node, and a turning point of a road (excluding branch points).
The node that represents this is sometimes called an interpolation point node. The node data includes a node number, an address of an adjacent mesh node corresponding to the node, an address of a link connected to the node, and the like.

A link is a connection between branch nodes.

The link data includes the link number, the addresses of the start and end nodes of the link, the distance of the link, the direction of passing through the link, the time required in that direction, the road type,
It consists of traffic regulation data such as road width, one-way streets, and toll roads.

The calculation process memory 3B is a memory in which initial data is set by the initial setting section 6 and stores a part of the calculation process in which the optimum route is determined in the lower hierarchical map by the processing section 7.

Next, the initial setting procedure and the optimal route calculation procedure for calculating the optimal route using the calculation process memory 3B will be explained.

The initial setting procedure is as follows. That is, when a road map including a departure point that matches the input conditions is displayed on the screen, the driver scrolls the road map as necessary to search for the destination, and then touches the display position of the destination. The touched position is input to the initial setting section 6. Further, the initial setting unit 6 stores the current position of the vehicle output from the locator 11.

When determining the optimal route from the departure point to the destination, the processing unit 7 sets the departure point node closest to the departure point and the destination node corresponding to the destination based on the information from the initial setting unit 6. .

After the initial settings are input as described above, the processing unit 7 returns to the display map of the starting point and calculates the optimal route.

FIG. 3 exemplifies a road map that is the target of route calculation.

Figure (A) shows an upper layer map M1 consisting only of data on arterial roads (thick roads), and Figure (B) shows a lower layer map M2 of a predetermined range consisting of data on arterial roads and general roads (narrow roads). ing.

Some nodes on the main road in the upper hierarchy map have the same coordinates as nodes on the main road in the lower hierarchy map. These are referred to as interlayer connection notes pl, p2, and p3.

Nodes on the main roads and general roads in the lower layer map (excluding interlayer connection notes) are sl, s2, S3...
It is expressed as

The starting point P is located on the lower hierarchical map M2 and is surrounded by closed links J consisting of main roads. In other words, once the starting point P is determined, the route search area range of the lower hierarchical map M2 is set to be expanded until a closed link of the main roads surrounding the starting point P is established. The reason for setting a closed link surrounding the starting point P in this way is that when calculating the route that becomes the optimal route candidate starting from the starting point P, the candidate route does not expand infinitely and always reaches the main road. This is to ensure that.

When calculating a route, search for the node closest to the departure point P on the lower layer map M2, and use the node S5 as a starting point to calculate the interlayer connection nodes p1. p2. Calculate up to p3. FIG. 4 is a map showing an enlarged view of the route search area of the lower hierarchical map M2, that is, the portion inside the closed link J of FIG. 3(B).

Below, links connecting nodes and link costs evaluated in terms of travel time (minutes) are defined as shown in Table 1. (Leaving space below) Table 1 Table 2 shows the process of calculating the optimal route based on the above conditions.

The calculation process will be explained in detail with reference to FIG. 4 and Table 2.

From the starting point Note S5, proceed along vehicle link G.
Note's 4 appears. The link cost when 2 is the cost 3 of link G. Therefore, the first link in Table 2
Starting point note s5. It is stored as via link G1, arrival note S1, and link cost 3.

Next, it exits from node S4 to node S1 on the main line. The link cost of the route from node s4 through link A is 3+10-13 because the cost of node s4 and the cost of link A can be added. Therefore, as shown in the fifth row of Table 2, the starting point node s4, the via link A, the destination node S1, and the link cost 13 are stored.

If a route from node s4 to link B is selected, the link cost will be 3+8-11. Therefore, as shown in the sixth row of Table 2, the starting point node s4. It is stored as the via link B1, the destination node S2, and the link cost 11.

Thereafter, the route to each node on the trunk line and link cost are found in the same manner.

If the destination node is the same but the routes are different, the one with the lower link cost is given priority. For example, node s6
There are two routes to reach , the link D route and the link E → R route, and the link costs are shown in the third row, respectively.
As you can see from line 10, they are 12 and 19, so link D
Only the route is selected, and the cost of node s6 is set to 12. The route of link E-R that reaches node s6 will not be included in the calculations below (it may be deleted).

Furthermore, there are two routes to reach node p1: the link C→N route and the link DQ route (link E-4R-4
Q's route is not considered as above), but the link cost is 13 as seen from the 8th and 9th lines, respectively.
and 18, so the link C-link N route is selected, and the cost of node 1 is set to 13. That is, in the calculations below, only the link cost of the link C-link N route is used as the route to node p1.

Interlayer connection nodes p1 and p2 found as above
．． Table 3 summarizes the optimal route to reach p3. Table 3 shows the structure of the calculation process memory 3B as it is.

Table 3 As can be seen from Table 3, interlayer connection nodes p1゜p2.
The optimal routes to reach p3 are C-N, respectively.

G-4B-, G-+A→I, and the way to reach the interlayer connection node with the least cost is through link C-N, and it takes 13 minutes to reach the interlayer connection node p1.

Conventionally, when the above-mentioned route C-N reaching the interlayer connection node with the lowest cost is specified, other routes G-B-,
The data related to G-A-1 is erased and the interlayer connection node p1
Using this as a starting point, route calculations were performed on the main line on the upper layer map M1.

However, in this example, the other route G-484K.

All link costs related to G→A→■ are stored and used for route calculation as necessary. This procedure will be explained with reference to FIG.

FIG. 5 is a road map when route calculation is performed for trunk lines on the upper layer map M1. Interlayer connection node pl
, p2. A route to the destination is calculated using p3 as a starting point. It is assumed that the destination exists in the lower right direction of node p2 in FIG.

However, links and link costs are defined as shown in Table 4.

As shown in Table 4, in the conventional method, as described above, the route was calculated using the interlayer connection node p1 as the starting point. the result,
The optimal route starts from the starting point P and passes through the node p1,
It was likely to proceed to node p2 via the main road.

Or should I go directly to notebook p2 from departure point P?
Compared to going to node p2 via node p1,
It should be possible to go there in a short time.

To go directly from the starting point P to node p2, from Table 3,
14 minutes, whereas it takes 13 minutes to go from the starting point P to node p1 and 12 minutes to go from node p1 to node p2 (the cost in the reverse direction of link N is 7 +
Add the cost of link M by 2 + the cost of link by 3 - 12 degrees, and assume that the cost is the same even if the two directions of the link are different. ) takes a total of 25 minutes.

As described above, in the conventional method, when considered comprehensively, a route with a higher link cost may be selected.

To overcome this drawback, in this embodiment, the interlayer connection node pl is used to reach the destination.

p2. Route calculation is restarted as shown in Table 5, with p3 as a passing point.

Table 5 The calculation process will be explained in detail with reference to Table 5.

If the passing point node is pl, the link cost of the destination node p2 is 25 by adding the cost 12 of link T to the link cost 13 (see Table 3) of the passing point node p1.
is required. Furthermore, if the passing point node is p3, the link cost 18 (see Table 3) of the passing point node p3 is added to the cost 10 of the link U, and the reached node p2 is
The link cost of is calculated as 28. On the other hand, since the link cost of the destination node p2 is 14 (see Table 3), it can be seen that the optimal route is the route that goes directly from the starting point P to the interlayer connection node p2. Therefore, in the following route calculation using the link V, etc., the link cost of the reached note p2 is set to 14, and the calculation proceeds.

As mentioned above, by storing the route calculation process in the lower layer map in the form shown in Table 3, and calculating the route using multiple interlayer connection nodes as passing point nodes, the route calculation process in the upper layer map can be calculated as shown in Table 3. It is possible to obtain an accurate optimal route from the departure point to the destination by calculating the route in consideration of the relative positional relationship with the destination.

FIG. 6 is a diagram showing a route guidance flow for guiding a vehicle along an optimal route. In step S1, a display map within the area to be displayed centered on the current position of the vehicle is obtained from the road map memory 3A, and in step S2, the display map is drawn on the frame memory according to a predetermined enlargement ratio. Then, in step S3, the calculation process memory 3
Data on interlayer connection nodes is obtained from B using the procedure described above, and an optimal route is calculated. This calculation may be performed before the vehicle starts (or may be performed while the vehicle is running, using the waiting time at an intersection.

In step S4, it is checked whether the optimal route to be displayed has been acquired, and if the optimal route has not been acquired (as described above, the route search area for obtaining closed links has become too large, (This occurs when the calculation time becomes too long), the process proceeds to step S7, where only the current position mark of the vehicle is drawn on the frame memory, and the contents of the frame memory are displayed on the display in step S8.

If the optimal route to be displayed has been determined in step S4, the optimal route is drawn as a link string or the like on the currently drawn road display map in step S5. Then, in step S6, the optimal route is displayed along the road using the direction vector.

Note that the present invention is not limited to the above embodiments. For example, in the embodiment, an example of route calculation near the departure point has been shown, or when calculating a route near the destination, the same procedure can be used starting from the destination.

In addition, a node may be used as the starting point for route calculation, or a link may be used. This is because, as described above, the link data includes the addresses of the start point node and end point node of the link, so the point can be specified by the link alone. Furthermore, since the link data includes the direction in which the vehicle passes through the link, it is convenient to specify the direction in which the vehicle is traveling by specifying one link.

Various design changes can be made without changing the gist of the invention.

<Effects of the Invention> As described above, according to the route calculation method of the present invention, when a route calculated on a lower hierarchy map is stored and a route is calculated on an upper hierarchy map, the stored route and its link cost are By using it as is, it becomes possible to more accurately and quickly determine the entire route from the destination to the departure point as a series.

In the route guidance device of the present invention, by using the above method, the optimal route can be shown to the driver, the vehicle can be appropriately guided, and smooth driving can be achieved.

[Brief explanation of the drawing]

Fig. 1 is a functional block diagram showing the configuration of the route guidance device of the present invention, Fig. 2 is a block diagram of the route guidance device of the present invention, and Fig. 3 is a road map with a hierarchical structure exemplified as a target for optimal route calculation. , FIG. 4 is a detailed diagram of the lower layer map, FIG. 5 is a detailed diagram of the upper layer map, and FIG. 6 is a flowchart showing the optimal route display routine. 1...Display device, 3A...Road map memory, 3B...Calculation process memory, 6...Initial setting section, 7...Processing section Patent applicant Sumitomo Electric Industries, Ltd.

Claims (1)

[Claims] 1. A method for calculating an optimal route from a departure point to a destination by using road map data configured by classifying road maps into at least two levels, upper and lower, which includes the following (1):
A route calculation method characterized by following the steps of (4). (1) Set the departure point and destination. (2) In a lower layer map, a closed link consisting of roads that correspond to the roads that make up the upper layer map includes the starting point, and a closed link that includes the starting point and consists of roads that correspond to the roads that make up the upper layer map. Identify each of the following: (3) In the lower hierarchical map, one or more routes connecting to the closed link are determined with the departure point and destination as the starting and ending points, respectively, and each route and its link cost are stored. (4) Perform route calculation on the upper layer map using each route stored in step (3) above as a passing route. 2. Road map memory (A) that stores road map data configured by classifying roads into at least two levels, upper and lower.
an initial setting means (B) for setting a destination and route calculation conditions desired by the driver; and an initial setting means (B) for reading out road map data from the road map memory (A), and reading the road map data and the initial setting means ( A route calculation means (C) that calculates the optimal route from the departure point to the destination based on the route calculation conditions set by B), and a route that superimposes the optimal route on a road display map and displays it on the screen. and a display means (D), and the route calculation means (C) includes a starting point on the lower layer map and is surrounded by closed links consisting of roads corresponding to roads constituting the upper layer map. Means (C1) for setting a route search area including a destination and a route search area surrounded by closed links consisting of roads corresponding to roads constituting the upper layer map; and a means (C2) for determining one or more routes connecting to the closed link on each route search area, with the destination as the point and the end point, respectively; means (C3) for storing one or more routes and their link costs, and means (C4) for calculating a route using each route stored in the above means (C3) as a passing route in the upper layer map. A route guidance device using a route calculation method, characterized by: