JPH04177290A - Optimum path calculation device - Google Patents

Abstract

PURPOSE:To rapidly decide the optimum path up to a final destination location by a method wherein a passing location where a calculated optimum path is stored in a passing location table in correspondence with a pair of each of path starting points and each of destination points or a pair of each of starting points and a path destination. CONSTITUTION:A destination location is set through an operation of a driver and a specified location near the present position of a vehicle is set as a path starting point. Then, a passing location getting means 7 calculates in advance the optimum path reaching each of destination locations with each of the specified locations being applied as a path starting point and one or a plurality of passing locations through which the optimum path passes are corresponded to the specified location acting as the destination location and the path starting location and stored as a passing location table. The table is retrieved through a memory drive 4 and then a passing location ranging from the specified location acting as the path starting point to the destination location is obtained. With such an arrangement, even if the destination location is positioned at a remote location, path calculation can be performed within a short period of time and the optimum path can be obtained rapidly.

Description

[Detailed Description of the Invention] <Industrial Application Field> The present invention provides the
Optimal route calculation that reads out road map data for a range including a starting point and a destination point from the road map data stored in the road map memory, and calculates an optimal route from the starting point to the destination point based on this road map data. It is related to the device.

<Prior Art> Conventionally, route guidance devices have been known that have been developed to display the position and orientation of a vehicle on a screen to facilitate driving in unfamiliar territory or at night.

The route guidance device described above is equipped with a display, a direction sensor, a distance sensor, a road map memory, and a computer on a vehicle, and receives direction data manually inputted from the direction sensor, mileage data inputted from the distance sensor, and road map memory. The vehicle position is detected based on the match with the road pattern stored in the system, and the vehicle position and destination point are displayed on the display together with the road map.

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

However, in recent years, computers have been able to automatically calculate the route from the departure point to the destination point according to the destination point input by the driver, and display the route superimposed on the road map before or while driving. It is proposed to do so.

The so-called Dijkstra method is a method for calculating the route from the starting point to the destination point (Development research report on emergency vehicle travel guidance system, Japan Traffic Management Technology Association, March 1986, Dirck Von Vli).
et, “Ia+proved 5hortest P
athAlgorittv for Transport
tation Network'', Trans-po
ration Research, Vol. 12.
1978) o This method divides a number of routes to be 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, sequentially add the link costs of all routes that make up the tree, -, and calculate the highest link cost to reach the destination point. This is a method to calculate a route with less. Things to consider when estimating 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 preferences. There are some settings that have been made.

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

<Problem to be solved by the invention> However, in the Dijkstra method described above, the calculation time is determined depending on the number of nodes and the number of links in the area to be calculated. ,If there are many links, the computation time increases,exponentially.

Therefore, the driver has to wait patiently from the time the destination is set until the optimal route is calculated, especially if the destination is far away, which poses a problem in practicality when in a hurry.

The present invention has been made in view of the above problem, and when calculating a route from a starting point to a destination point by reading road map data from a road map memory according to the destination point setting by the driver, To provide an optimal route calculation device capable of calculating a route in a short time even if the destination is far away and quickly obtaining an optimal route.

<Means for Solving the Problems> To achieve the above object, the optimal route calculation device of the present invention selects a plurality of specific points from among the points constituting road map data according to a certain standard. The optimal route to each destination point is calculated in advance using each specific point as the route starting point, and one or more passing points along this optimal route are associated with the destination point and the specific point that is the starting point of the route. an initial setting means for setting a destination point and a specific point near the current position of the vehicle; When calculating a route from a specific point serving as a route starting point to a destination point, the method is divided into sections for each passing point acquired by the passing point obtaining means. (Claim 1).

The above destination point may be selected from all the points that make up the road map data, or may be selected from several points set based on certain standards, corresponding to the destinations that the driver often travels to. It may be something that can be used.

Preferably, the specific point is selected from the main points on the road map, or may correspond to all points on the road map.

The optimal route calculation device described above uses each specific point as the route starting point and calculates the route to each destination point, but conversely, it can also calculate the route from each starting point with a specific point as the route end point. Good (Claim 2). In this case, the starting point may be selected from all the points constituting the road map data, or may be selected from one or several points corresponding to the permanent parking location of the vehicle.

Further, the road map data may be composed of a combination of nodes and links, and points on the road map may be specified by nodes or links (Claim 3).
.

Further, the passing point table may store the passing point only when the distance between the destination point and the departure point is longer than a certain reference value (claim 4).

