JPH08166939A - Digital map route simulation method - Google Patents

Abstract

(57) [Summary] [Purpose] To realize high-speed and high-value-added route simulation in digital maps. For example, speeding up can be achieved by a stepwise calculation method or a reverse route calculation method, and high accuracy can be achieved by a sorted node table and road condition estimation processing. [Structure] A node data creation processing unit that sorts link transit times in ascending order, a node data table that stores the results, a digital map data file that stores map information, and a data input processing unit that inputs a departure point, It is composed of a stepwise reachable range calculation processing section including the Dijkstra method and the priority link method, and a result display processing section for displaying a simulation result.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a route simulation method in a digital map using a digital computer, and more particularly, in a method for determining a range that can be delivered within a fixed time at a courier shop, or a dispatch decision support method by taxi, etc. Simulation time is required because of the large number of nodes (vertices, intersections), links (short routes that directly connect adjacent nodes, roads between intersections), and the number of routes (sets of links that connect any node to any node) The present invention relates to a route simulation method for a digital map, which is suitable when the road condition changes depending on the conditions of time and place.

[0002]

2. Description of the Related Art Conventionally, as a route simulation method on a digital map, for example, the Dijkstra method described in Chapter 4 of Kiyoshi Ishihata's "Algorithm and Data Structure" (Iwanami Shoten, 1989) has been proposed. There is. This method is a method in which the shortest route of each node is determined one by one from a position close to the starting point, which is extremely accurate, but has a problem that it takes too much processing time. The digital map means a map drawn using a digital computer. The Dijkstra method will be described below. FIG. 27 is an explanatory diagram of the Dijkstra method. (1) Initialization As shown in FIG. 27, nodes n0, n1, n3, n5,
And nodes n0, n1, n4, n6, and node n
It is assumed that there are paths 0, n2, n7 and nodes n0, n2, n8. Now, let V be the set of nodes whose arrival time is fixed, U be the set of undetermined nodes, and W be the set of confirmed candidate nodes whose arrival time is being calculated, as shown in FIG. 27. To set. Each node included in the set U is given a time (hereinafter referred to as a link transit time) required for moving from the node (hereinafter referred to as a corresponding node) to a node connected to the corresponding node (hereinafter referred to as an adjacent node). First, U, V and W are all set to an empty set (empty each register). Next, the following processing is performed. A starting point n0 is added to the set V of confirmed nodes (n0 is added to the V register).
Store). All n0 adjacent nodes are added to the set W of decision candidate nodes (n1 and n2 are stored in the W register). All other nodes are added to the set U of undetermined nodes (stored in the U register at n3 to n8). Also, a variable d [n0] representing the arrival time from the departure point is set to 0 (d is a register in which the arrival times are arranged). Furthermore, for all nodes other than the starting point, d [ni] is set to infinity (a value larger than any calculation result).

(2) While the finalized candidate node W is not an empty set, the following processing is repeated. (2-1) W is the element p with the smallest arrival time
Is added to V (the distance from the starting point n0 to n1 is compared with the distance from n0 to n2, and n1 is smaller, so it is removed from W (x) and stored in V (arrow)). (2-2) The following processing is performed for all adjacent nodes x of p.
If x belongs to U, remove x from U and add to W (remove adjacent nodes n3 and n4 of n1 from U (x) and store in W (arrow)). When the arrival time of the route reaching via p is shorter than the arrival time obtained so far, the arrival time of x is rewritten (each distance up to n2, n3 via n1 and n4 is compared to n2. Is the smallest, and then n3 is smaller, so n2, n3, n
4 is transferred from W to V and stored, then n1 in the d register
Is rewritten to the obtained distance, and then n2, n3, and n4 are rewritten. ). Similarly, via n2, n7, n
N5 or n via distances up to 8 and n1, n3
Compare the distance to n6 via 1, n4, n8, n7
The order is smaller, and then the order is m5 and n6. Therefore, except for n8, n7, n5 and n6 in the U register, they are stored in the W register in this order. Next, these n8, n7, n
After moving 5 and n6 from W to V and storing them, the value of d is rewritten. In short, the Dijkstra method is a method in which roads in a digital map are linked to each other, intersections are regarded as nodes, and the shortest route of each node is determined one by one starting from a point near the starting point. In this case, it is necessary to determine whether or not there is a link connecting n2 and n4. When there is, a distance to reach n7 and n8 via n2 and n4 and n6 via n2. Also compare the distance to reach.

Next, as a method that can be easily inferred from the Dijkstra method, there is a priority link method for sequentially searching for nodes. The outline of the priority link method is described below. FIG. 28 is an explanatory diagram of the priority link method. (1) Initialization First, U, V, and W are all set to an empty set. Next, the following processing is performed. A starting point n0 is added to the set V of established nodes. All n0 adjacent nodes are added to the set W of confirmed candidate nodes in ascending order of link transit time (n1, n3, n
2 is stored in W). All other nodes are added to the set U of undetermined nodes (n4 is stored in U). Further, the variable d [n0] representing the arrival time from the starting point is set to 0. Further, d [ni] is set to infinity for all nodes other than the starting point. Unlike the Dijkstra method, in the Dijkstra method, the shortest routes are determined one by one starting from a point near the starting point and stored in V. In the priority link method, however, the shortest link transit time is added when W is added. Since it is added and V is added in that order, rapid processing is possible. (2) While the finalized candidate node W is not an empty set, the following process is repeated. (2-1) In the element of W, the node p added at the beginning is removed from W and added to V. (2-2) For all adjacent nodes x of p, the following processing is performed in the ascending order of link transit time. If x belongs to U, remove x from U and add to W. Write the arrival time of x. When the calculation is incorrect, for example, in FIG. 28, when n1 and n3 are added to W in the order closer to the starting point n0, they are added in the correct order, but then n4 is passed via n3.
There is a risk of misjudging that the distance to reach to is smaller than the distance to reaching to n2 and adding to W. In short, the priority link method is a method of establishing nodes in the order of addition to W. The difference between the priority link method and the Dijkstra method lies in the method of determining the element to be transferred from W to V in the procedure (2-1).
The Dijkstra method examines all elements of W before making a decision, whereas the priority link method moves elements to V in the order in which they are added to W. Therefore, although the arrival time has an error, high-speed calculation is possible.

