JPH087527B2 - Optimal route determination device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION <Industrial field of application> The present invention relates to an optimum route determination device that determines an optimum route from a starting point to a destination point according to the setting of a destination point by a driver. .

<Prior Art> Conventionally, there is known a route guidance device developed to display the position and orientation of a vehicle on a screen to facilitate traveling on a strange land or at night.

The route guidance device includes a display, an orientation sensor, a distance sensor, a road map memory, and a computer mounted on a vehicle, and stores the orientation data input from the orientation sensor, the traveling distance data input from the distance sensor, and the road map memory. The vehicle position is detected based on the matching with the road pattern being displayed, and the vehicle position and the destination point are displayed on the display together with the road map.

In this case, the driver himself / herself has to determine the traveling route from the starting point to the destination point.

However, in recent years, the route from the departure point to the destination point is automatically calculated by the computer according to the destination point setting input by the driver, and the route is superimposed and displayed on the road map before or during driving. It is suggested to do so.

As a method of calculating the route from the departure point to the destination point, there is a so-called Dijkstra method (Development research report of emergency vehicle traveling guidance system Japan Traffic Management Technology Association March 1986, Dirck Von Vliet, “Improved
Shortest Path Algorithm for Transportation Networ
k ", Trans-portation Research, Vol.12, 1978). This method divides roads that are the targets of route calculation into multiple nodes, defines the separated points as nodes, and links routes that connect nodes to each other. Assuming a tree of links from the start point to the end point with the node or link closest to the start point as the start point and the node or link closest to the destination as the end point, add the link costs of all the routes that make up the tree in order. This is a method of calculating the route with the lowest link cost to reach the destination. Here, the items to be considered when estimating the link cost are mileage, travel time, whether or not the highway is used, and the number of right and left turns. There are items set according to the driving probability of highways, avoidance of accident-prone areas, and other preferences of the driver.

If the route is calculated in this way, as long as there is a route from the starting point to the destination, the vehicle will surely reach the destination.

<Problems to be Solved by the Invention> However, in the Dijkstra method, the calculation time is determined according to the number of nodes and the number of links in the area to be calculated, and the nodes and links are the objects of calculation. Since there are a considerable number of regions, the calculation usually takes a considerable amount of time.

Therefore, the driver has to wait until the optimum route is calculated after setting the destination point, and there remains a problem in practicality when the driver is in a hurry.

The present invention has been made in view of the above problems, and in the case of obtaining a route from a departure point to a destination point according to the setting of the destination point by the driver, an optimal route can be quickly obtained without calculating the route. It is an object of the present invention to provide an optimum route determination device that can obtain

<Means for Solving the Problem> The optimum route determination device of the present invention for achieving the above-mentioned object selects a plurality of specific points according to a certain standard from the points constituting the road map data. Every time, the optimum route to each destination point is calculated in advance with each specific point as the departure point, and from this specific point on this optimum route,
A route table in which information about the initial route to at least the next specific point through which this optimum route passes is stored in association with the specific point that is the destination point and the departure point, and the destination to set the destination point Setting means, specific point determining means for determining a specific point near the current position of the vehicle and a specific point along the route, setting of the destination point by the destination setting means, and current of the vehicle by the specific point determining means The route table is searched according to the determination of the specific point close to the position, information about the initial route is acquired, and the destination point is also determined according to the determination of the specific point along the initial route by the specific point determination means. Search the route table for each route to obtain the information about the next initial route one after another, and connect the obtained routes to find the optimal route. Is intended to include the optimal route acquiring unit that (claim 1).

The destination may be selected from all the points constituting the road map data, or selected from a number of points set on a certain basis corresponding to the destination to which the driver often travels. It may be something.

The specific point is preferably selected from the main points on the road map (claim 5), but may correspond to all points on the road map.

Further, the route table may not only store information on the initial route from a specific point to the next specific point, but may also store the route of the measure from the next specific point at the same time.

The optimal route determination device, the route to each destination point with each specific point as the route starting point is the calculation target,
On the contrary, the route to each departure point may be set as the calculation target with the specific point as the route end point (claim 2).

Further, the road map data may be a combination of a node and a link, and a point on the road map may be specified by the node or the link (claim 3).

In addition, the route table may store information about the initial route or the final route only when the distance between the specific points serving as the destination point and the departure point is longer than a certain reference value. (Claim 4).

<Operation> According to the optimum route determination device of the above-mentioned claim 1, when the destination point is set by the driver's scanning or the like and the specific point determination means determines the specific point near the current position of the vehicle, the optimum route is determined. The acquisition means can search the route table and acquire an initial route starting from a specific point near the current position of the vehicle.

This initial route is a part of the optimum route to the destination point and continues from a specific point near the current position of the vehicle to at least the next specific point through which the optimum route passes,
By showing the driver, it is possible to guide from a specific point to the next specific point.

Further, when the specific point determination means determines the next specific point along the optimum route, the optimum route acquisition means starts the specific point and then starts the next initial point which is a part of the optimum route to the destination point. You can get the route.

Therefore, the driver can be shown the next initial route starting from the next specific point.

Thereafter, the same procedure can be followed to show the driver a continuous initial route, and finally show all optimum routes to the destination.

Also in the optimum route determination device of claim 2, the only difference is that the order of calculation is performed from the destination side, and by showing continuous end routes, the optimum route from the destination point to the departure point is finally determined. What can be shown is the same as that of the optimum route determination device of claim 1. Therefore, in the following description and the description of the embodiments, it is assumed that the route is acquired from the departure side as described in claim 1.

The form of the information regarding the initial route stored in the route table varies depending on what route information is shown to the driver. For example, if a row of arrows along the initial route, that is, a link row is displayed, it is necessary to store the link row in the route table. If the point sequence along the initial route is displayed, it is necessary to store the node sequence in the route table. If only the intersections along the initial route are displayed, the column of nodes corresponding to the intersections may be stored.

In addition, if the information about the initial route is stored in the route table only when the distance between the destination and the specific point that is the departure point is longer than a certain reference value, the departure point and the destination are compared. When it is close to each other, the optimal route is calculated directly without using the route table.
The memory capacity of the route table can be saved.

<Example> Hereinafter, an example of the present invention will be described in detail with reference to the accompanying drawings.

The optimum route determination device of this embodiment is incorporated in a route guidance device that guides a vehicle by displaying the optimal route on a screen or outputting a voice.

As shown in FIG. 3, the route guidance device has a display 1
, Console 2, direction sensor 10, distance sensor 9
And a road map memory 3A that stores road map data
And the route memory 3B that stores the route table and each memory
A memory drive 4 for reading stored data from 3A and 3B, and a traveling distance and direction sensor detected by a distance sensor 9
The running direction change amount detected by 10 is integrated respectively,
A locator 11 for detecting the vehicle position based on a comparison between the integrated data and the road map data read by the memory drive 4, and for searching / acquiring an initial route, reading a road map in a predetermined range, and guiding the vehicle. From the processing unit 7 that performs various controls such as generation of display data, control of the audio output device 15, and control of the locator 11 (this processing unit 7 also functions as optimum route acquisition means), and the processing unit 7. It has a main memory 8 for storing display data to be output, an output controller 12 for controlling the display 1, and an initial setting section 6 for setting initial data input from the console 2.

The display 1, the console 2, the locator 11, and the initial setting section 6 function as a destination setting means and a departure place setting means.

More specifically, the console 2 includes a key input board (start / stop), a cursor movement on the screen, setting of initial data such as a destination point, scrolling of a road map displayed on the screen, and the like. (Not shown).

The azimuth sensor 10 detects a change in azimuth 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, the number of rotations of the wheels, and the like, and a wheel speed sensor, a vehicle speed sensor, or the like can be used.

The locator 11 calculates travel trajectory data by integrating distance data detected by the distance sensor 9 and azimuth change data detected by the azimuth sensor 10, respectively, and is stored in the travel map data and the road map memory 3A. The vehicle position is detected based on a comparison with a road pattern (a so-called map matching method, see JP-A-64-53112).

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

The display 1 is provided with a transparent touch panel 5 on the screen such as a CRT or a liquid crystal panel.

Each of the memories 3A and 3B has a large capacity storage medium such as a CD-ROM,
It is composed of a memory such as a C memory card and a magnetic tape.

Road map memory 3A is used for road maps (highway national roads, urban highways, general national roads, major local roads, general prefectural roads,
General city roads in designated cities and other living roads) are divided into meshes, and data obtained by combining nodes and links in each mesh unit is stored. Other, railway,
It may include background data for display such as rivers, place name fields, famous facilities, points pre-registered by driving vehicles, contour lines, and the like.

Here, in general, a node is a coordinate position for identifying an intersection or a bend of a road. A node representing the intersection is an intersection node, and a node representing a bend (excluding the intersection) of the road. Sometimes referred to as an interpolation point node.
The node data includes a node number, an address of a node of an adjacent mesh corresponding to the node, an address of a link connected to the node, and the like.

A link is formed by connecting each intersection node. Link data consists of link number, link start node and start node address, link distance, link passing direction, required time data in that direction, road type, road width, traffic regulation data such as one-way and toll roads. Become.

As described above, since the addresses of the start point node and the end point node of the link are included in the link data, the point can be specified only by the link. The link is called an "exit link" when the start point of the link is specified by the link, and the "entry link" is called when the end point of the link is specified. Further, since the link data includes the direction of passing through the link, the traveling direction of the vehicle can be identified by identifying one link. FIG. 2A illustrates four exit links that specify a crossroads, and FIG. 2B illustrates four entry links that specify a crossroads.

In the following example, an exit link is used to identify a point.

The route memory 3B includes major intersections, leisure facilities, stations,
Route calculation conditions (shortest time route) that set the optimum route from each specific link corresponding to parking lot, on-ramp of highway, off-ramp, service area, roadside beacon, etc. to all links corresponding to destination ,
Calculate in advance according to the shortest distance route, route with few right and left turns, route with wide road, etc. (for example, before shipping the optimal route determination device from the factory),
The link sequence of the initial route from the specific link to at least the next specific link through which the optimum route passes is stored in association with the link corresponding to the destination point and the specific link. .

Next, the operation of the optimum route determination device having the above configuration will be described with reference to FIG.

FIG. 1 is a road map for explaining the optimum route determination procedure. An exit link at each intersection of the mesh-shaped road R is displayed by an arrow. Capital letters Pi (i = 1,2,
There are two types, those with ...) and those with lower case pik (k = 1,2, ...), but the upper case Pi indicates a specific link corresponding to the main intersection, and the lower case is this The links corresponding to the intersections other than the above shall be shown.

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

When obtaining the optimum route from the departure point P to the destination point Q, the processing unit 7 determines a specific link closest to the departure point P (link P in the figure) based on the information from the initial setting unit 6.
1) and the link p42 corresponding to the destination point Q are determined. It goes without saying that this determination is automatically made without the driver's operation (the processing unit 7 functions as the specific point determining means).

