JP3036473B2 - Route search apparatus and method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a route search apparatus and method for finding a minimum cost route of a graph, and more particularly to a route search apparatus and method effective for limiting a search range at the time of search and searching for a route at high speed. And a record of the program
Regarding recording media .

[0002]

2. Description of the Related Art The problem of finding the minimum cost path in terms of distance, time, and price between two points is one application of graph theory. Then, by the route search device for finding the minimum cost route of the graph, it is possible to know the cheapest route and the fastest route from the starting point to the target point when traveling by rail, car or airplane, for example. . Similarly, the user of the communication line can select the cheapest communication route from point A to point B.

[0003] As this minimum cost path algorithm,
Dijkstra's algorithm is widely known. According to this algorithm, if the number of arcs in the graph is e and the number of nodes in the graph is n, then O ((e
+ N) · log (n)) can calculate the minimum cost route in the processing time.

[0004] However, when the graph scale is large and the number of nodes is large like a traffic network, there is a problem that the processing time becomes long.

As a prior art intended to solve such a problem, for example, Japanese Patent Application Laid-Open No. 1-142825 discloses a shortest path table for storing the shortest paths from a predetermined reference point of all nodes, A node coordinate table for storing the coordinate positions of the nodes is provided. The sum of the shortest paths from the reference point of the departure point and the arrival point with reference to the data of the shortest path table is obtained, and the search is limited to the search range. A route guidance device has been proposed. Japanese Patent Laid-Open No. 3-2
No. 972 discloses a place name index table means, a place name index table search logic means, and a necessary route candidate data group selection logic means, and only the necessary route candidate data group is picked up and the shortest time from the starting point to the destination is taken. A shortest route search method for efficiently searching for a route that has been proposed has been proposed. Furthermore, literatures (Ichimura Iimura, Makoto Kato, "Route search method in Japan nationwide road network where search area is limited by lookup table", Transactions of Information Processing Society of Japan, 19
1994, No. 12, pp. 2831).

In each of these conventional techniques, the search time is shortened by preparing additional data for limiting the search range, separately from the data structure of the graph.

More specifically, for example, Japanese Patent Application Laid-Open No.
In the route guidance device described in Japanese Patent No. 2825, a minimum cost route table storing the minimum cost route from a predetermined node and a node coordinate table storing the coordinate values of the nodes are prepared for all the nodes. By referring to these additional data, find the maximum value of the minimum cost distance from the starting point to the destination point, and do not search the range exceeding the maximum value when searching from the starting point To speed up.

That is, the minimum cost distance from the reference point to the start point and the minimum cost distance from the reference point to the destination point are obtained by referring to the minimum cost path table, and the sum is calculated from the start point to the destination point. This is the maximum value of the minimum cost distance. Then, the minimum cost distance from the departure point to the midpoint obtained in the middle stage of the search from the departure point to the arrival point, and the linear distance from the midpoint to the arrival point obtained from the node coordinate table are obtained. It is the minimum value from the starting point to the destination via the waypoint.

Here, if the minimum value obtained from the node coordinate table or the like is larger than the maximum value obtained from the minimum cost route table or the like, the route passing through the intermediate point is excluded from the search range. .

[0010] Further, Japanese Patent Application Laid-Open No. Hei 3-2972,
In the prior art described in the above-mentioned paper entitled "Route search method in Japan's national road network in which the search area is limited by a look-up table" by Iimura et al. A search range lookup table describing node groups outside the search range is prepared for all combinations of the node groups.

By referring to the additional data, a node group that does not need to be searched for the combination of the node group to which the starting point belongs and the node group to which the destination point belongs can be found, and a route via the node belonging to the node group is searched. Excluded from the range to speed up.

In order to find this search range lookup table, it is necessary to find the minimum cost routes for all nodes in advance.

That is, minimum cost paths are obtained for all combinations of nodes belonging to node group A and nodes belonging to node group B. As a result, a node group that does not belong to all of the routes is found outside the search range.

In this way, for all combinations of node groups, node groups outside the search range are obtained and stored in the search range lookup table.

[0015]