Further, a stepwise search method which is a practical method for a map will be described. Above method (priority link method)
However, if the processing time does not meet the requirement, there is a method of speeding up the apparent processing time by performing a stepwise search. A known stepwise search method will be described below. (1) First, the main highways such as highways and national roads are searched, and the reachable range is estimated and displayed. (2) Next, search including prefectural roads and other semi-main trunk roads, estimate the reachable range, and display it. (3) Finally, all roads including branch roads are searched and the reachable range is estimated and displayed. As described above, the known stepwise search method can display the tentative result in a timely manner, so that the time until the result is displayed is apparently shortened.

[0006]

As described above, when the reachable range within the set time is obtained by using the point on the digital map as the starting point by the Dijkstra method or the priority link method, there are the following problems. . (1) When the Dijkstra method is used, the processing time increases as the number of nodes increases. Further, in the priority link method, if there are a plurality of routes, an error will occur if the one that is not the shortest route is calculated first. Since the error is proportional to the route length, there is a problem that the shortest route search error increases as the simulation range expands.
Although the known stepwise search method apparently speeds up the calculation process, it has the problem that the error cannot be reduced and the processing time until the search for all roads is completed is the same or longer. In particular, if an error occurs near the starting point or on a main highway, it will spread to the peripheral areas and branch roads of the reachable range, causing a large error. In addition, the peripheral portion and the branch road do not cause a large error, but since the number of links is large, the processing time increases. (2) In the priority link method, the route with a small number of nodes is considered to be the shortest, so if the deviation of the link transit time is large,
An error may occur because a route with a small number of passing nodes and a long route transit time is calculated first. (3) When the rough moving direction from the starting point is known, it is possible that the actual reachable range is not the direction other than the moving direction. In the conventional method, since the moving direction is not considered, there is a problem that a range wider than the actual reachable range is calculated.

(4) When the reachable area that crosses the administrative boundaries (boundaries of prefectures and municipalities) is displayed, a single color display may cause the user to misunderstand the administrative boundaries (for example, administrative boundaries of fire engines and ambulances). Difficult). (5) For example, in the case of pizza delivery or taxi dispatch, it is necessary to find the shortest reverse route in order to return to the origin from within the reachable range as a return route. When the shortest reverse route is calculated, if the forward and return paths have the same link transit time, there is a problem that the reachable range calculation and the shortest reverse route calculation take more processing time. Further, when the forward path and the return path have different link transit times, the forward path of the reachable range calculation result is not equal to the shortest reverse path of the return path, and therefore the reachable range calculation and the shortest reverse path calculation need to be performed independently. At this time, the route calculation process from a plurality of arrival points has to be repeated for the number of arrival points, which causes a problem that processing time is required. (6) In order to perform accurate route simulation, it is necessary to set the link transit time according to the road conditions of the road. If the road condition of the road is unknown, it is necessary to estimate it by using the road condition of the adjacent road and the road condition of the main roads around it. If the link transit time deviates from the actual value, an error occurs in the Dijkstra method or the priority link method. An object of the present invention is to solve these conventional problems and to provide a route simulation method for a digital map that can realize high-speed and high-value added route simulation of a digital map. More specifically, the step-by-step route simulation method and the reverse route calculation method that uses the reachable range calculation results enable speedup without degrading accuracy, and link accuracy is sorted in order of decreasing link transit time. By using the data table and the method of estimating the road condition of the surrounding branch roads according to the road condition of the main highway from which the measured value is obtained, it is possible to improve the accuracy without deteriorating the speed.

[0008]

In order to solve the above-mentioned problems and problems of the prior art, the following points are important features of the present invention. (1) The high-precision Dijkstra method is used to calculate the route around the starting point or the main trunk road where the number of nodes is relatively small and accuracy is required. The number of nodes is large but the accuracy is not required. The high-speed priority link method is used to calculate the route. At this time, there is a method of switching between the Dijkstra method and the priority link method, and a method of gradually shifting from the Dijkstra method to the priority link method, so either one is used. (2) When the deviation of the link transit time is large, a virtual node is provided in the middle of the long link, and it is divided into a plurality of short links, and the transit times of all the links are roughly aligned. (3) If the rough moving direction from the starting point is known, increase the route transit time of the route other than the moving direction. As a method of increasing the route transit time, a method of increasing a link transit time in a direction other than the moving direction, a method of increasing a time required to pass a node in a direction other than the traveling direction (node transit time), and a method different from the moving direction There is a way to increase the link transit time of facing links. There is also a method of rejecting routes other than the moving direction after calculating the reachable range. One of these may be used. (4) When displaying results, use different colors, line types, and tile patterns for each administrative world. The tile pattern is a pattern using various patterns for each section. (5) When calculating the shortest reverse route to return to the origin from within the reachable range, if the forward and return trip link transit times are the same, the shortest forward route calculated with reachable range calculation is the shortest reverse route. Output the reverse path. When the forward and return link transit times are different, the shortest reverse route from any node within the reachable range is calculated by calculating the reachable range from the starting point using the reverse route link transit times. . (6) The link transit times of the surrounding branch roads are estimated according to the road conditions of the main trunk roads where the actual measured values of the link transit times are obtained. Also, the link transit time is updated based on the measured value and the estimated value.