According to the optimal route calculation device of claim 1, when a destination point is set by a driver's operation or the like and a specific point close to the current position of the vehicle is set as a route starting point, the passing point obtaining means can retrieve the passing points from the specific point serving as the starting point of the route to the destination by searching the passing point table.

This passing point follows the optimal route to the destination point, so
The route calculation means can divide and calculate the route from the specific point serving as the route starting point to this passing point, the route between passing points, and the route from the passing point to the destination point.

According to the optimal route calculation device of claim 2, when a destination is set by the driver's operation and a specific point near the destination is set as the route end point, the passing point acquisition means By searching the point table, it is possible to obtain the passing points from the starting point corresponding to the current location of the vehicle to the specific point serving as the end point of the route.

This passing point follows the optimal route to the end point of the route, so
The route calculation means calculates a route from the departure point to the passing point,
The route between passing points and the route from a passing point to a specific route end point can be divided and calculated.

Therefore, in either of the apparatuses according to claim 1 or 2, a route that would normally span a long distance is divided into short-distance routes, and calculation time can be dramatically reduced.

Further, as described in claim 4, by storing the passing point in the passing point table only when the distance between the destination point and the starting point is longer than a certain reference value,
When the starting point and destination are relatively close, the memory capacity of the passing point table can be saved by directly calculating the optimal route without using the passing point table.

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

The optimal route calculation device of this embodiment is incorporated into a route guidance device that guides a vehicle by displaying an optimal route on a screen or outputting audio.

The above-mentioned optimal route calculation device calculates the route to each destination point with each specific point as the route starting point, or conversely, calculates the route from each starting point with a specific point as the route end point. It may be. In this case, the contents of the process can be deduced by analogy by exchanging the starting point and the destination point, and the route starting point and the route ending point. Once, below,
Only an embodiment in which the route to each destination point is calculated using each specific point as the route starting point will be described.

As shown in FIG. 1, the route guidance device includes a display 1, a console 2, a direction sensor 10, a distance sensor 9, a road map memory 3A storing road map data, and a passing point table. The stored passing point memory 3B, the memory drive 4 that reads stored data from each memory 3A, 3B, the travel distance detected by the distance sensor 9, and the amount of change in the travel direction detected by the direction sensor 10 are integrated, respectively, 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, and a locator 11 for searching and acquiring passing points, reading a road map of a predetermined range, and guiding the vehicle. Generation of display data, control of the audio output device 15, and locator 1
A processing section 7 (this processing section 7 also functions as a passing point acquisition means) that performs various controls such as control 1, a main memory 8 that stores display data output from the processing section 7, and a display It has an output controller 12 that controls the device 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 (key board) that allows you to start and stop the device, move the cursor on the screen, set initial data such as destination points, scroll the road map displayed on the screen, etc. (not shown).

The orientation sensor 10 detects changes in orientation as the vehicle travels, and may 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 can be a wheel speed sensor, a vehicle speed sensor, or the like.

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 Patent Application Laid-Open No. 84-53112).

Note that a beacon receiver or a GPS receiver may be added to improve the accuracy of position detection.

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

Each of the memories 3A and 3B is a CD-R which is a large capacity storage medium.
It consists of memory such as OM, IC memory card, and magnetic tape.