After the initial settings are input as described above, the display map of the departure point of the processing unit 7 is returned and the route memory is displayed.
Search for 3B.

The route memory 3B stores, as a table, a link string constituting an initial route starting from each specific link Pi (i = 1, 2, ...) Corresponding to the destination link p42. Table 1 shows an example of the route table.

The processing unit 7 first accesses the route memory 3B through the memory drive 4 and reads the link strings P1, p11, p12, p13 of the initial route corresponding to the departure point link P1. As a result, the initial route P1 → p11 → p12 → p1 with the starting point link P1 as the starting point
You can get 3. This route is immediately display 1
May be displayed on the screen, or may be displayed collectively after all routes are obtained as described later.

Next, the processing unit 7 accesses the route memory 3B until the vehicle reaches the specific link P2 (for example, the signal waiting time at the intersection may be used or the time before departure may be used). Then, the link strings P2, p21, p22 of the initial route corresponding to the specific link P2 are read. As a result, it is possible to acquire the initial route P2 → p21 → p22 with the specific link P2 as the departure point. This route may be displayed on the display device 1 immediately or may be displayed together with all the routes.

In the same manner, read the link sequence P3, p31, p32, p33 of the initial route with the specific link P3 as the starting point from the route P3 → p31 → p
32 → p33 is acquired and displayed, and finally, the link sequence P of the route from the specific link P4 to the destination link p42
4, p41, p42 can be read out and the path P4 → p41 → p42 can be acquired and displayed.