However, the above-mentioned prior art has the following problems.

The first problem is that, in the above-mentioned prior art, there are routes that cannot be excluded.

The reason is as follows. For example, in the case of a method using a look-up table, it is not possible to exclude a route that returns at an intermediate node and deviates from the minimum cost route. This is because information for specifying nodes that do not pass through is stored, but information for specifying the order of nodes that pass through is not stored.

That is, a node that may pass through the route cannot be excluded even if the route is far (returns back) to the destination.

Also, in the case of the method using the minimum cost route table and the node coordinate table, since there is no information for specifying the order of passing nodes, only a very large return route can be excluded. At least, a return route shorter than the minimum cost distance from the intermediate node to the destination cannot be excluded.

Further, as a second problem, since the search range is limited based on the distance with a large error, the efficiency of the route that can be excluded is not very good.

That is, in order to roughly estimate the distance between the starting point and the arrival point from the sum of the minimum cost path between each point of the starting point and the arrival point and the specific node, the starting point, the arrival point and the specific node If the positional relationship between these three points is not very good,
Very large error.

Also, the difference between the straight-line distance from the intermediate point to the destination determined from the node coordinate table and the minimum cost distance between the intermediate point and the destination is quite large.

For example, in the case of a train network, the time cost of a section where the Shinkansen can be used and the time cost of a section where only a regular train can be used largely deviate from the distance obtained from the latitude and longitude of the station.

As a third problem, the method using a look-up table has a problem that a very large memory capacity is required to store the look-up table.

This is because a two-dimensional table for storing node groups in (or outside of) a search is required for a set of node groups.

Accordingly, the present invention has been made in view of the above-described problems, and has as its object to provide a route that can limit the search range of a minimum cost route search of a graph structure with a small amount of additional data. Searching device and method and professional
Another object of the present invention is to provide a recording medium on which a gram is recorded .

[0027]

In order to achieve the above object, a route search device of the present invention searches for a route in a given graph and outputs a minimum cost route connecting two given nodes. In the apparatus, virtual coordinate storage means for storing virtual coordinate values of the nodes, graph structure storage means for storing a network structure consisting of arcs connecting the nodes, and sequentially reading the graph structure from the graph structure storage means, A search range storage means for storing a search target range as an intermediate state of the search process; and a search range from the given start point node to the destination point node while sequentially reading and writing the search range to the search range storage means. and route searching means for searching a route with the shortest cost, a first threshold value storing means for storing the detour of the threshold, the virtual coordinate Symbol Stored in unit, the virtual coordinates of the starting point node, the area defined by the virtual coordinate of the destination point node, stored in the first threshold value storage means,
The route via the node with virtual coordinates to deviate more bypass amount of the threshold, and a search range restriction unit to be deleted from the search range storing means, the first threshold value memory
The detour amount threshold stored in the means is
An area defined by the virtual coordinates and the virtual coordinates of the destination node
Virtual coordinates of all nodes included in the shortest cost route from
Of each node group
From the maximum value obtained.

Further, according to the present invention, there is provided a route searching apparatus for searching a given graph for a route and outputting a minimum cost route connecting the given two nodes, the virtual coordinate storage means for storing a virtual coordinate value of the node. And a graph structure storing means for storing a network structure composed of nodes and arcs connecting the nodes, and a search for sequentially reading the graph structure from the graph structure storing means and storing a search target range as an intermediate state of the search processing. A range storage means, a route search means for sequentially searching and writing out a search range to the search range storage means, and searching for a shortest cost route from a given departure point node to an arrival point node; Second threshold value storage means for storing the virtual coordinates of the node of interest stored in the virtual coordinate storage means during the search; A divergence distance calculating means for calculating a divergence distance between the target node and the destination node from the virtual coordinates of the point node, and a divergence of the immediately preceding node on the route to the target node obtained by the divergence distance calculation means A route that passes through an arc whose difference between the distance and the divergence distance of the node of interest is equal to or greater than the threshold value of the return amount stored in the second threshold storage unit is deleted from the search range storage unit. And a search range limiting means.

[0029]