The road map memory 3A stores road maps (highway national highways, urban expressways, general national roads, major local roads, - general prefectural roads,
(including general city roads and other community roads in designated cities) is divided into meshes, and data combining nodes and links is stored in each mesh. Other information includes railways, rivers, place names, famous facilities, points registered in advance by the driver, and contour lines.

may include background data for display.

The above mesh is based on the Japanese road map with a longitude difference of 1 degree and a latitude difference of 4 degrees.
Divide by 0 minutes and make the vertical and horizontal distance approximately 80 × 80KIIl
The first mesh is 8 in length and width.
It has a double structure with a secondary mesh (see Fig. 2) which is divided into equal parts and has a vertical and horizontal distance of about 10KliXl0Kn.

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

Links connect 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.

In this way, since the link data includes the addresses of the start point node and end point node of the link, it is possible to specify a point using only the link. Note that when a link specifies the starting point of a link, the link is referred to as an "exit link," and when the end point of the link is identified, the link is referred to as an "entering link." Furthermore, since the link data includes the direction in which the vehicle passes through the links, by specifying one link, the direction in which the vehicle is traveling can also be specified. FIG. 3 illustrates four exit links that specify a crossroads, and FIG. 4 illustrates four entry links that specify a crossroads.

In the following example, it is assumed that an approach link is used to specify a point.

Passage point memory 3B includes major intersections, leisure facilities,
Route calculation conditions set for optimal routes from specific links corresponding to stations, parking lots, expressway on-ramps, off-ramps, service areas, roadside beacons, etc. to all links corresponding to the destination point. (Shortest time route, shortest distance route, route with fewer left and right turns, route with wide road width, etc.) One or more links constituting a point are stored in association with the specific link and the link corresponding to the destination point.

Furthermore, the structure of the passing point memory 3B will be explained in detail using drawings and tables. FIG. 2 is a diagram showing a primary mesh M1 and an adjacent primary mesh M2.

One of the secondary meshes m1 in the primary mesh M1 has a specific link PO (a specific link closest to the starting point P) indicating the route starting point. Note that specific links are indicated by thick arrows (in the figure, only one specific link is displayed, or in reality there are multiple links).

The secondary meshes adjacent to the secondary mesh m1 are m2 to m9.
and defines the outer boundary B1 of the secondary meshes m2 to m9. A boundary B2 is defined by separating two secondary meshes from the boundary B1. For example, let the secondary mesh immediately inside the boundary B2 be mlO.

Also, the 2 to which the destination Q in the adjacent primary mesh M2 belongs
Let the next mesh be mll. A destination link corresponding to destination Q is expressed as link p3.

The optimal route from the route origin link Po to the destination link p3 is represented. A link on this optimal route that intersects with boundary B1 is designated as pl, and a link on this optimal route that intersects with boundary B2 is designated as p2.

The passing point table stores links pl and p2 on the boundary through which the optimal route passes, corresponding to the route origin link Po and the destination link p3.

An example of the passing point table is shown in Table 1.

Table 1 Destination link p3 Next, the operation of the optimal route calculation device with the above configuration is shown in Figure 2 and Figure 1.
Explain with reference to the table.

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

When determining the optimal route from the starting point P to the destination point Q, the processing unit 7 selects a specific link closest to the starting point P (link P in the case of FIG. 2) based on information from the initial setting unit 6.
O) and a destination link corresponding to the destination point Q.

After the initial settings are input as described above, the processing unit 7 returns to the display map of the starting point P and searches the passing point table stored in the passing point memory 3B.

As already explained using Table 1, the passing point table stores 0 links of passing points through which the optimal route passes, corresponding to the destination link p3.

The processing unit 7 first accesses the route memory 3B through the memory drive 4 and reads out the link strings pi and p2 of passing points corresponding to the destination link p3 and the route starting point link PO. As a result, it is possible to specify passing points on the optimal route with the route starting point link Po as the route starting point.

The processing unit 7 calculates the optimal route in the following three stages.

(1) Calculation from route origin link PO to passing point link p1 (2) Calculation from passing point link p1 to passing point link p2 (3) Calculation from passing point link p2 to destination link p3 The specific calculation is , using the already explained Dijkstra method. In this case, instead of calculating from the route origin link PO to the destination link p3 as described above, it is divided by passing points and calculations are made for each section, which makes it possible to narrow the area subject to calculation. This can dramatically reduce calculation time.

As described above, from route origin link PO to destination link p3
You can get all the route data for the train in a short time.

In the above case, the route from the initial position P of the vehicle to the first specific link Po, which is the route starting link, is usually a short distance, so if the route is calculated using the conventional method, it can be optimally calculated in a relatively short time. You can get directions. If there is no risk of the driver getting lost because it is nearby, it may be possible to point out a specific link Po without calculating the route.

Further, if the distance between the destination point and the departure point is shorter than a certain distance, the route may be calculated directly without storing the vehicle guidance information in the route table. This results in
This is because memory is saved, and if the distance between the destination point and the starting point is short, the time required to calculate the route does not take much time.

FIG. 5 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 passing point memory 3
From B, data on passing points is acquired 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 waiting time at an intersection or the like.

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, this is because the distance between the destination point and the departure point is short and the initial route is not displayed in the route table). ), 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.

As described above, links representing specific points provided in road map data corresponding to major intersections, leisure facilities, stations, parking lots, expressway on/off ramp areas, service areas, beacons, etc. are set as route starting points. For each destination link, the optimal route to the destination link is calculated in advance, and only the passing points of the optimal route are stored in a passing point memory such as a CD ROM, IC card, DAT, or cassette tape. By storing it in 3B, if the driver or the destination is entered manually, this passing point table can be used to instantly search for passing points leading to the destination and divide the route to calculate it. . Since each of these divided routes is a single distance, the time required for route calculation can be dramatically reduced. can.

