JPS60122467A - Path retrieval system - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed description of the invention] [Technical field to which the invention pertains] The present invention relates to a route search method, and in particular, a method for approximating an optimal route from a designated starting point to a designated destination point via a designated route. This relates to a route search method that targets targets.

[Prior art and its problems]

This type of route search method has been studied in so-called graph network theory, scheduling problems, etc., and includes enumeration method and integer programming method.

Dynamic programming, two-branch-and-bound method, cutting plane method, and the like are known. However, in either method, the search time and the amount of data used for the search are enormous, and as the number of paths increases, the amount of processing increases exponentially, making them difficult to say practical.

For example, an actual route network may be modeled, and the modeled route network may be divided into passages (paths in this modeled route network are hereinafter referred to as links) and their connection points (including end points. In this specification, Same, if the connection point in the modeled route network is defined as a node (hereinafter referred to as a node), and the number of nodes for the link that must be passed at least once (if it overlaps, it is counted as one) is n. ,
The optimal route exists among the routes that always pass through this n point once, and the number of calculations is as follows.

■Enumeration method: (n-1)! ■Branch and bound method: Order of 03 Therefore, in the worst case of either method, the required calculation is
It is considered that a problem of magnitude order a (where a is a constant) or more cannot be avoided.

Therefore, a viable route network has 10 nodes.
The number is limited to about 50 pieces, and it is difficult to say that it is practical.

On the other hand, methods have been proposed that abandon the search for the optimal solution and find an approximate solution, but methods that require short search time, such as the random method and nearest neighbor method, focus on creating a path. However, if an improved solution (for example, by the λ-optimization method) is to be obtained, the computation time becomes long.

Either way, in these cases, a route network with no direction for each link is basically assumed, and a more complex search method is generally required for a route network with a specified traffic direction. It becomes necessary.

Moreover, if the route network has about 10 to 50 nodes,
Although this process is possible, if the number exceeds 50, the process becomes nearly impossible.

In addition, as shown in Figure 1, a departure point/destination table (hereinafter referred to as an OZD table) is used in which route information from an arbitrary point (n points) to another point is stored at the intersection of the matrix nodes. In this case, the storage capacity is 2 of the scale n of the number of nodes.
An amount proportional to the power is required, and for example, as the number of nodes or links increases, the storage capacity becomes enormous.

[Purpose of the invention]

The purpose of the present invention has been made in view of the drawbacks of the prior art, and it is an object of the present invention to eliminate the drawbacks of the prior art, and also to eliminate the problem of a somewhat large number of nodes and a link (passageway) that is An object of the present invention is to provide a route search method capable of searching for an approximately optimized route without requiring much processing time even if .

[Key points of the invention]

The feature of the route search method of the specific invention in this application for achieving such purpose is that in a modeled route network having a plurality of paths and a plurality of connection points, local O//
Using the D table, a route is set with an even number of nodes having an odd number of links among the nodes in the route network, and then a non-directional heat This method searches for a so-called Eulerian route by orienting interlinks, thereby searching for an approximately optimized route.

An example of such a configuration is one that includes a processing unit and a memory, and configures a route network by modeling it with links and nodes. (and/or an attribute of the node), and for each node in the route network, the sum of the evaluation values leading to its neighboring nodes is the best and the route Find a route that satisfies the traffic conditions of A 0/D table is created, this table is set in memory, and based on this table and a traffic condition table that shows the traffic conditions of the route stored in advance in memory, the processing device performs the following in the 0/D table. , If there is node information in which the number of links connected by a node is odd, the additional link is made into a passing link and a new passing link is added so that the evaluation criterion is the best within the range of the local 0/D table. etc., to make the number of passing links even between each odd-numbered node information, and then directing undirected passing links, etc., and calculating the number of incoming links and the number of outgoing links. equal, select a route that follows the route traffic conditions,
Each node is connected to create a single route.

By performing such processing, it is possible to search for an Euler route that connects the starting point and the destination point according to the passage conditions of the passage, and by setting this, an approximately optimized Routes can be extracted. Moreover, the route search can be performed in proportion to the specified number of nodes when creating the local ○/D table, and the processing time can be reduced in proportion to the overall optimized route search. Become. As a result, it is possible to process data in a reduced form for a large-scale route network with a large number of links and nodes, making it possible to search for so-called sub-optimal routes.

Note that the feature of the route search method of the related invention in this application for achieving the above-mentioned purpose is that a local ○/D table is used to find nodes with an odd number of links among the nodes in the route network. Then, we search for a so-called Eulerian route by orienting an infinite number of undirected links so that the number of inflow and outflow links is equal, and thus we obtain an approximately optimized path. , and furthermore, when it is impossible to make it even or directed,
Data such as node information or link 11 report at that time can be displayed on the display means.

[Embodiments of the invention]

An embodiment of the present invention will be described below with reference to the drawings.

FIG. 2 is an explanatory diagram showing an example of a route network to which the processing of the present invention is applied, and FIG. 3 is a configuration diagram illustrating and modeling the route network of FIG. 2 using nodes and links. .

In the route network 3 in FIG. 2, solid line 1 and solid line 2a,
The paths indicated by 2b each represent an essential path that must be passed in the actual route. Also, the path from point B to point B is as shown by the arrow in Figure 3.
It will be a one-way street.

In FIG. 3, 4 is a route network that is a model of the route network 3 in FIG. The ○ shown in FIG. 3 means nodes that are connection points when the route network 3 in FIG. 2 is modeled, and the numbers therein are node information for identifying each node from other nodes. It is. Also, solid lines connecting each node.

Each dotted line represents a link as a passage connecting these connection points when a route network is modeled, and its subscript K
l, to 2. 3. . . , 13 is link information for identifying each passage from other passages. Note that if you want to represent the passage by dividing it, you may assume a node in the middle, and if you need to pass through the same passage twice,
It will be represented by two links. Here, the links (Kl, 3., 4., 5., 8., 9., 13) corresponding to the mandatory paths shown by solid lines are called passing links, and the links shown by broken lines are called passing links. Links corresponding to possible paths (K2, K6, KIO, Kll, K12)
will be called an additional link. In addition, links for which the direction of the passage is specified are called directed links, and links for which the direction of the passage is not specified are called hot links, and these are identified respectively. It is managed using information that indicates direction.

Z Furthermore, the number of passing links connected to a node of 1 (11) is defined as the degree of that node, and a node with an odd degree is treated as an odd degree node.Also, a directed link going out from a certain node is defined as that node. We will call the outflow links of a node, and the directed links coming toward that node the inflow links of that node.

Now, the links in these modeled route network 4,
The nodes, their directional information, and the traffic conditions of the route network are input into, for example, a computer and processed based on the information such as the identification number, and a search process for an approximately optimal route is performed. Ru.

By the way, in such a modeled route network,
If all nodes have an even number of passing links, there exists an Euler route connecting the starting point and the destination point, and by searching for this, a more optimal rule l can be obtained. Furthermore, an Eulerian route exists even when the inflow and outflow links are equal in a directional modeled route network, and by searching for this, a more optimal route can be obtained. Therefore, by combining these and realizing this combination condition within the range of the locally set O/D table, it is possible to search for an optimized route. That is, when the setting of node data in this O/D table is a predetermined number or more, it is possible to calculate this approximate optimal route.

FIG. 4 is a block diagram of a route search system that searches for a so-called quasi-optimal route under such twists and turns to which the present invention is applied.

10 is a route search system, which includes, for example, an input device 11 for inputting various data in the modeled route network 4 shown in FIG. D table creation means 14, node even number calculation means 15, link directed calculation means 16, link combination calculation means 17, display means 18, node table/link table storage means 19, local 0/D table storage means 20, and ,
The traffic condition storage means 21 is also provided. Note that these node table/link table storage means 19 and local 0/D5 may be allocated specific storage areas in the same memory to store their data, or may each have their own memory.

Now, the input device 11 has a built-in so-called keyboard and an encoder, etc., and according to the settings of predetermined function keys, configuration data of the modeled route network 4 such as link information and node information, route traffic conditions, etc. A route network configuration data input means 11a and a route traffic condition input means 11b are capable of individually inputting various data such as route search condition data and route search condition data.

and route search condition input means lie.

Here, when the link information of passing links and additional links, node information at both ends of each link, and distance information of the link targeted for evaluation criteria are input from the route network configuration data input means 11a of this input device 11. , these input information are sent to the node table/link table creation means 12. Here, for the 1-day node table, the node table/link table creation means 12
assigns separate numbers to nodes input from such data, and generates data for each node number indicating the node number (or node name), node degree, number of inflow links, and number of outflow links. Also, for the link table,
The node table/link table creation means 12 assigns a separate link salt (or a link number) to each link, and when the search start node and the search end node are different, the node table/link table creation means 12 adds a virtual Create a loop-like route by adding directed links such as In case,
Information is generated for each link salt, distinguishing it from a hot link, and indicating its direction in correspondence with each link salt.

The information for each node and each link generated in this way, together with its node number or link salt, is sequentially sent to the node table/link table storage means 19 and stored therein in the form of a table. .

In addition, in this embodiment, the evaluation target of the route network is distance.

Therefore, the length of each link is input as a characteristic of the route network.

On the other hand, the route traffic condition from the route traffic condition input means 11b of the input device 11 is, for example, one-way traffic.

When information on traffic conditions such as U-turn prohibited 2, excessively prohibited, left turn prohibited, etc. is input corresponding to or in connection with the link information or node information, this information is sent to the traffic condition table creation means 13. At the same time, related link information or node information is sent from the node table/link table creating means 12 to the traffic condition table creating means 13.

The traffic condition table creation means 13 is a route traffic condition input means],
1b, based on the route traffic condition information and the related link information or node information from the node table/link table creation means 12, with reference to the node table and link table stored in the node table/link table storage means 19. , according to the entered passage prohibition conditions, calculate the link passage conditions 9 appropriate prohibition conditions etc. in relation to a certain node or other link for each link, and set these passage prohibitions according to each link name. A route is generated that meets the conditions ()t, and this data is sent to the entrainment condition storage means 21.