As described above, all route data from the specific link P1 to the destination link p42 can be displayed.

In the above case, the route from the first position P of the vehicle to the first specific link P1 cannot be shown to the driver immediately because it is not included in the route table. There is no problem if the route is calculated by the above method, since the optimum route can be obtained in a relatively short time. If the driver is not at a loss because it is near, it may be enough to show the specific link P1 without calculating the route.

Further, when the distance between the destination point and the departure point is short, the initial route may not be stored in the route table and direct route calculation or the like may be performed. This is because if the distance is stored in the route memory until the distance between the destination point and the departure point is short, the memory capacity increases, and if the distance is short, the route calculation time does not become so long.

FIG. 4 is a diagram showing a route guidance flow for guiding the vehicle along the optimum route. In step S1, a display map in an area to be displayed centering 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 magnification.
Then, in step S3, the data of the initial route is acquired from the route memory 3B by the procedure described above.

In step S4, it is checked whether or not the initial route to be displayed is acquired, and when the initial route is not acquired (this is because the distance between the destination point and the departure point is short as described above, the initial route is not displayed in the route table). If it is not stored.), Proceed to step S7, draw only the current position mark of the vehicle on the frame memory, and
In S8, the contents of the frame memory are displayed on the display. At this time, the route may be calculated as usual and the calculated route may be displayed.