The optimal route to the final destination can then be displayed on the screen.

Although the present invention has been described above based on examples, the present invention is not limited thereto. For example, in the above embodiment, the boundary line of the mesh structure is used to define the passing point, but the method of defining the passing point is not limited to this. It is also possible to use circumferences located at the same straight line distance from a specific link that is the starting point of the route, or passing points may be defined for every fixed traveling distance along the optimal route.

If the optimal route is an expressway, passing points may be defined for each major ramp.

Further, in each of the embodiments described above, an entry link is used to specify a point, or an exit link may be used instead of an entry link. Alternatively, nodes may be used.

In addition, road map data is said to be composed of links or nodes related to all roads, large and small, but if the number of links and nodes is large and the capacity of the passing point memory 3B is insufficient, only major arterial roads can be used. It may be composed of links and node data.

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

<Effects of the Invention> As described above, according to the optimal route calculation device of the present invention, an optimal route from a route starting point, which is each specific point, to each destination point, or a route, which is from each starting point to each specific point, is calculated. The route to the end point is calculated in advance, and the passing points along which the optimal route passes are stored in a passing point table corresponding to each route starting point and each destination point pair, or each starting point and route ending point pair. Therefore, this passing point is searched from the passing point table according to the driver's destination setting, and
The optimal route can be divided and calculated for each passing point. Therefore, the calculation time for the optimal route is dramatically reduced, and the optimal route to the final destination can be quickly determined.
It can be shown to the driver.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing a route guidance device for implementing the optimal route calculation device of the present invention, FIG. 2 is a mesh map for explaining the structure of a passing point table, and FIGS. 3 and 4 are respectively Exit link at crossroads,
FIG. 5 is a diagram showing an example of an approach link, and FIG. 5 is a diagram showing a vehicle guidance flow. P...Departure point, Q...Destination, Po...Route starting point link, p3...Destination link,
3A...road map memory, 3B...passing point memory, 6...initial setting section, 7...processing section (passing point acquisition means) Patent applicant Sumitomo Electric Industries Co., Ltd. Agent Patent attorney Kame Masaru Ii Hiro (and 2 others) P... Departure point PO... Route starting point link... Optimal route p3... Destination link pi, p2... Passage point link Q... Destination number Figure 2 Figure 3 Figure 4 Figure 5

Claims (4)

[Claims] 1. According to the driver's settings such as the destination point, road map data for the range including the departure point and destination point is read from the road map memory, and the optimal route from the departure point to the destination point is calculated based on this road map data. An optimal route calculation device that calculates in advance an optimal route to each destination point using a plurality of specific points selected based on certain criteria on the road map as route starting points, and A passing point table that stores one or more passing points in correspondence with the destination point and a specific point that is the starting point of the route; an initial setting means for setting the destination point and a route starting point by the initial setting means; a passing point obtaining means for searching a passing point table and acquiring a passing point according to the setting of a destination point and a route starting point by the initial setting means; An optimal route calculating device comprising: a route calculation means for dividing and calculating a route for each passing point acquired by the passing point acquiring means when calculating a route from a point to a destination point. 2. According to the driver's settings such as the destination point, road map data for the range including the departure point and destination point is read from the road map memory, and the optimal route from the departure point to the destination point is calculated based on this road map data. In the optimal route calculation device, the optimal route is calculated in advance from each starting point using a plurality of specific points selected based on certain criteria as the route end points on the road map, and the route taken along this optimal route is calculated in advance. A passing point table that stores one or more passing points in correspondence with the starting point and the specific point that is the end point of the route; an initial setting means for setting a passing point as a starting point; a passing point obtaining means for searching a passing point table and acquiring a passing point according to the setting of a departure point and a specific point serving as a route end point by the initial setting means; When calculating a route from a point to a specific point that is a route end point, the optimal route calculation is characterized by having a route calculation means that calculates the route by dividing it into each passing point acquired by the passing point acquisition means. Device. 3. Claim 1 or 2, wherein the road map data consists of a combination of nodes and links, and points on the road map are identified by nodes or links.
The optimal route calculation device described. 4. The optimal route determining device according to claim 1 or 2, wherein the passing point table stores the passing point only when the distance between the destination point and the starting point is longer than a certain reference value. .