The traffic condition storage means 21 stores these sent data in the form of a traffic condition table corresponding to each link name.

Once the above node table, link table and traffic condition table have been created and stored, a local 0/D table is then created based on the data in these tables.

That is, the route search condition input means 11C of the input device 11
When inputting the search start node, search end node, specification of passing links, specification of additional links, and the number of nodes to be created for creating the local 0/D table as route search conditions,
First, these pieces of information are stored in the node table/link table creation means 1.
2, predetermined information is sent from the node table/link table creation means 12 to the node table/link table storage means 19, and the search interval 9 is stored in the created node table and link table. , information such as designation of passing links, designation of additional links, etc. are written in predetermined positions corresponding to node information and link information. On the other hand, the local 0/D table creation means 4 that receives the information on the number of nodes to be created for creating the local 0/D table refers to each data of the node table, link table, and traffic condition table, and inputs the input device 11. Accordingly, a local 0/D table 26 as shown in FIG. 5 is created based on information Q on the number of created nodes sent from the IC.

This local 0/D table 26 stores the characteristics of the route network to be evaluated in a predetermined manner for each node according to the input number of created notes and the conditions recorded in the traffic condition table of the traffic condition storage means 21. , here, the evaluation target is distance, so based on the input length of each link, the distance from each node to other nodes in its vicinity via an arbitrary link according to the traffic conditions. The information indicating the sum of (evaluation values) and the route leading thereto is stored in the order of the sum of the distances, the number of which is set to 0, corresponding to each node number corresponding to each node.