[0009]

The above-mentioned characteristic points have the following functions, respectively. (1) By using the highly accurate Dijkstra method near the starting point and on the main highways, the error factors that spread to the peripheral areas and branch roads are eliminated. The increase in processing time is small because the ratio of these links is relatively small. Further, in the peripheral portion or branch road with a large number of links, the use of the fast priority link method eliminates the factor of increasing the time required to calculate the reachable range. Since the error generated in this portion does not spread to other portions, it is possible to prevent an increase in the reach range calculation error. This makes it possible to suppress an increase in path error and reduce the calculation time. (2) By providing a virtual node in the middle of a long link and dividing it into a plurality of short links, it is possible to reduce the deviation in link transit time. As the deviation of the link transit time decreases, the number of routes with a small number of transit nodes and the route with a long link transit time decreases. This makes it possible to reduce the error when the priority link method is used. (3) By increasing the link transit time or node transit time on a route other than the traveling direction, the route transit time in that direction becomes longer and the reach range becomes narrower. Further, after the reachable range is calculated, routes other than the moving direction are rejected, so that only the route heading in the same direction as the moving direction remains. As a result, it is possible to obtain a result in accordance with the actual reachable range in consideration of the initial moving direction. (4) The visibility of the display result is improved by changing the color for each administrative world. As a result, it is possible to reduce the possibility that the user will misunderstand the administrative world. (5) By outputting the shortest reverse route using the reachable range calculation result, the shortest reverse route for returning to the origin from within the reachable range can be obtained at high speed. This makes it possible to shorten the calculation time of the route simulation. (6) By estimating the road condition of the surrounding branch roads according to the road condition of the main trunk road and updating it sequentially, the transit time of the road where the sensor is not installed can be brought close to the actual value. As a result, it is possible to improve the accuracy of the route simulation.

[0010]

【Example】

<First Embodiment> An embodiment of the present invention will be described below in detail with reference to the drawings. FIG. 1 is a functional block diagram of a deliverable range determination support system showing a first embodiment of the present invention, and FIG. 2 shows the function of the deliverable range determination system using a display screen of a car navigation system as an example. It is a figure explaining. The system of the present embodiment is a system for supporting the determination of the deliverable range within a fixed time at a home delivery shop, for example, and will be described with reference to FIGS. This system determines the range that can be delivered within the scheduled time by inputting the current location and the delivery time on the map displayed on the display. The time required to pass the road changes every moment due to traffic congestion, etc., so the road conditions of the main highways are input by sensors. A road node table is created in advance based on these pieces of information and a digital map, and is used for reachable range calculation. The outline of the function of this system will be described with reference to FIG.
For the road 260 (dotted line in the figure) and the main delivery point 200, etc. (○ in the figure) displayed on the screen, the delivery person determines the current position (● in the figure) 230 and the estimated delivery time to determine the deliverable range. By inputting into the system, the deliverable range (reachable road 220) within the scheduled driving time is displayed as a solid line in the figure, and the main deliverable point 240 etc. in the area (in the solid line in the figure) (in the figure) Double circle mark) is displayed. The thick line in the figure is a major highway. In this case, the node data creation process 110
Then, the lengths of the links (distances between the intersections) are made substantially equal, and when the deviation of the links is large, the links are divided and the lengths are aligned with other links. Further, in the stepwise reachable range calculation processing 150, a high-speed and high-precision search is realized by combining the high-speed bond search method and the high-precision search method. For example,
The thick main roads are calculated using the high-precision Dijkstra method, and the other branch roads are calculated using the high-speed priority link method. It should be noted that it is possible to search the vicinity of the starting point with high accuracy and the peripheral part at high speed. Further, in FIG. 2, when delivering from the departure point 230 to the deliverable point 210, the link transit time is calculated in the shortest time for the link parallel to the road directly connecting both points, and for the other links. As a result, the transit time may be increased, or the link transit time may be maximized for a link perpendicular to the road directly connecting both points, and the other links may be calculated in a short time.

The details of the processing in this embodiment will be described below with reference to FIG. The node data creation process 110 and the stepwise reachable range calculation process 150 are processes within the computer, and the digital map data file 100 and the node data table 120 are included.
Are files and tables stored in the memory of the computer. The data input 140 and the output device 130 are input / output devices, and the result display processing 160 is processing in the input / output control device and the computer. 3 is a functional block diagram of the node data creation processing unit in FIG. 1, and FIG. 4 is an operation flowchart of the node data creation processing unit. 1． Node data creation processing 110 Creates a road node data table 120 from the digital map data file 100. Node data creation process 110
Has a functional configuration as shown in FIG. 3 and is executed by the flow of FIG.

(1) Processing for creating a main trunk road condition data table 315 FIG. 5 is a diagram showing a format of the main trunk road condition data table in FIG. 3, and FIG. 6 shows a format of the digital map data file in FIG. FIG. The congestion status of the road and the average vehicle speed that change every moment are used as road information 335. Therefore, a main road condition sensor 310 for measuring road information 335 is installed on a main road.
The main trunk road condition data table creation processing 315 creates a main trunk road condition data table 340 based on the main trunk road information 335 input from the main trunk road condition sensor 310 and the digital map data file 100. The main trunk road condition data table 340 has a structure as shown in FIG. Of these, the node number 510 of the main trunk line, the number of adjacent nodes 520, and the node pointer 530 are copied from the digital map data file 100. As shown in FIG. 6, the digital map data file 100 has an X coordinate 600 and a Y coordinate.
610, the number of adjacent nodes 620, the number of adjacent nodes 640, a main trunk road flag 630, and a link length 650 are stored. In the main highway flag 630, when a sensor is installed on a link to an adjacent node (shown by 1), when the sensor is not installed on a main highway (shown by 2), when a branch road is shown (0). (Indicated by) is stored. Using this flag 630, a high-precision search can be performed when the flag is 2, and a high-speed search can be performed when the flag is 0.