Embodiments of the present invention will be described below. According to a preferred embodiment of the present invention, in a route search device that searches a given graph for a route and outputs a minimum cost route connecting the given two nodes, a virtual coordinate storing a virtual coordinate value of the node is provided. A storage unit (103 in FIG. 1), a graph structure storage unit (101 in FIG. 1) for storing a network structure composed of arcs connecting nodes, and a graph structure storage unit (101 in FIG. 1). Are sequentially read, and a search range is sequentially read and written to a search range storage means (102 in FIG. 1) and a search range storage means (102 in FIG. 1) for storing a search target range as an intermediate state of the search processing. While searching, finds the shortest cost route from the given departure point node to the destination point node (106 in FIG. 1), and records the detour amount. A first threshold value storing means for (105 in FIG. 1), the virtual coordinate storage unit (Fig. 1
103), the virtual coordinates of the starting point node,
The area defined by the virtual coordinates of the destination node is defined as a search range along a route passing through a node having virtual coordinates deviating from the threshold value of the detour amount or more stored in the first threshold value storage means. Search range limiting means (107 in FIG. 1) for deleting from the storage means (102 in FIG. 1).

In the embodiment of the present invention, the minimum route cost between each node is obtained, and the virtual coordinates of each node are obtained by multivariate analysis (fourth digitization) using the minimum cost as the difference.
In the process of solving the all-pair problem again, the maximum amount of detour around the area between the start point and the arrival point on the virtual coordinates, and the maximum amount of backward movement of each arc in the path that goes in the opposite direction to the arrival point Ask for. The obtained detour amount and return amount are stored as threshold values, and the search range is limited when performing the minimum cost route search.

[0031]

BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a block diagram showing an embodiment of the present invention; FIG. 1 is a block diagram showing a configuration of a route search device according to an embodiment of the present invention. Referring to FIG. 1, a path search device according to the present embodiment includes a graph structure storage unit 101 composed of a semiconductor memory, a magnetic memory, or the like.
, Search range storage means 102, virtual coordinate storage means 10
3 and first threshold value storage means 104 for storing the bypass amount
And second threshold value storage means 105 for storing the return amount
And a route search means 106 realized by program control or the like on the CPU, and a search range limiting means 107.

The graph structure storage means 101 stores a given graph structure.

The search range storage means 102 determines, as a result of the search, a node adjacent to the group of nodes from which the shortest path has been found from the starting point node, to a path of the currently known minimum cost path from the starting point node to that node. Remember with cost.

Then, in accordance with a request from the route search means 106, the graph structure to be searched is sequentially read from the graph structure storage means 101. In addition, search range limiting means 107
According to the request, the search target node is excluded.

Incidentally, a heap structure or the like is usually used to quickly select a set of a node and a cost having the minimum cost.

The virtual coordinate storage means 103 stores virtual coordinates corresponding to each node of the graph structure storage means 101.

The first threshold value storage means 104 stores the maximum bypass amount obtained in advance.

The second threshold value storage means 105 stores the maximum return amount obtained in advance.

The route search means 106 sets the area adjacent to the departure point node as a search range as the search range storage means 102
The search is performed on the nodes within the search range while sequentially expanding the search range, and the minimum cost route to the destination node is searched.

The search range limiting means 107 reads the corresponding virtual coordinate value from the virtual coordinate storage means 103 for each node stored in the search range storage means 102,
The amount of detour and the amount of return are calculated, and the first threshold value storing means 1
In comparison with the detour amount (threshold value) read from step S04, if the detour exceeds the threshold value, the node is deleted from the search range storage means 102 and the second threshold value storage means 105 The read-back amount (threshold) is compared with the read-back amount, and if the value has returned beyond this threshold, the node is deleted from the search range storage unit 102.

The operation of the route search device according to one embodiment of the present invention will be described.

FIG. 2 is a flowchart showing the operation of the route searching means 106 and the search range limiting means 107. In this embodiment, a Dijkstra algorithm is used for the route search means 106.

In FIG. 2, steps 201, 205, 207, and 208 are executed by the search range limiting means 107, and steps 202 to 204, steps 206, 209, and 210 are executed by the route searching means 106. You.