As shown in FIG. 5, this local 0/D table 26 consists of a node number column 22 indicating each node number and an evaluation value ranking tank 23. Number of nodes 2 For example, if the number is m, it has m storage columns 23a, 23b, 23c, . . . , 23m. And each memory column 23a, 23b, 23c
,−・−.

23m has a storage area 24 for node numbers, which is indicated by the node number via the route to reach the node, and a weight storage area 25, which stores the distance between nodes, which is the weight indicating the evaluation value. A combination of distance and route information is recorded in these areas. Then, these records are stored in the memory column 23 in descending order of distance, which is the evaluation value.
The data are stored in the order of a, 23b, 23c, . . . , 23m, and a table is created.

Note that the distance calculated in this case is for the route selected according to the traffic conditions in the traffic condition table. Further, the count value m of neighboring nodes indicating the number of local 0/D table creation nodes is determined by the number of other nodes connected to one node. That is, it is calculated as the sum of the number of nodes at the other end of the link that connects to a certain node of interest and the number of next nodes via that node.

By the way, the local 0/D table 26 in FIG. 5 is a table for the route network 4 in FIG. 3, and the total number of nodes written in the node number field 22 is n-10. However, in general, it corresponds to the total number of nodes n in the route network.

Here, an example of selection of neighboring nodes in such a local 0/D table 26 is shown in FIG.