FIG. 7 is a schematic diagram of intersections and roads for explaining the present invention. The main highway sensor 310 is, for example, a vehicle sensor installed on the road, measures the density and average speed of the vehicles passing on the main highway among the roads 250 in FIG. 2, and calculates the vehicle traffic density 550 in FIG. Save to vehicle average speed 540. For example, in FIG. 7, when a sensor is installed on the road from the node (49) to the node (51), the following processing is performed. Then k
= 0. First, the data of the node (49) on the digital map data file is searched for the one having the adjacent node number of 51. In this example, i = 49 and j = 2. In this case, i is the value of 51 to i in the margin of FIG. 6, 49 is the value that should be entered in the uppermost row, and j is the main highway flag 2 (sensor is not installed). is there. Therefore, the node number (49) and the adjacent node pointer (j) are written in the main road condition table. 2 is written in the adjacent node pointer. Finally, write the average speed and vehicle traffic density input from the sensor, and add 1 to k.
By repeating the above processing for the number of sensors, the main trunk road condition data table 340 is created.

(2) Road Condition Calculation 320 FIG. 8 is a diagram showing the format of the road condition data table in FIG. Initial values of the road condition data table 345 are created. The road condition is calculated by the road condition calculation process 320 using the rules stored in the road condition rule data table 300, the digital map file 100, and the data stored in the main trunk road condition data table 340. FIG.
First, in the main trunk road condition data table
Initialization 310 of 340 is performed (step 410). That is, the vehicle traffic density 840 and the vehicle average speed 830 of the road condition data table 345 are set to 0. Next, the contents of the main trunk road condition data table 340 are transferred to the road condition data table 345.
420, and sets the decision flag to 1 (step 420). Set the decision flag to 0 for undecided links. When a link adjacent to an uncalculated link (decision flag is 0, that is, vehicle traffic density 840 and vehicle average speed 830 are not calculated) on the road condition data table 345 has been set (step 43).
0), calculate uncalculated link transit time (step 440).
Repeat this process until there are no uncalculated links
(Step 450). In the road condition setting rule table 300,
For example, the following rules are stored. Variables are in parentheses, and func is a function.

Rule: node (x0) to node (x1)
When the link speed qv [x0] [x1] to the node is known and the number of other known links is (m [x1]), the link speed qv [(x1)] [from the node (x1) to the node (x2). (X2)] is (fu
nc ((qv [x1] [x2]) (qv [x0] [x1]), m [x
1])). For example, the following rules are stored in the road condition rule data table 300. Specific rule: When the link speed dv [50] [51] from the node (50) to the node (51) is known and the number of other known links is (2), the node (51) to the node (52). Link speed dv [(51)] [(52)] to (dv [50] [51] + dv
[50] [51] / 2).

(3) Contradiction cancellation processing 325 FIGS. 9 and 10 are diagrams showing the format of the adjacent road correlation coefficient table in FIG. Here, the contradiction in the road condition data table 345 is offset. The contradiction cancellation is performed in the contradiction cancellation process 325 by using the data table 345 and the adjacent road correlation table 305 in the road condition created in the road condition calculation process 320. If there is a contradiction during the calculation,
For example, if there is a large number of vehicles flowing into the entrance of an intersection but there is no vehicle leaving, the contradiction is resolved by the stochastic relaxation method. The probabilistic relaxation method is a method of estimating the situation of a point of interest from the surrounding situation. The situation of the point of interest is obtained by the degree of influence of a surrounding point on the point of interest and the sum of products of the situation of the point.
(For details on this, see, for example, "SPID
ER USERS MANUAL "(SPIDER working group, published in 1989)
Please refer). In the case of the above example, a change is made to the established link (step 460). That is, the number of vehicles on the link that flows into the intersection is reduced and the number of vehicles on the link that flows out is increased. The road condition of the link connecting the node x1 to the node x2 is calculated using the adjacent road correlation table 305 and the road condition data table 345. The vehicle speed of the link connecting node x0 to node x1, and node x
The strength of the relationship between the links from 1 to the node x2 is stored in advance in the correlation coefficient on the adjacent road correlation table.

For example, in FIG. 7, the nodes (51) and (52) are both three-forked, and the nodes (51) to (52) are connected.
Vehicles flowing into the link connected to the node (50) and the node (49) flow out, and vehicles flowing out to the nodes (53) and (54) flow out. At this time, the number of links (relational links) related to the node (51) to the node (52) is 920.
Is 5, including myself. The number of adjacent nodes bn [51] of the node (51) is 3, adjacent node numbers bc [51] [0], bc [5
1] [1], bc [51] [2], (49), (50), (5
If the value 2) is stored, the number of relational links bl [5
5 is stored in 1] [2]. The relation link start point 930 stores the start point node number of the relation link. In addition, the relational link pointer 940 stores the information "where in the start point node information each link information is stored". For example, when bs [51] [2] [0] is 49, the vehicle average speed from nodes (49) to (51) is dv [49] [bp [51] [2] [0] on the road condition table. ].