The search range limiting means 107 reads out the threshold value of the bypass amount from the first threshold value storage means 104. Then, an area wider than the area surrounded by the start point coordinates and the arrival point coordinates by the threshold value of the detour amount is set as the search range P (step 201).

Next, the route search means 106 causes the search range storage means 102 to store "0" as the starting point node and the cost corresponding thereto (step 202).

Next, the route search means 106 reads out the set having the lowest cost from the set of nodes and costs stored in the search range storage means 102 (step 203).

Next, it is determined whether or not the node v selected in step 203 is a destination (step 204). In the case of the arrival point, since the shortest path from the starting point to the arrival point has been obtained, the result is output and the processing is terminated. If not, the process proceeds to step 205.

Next, based on the difference between the coordinates of the node v selected in step 203 and the coordinates of the destination, the destination deviation distance L
Ask for. Further, a backward threshold value is read from the second threshold value storage means 105 and added to the destination deviation distance L to obtain a solution R (step 205).

Next, a set A of all nodes adjacent to the node v selected in the above step 203 is obtained and stored in the search range storage means 102 (step 206).

Next, a node set A ′ included in the search range P obtained in step 201 is obtained from the node set A obtained in step 206, and a node set not included in the search range P is obtained from the search range storage means 102. Delete (Step 2
07).

Next, the destination departure distance is obtained from the difference between the coordinates of each node of the node set A 'obtained in step 207 and the coordinates of the destination, and is compared with R obtained in step 205. As a result of the comparison, a node set A ″ equal to or smaller than R is obtained, and a node set larger than R is set as a search range storage unit
2 (step 208).

Next, the cost to reach each node of the node set A ″ obtained in step 208 via the node v selected in step 203 is calculated, and added to the cost forming a pair with the node v selected in step 203. , Node set A ″
(Step 209).

Finally, the cost corresponding to the node set A "obtained in step 209 is stored in the search range storage means 102 (step 210). If a node included in the node set A" is already replaced by another node, If a cost is stored in the search range storage unit 102 because the cost to go through is found, a smaller cost is stored with priority. Then, the process proceeds to step 203.

Referring to FIG. 3, the mapping of each node of the graph structure to the virtual space will be described. FIG. 3 (a)
Shows an example of a graph structure, and a number added to an arc between nodes indicates a cost value. FIG. 3B is a table showing the time cost between the nodes. A brief description will be given of the discontinuation of the search in which the virtual space coordinates of the node, the amount of detour and the amount of backward movement occurring on a valid route are set as thresholds (stored in the first and second threshold storage units).

As described above, in a transportation network including trains and air routes, there is a large difference between the linear distance obtained from the longitude and latitude of each node point and the actual cost (such as arrival time). In this embodiment, each node is mapped to a virtual space (virtual coordinates) reflecting the cost of the actual route.

First, a route search is actually performed for all combinations of nodes, and the cost between each node is calculated. By performing multivariate analysis (4 types of numerical analysis) or the like using the obtained cost between the nodes as the similarity between the nodes, each node can be mapped to a virtual space of an arbitrary dimension.

For example, when each node of the graph structure shown in FIG. 3 is mapped to a one-dimensional space, A: (234),
B: (125), C: (144), D: (191),
E: (908) and F: (218).

Next, an increase in the amount of detour occurring in the shortest path of all node pairs is determined.

The amount of detour refers to the amount by which the virtual space coordinates (virtual coordinates) of the intermediate node deviate from the area formed by the virtual space coordinates of the starting point node and the virtual space coordinates of the destination node.

For example, in the case of the example shown in FIG.
4) → D (191) → F (218) and F (218) → D
(191) → A (234), the amount of detour generated in the two routes is the largest, and the node D from the area [218 234]
Of the coordinate (191) is | 191-218 | = 27
It is.

Next, the maximum value of the return amount generated in the shortest path of all the node pairs is obtained.

The backward movement amount is an amount by which the distance between the preceding and succeeding nodes and the virtual space of the destination node increases as the arc progresses. More precisely, from node i to node j
The arc of turning back amount to the distance R _i in the virtual space of the node i and the destination node, using the distance R _j in the virtual space of the node j and the destination node, the R _j -R _i Is defined as