If the initial route to be displayed is found in step S4, the initial route is drawn as a link string on the road display map currently drawn in step S5. Then, in step S6, the initial route is displayed along the road using the direction vector.

As described above, links that represent specific points provided corresponding to major intersections, leather facilities, stations, parking lots, on / off ramp areas of highways, service areas, beacons, etc. in the road map data are used as departure points. , For each destination link, the optimum route to the destination is calculated in advance, and only the initial route, which is a part of the optimum route, is not stored in the route memory 3B such as CDROM, IC card, DAT or cassette tape. By remembering
If the driver inputs a destination and travels, the vehicle can pass through any of the specified points and then immediately search and display the initial route on the optimal route using this route table. it can. Then, by the time you complete the initial route,
Search and display the initial route starting from the next specific point,
After that, the same measures can be repeated to display the optimum route to the final destination on the screen.

Although the present invention has been described based on the embodiments, the present invention is not limited thereto. For example, in the above-described embodiment, the exit link is used to specify the point, but the entry link may be used instead of the exit link. Also, a node may be used.

Also, the road map data consisted of links or nodes related to all large and small roads, but if the number of links and the number of nodes are large and the capacity of the route memory 3B is insufficient, links for only major highways are , Nodes.

Various other design changes can be made without departing from the scope of the present invention.

<Effects of the Invention> As described above, according to the optimum route determination device of claim 1 of the present invention, the optimum route from each specific point to each destination point is calculated in advance, and the optimum route is calculated. Since the first part is stored as the initial route in the route table corresponding to each specific point and each destination point,
This initial route can be retrieved from the route table and shown to the driver according to the driver's setting of the destination. Then, after that, since the specific point which is the end point of the initial route is set as the starting point, the next initial route can be searched from the route table by the same procedure, so that, in the end, a short time without any calculation, The optimal route to the final destination can be determined and shown to the driver.