That is, in FIG. 6, the mouth is the starting point node of interest, and ◎ is the node adjacent to it.

Then, ◯ is selected based on the condition that the number m of neighboring nodes is 12 in total by sequentially selecting those with short distances from the mouth node through these neighboring nodes. That is, m=8+4=12 However, 8 is the number of nodes indicated by ◎, and 4 is the number of nodes indicated by ◎.

As a result, the node marked "." will be removed from the neighboring nodes.

Also, this figure uses a square-shaped route network model for convenience of explanation, but the form of the actual route network model is
Various methods are possible, and the method is not limited to these.

As a result of the above, the storage area and number of calculations that are required in proportion to the total number of notes n2 can be expressed as mXn, that is,
This means that processing can be performed with a storage area and number of calculations proportional to n.

Such a local 0/D table 26 is the local 0/D table creation means 1.
4 and stored in the local 0/D table storage means 20. Here, in response to a signal from the local ○/D table creation means 14, the node even number calculation means 15 is activated, refers to the local 0/D table storage means 20, and stores the local 0/D table stored therein. 26, with reference to the node table/link table storage means 19, a new passing link is added for the odd-numbered node existing in the local 0/D table 26, and the additional link is changed to a passing link. , and process the passing links to even numbers. Then, a route network model having new routes with even numbers is created.

Here, this even numbering process is performed as follows.

First, for each node information in the node number column 22 of the local ○/D table 26, it is determined whether or not it is an odd degree node by referring to the node table/link table storage means 19. Then, for the determined odd-degree node, the storage area 24 of the corresponding node number is then referred to, and if another odd-degree node is stored in this column, the distance to it is calculated. With reference, the maximum value up to a certain odd-numbered degree node and the minimum value up to a certain odd-numbered degree node are calculated, and the odd-numbered degree node with the largest difference between the maximum value and the minimum value is searched.

Then, the nodes in the node number column 220 with the largest difference value between the maximum value and the minimum value are selected preferentially, and links are first added between these nodes to make them even numbers. Note that in the route network 4 of FIG. 3, the odd-numbered degree nodes are nodes 2 . Node 4, node 7, and node 8.

Here, the link for even numbering to be set is the node table
The link table storage means 19 is referred to, and the traffic condition storage means 21 is referred to, and according to the conditions, an additional link is made into a passing link, or a passing link having the same characteristics as the link stored in the link table is created. This is done by adding an even number of passing links.

In this way, the odd numbered nodes with the largest difference between the maximum value and the minimum value are sequentially changed to even numbers. In this case, sequentially starting from the odd numbered node with the largest difference between the maximum value and the minimum value, the order of the nodes to be made even is simply to give priority to the odd numbered node that is farthest apart. , it is not necessary to follow such conditions.

Here, when all the nodes in the local 0/D table 26 are made even, several combinations of routes are generally created, and one of these is selected. In this case, the selection condition is to set a predetermined link for even numbering for each of these combinations of routes, and for the newly set link,
The combination route with the minimum average link length per joined odd-numbered node is selected. Note that in this assumption of even numbering, processing is performed to change the link information in the node table/link table storage means 19 by converting additional links into passing links on the assumption that a predetermined route is determined. This change process is written in a specific change column without destroying the data about the original link. Also,
Regarding the newly set transit links due to even numbering,
They are stored as additional links in a dedicated table area provided in the node table/link table storage means 19. In this way, a new route network is created in which all the node information in the node storage column of the local 0/D table 26 is even-degree node information.

At this time, if such an even number calculation is not possible, result information to that effect is sent from the node even number calculation means 15 to the display means 18, and furthermore, node information that is the reason why the number cannot be made even is displayed. And link information 9 related to this node, traffic conditions, etc. are sent to the display means 15. Therefore,
These pieces of information are displayed on a display device provided in the display means 15. As a result, for example, local 07
9. New search conditions such as increasing the number of neighboring nodes in the table 26 are inputted from the search condition input means of the input device 11,
Similar processing will be performed again.

Now, a route is set from a certain odd-numbered node to another odd-numbered node based on the link information about the links added by even numbering, and the link information or node information connecting these odd-numbered nodes is displayed in the node table/link table. Furthermore, for routes formed by link information or node information, etc., new route traffic condition data indicating the input traffic conditions corresponding to these routes is created, and this data is used as the traffic condition. It is sent to the storage means 21. The traffic condition storage means 21 stores this sent data as a table.

In this way, a new modeled route network consisting of even-numbered routes is established.

FIG. 7 shows an even-numbered model route network when such even numbering is performed on the modeled route network 4 shown in FIG. 3.

As shown in Figure 7, in the additional link in Figure 3, 2
, K6, K7, KIO, Kll, and K12, 2, K7, Kll, and K12 are set as passing links as additional links, and KI4 is newly set as an undirected passing link.

Regarding the route network thus set by the node even number calculation means 15, the link directed calculation means 16 operates in response to the start signal from the node even number calculation means I5, and stores the node table/link table. The link table of the means 19, the traffic condition table of the traffic condition storage means 21, and the local 0/D table 2
6, if there is an undirected passing link, for a node with this undirected link, set the undirected link as a traffic condition so that the inflow link and outflow link of that node are equal. The links are made directed according to the following, and combination operations are performed until all undirected links are made directed. In this case, an arbitrary undirected link is selected, the direction of the link is assumed, and directing operations are sequentially performed. By repeating this process, appropriate directionality is achieved. and,
When validation is completed for all undirected passing links, the results are stored in the node table/link table storage means 19 to create a new route network.

FIG. 8 shows the route network created in this way. As shown in FIG. 8, all links are directed at each node, and the number of inflow and outflow links at each node is equal.

Note that if such directedness is not possible, as in the case of even numbering, result information to that effect is sent from the link directionality calculation means 16 to the display means 18, and furthermore, the result information is sent to the display means 18. The node information that is the cause of the inability to be converted and the link information 5, traffic conditions, etc. related to this node are sent to the display means 18. Therefore, 8 these pieces of information are displayed on a display device provided in the display means. As a result, a new search condition such as a change in the nature of the link is input from the route search condition input means 11c of the input device 11, and the same process is performed again.

When such a new directed route network is completed, the link direction calculation means 16 activates the link connection calculation means 17. The link combination calculation means 17 refers to the new link table stored in the node table/link table storage means 19 and the traffic condition table stored in the traffic condition storage means 21, and determines a link that avoids the prohibition condition. The connections are performed sequentially to create a path that passes through each directed link once, and a so-called Eulerian route is searched. FIG. 9 shows a so-called Euler route route network obtained as a result of the above-described sub-optimal route search process for the route network 4 of FIG. 3.

Here, the combined data of each route is sequentially stored in the node table and link table of the node table and link table storage means 19, respectively. Note that when referring to the traffic condition table, if the prohibition condition cannot be avoided, the necessary information is sent to the display means I8 at that point and displayed on the display device, as in the case of even numbering. . As a result, new search conditions are input from the route search condition input means 11c of the input device 11, and the same process is performed again.

Note that the display means 18 is an even number as described above.

When directing is impossible, the results obtained from each means are displayed, and if necessary, the node table/link table storage means at that time] 9. It has a function to display data in the link table.

Next, in the embodiment of the route search system for searching for a sub-optimal route shown in FIG. 4, an embodiment will be described in which the evaluation criterion is the passage time of the route instead of the distance. Note that the means constituting each system are as shown in FIG. 4, so they are not particularly illustrated. However, since the data handled and how they are handled are different, this point will be mainly explained below.

By the way, if the evaluation criterion is the passing time, if
! The route with the least elapsed time is selected as the optimal route.

From the route network configuration data input means 11a, the names of passing links and additional links, the node numbers at both ends of each link, and here, in addition to the link length, the maximum and minimum link passing speed, and the number of links within the link are input. Necessary data such as the number of existing work points, the amount of work at all work points, the time required to pass through the nodes belonging to the link, and the stop time during the link are respectively input.

On the other hand, from the route traffic condition input means 11b, one-way traffic,
Route traffic conditions such as no U-turns, no passing, no right or left turns are input, and from the route search condition input means 11C,
Specifying the start node, end node, passing links and additional links for route search, the number of created nodes for creating local ○/D table, average traffic speed within the route network, and work at one work point on the link. The time required for preparation and the working time per unit working time are respectively input.

Now, the node table/link table creation means 12 uses each data inputted from the route network configuration data input means 11a, the route traffic condition input means 11b, and the route search condition input means 11c described in 1. Separate node numbers are assigned, and the node number, node degree, inflow link, and outflow link number are generated according to the node number for the node table. Furthermore, a separate link name (number may be used) is given to each link, and if the search start node and end node are different, a virtual directed link from the end node to the start node is added, and the link name, link Node numbers at both ends, length of the link, maximum and minimum speed through the link, number of work points existing within the link, amount of work at all work points, time required to pass through the nodes belonging to that link, and link passing. Stop time 1 Identification information that identifies passing links and additional links; in the case of directed links, information that distinguishes them from unlimited links and identifies their direction; Data for the required time T is generated according to the link name for the link table.

2 Tm L/V →-m -Tm + n -Tn + Tnode+
TstopV=Vo (However, when VO>Vmax, Vo=Vmax; when Vo<Vmin, Vo=Vmin) Here, T: Link transit time L: Link length Vo: Average transit time within the route network Vmax: Maximum link passing speed Vmin: Minimum link passing speed m: Number of work points within the link Tm: Time required for work preparation at one work point Tn: Unit work time n: Work amount of all work points within the link Tnode: Node belonging to the link Time required for passing TstOp: Time during which the link is stopped for purposes other than work. Information about the node table and link table thus generated is sent to the node table/link table storage means 19 and stored.

Further, based on the information inputted from the route passage condition input means 11b, a traffic condition table is created by the traffic condition table creation means 13 and stored in the traffic condition storage means 21, similarly to the embodiment shown in FIG.

Now, the local 0/D table creation means 14 is a node table.

Referring to the link table and the traffic condition table, search the route from any node in the route network according to the conditions and the number of local 0/D table creation nodes in the vicinity inputted from the route search condition input means 1 and c. Calculates the evaluation time to reach a nearby node, stores this as a weight along with its route information, generates local 0/D table creation information, and sends this information to the local 0/D table storage means 20. and memorize it.

In this case, for each node, from among the routes leading from that node to other nodes, the route with the shortest time according to the traffic rules in the traffic condition table is searched, and the route with the shortest time is selected. Priorities are assigned, and the number of nodes according to the priorities are sequentially stored, and a table similar to the table shown in FIG. 5 is created.