For example, in the example described above, F
The return amount generated in the route of (218) → D (191) → A (234) is the largest, and the distance R _F = [218-234] =
16 and the distance R _D = | 191-234 | = 43, and the return amount of the arc from the node F to the node D is R
_D- R _F = 43-16 = 27.

As described above, the virtual coordinates of each node, the maximum value of the detour amount, and the maximum value of the post amount are obtained.

In the above-described embodiment, the area defined by the virtual coordinates of the given starting point node and the virtual coordinates of the destination point node is changed to a node having virtual coordinates deviating by more than the threshold value of the detour amount. The route that passes is deleted from the search range storage means to limit the search range. Since only the virtual coordinates are used as additional data, the search range of the minimum cost route search of the graph structure with a small amount of additional data is used. Limitations can be made.

[0066]

As described above, according to the present invention,
Since only the virtual coordinates are used as the additional data, there is an effect that the search range of the minimum cost route search of the graph structure can be limited with a small amount of additional data.

Further, according to the present invention, an unnecessary route including a return route can be effectively removed from the search range, so that the speed can be increased.

[Brief description of the drawings]

FIG. 1 is a block diagram illustrating a configuration of a route search device according to an embodiment of the present invention.

FIG. 2 is a flowchart for explaining the operation of the route search device according to one embodiment of the present invention.

FIG. 3 is a diagram for explaining one embodiment of the present invention;
FIG. 9 is an explanatory diagram illustrating an example of setting virtual coordinates.

[Explanation of symbols]

 Reference Signs List 101 Graph structure storage means 102 Search range storage means 103 Virtual coordinate storage means 104 First threshold storage means 105 Second threshold storage means 106 Route search means 107 Search range limitation means

──────────────────────────────────────────────────続 き Continued on the front page (58) Fields investigated (Int. Cl. ⁷ , DB name) G01C 21/00 G06F 17/00 G06F 17/30 G06F 17/50 JICST file (JOIS)

Claims (9)