Even in the optimum route determination device of claim 2, the optimum route from each departure point to each specific point is calculated in advance, and the last part of the optimum route is set as the final route. Since it is stored in the route table corresponding to a specific point and each starting point, the final route can be retrieved from the route table and shown to the driver according to the setting of the driver's destination or the like. Then, after that, the end point is a specific point that is the start point of the final route, and the next final route can also be searched from the route table by the same procedure, so in the end, without any calculation, in a short time, The optimal route from the initial departure point can be determined and shown to the driver.

[Brief description of drawings]

FIG. 1 is a road map for explaining a route acquisition procedure, FIG. 2 is a diagram showing examples of exit links and approach links at a crossroads, and FIG. 3 is route guidance for implementing an optimum route determination device of the present invention. FIG. 4 is a block diagram showing the device, and FIG. 4 is a diagram showing a vehicle guidance flow. P ... Departure point, Q ... Destination point, P1 ... Departure point link, p42 ... Destination link, 3A ... Road map memory, 3B ... Route memory, 6 ... Initial setting section, 7 ... Processing Department (optimum route acquisition means)

 ─────────────────────────────────────────────────── ─── Continuation of the front page (56) Reference JP-A-2-56591 (JP, A) JP-A-62-91811 (JP, A) JP-A-59-105113 (JP, A) JP-A-4- 204881 (JP, A)

Claims (5)

[Claims] 1. An optimum route determining apparatus for determining an optimum route from a starting point to a destination point according to a setting of a destination point by a driver, wherein a plurality of routes selected on a road map based on a certain standard are selected. Information about the initial route from a specific point that is the above-mentioned departure point to at least the next specific point through which this optimum route passes, by pre-calculating the optimum route from the specific point as the departure point to each destination point , A route table that stores the destination points and the specific points that are the departure points, destination setting means that sets the destination points, and specific points and routes that are close to the current position of the vehicle. Specific point determining means for determining the point, and a specific point close to the current position of the vehicle by the specific point setting means for setting the destination point and the specific point determining means. The route table is searched according to the determination of No. 1, and the information about the initial route is acquired, and the route table having the same destination is also searched according to the determination of the specific point along the initial route by the specific point determination unit. The optimum route determination device further includes an optimum route acquisition unit that acquires the information about the next initial route one after another, and obtains the optimum route by connecting the acquired routes. 2. An optimum route determining apparatus for determining an optimum route from a starting point to a destination point according to the setting of a destination point by a driver, wherein a plurality of routes selected on a road map based on a certain standard are selected. Information about the final route between the specific point that is the destination and at least the next specific point through which this optimum route passes, with the optimum route from each departure point calculated in advance with the specific point as the destination The route table that stores the corresponding points of departure and destinations, the destination setting means for setting the departure point, and the location along a specific route and route near the travel destination. The specific point determining means for determining the point of the, and the setting of the starting point by the starting point setting means and the determination of the specific point near the destination of the trip by the specific point determining means. Then, the route table is searched to obtain the information about the final route, and the route table having the same departure point is searched according to the determination of the specific point along the final route by the specific point determination means, An optimum route determination device including: an optimum route acquisition unit that acquires information about the final route one after another and obtains the optimum route by connecting the acquired routes. 3. The road map data is composed of a combination of a node and a link, and a point on the road map is specified by the node or the link.
Alternatively, the optimum route determination device described in 2. 4. The route table stores information about the initial route or the final route only when a distance between a specific point serving as a destination point and a starting point is longer than a certain reference point. 3. The optimum route determination device according to claim 1, which is characterized in that. 5. The specific point on the route table is selected from the main points on the road map.
The optimal route determination device described.