The node even number calculation means 15 refers to the node table/link table storage means 19 and the local ○/D table storage means 20, and converts all odd-order nodes among the nodes in the local 0/D table into even numbers. Select the odd-degree node with the largest difference between the maximum and minimum transit times between the odd-degree node in the local 0/D table and the corresponding other odd-degree nodes stored in the local 079 table until do. Then, when that node is combined with other odd-numbered nodes in the local ○/D table corresponding to that node, the combination that minimizes the link transit time per connected odd-numbered node is selected. , local○
Create a new even-numbered route network by converting additional links into passing links and adding new passing links within the range of the /D table, and create the link information and node information obtained from these results in the node table and link table, respectively. It is stored in the link table and node table of the storage means 19.

Further, if such even numbering is not possible, predetermined information is sent to the 5 display means 18 to display data to that effect.

Other traffic condition table creation means 13. Link directed calculation means 16. The operation of the link connection calculation means 17 etc. is based on the fourth
Since it is almost the same as the embodiment shown in the figure, its explanation will be omitted.

As described above, each means in the system of FIG. 4 can be realized by a program using a computer system having a processing device, a memory, and a display device. In this case, each storage means is realized using the same memory.

In addition, the link transit time T calculated by the formula shown in the second embodiment is not calculated by such a formula, but is calculated separately from the data, or is set separately and used as route network configuration data. It is also possible to input the information directly from the input means 11a and store it in the link table.

In the embodiment described above, distance and time are used as evaluation criteria, but the evaluation criteria are not limited to such distance and time. Regarding distance and time mentioned above, the minimum evaluation value will be selected as the characteristic, but in general, the evaluation value should be selected so that it is the best value. become.

In addition, in the embodiment, when making even numbers, the corresponding odd number nodes in the node column for a specific odd number node in the local 079 table are made even numbers.
This can be applied to any odd degree node as long as it is information inside the local 0/D table.

〔Effect of the invention〕

As explained above, in the specific invention of this application, a local O/D table is used to set a route by making nodes with an odd number of links among the nodes in the route network an even number, and then , the so-called Eulerian route is searched by orienting the non-directional invalid links so that the number of inflow and outflow links is the same, thereby searching for an approximately optimized path. Therefore, the amount of processing is proportional to the number of nodes in the local 0/D table, and it is also possible to process a route network having a larger number of paths.

In addition, in the related invention of this application, in the configuration of the specific invention, when it is impossible to make the data even or directed, data such as node information or link information is added to the configuration of the specific invention, for example, to a display device. Since the information can be displayed using a display means having the following, there is an effect that an optimized route can be searched by changing the conditions.

[Brief explanation of the drawing]

FIG. 1 is an explanatory diagram of a conventional starting point/destination table that stores route information from an arbitrary point to another point, and FIG. 2 is an explanatory diagram showing an example of a route network to which the processing of the present invention is applied. figure,
FIG. 3 is a configuration diagram of a route network that is a diagrammatic model of the route network shown in FIG. The block diagram, FIG. 5, is a concrete explanatory diagram of the local 0/D table stored in the local 0/D table storage means in FIG.
The figure is an explanatory diagram of the neighborhood node 9 in the local 0/D table in Figure 5, and Figure 7 is an even-numbered model route when the modeled route network shown in Figure 3 is even-numbered. FIG. 8 is an explanatory diagram showing the route network shown in FIG. 7, and FIG. 9 is an explanatory diagram of the route network when the route network shown in FIG.
FIG. 2 is an explanatory diagram of a so-called Eulerian route network obtained as a result of searching for a sub-optimal route for the route network shown in the figure. 10 is a route search system, 11 is a route network configuration data input device, 11a is a route network configuration data input means, 11b is a route traffic condition entry means, a route search condition input means, 12 is a node table/link table creation means, 13 14 is a traffic condition table creation means, 14 is a local 0/D table creation means, 15 is a node even number calculation means, 1G is a link direction calculation means, 17 is a link connection calculation means, 18 is a display means, and 19 is a node table.・Link table storage means, 20 is local O/D table storage means, and 21 is traffic condition storage means. 0 - N Do 1 Sa ”---1 (: Φ Do Q publication Kihan S Tokukai Sho GO-122467 (13)

Claims (4)

[Claims] (1) A route search method that searches for an approximately optimal route using a modeled route network having a plurality of passages and a plurality of connection points, comprising a processing device and a memory, and information regarding the passage. is set as link information, information regarding the connection point is set as node information, each node information is stored in the memory as information regarding the route network in association with link information entering and exiting there, and each link information is associated with its link information. stored in association with node information arranged at both ends, and direction information indicating the presence or absence of directionality of each of the passages and the direction thereof is stored in correspondence with each of the link information;
Passage conditions of a route consisting of the passage and the connection point are stored in association with the node information or the link information, and the memory further stores characteristics of the route network that are subject to a predetermined evaluation. as an attribute of the passage, and information indicating the sum of each evaluation value according to the attribute from each connection point via the passage to another connection point in the vicinity according to the passage conditions and the route leading thereto, A local table is stored in which a predetermined number of pieces of the node information corresponding to each connection point are stored in descending order of the sum of the evaluation values, and the processing device stores each node in this table. Among the information, regarding node information that has an odd number of link information,
A route in which link information according to the direction of the path is set for other node information having odd-numbered link information stored corresponding to this node information, and the link information is made even by mutually coupling. and selects the route with the best average evaluation value of the set link information from among the set routes, and on a new route network including this selected route, the inflow direction is determined according to the traffic conditions. The hot link information is changed to link information with directionality so that the number of link information in the outflow direction is equal to the number of link information in the outflow direction. A route search method characterized in that link information is combined according to traffic conditions to select an approximately optimized route from a specified connection point to another specified connection point. (2) The route according to claim 1, wherein the evaluation condition is distance, and the order of the sum of the evaluation values in the local table in which a predetermined number of evaluation values are stored is the order of the shortest distance. Search method. (3) The route according to claim 1, wherein the evaluation condition is time, and the order of the sum of the evaluation values in the local table stored in a predetermined number is the order of the shortest time. Search method. (4) A route search method for searching for an approximately optimal route using a modeled route network having a plurality of passages and a plurality of connection points, comprising a processing device, a memory, and a display means, The information regarding the passage is used as link information, the information regarding the connection point is used as node information, each node information is stored in the memory as information regarding the route network in association with link information entering and exiting there, and each link Information is stored in association with node information arranged at both ends thereof, and direction information indicating the presence or absence of directionality of each said passage and its direction is stored corresponding to each said link information. Passage conditions of a route consisting of connection points are stored in association with the node information or the link information, and the memory further stores characteristics of the route network that are subject to a predetermined evaluation. As an attribute, information indicating the sum of each evaluation value according to the attribute and the route leading therefrom from each connection point via the passage to another connection point in the vicinity according to the traffic condition, is included in the evaluation value. A local table is stored in which a predetermined number of pieces of the node information corresponding to the respective connection points are stored in descending order of the sum, and the processing device is configured to store a predetermined number of local tables corresponding to the node information corresponding to each of the connection points in descending order of the sum. , for node information having an odd number of link information, link information according to the direction of the path is set for other node information having an odd number of link information stored corresponding to this node information, so that they can mutually interact. A route is set in which links are combined to make the link information an even number, and a route with the best average evaluation value of the set link information is selected from among the set routes, and a new route including this selected route is created. On the network, according to the traffic conditions, the unlimited link information is changed to link information with directionality so that the number of link information in the inflow direction is equal to the number of link information in the outflow direction, and the direction is directed. The method selects an approximately optimized route from a specified connection point to another specified connection point by combining each piece of link information in accordance with the traffic conditions in the new route network that has been created. The route search method is characterized in that the display means displays node information that cannot be made into an even number or link information that cannot be given an even number when the even numbering or the direction cannot be made.