(57) [Claims] 1. Searching a path for a given graph,
In a route search device that outputs a minimum cost route connecting two given nodes, virtual coordinate storage means for storing virtual coordinate values of nodes, and graph structure storage for storing a network structure consisting of arcs connecting the nodes. Means, a search range storage means for sequentially reading a graph structure from the graph structure storage means, and storing a search target range as an intermediate state of a search process; and sequentially reading and writing a search range to the search range storage means. While searching for the shortest cost route from a given departure point node to a destination point node; first threshold value storage means for storing a threshold value of the amount of detour; A region defined by the virtual coordinates of the starting point node and the virtual coordinates of the destination point node stored in the means,
A search range limiting unit that deletes, from the search range storage unit, a route that passes through a node having virtual coordinates that deviates by more than the threshold value of the detour amount stored in the first threshold storage unit; comprising, threshold detour amount stored in the first threshold value storage means
Are the virtual coordinates of the starting point node and the virtual coordinates of the destination node.
Included in the shortest cost path from the area defined by the coordinates
Of the virtual coordinates of all nodes
A route search device , which is a maximum value obtained for all node sets . 2. Searching a path for a given graph,
A route search device for outputting a minimum cost route connecting two given nodes, wherein a virtual coordinate storage means for storing virtual coordinate values of the nodes, and a graph structure for storing a network structure comprising an arc connecting the nodes. A storage unit, a search range storage unit that sequentially reads a graph structure from the graph structure storage unit, and stores a search target range as an intermediate state of a search process, and sequentially reads a search range from the search range storage unit. Route search means for searching for the shortest cost route from a given departure point node to an arrival point node while writing out, a second threshold value storage means for storing a return amount, and storage in the virtual coordinate storage means From the virtual coordinates of the target node in the middle of the search and the virtual coordinates of the destination node, the distance between the target node and the destination node is calculated. The difference between the divergence distance of the immediately preceding node on the route to the node of interest and the divergence distance of the node of interest, obtained by the divergence distance calculation unit for calculating A search range limiting unit that deletes, from the search range storage unit, a route that passes through an arc that is equal to or more than the threshold value of the return amount stored in the threshold storage unit. . 3. A threshold value of a return amount stored in said second threshold value storage means, wherein a threshold value of a divergence distance between all nodes included in the shortest cost route and a node immediately before on the route. 3. The route search device according to claim 2, wherein the difference between the two divergence distances from the arrival point, that is, the return amount, is the maximum value obtained for all node sets. 4. The virtual coordinates stored in the virtual coordinate storage means are converted into numerical values by multivariate analysis of numerical class 4 using the cost of the minimum cost path between all nodes as the degree of difference between the nodes. The route search device according to any one of claims 1 to 3 , wherein the coordinate value is a coordinate value obtained. 5. An apparatus for performing a route search by a computer.
A virtual coordinate storage unit for storing virtual coordinate values of the nodes, and a search for storing a search target range as an intermediate state of the search processing.
The search range storage unit stores the virtual coordinates of the starting point node and the virtual coordinates of the destination point node.
All nodes in the shortest cost path from the defined area
The amount of deviation of the virtual coordinates of the node, that is, the amount of detour
The maximum value obtained for the pair is recorded as the threshold value for the bypass amount.
A first threshold value storage unit for憶comprises, a region defined by (a) and the virtual coordinate storage unit stored in the virtual coordinates of a given starting point node and the virtual coordinates of the destination point node, deviates more than the first storage detour amount threshold storage unit threshold, the route via the node with virtual coordinates, the search range limiting means for deleting from the search range storing unit and, (b) the while sequentially reading and writing the search range for the search range storing unit, the route searching means for searching for a shortest cost path to reach point node from the given starting point node, the (a) and by functioning the respective means in the computer (b), and search for a route for a given graph, find the minimum cost path connecting two nodes given recording medium which records a program . 6. An apparatus for performing a route search by a computer.
A virtual coordinate storage unit for storing virtual coordinate values of the nodes, and a search for storing a search target range as an intermediate state of the search processing.
Search range storage unit, and second threshold storage unit for storing a threshold value of the return amount
When provided with a, stored in (a) the virtual coordinate storage unit, and the virtual coordinates of the search middle node of interest, and a virtual coordinate of a given goal node, with the goal node and the node of interest Divergence distance calculation means for calculating a divergence distance, (b) a difference between the divergence distance of the immediately preceding node on the route to the target node and the divergence distance of the target node, obtained by the divergence distance calculation means, the second of stored backtracking amount threshold storage unit path through arc is greater than or equal to the threshold, search range restriction unit to be deleted from the search range storing unit, and, (c) said search range while sequentially reads and writes the search range to the storage unit, each of the route search means for searching for a shortest cost path to reach point node from the given starting point node, the (a) to (c) Before the means By function in serial computer, search for a route for a given graph, find the minimum cost path connecting two nodes given recording medium recording a program. 7. Searching a path for a given graph,
In a route search method for outputting a minimum cost route connecting two given nodes, a process of obtaining a minimum route cost between each node, obtaining a virtual coordinate of each node by using this as a degree of difference, and solving the all-pair problem again In, the maximum amount detouring around the area between the starting point and the arrival point on the virtual coordinates, and, among the arcs in the route, the maximum amount of the backward movement, which proceeds in the opposite direction to the arrival point, was obtained and obtained. A route search method, wherein the amount of detour and the amount of return are stored as threshold values, and a search range is limited when a minimum cost route search is performed. 8. An area defined by the virtual coordinates of the starting point node and the virtual coordinates of the destination node is searched for a route passing through a node having virtual coordinates that deviate from the threshold value of the stored detour amount or more. The route search method according to claim 7 , wherein the route is deleted from the target range. 9. A divergence distance between the target node and the destination node is determined from virtual coordinates of the target node in the middle of the search and virtual coordinates of the given destination node. In the method, the difference between the divergence distance of the immediately preceding node and the divergence distance of the target node is equal to or greater than the threshold value of the stored return amount. The route search method according to claim 7, wherein: