JP3522665B2 - Route search method, route search device, and recording medium storing route search program - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a technique for automatically searching a route from a start point to an end point designated on a map by a computer, and particularly, without using road network data describing a road connection relation. In addition, the present invention relates to a method and an apparatus for realizing an effective route search, and a recording medium recording the program thereof.

[0002]

2. Description of the Related Art In recent years, electronic maps used in personal computers, car navigation systems, etc. have rapidly become popular. Recently, with the spread of DVD-ROM and the like, electronic maps including more detailed map information have been provided. One of the purposes of using such an electronic map is to search for a route to a destination desired by the user. There have been several techniques for searching such a route on a map. For example, Japanese Unexamined Patent Publication No. 6-160106 describes that a route search is performed using road network data that describes road connection relationships. Then, here, the route search having various variations is realized by considering the distance between both points, the number of turns, and the size of the width.

However, it is very difficult to create the road network data necessary for such a route search,
Manual modification is required for actual use.
Moreover, the detailed map information that is often used recently is
It contains an order of magnitude more road information than conventional road maps, and the price of such road network data itself is very high, and it is a very time-consuming process. It is very difficult to use for.

[0004]

As described above, in the conventional method for searching a route using road network data, the process of creating the road network data is very difficult, and the map information often has a lot of problems. Although the road information is included, there is a problem that it is difficult to use it easily.

The present invention has been made in view of the above-mentioned problems of the prior art. The route search from the start point to the end point designated on the map is performed by using the road network data describing the road connection relationship. The purpose is to realize it easily without using it.

[0006]

SUMMARY OF THE INVENTION According to the present invention, a route search from a start point to an end point designated on a map is not searched for a road connection relation, but for a block connection relation of a map database. It is characterized by performing by.

In the present invention, when the information of the starting point and the ending point for requesting the route search is received from the user, the block connected to the target block is searched, and the graph structure for the block is calculated. Then, the route information is acquired from the block route calculated using this graph structure and output. In addition, the block route is calculated by performing the shortest cost calculation with the distance between adjacent block blocks as the cost.

According to the present invention, the route can be searched very quickly by using the graph structure based on the block. As a result, the route search can be performed without using the road network data that has been conventionally required. In addition, the shortest route can be searched for by performing the shortest cost calculation using the distance between the adjacent blocks as a cost.

[0009]

BEST MODE FOR CARRYING OUT THE INVENTION An embodiment of the present invention will be described below with reference to the drawings. FIG. 1 is a block diagram showing a main configuration of a route search device according to the present invention. The route search device 100 searches an input reception processing unit 110 that receives information about a start point and an end point that requests a route search from a user, a block that is connected to a target block, and sets the block as a node and a connection relationship as a link. By using the block network calculation processing unit 120 that calculates the graph structure and the graph structure calculated by this block network calculation processing unit 120,
A block route search processing unit 130 for calculating a block route from the requested start point to the end point, and this block route search processing unit 13
Obtain route information from the block route calculated in 0,
The output control processing part 140 which outputs is provided. The map database (map DB) 150 stores data of coordinate point sequences of figures existing in the map, data including attributes given to the figures, and the like.

Here, the route search apparatus 100 may be on a network such as the Internet, or may be a part of a stand-alone personal computer. Any of the present inventions can be used. For example,
When the route search device 100 is on the network,
The user selects a route search device 10 from a personal computer or a mobile terminal.
The route search device 100 responds to the user side with desired route information by accessing 0 and sending information on the start point and end point for requesting the route search. When the standalone personal computer itself has the function of the route search device 100,
The user inputs the information on the starting point and the ending point of the route search with the keyboard or the mouse, and the target route information is displayed on the denomination or the like.

Below, the route search apparatus 100 shown in FIG.
Each processing of the input reception processing unit 110, the block network calculation processing unit 120, the block route search processing unit 130, and the output control processing unit 140 in the above will be described in detail.

<Input Reception Processing> Input reception processing unit 110
Receives the information of the starting point and the ending point for requesting the route search from the user, and acquires the information of the nearest block to the starting point and the ending point. This process is performed according to the procedure shown in FIG.

[Step 201] The search request from the user is analyzed. [Step 202] The map database 150 is searched, and information on the start point and the end point is held. [Step 203] The block closest to the start point and the end point is acquired from the map database 150. [Step 204] Information on the acquired starting block Gs and ending block Gg is held. Then, the process is transferred to the block route search processing unit 130.

<Block City Network Calculation Processing> The block network calculation processing unit 120 is a block route search processing unit 130.
The target block Gi is sequentially received from, and the block connected to this target block Gi is searched, and the graph structure for the block is calculated. This processing is performed according to the procedure shown in FIG.

[Step 301] Target block Gi
The map database 150 is searched for, and the information of the block Gj adjacent to Gi is held. [Step 302] A block Gj adjacent to an unprocessed line segment L (Gi, m) forming the target block Gi
The line segment L (Gj, n) existing in the shortest distance from the above line segment among the line segments forming In addition, m and n are the numbers of the line segments which respectively comprise the block. [Step 303] The relative angle between the line segment L (Gi, m) of the block Gi and the line segment L (Gj, n) of the block Gi is calculated. [Step 304] It is determined whether the calculated angle satisfies a predetermined threshold value. Then, if satisfied, the process proceeds to step 305, and if not satisfied, the process returns to step 302. This step 304 is to exclude a pair of line segments that are opposed to each other and have extremely different line lengths from the connection target. [Step 305] Replace the line segment L (Gg, n) with the line segment L (G
i, m) is the connection target line segment, and the average distance D between the line segments
ist (L (Gi, m), L (Gj, n)) is calculated. [Step 306] Steps 302 to 305 are repeated until the processing is completed for all the target line segments. [Step 307] The shortest average distance Dist (L (Gi, m), L (G) for the block Gj adjacent to the block Gi
j, n)), and the cost Cost between Gi and Gj
(Gi, Gj).

By this block network calculation processing, a graph structure is calculated in which the block is a node and the connection relationship of the block is a link, and the attribute value of the link is the cost of the distance of the block. The block network calculation process is performed on the block stored in the map database 150 in advance, the result is stored in, for example, the memory of the device on which the process is executed, and the stored data is stored. It may be used.

<Block Route Search Process> The block route search processing unit 130 uses the graph structure calculated by the block network calculation processing unit 120 to search for the route of the block with the shortest cost. This processing is performed according to the procedure shown in FIG. Here, the node information of a block is represented by control information (previous block, cost, determination flag). "1
"Previous block" is the previous block I connected to the block.
When D is set and there is no initial state or connected block, it is set to "NULL". The "cost" is set to the total cost of the searched block route from the first block to the block, which is "infinity" in the initial state and "0" when there is no block to be connected. The “decision flag” indicates whether or not the block is determined as the target block for the route search, and is “OFF” in the initial state or when the block is not determined, and “O” when it is determined.
N ".

[Step 401] The starting block Gs,
Information on the last block Gg is acquired from the input reception processing unit 110. [Step 402] Control information of the starting block Gs (1
Previous block: NULL, cost: 0, decision flag: O
N) is set. [Step 403] The information of the block Gi connected to the block Gs is acquired from the block network calculation processing unit 120, and the control information of the block Gi (previous block: Gs, cost: Co
st (Gi) = Cost (Gs, Gi), decision flag:
OFF) is set. This is performed for each block connected to the block Gs.

[Step 404] The control information decision flag is OFF for all the blocks Gi for which information has been acquired.
Then, the block Gj that minimizes the cost is calculated. [Step 405] Control information of block Gj (previous block: Gk, cost: Cost (Gj) = Cost (G
k) + Cost (Gk, Gj), decision flag: ON). Note that Gk = Gs in the case of steps 403 and 404. [Step 406] The information on the block Gi connected to the block Gj is acquired from the block network calculation processing unit 120.
This is performed for each block connected to the block Gj. [Step 407] When a block Gi whose control information has not been initialized is selected, the control information is initialized. That is, the control information (one block before: NULL, cost: infinity, determination flag: OFF) is set. [Step 408] All blocks Gi for which information has been acquired
, The control information determination flag is OFF, and Cost
(Gi)> Cost (Gj) + Cost (Gj, Gi)
Determine if If not satisfied, the process returns to step 404, and if satisfied, the process proceeds to step 409.
By this determination, all the blocks Gi whose control information has been initialized in step 407 proceed to step 409. [Step 409] Control information of block Gi (block immediately before: Gj, cost: Cost (Gi) = Cost (G
j) + Cost (Gj, Gi), decision flag: OFF)
To set. [Step 410] It is determined whether the final block Gg is selected and the determination flag of the control information is set to ON,
If not, return to step 404. Hereinafter, steps 404 to 4 are performed until the last block Gg is selected.
Repeat 10. Then, when Gg is selected, the process is transferred to the output control processing unit 140.

<Output Control Processing> Output control processing section 140
Acquires route information from the block route searched by the block route search processing unit 130 and outputs it to the user. This process is performed according to the procedure shown in FIG.

[Step 501] Information on the start point and the end point is acquired. [Step 502] The control information of the block route searched by the block route search processing unit 130 is acquired. That is, the control information whose decision flag is NO is acquired. [Step 503] From the acquired block control information, the last block is sequentially traced from the end block Gg to the start block Gs, and the route order of the block is calculated. [Step 504] Route information is acquired from the calculated route order of the block. [Step 505] The route information is output in the designated format.

The route information thus calculated may be used, for example, for generation of a deformed map described in Japanese Patent Laid-Open No. 10-198267, and the deformed map may be output.

FIGS. 6 to 11 concretely show the above-mentioned processing procedure in accordance with actual data. Hereinafter, this example will be described.

From the user, the starting point O as shown in FIG.
It is assumed that a route search request for s and the end point Og is received. The input reception processing unit 110 acquires the block Gs, Gg closest to the Os, Og from the map database 150, and moves the process to the block route search processing unit 130.

The block route search processing unit 130 obtains the information of the starting block Gs and the ending block Gg as shown in FIG. 7, and first, the control information of the starting block Gs (previous block: NULL , Cost: 0, decision flag: ON). Then, the information on the block connected to this Gs is acquired from the block network calculation processing unit 120.

In the block network calculation processing unit 120,
Map database 150 for the target block Gs
Is searched and the information of the adjacent blocks G1, G2, G5 is held. Next, as shown in FIG. 7, the target block G
For the unprocessed line segment L (Gs, 1) forming s, for example, among the line segments forming the adjacent block G2, the line segment L (G2, G2, which exists in the shortest distance from the line segment. 1) is calculated,
It is determined whether these opposing angles satisfy the threshold value. Here, assuming that the angle between L (Gs, 1) and L (G2, 1) satisfies the threshold value, the line segment is set as the connection target line segment, and the average distance Dist (L (Gs, 1) between the line segments. , L (G
2, 1)) is calculated. This process is repeated until all target line segments are processed. As a result of performing the processing in this way, the shortest Dist (L (Gs, 1), L (G2, 1) is Gs-G for the adjacent block G2.
The cost between two is set as Cost (Gs, G2). Similarly, cost (Gs, G
In 1), Cost (Gs, G5) is set for the block G5.

In the block route search processing unit 130, the Gi of the block connected to the Gs thus acquired (i = 1, 2, 5)
In contrast, control information (previous block: Gs, cost: C
ost (Gi) = Cost (Gs, Gi), determination flag: OFF) is set, and the state shown in FIG. 8 is obtained.
With respect to this Gs, the block Gj in which the determination flag is OFF and the cost is the minimum is calculated for all the blocks Gi for which information has been acquired. Here, it is assumed that G5 is selected, and its control information (previous block: Gs, cost: Cost
(Gs, G5), decision flag: ON) is set.

Next, the city route search processing unit 130 obtains the information of the city block Gi connected to the city block G5 from the city block network calculation processing unit 120 as described above. At this time,
When a block for which the control information has not been initialized is selected, the control information is initialized (one block before the block: NULL,
Cost: infinity, decision flag: OFF). For the block Gi acquired in this way, a determination flag: OFF,
Cost (Gi)> Cost (Gj) + Cost (G
j, Gi), the control information (1
Previous block: Gj, cost: Cost (Gi) = Cos
t (Gj) + Cost (Gj, Gi), decision flag: O
FF) is set. Here, Gs and G connected to G5
Blocks G4, G6 that meet the conditions of 4, G6, G9
The control information of G9 is set, and the state becomes as shown in FIG.

In the following, the block route search processing unit 130 cooperates with the block network calculation processing unit 120 to calculate the block for which the decision flag is OFF and the cost is the minimum, for all the blocks for which information has been acquired. But the end Gg
Is repeated until is selected. Here, the processing ends in the state as shown in FIG. 10, and the processing is transferred to the output control processing unit 140.

The output control processing unit 140 acquires control information whose decision flag is ON from the start point and end point information and the control information of the block calculated by the block route search processing unit 130. Then, from this acquired control information, Gg
Starting from, the previous block is sequentially traced to Gs, and the route sequence of the block from Gs to Gg is calculated. Here, FIG.
Gs, G5, G9, G12, G
The order of the routes in the block is g. Route information is acquired using the route order of this block, and for example, (a) of FIG.
The route information is output as shown in (b).

Although the present invention has been specifically described based on an embodiment, the present invention is not limited to the above embodiment, and various modifications can be made without departing from the scope of the invention. There is no end.

A program in which the algorithm of the processing procedure as shown in FIGS. 2 to 5 is described in a computer-executable language is called, for example, a route search program, a floppy (registered trademark) disk, a CD-ROM, It is also possible to provide by recording in a computer-readable recording medium such as a memory card. By installing the route search program recorded on the recording medium in the computer, the functions of the processing units 110 to 140 in the route search device 100 shown in FIG. 1 are constructed on the computer.

[0033]

According to the present invention, there is an effect that a route can be searched at a very high speed by using a graph structure based on a block. As a result, there is an effect that the route search can be performed without using the road network data that has been conventionally required. In addition, there is an effect that a route closer to the shortest route can be searched for by performing the shortest cost calculation by using the distance between adjacent blocks as a cost.

[Brief description of drawings]

FIG. 1 is a block diagram showing an embodiment of a device configuration for realizing a route search method of the present invention.

FIG. 2 is a diagram showing an example of a processing flow of an input reception processing unit shown in FIG.

3 is a diagram showing an example of a processing flow of a block network calculation processing unit shown in FIG.

FIG. 4 is a diagram showing an example of a processing flow of a block route search processing section shown in FIG.

5 is a diagram showing an example of a processing flow of an output control processing unit shown in FIG.

FIG. 6 is a diagram showing original data for explaining a specific example of the route search processing according to the present invention.

FIG. 7 is a continuation diagram for explaining a specific example of the route search processing according to the present invention.

FIG. 8 is a further subsequent diagram for explaining a specific example of the route search processing according to the present invention.

FIG. 9 is a still further diagram for explaining a specific example of the route search processing according to the present invention.

FIG. 10 is a subsequent diagram for explaining a specific example of the route search process according to the present invention.

FIG. 11 is a diagram for explaining a specific example of output by the route search processing of the present invention.

[Explanation of symbols]

100 route search device 110 Input reception processing unit 120 Block network calculation processing unit 130 Block Route Search Processing Unit 140 Output control processing unit 150 map database

─────────────────────────────────────────────────── ─── Continuation of front page (51) Int.Cl. ⁷ Identification code FI // G08G 1/0969 G08G 1/0969 (72) Inventor Tomohiko Arikawa 2-3-3 Otemachi, Chiyoda-ku, Tokyo Nippon Telegraph and Telephone Incorporated (56) Reference JP 10-319839 (JP, A) JP 9-258982 (JP, A) (58) Fields investigated (Int.Cl. ⁷ , DB name) G01C 21/00 -21/36 G06F 17 / 30,17 / 60 G09B 29/00-29/10 JISC file (JOIS)

Claims (4)

(57) [Claims] 1. A route search method for calculating a route from a start point to an end point requested by a user by a computer, and an input receiving process for receiving information of a start point and an end point for which a route search is requested by the user. , A block network calculation process for searching a block connected to the target block, and calculating a graph structure with the block as a node and a connection relation as a link, and a graph structure for the block calculated in the block network calculation process Block search processing for calculating a block path from the requested start point to the end point, and output control processing for acquiring path information from the block path calculated in the block path search processing and outputting to the user A route search method comprising: 2. The block route search process calculates a graph structure using the distance between adjacent block blocks as a cost, and the block route search process calculates the block route with the shortest cost from the requested start point to the requested end point. The route search method according to claim 1, wherein: 3. A route search device that utilizes a map database to calculate a route from a start point to an end point requested by a user, and receives information on the start point and end point for which the user has requested a route search, Input receiving processing means for obtaining information on blocks adjacent to the start point and end point from a map database, and a block structure for searching block blocks connected to the target block from the map database and linking block blocks with connection relationships A block network calculation processing unit that calculates a block block route calculation processing unit that calculates a block block route from a requested start point to an end point by using a graph structure for the block calculated by the block block network calculation processing unit. And an output control processor that acquires route information from the block route calculated by the block route search processing means and outputs it to the user. Route search device characterized in that it comprises a and. 4. A computer-readable recording medium on which a route search program for executing the route search method according to claim 1 or 2 is recorded.