On the other hand, in velocity ← velocity correlation coefficient 950,
In bvv [51] [2] [0], the influence of the vehicle average speed of the link connecting the nodes (49) and (51) on the vehicle average speed of the link connecting the nodes (51) and (52) is large. Is stored. Speed ← bvm [51] [2] at the density correlation coefficient 960
In [0], the magnitude of the influence of the vehicle traffic density of the link connecting the nodes (49) and (51) on the vehicle average speed of the link connecting the nodes (51) and (52) is stored. Velocity ← In velocity correlation coefficient 950, bmm [51] [2] [0] has the vehicle traffic density of the link connecting the nodes (49) and (51) to the link connecting the nodes (51) and (52). The magnitude of the effect on vehicle traffic density is stored. Density ← Velocity correlation coefficient 980
In bmv [51] [2] [0], nodes (49) and (5
The average vehicle speed of the link connecting (1) is calculated from nodes (51) and (5
The magnitude of the influence of the link connecting 2) on the vehicle traffic density is stored.

Vehicle speed and density of all links involved,
And the road condition of the link connecting the nodes (51) and (52) is recalculated based on the degree of mutual influence. For example, when the stochastic relaxation method is used, the average speed of this link is calculated as follows. qv [bl [51] [2] [0]] [bp [51] [2] [0]] x bvv [51] [2] [0] + qv [bl [51] [2] [1]] [bp [51] [2] [1]] × bvv [51] [2] [1] + qv [bl [51] [2] [2]] [bp [51] [2] [2]] × bvv [51] [2] [2] + qv [bl [51] [2] [3]] [bp [51] [2] [3]] × bvv [51] [2] [3] + qv [ bl [51] [2] [4]] [bp [51] [2] [4]] × bvv [51] [2] [4] + qm [bl [51] [2] [0]] [bp [51] [2] [0]] × bvm [51] [2] [0] + qm [bl [51] [2] [1]] [bp [51] [2] [1]] × bvm [ 51] [2] [1] + qm [bl [51] [2] [2]] [bp [51] [2] [2]] × bvm [51] [2] [2] + qm [bl [ 51] [2] [3]] [bp [51] [2] [3]] × bvm [51] [2] [3] + qm [bl [51] [2] [4]] [bp [51 ] [2] [4]] × bvm [51] [2] [4] where qv is the link speed, bvv is the vehicle average speed, qm is the vehicle density, and bvm is the vehicle traffic density of the link. The vehicle traffic density is calculated in the same manner. The calculation ends when there is no contradiction between the vehicle traffic density and the vehicle average speed. In order to confirm that the contradiction disappears, for example, the vehicle traffic density before recalculation and the vehicle average speed are saved and compared with the value after recalculation 470, and the difference between the two is below a certain threshold. If so, the process proceeds to the next process.

(4) Road Node Data Table Creation 330 FIG. 11 is a diagram showing the format of the node data table in FIG. As shown in FIG. 3, sorted node data table 35 is arranged in ascending order of link transit time.
0 and the main trunk road node data table 355 are created. To create the node data table 120, the digital map data file 100 and the road condition data table 345 are used. The link transit time 1040 is calculated by the vehicle average speed 840 × link length 650. For each node, adjacent node numbers and link transit times are sorted 480 in ascending order of link transit time. For example, in FIG. 7, the node (5
The nodes adjacent to 2) are node (51), node (53),
These are the three intersections of the node (54). Therefore, the number of adjacent nodes in the 52nd item of the node table is 3. In addition, when the link transit time from the node (52) is arranged in ascending order, the node (54), the node (53), and the node (51) are obtained. Therefore, as the adjacent node numbers, the values (54), (53), and (51) are stored in order.

2. Data Input 140 FIG. 12 is a functional block diagram of stepwise reachable range calculation processing, FIG. 13 is an operation flowchart of stepwise reachable range calculation processing in FIG. 12, and FIGS.
6 is a diagram showing a display example of the stepwise reachable range calculation result in FIG. 12, and FIG. 17 is a diagram of the reachable range table. In the data input 140 of FIG. 1, the delivery destination and the scheduled driving time are input. For example, when a position is specified on the map using a mouse, x and y coordinates are input. The node closest to the input x, y coordinates is searched from the road node data table and set as the delivery destination node is. Separately enter the scheduled driving time t using the keyboard. At this time, a map may be displayed in advance. In that case, the contents of the digital map data file 100 including the delivery destination and the road node data table 120 are displayed as a vector map on the display device 130 such as a car navigation system. 3. Stepwise reachable range calculation process 150 and result display process 160 Based on the above input data, the reachable range reachable within the planned driving range is calculated and displayed on the display device 130 such as the car navigation system. To calculate the reachable range,
Consider the contents of the road node data table 120. The process for calculating the reachable range that can be reached within the scheduled driving range is a stepwise reachable range calculation process 150 for calculating the reachable range stepwise as shown in FIG.
The flow is as shown in. First, calculation processing 1100 from the starting point to the main highway is performed. Next, a route calculation process 1110 for the main trunk road for calculating the reachable range on the main trunk by the Dijkstra method is performed. Finally, branch road route calculation processing 1120 for calculating the reachable range of all roads including branch roads by the priority link method is performed. 14 to 1
6 shows a process of performing the simulation step by step. The reachable range calculation 70 will be described in detail with reference to FIGS. 12 and 13. The reachable range table is
17 is a table as shown in FIG.
It is composed of an X coordinate 1410 of a node, a Y coordinate 1420, an arrival time 1430 from a starting point, and an adjacent node number (node number 1440 of the source node) through which each node is reached.

(1) Route calculation processing to the main trunk road 110
As shown in FIG. 13, first, the arrival times of all nodes on the reachable range possibility table 1140 are set to values larger than all arrival times (step 1205). For example, if the maximum arrival time does not exceed 99999 minutes, set it to 99999. Next, reachable range calculation processing is performed from the starting point node is to the starting point (step 1210). This processing is performed by the Dijkstra method or the sequential calculation method. A process of sequentially writing the arrival time 1430 (determined arrival time in the case of the Dijkstra method) to each node obtained in the calculation progress in the reachable table 1140 is performed (step 1215). Further, the number of the adjacent node (source node 1440) through which each node is reached is written in the reachable table 1140. For example, in FIG. 7, when the node (48) is the starting point, the node (51)
The source node 1440 of is the node (50). When the node on the main highway is reached, the result is displayed (step 1220). In FIG. 7, nodes (51) to (5
When the road to 2) is a main road, the result is displayed when the node (51) is reached (160 in FIG. 11), and the process proceeds to the next step.

(2) Route calculation processing 1110 for main roads When the road is reached (step 1220), the node is used as a starting point (step 1225), and reachable range calculation processing is performed by the Dijkstra method (step 1230). . In the process by the Dijkstra method, the route is calculated only for the main road. A process of writing the arrival time 1430 and the source node number 1440 to each node obtained here to the reachable table range table 1140 is performed (step 1235). When the arrival time exceeds the delivery time t, that is, when the search for the main road is completed (step 1240), the result is displayed (160), and the process proceeds to the next step. (3) Branch road route calculation processing 1120 The starting point is set again as the starting point (step 1245), and the reachable range calculation processing is performed by the sequential calculation method. This process is performed for all roads. First, it is checked whether the reachable range result has been calculated for the node to be calculated (step 1250). If it is already calculated, copy the result from the reachable range table to the simulation table.
(Step 1255), and let it be the simulation result.
If it has not been calculated, the reachable range from the starting point is calculated by the priority link method (step 1260), and the result is written in the reachable range table (step 1265). Since all the nodes on the main road have been calculated by the Dijkstra method, error correction is performed when passing through the nodes on the main road. For example, in FIG.
Since the node (52) is connected to the main road, the reachable range calculation process from the starting point (step 1260) is not performed, and the result of the Dijkstra method is copied to the simulation table (step 1255). In the arrival time calculation processing of the node (54) and the node (53), the route error to the node (52) is 0, so the route error to the node (52) is 0.
The error is smaller than the general priority link method. After the processing is completed (step 1270), the result display (160) is performed.

The above is a detailed embodiment of the stepwise reachable range calculating method of the present invention. In the method of the present embodiment, a system that determines the range and action time that can be supported by fire engines and ambulances by calculating the action range within a certain time, the support range such as the location of a courier's collection point and pizzeria, convenience store, etc. It can also be used for a decision making system and a decision command support system for deployment points in the police. In the suburbs of the city, the flow of vehicles changes in the morning and evening, and the range that can be supported also changes significantly. Normally, the up road is crowded in the morning and the down road is crowded in the evening. When there are a plurality of delivery destinations, the delivery time can be shortened by delivering from the delivery point delivering in the downward direction in the morning and from the delivery point delivering in the upward direction in the evening. In addition,
In the contradiction cancellation processing, in addition to the probabilistic relaxation method, a statistical relaxation method (relaxed by a statistical table), a neural network,
It is possible to use GA (genetic algorithm), rule-based processing, link speed average value, or link speed intermediate value to perform the relaxation processing.

<Second Embodiment> The second embodiment is a vehicle allocation decision support system such as a taxi. The vehicle allocation decision support system is a system that assists a person who directs a vehicle allocation to make a vehicle allocation decision such as a taxi. FIG.
FIG. 6 is an explanatory diagram of a vehicle allocation determination support system showing a second embodiment of the present invention. The present embodiment is a system that assists a customer in deciding the allocation of a vehicle that can go straight in the shortest time when there are a large number of moving taxis. The outline of the function of this system will be described with reference to FIG. FIG. 18 is a window screen of a workstation, for example. The conductor displays the range (reachable range 1510) that can be dispatched within the scheduled driving time by inputting the customer's current position (marked with ● in the figure) 1540 and the scheduled dispatch time to the dispatch decision support system (in the figure) The solid line) is displayed, and the information (1) in the area where the vehicle is located (double circle in the figure) and the road that can be reached in the shortest time (the thick line in the figure) is displayed. It should be noted that the white circle 1500 is the point where the vehicle currently exists, and there are four vehicles including the double circle. Among them, the vehicle that can reach the customer in the shortest time is the double circle 1550.
The details of the processing in this embodiment will be described below by the deliverable range determination system of FIG.

1. Node Data Creation Processing 110 First, the node data table 120 is created from the digital map data file. This is the same processing as that of the first embodiment, but if the link transit time differs between the forward path and the return path, the following processing is performed in the node data creation processing 110. That is, the forward route link information and the backward route link information are exchanged to create a reverse route calculation processing node table. The configuration of the reverse route calculation processing table is the same as the node data table 120. 2. Data input 140 Enter the current position and scheduled driving time of each vehicle. This is also the same processing as in the first embodiment.

[0027] 3. Calculation of reachable range Based on input data of 150 or more, reachable range within the planned operation range is calculated. This is also the same processing as that of the first embodiment, but if the link transit time differs between the forward path and the return path, the reverse route calculation processing node table is used. Four. Reverse Route Calculation 1600 and Result Display Processing 160 FIG. 19 is a functional block diagram of the reverse route calculation processing unit.
20 is a detailed block diagram of the reverse route calculation processing unit in FIG. 19, and FIG. 21 is an operation flowchart of the reverse route calculation processing unit. Using the vehicle position within the reachable range and the reachable range calculation result, the round trip path of each vehicle is calculated and displayed. The difference from the first embodiment is that a reverse route calculation processing unit 1600 is provided as shown in FIG. The details of the reverse route calculation processing unit are composed of a reachable vehicle search process 1700 and a route calculation process 1710 as shown in FIG. 20, and the flow is as shown in FIG. The reverse path calculation processing 1600 will be described in detail with reference to FIGS. 19 and 20.

(1) Reachable vehicle search processing 1700 A node number in which all vehicles are present is checked, and a vehicle whose arrival time to the node number is within the scheduled driving time is a reachable vehicle. Processing is performed to check the node number of reachable vehicles and the total number of reachable vehicles (step 1810). In addition,
A method is also conceivable in which the process of performing route calculation processing by checking whether or not one vehicle is reachable is repeated. (2) Route calculation processing 1410 Route calculation processing is performed for reachable vehicles. The vehicle location node i1 is set to the reverse route search node n (step 1820). Next, reachable range table 1
Using 140, search 1830 for source node m [i1] = i2 for n. The source node i2 is set as the reverse path search node n (step 1840), and a new source node m [i2] is searched (step 1830). This process is repeated until n becomes the customer position node (step 1850). For example, in FIG. 7, when the departure node is the node (48) and the vehicle is at the node (53), n = 53. The source node of the node (53) is the node (52), and the source node of the node (52) is the node (5
1), ..., Recursively obtained, and when n = 48, the process ends. As a result, the route to be passed is calculated. When there are a plurality of vehicles, the shortest route calculation process is repeated by the number of vehicles until all vehicles have been calculated (step 1860).

5. Result display 160 The result of the route simulation is displayed on the digital map shown in FIG. The thick arrow 1520 is the calculation result. The above is a detailed example of the reverse route calculation using the reachable processing result of the present invention. In a home delivery / business trip service such as a pizzeria with a plurality of stores, it is determined from which store the delivery / business trip is to be performed. It can also be used for command support. The delivery conductor inputs the delivery destination and the estimated delivery time into the deliverable range determination support system to obtain the closest delivery vehicle within the maximum movement range and the forward and return road information that the delivery vehicle can reach in the shortest time. You can decide. It can also be used in fire command, ambulance, and command support systems for deciding express vehicles to the accident site in police. In such a case, by outputting the main arrival points (delivery destinations and deployment locations) using a table as shown in FIG. 22, it is possible to assist in determining which delivery destination to go to. In addition, as shown in FIGS. 23, 24, 25, and 26,
By taking out the node information by using the pointer of the node number, the speed can be further increased.

In FIG. 22, the deployment locations (1, 2, 3, ...) Are prepared in advance in the deployment location table, and the deployment locations are searched using the simulation table (1). Next, the result is stored in the deployment result table (2). Next, the deployment location is displayed on the map (3). The map is represented by the node numbers and coordinates in the node table. Next, the place name is transferred from the deployment decision table to the deployment location table and entered. 23 and 24 show tables for searching a candidate node or a simulation node by the candidate node and the address point, respectively. In each table, the node number, arrival time, calculation status, and caller node number are registered. FIG. 25 is a node number table in which a target node and an adjacent node are registered. FIG. 26 is a diagram showing a police car search method that can be applied to a command support system that determines a fire engine, an ambulance, and an express vehicle to an accident occurrence site in a police station. First, a candidate police car is searched from the simulation table by using the node number of the police car from the police car table. A node number, arrival time, calculation status, and caller node number are registered in the simulation table. Next, after the police car is determined, in order to search the police car route, the police car route table is looked up, the node table is searched by the node number of the relevant police car, and the route of the express police car and the police car is displayed. The node number of the route and its coordinates are registered in the node table.

[0031]

As described above, according to the present invention,
It is possible to realize high-speed route simulation and high added value in digital maps. For example, a step-by-step route simulation method or a reverse route calculation method that uses the reachable range calculation result can speed up the process without degrading the accuracy, and nodes that sort link information in ascending order of link transit time By using the data table and the method of estimating the road condition of the surrounding branch roads according to the road condition of the main trunk road from which the measured value can be obtained, it is possible to improve the accuracy without deteriorating the speed.

[Brief description of drawings]

FIG. 1 is a functional configuration diagram of a delivery destination determination command support system showing a first embodiment of the present invention.

FIG. 2 is a diagram of a simulation display example of a delivery destination determination command support system.

FIG. 3 is a detailed configuration diagram of a node data creation processing unit in FIG.

FIG. 4 is a flowchart of node data creation processing in FIG.

5 is a diagram showing a format of a main trunk road condition data table in FIG.

FIG. 6 is a diagram showing a format of a digital map data file in FIG.

FIG. 7 is a schematic diagram of an intersection and a road for explaining the present invention.

FIG. 8 is a diagram showing a format of a road condition data table in FIG.

9 is a diagram showing a part of the format of an adjacent road correlation coefficient table in FIG.

FIG. 10 is a style diagram showing another part of the adjacent road correlation coefficient table.

FIG. 11 is a diagram showing a format of a road node data table in FIG.

12 is a configuration diagram of a stepwise reachable range calculation processing unit in FIG.

13 is an operation flowchart of stepwise reachable range calculation processing in FIG.

FIG. 14 is a diagram showing a display example of a stepwise reachable range calculation result (No. 1).

FIG. 15 is a diagram showing a display example of a stepwise reachable range calculation result (part 2).

FIG. 16 is a diagram showing a display example of a stepwise reachable range calculation result (part 3).

FIG. 17 is a diagram showing a format of a reachable range table necessary for the calculation process of FIG. 1.

FIG. 18 is a diagram showing a simulation result display example of the vehicle allocation determination support system according to the second embodiment of the present invention.

FIG. 19 is a configuration diagram of reverse path calculation processing result output processing.

20 is a detailed configuration diagram of a reverse route calculation processing unit in FIG.

FIG. 21 is a flowchart of a reverse route calculation processing unit in FIG.

FIG. 22 is a diagram of a deployment location search table according to the present invention.

FIG. 23 is a simulation table diagram used in the high precision search method of the present invention.

FIG. 24 is a simulation table diagram used in the high-speed search method of the present invention.

FIG. 25 is a reachable range calculation processing result table of the present invention.

FIG. 26 is a part of a reverse path calculation processing table of the present invention.

FIG. 27 is an explanatory diagram of a conventional Dijkstra method.

FIG. 28 is an explanatory diagram of a conventional priority link method.

[Explanation of symbols]

100 ... Digital map data file, 110 ... Node data creation process, 120 ... Node data table, 130 ... Display, 140 ... Data input device, 150 ... Stepwise reachable range calculation process, 160 ... Result display process, 335 ... Road Info, 31
0 ... Main trunk road condition sensor, 315 ... Main trunk road condition data table creation process, 320 ... Road condition setting process, 325 ...
Contradiction cancellation processing, 330 ... Road node data table creation processing, 340 ... Main trunk road condition data table, 300 ... Road condition rule data table, 305 ... Adjacent road correlation table, 345 ... Road condition data table, 120 ... Node data table, 350 ... Road node data table, 355 ... Main trunk road node data table, 1100 ... Route calculation process to main trunk road, 1110 ... Main trunk road route calculation process, 1120 ... Branch road route calculation process, 1140 ... Reachable range Table, 1130 ... Simulation table, 1600 ... Reverse route calculation process, 1700 ... Reachable vehicle search process, 1710 ... Route calculation process.

 ─────────────────────────────────────────────────── ─── Continuation of the front page (72) Inventor Shuji Kitazawa 4-6, Surugadai Kanda, Chiyoda-ku, Tokyo Hitachi, Ltd.

Claims (10)

[Claims] 1. A node data creating process for calculating a link transit time between nodes based on digital map data stored in a file, a data input process for inputting a starting point from an input device, and the link transit time. A route simulation method for a digital map, comprising: a reachable range calculation process for calculating a reachable range from the starting point using a stored node data table; and a process for outputting the reachable range, wherein the node In the data creation process, when the deviation of the link length is large, a virtual node is provided in the middle of the long link and the process is divided into multiple short links. In the reachable range calculation process, the reachable range of the main highway is reached. A high-accuracy search method is used for the calculation, and as the branch roads derived from the main trunk road change to a high-speed search method. A route simulation of a digital map characterized by performing a transitional reachable range calculation process or performing a stepwise reachable range calculation process of switching to a high-speed search method when a branch road derived from the main trunk road is reached Method. 2. The route simulation method for a digital map according to claim 1, wherein in the reachable range calculation process, a link passage time and a node passage time of a route other than an initial moving direction from a starting point are increased, Alternatively, a route simulation method for a digital map characterized by performing reach point narrowing processing to narrow down the reachable range by rejecting. 3. The route simulation method for a digital map according to claim 1, wherein the reachable range output process displays the reachable range in different colors for each administrative boundary. Route simulation method. 4. A node data creating process for calculating a link transit time between nodes based on digital map data stored in a file, a data input process for inputting a starting point from an input device, and the link transit time. A reachable range calculation process for calculating a reachable range from the starting point using the stored node data table, a process for outputting the reachable range, and a reverse route using the result of the reachable range calculation process A method for simulating a route of a digital map, which comprises: output processing. 5. The digital map route simulation method according to claim 4, wherein in the reverse route calculation process, the result of the stepwise reachable range calculation process is used when the forward and backward passes times are equal, and when they differ. Is a route simulation method for a digital map, which outputs the shortest reverse route using the result of reachable range calculation processing based on the return link transit time. 6. The route simulation method for a digital map according to claim 4 or 5, wherein in the reachable range calculation process and the reverse route calculation process, a calculation result is searched based on a node number. Digital map route simulation method. 7. A node data creating process for calculating a link transit time between nodes based on a digital map data stored in a file and a road condition sensor for inputting an actual road condition, and a starting point from an input device. A data input process for inputting, a reachable range calculation process for calculating a reachable range from the starting point using a node data table storing the link transit time, and a process for outputting the reachable range, A route simulation method for a digital map, comprising: a road condition setting process for setting a passage time of each road according to a road condition of an adjacent road and a road condition of a main road around the road. 8. The digital map route simulation method according to claim 7, wherein the road condition setting processing is a rule for estimating a road condition of an adjacent road from a vehicle traffic density and an average speed of a road whose road condition is known. And a road condition estimation process for estimating an unknown road condition according to the rule. 9. The digital map route simulation method according to claim 7 or 8, wherein the road condition setting process includes a contradiction offsetting process for resetting the road conditions so that the road conditions of adjacent roads do not conflict. A method for simulating a route of a digital map, characterized by 10. The method for simulating a route of a digital map according to claim 9, wherein the contradiction cancellation processing is
Characteristic that offsets the contradiction by the probabilistic mitigation method by repeatedly performing the process of estimating the road condition of the road that is the target of road condition estimation from the correlation table that stores the calculated adjacent road condition and the correlation between roads. Method for simulating route of digital map.