JPH09258982A - Route decision device - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a route decision device for deciding a simple route which is slightly redundant, which is easy to understand and which is easy to follow in short time. SOLUTION: An input part 101 inputs graph information of an objective area, which is constituted of edge information, node information and block information, and stores it in an input information storage part 102. An order search part 103 searches an order for going round all blocks from an arbitrary block based on graph information in the input information storage part 102. A rotation order decision part 104 decides the rotation order of the block being the constitution element of the objective area by using graph information in the input information storage part 102 and the order search part 103 and outputs an order list constituted of the blocks and edges. A route development part 105 develops the order list from the rotation order decision part 104 into a node string being the set of nodes and displays and outputs the developed node string by an output part 107.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a route determining device for determining a route to visit a house such as a newspaper delivery or meter reading such as a house visit.

[0002]

2. Description of the Related Art Conventionally, for example, when a delivery route for newspaper delivery is determined, a delivery member empirically determines the position of the house shown on the map. In this case, in an area where houses are lined up neatly, it can be expected that an efficient route can be obtained without wasting visits. However, in reality, not only such areas but also areas with densely packed houses are difficult to determine, and it is difficult to determine efficient visit routes for these areas.

Therefore, as a means for solving such a problem, for example, a technique disclosed in Japanese Patent Laid-Open No. 7-244689 is known. In the technology of this publication,
We propose a method to find an approximate optimal solution in a short time by applying the one-stroke method. The method is to search a one-stroke writing route having the longest possible path length in the first step, and add the remaining portion (non-passed portion) in the second step.

[0004]

SUMMARY OF THE INVENTION The above-mentioned Japanese Patent Application Laid-Open No. 7-2
In the technique of Japanese Patent No. 44689, the determined route is the shortest. However, the route may repeatedly pass through the same road or turn at the same corner. Further, the same parcel is rarely delivered continuously, and the route tends to be a route ignoring the lot number. In addition, a route that frequently crosses a thick highway such as a national road may be generated. As described above, the complicated route has a problem that the person who actually performs the delivery is difficult to remember and may be confused. Therefore, it is an object of the present invention to provide a route determining device that can determine a simple route that is somewhat redundant but easy to understand and follow in a short time.

[0005]

A route determining device of the present invention stores an input means for inputting graph information of a target area consisting of edge information, node information and block information, and graph information input by this input means. Storage means,
Based on the graph information stored in the storage means, an order search means for searching an order of going around all blocks from an arbitrary block, and a cyclic order of blocks which are constituent elements of the target area are stored in the storage means as the graph information. And a cyclic order determining means that outputs the order list composed of blocks and edges by using the order searching means, and the order list output from the cyclic order determining means in a node sequence that is a set of nodes. It is provided with a route expanding means for expanding and an output means for visually observing output of the node sequence obtained from the path expanding means.

Further, the route determining device of the present invention comprises an input means for inputting graph information of a target area including edge information, node information and block information, and a storage means for storing the graph information input by this input means. An order search means for searching an order of going around all blocks from an arbitrary block based on the graph information stored in the storage means, and a cyclic order of blocks which are constituent elements of the target area, stored in the storage means A cyclic order determining means for outputting an order list composed of blocks and edges, which is determined by using the information and the order searching means, and an order list output from the cyclic order determining means are stored in the storage means. You can visually see the route expansion means that expands to a node sequence that is a set of nodes using graph information, and the node sequence obtained from this route expansion means. And and an output means for outputting to.

According to the present invention, compared to the conventional order determination method using one-stroke writing, by carrying out the turning method based on the in-block circulation, for example, a visit route that can be turned in the order of address can be achieved. . As a result, it is possible to configure a route that is easier to remember and easier to visit than in the case where the route is formed with a single stroke. Further, the heuristic method is used instead of the brute force method of testing combinations that go around all blocks, and thus the calculation time can be greatly saved. Furthermore, since the evaluation value can be changed relatively easily, it is possible to create a route that suits the operator's preference. Therefore, although it is somewhat redundant, it is possible to determine a simple route that is easy to understand and easy to follow in a short time.

[0008]

BEST MODE FOR CARRYING OUT THE INVENTION Embodiments of the present invention will be described below with reference to the drawings. FIG. 1 schematically shows a configuration of a route determining device according to the present embodiment, for example, for the purpose of determining a delivery order for distributing deliverables. The route determination device shown in FIG. 1 is an input unit 101 as an input unit for inputting graph (map) information of a target area including edge information, node information, and block information, and a storage unit for storing the input graph information and the like. The input information storage unit 102, and the order search unit 1 as an order search unit that searches the order of going around all blocks from an arbitrary block based on the input graph information.
03, the cyclic order determining unit 10 as a cyclic order determining unit that determines the cyclic order of blocks that are the constituent elements of the target area and outputs an order list composed of blocks and edges.
4. The route expansion unit 1 as a route expansion unit that expands the order list output from the cyclic order determination unit 104 into a node sequence.
05, the order search unit 103, the cyclic order determination unit 104, and the memory 106 that stores each information output from the route expansion unit 105, and an output unit that visually outputs the node sequence obtained from the route expansion unit 105. Output unit 10
It is composed of 7.

That is, the input unit 101 is composed of, for example, a keyboard, an optical character reader, etc., and inputs information of a graph (map) in an area where a route should be determined. At this time, the graph (map) is input with the intersections as nodes, the roads between the intersections as edges, and the sections divided by the roads as blocks.

The input information is structured as shown in FIGS. 2, 3 and 4, for example. That is, as shown in FIG. 2, the node information is composed of a node identifier for identifying the node and a node coordinate indicating the coordinate of the node. The edge information is, as shown in FIG. 3, an edge identifier for identifying an edge, a node 1 indicating nodes at both ends of the edge, a node 2, a distance indicating the length of the edge, and
It consists of the time required to pass the edge. Further, the block information is, as shown in FIG. 4, a block identifier for identifying the block, a representative point node indicating the delivery origin of the block, and an edge 1 surrounding the block.
2, ..., Q (q is a natural number). However, these edges 1, 2, ..., Q are input so as to follow the edge from the representative point node so as to go around the block, and for each edge, the end point node and the start point node of the next edge are input. And are given to match.

The input information storage unit 102 stores the graph information input by the input unit 101. The cyclic order determination unit 104 determines in what order a given block is to be rotated. In this case, since the cyclic order within a block is given by the information of the block, how to connect the blocks is determined.

At this time, the order search unit 103 checks the positional relationship between the blocks and searches for block connections. The memory 106 includes the order search unit 103.
At the time of searching, which block is circulated and which edge is used to connect the blocks are stored. The memory 106 is used not only by the order searching unit 103 but also by the cyclic order determining unit 104 to store the determined order.

After the cyclic order of the blocks is determined, the cyclic order is sent from the cyclic order determining section 104 to the route expanding section 105. At the same time, the input information storage unit 102 sends the node information, the edge information, and the block information to the route expansion unit 105.

The path expanding unit 105 checks the block information, the edge information, the node information, the order of the circulating blocks, and the order in which the nodes are traced from the edge connecting the blocks.

The output unit 107 prints out the order (node sequence) of the nodes expanded by the route expansion unit 105 or displays it on a display or the like. Hereinafter, a detailed description of each part will be given. As a concrete example, a graph as shown in FIG. 5 is used. Briefly explaining the graph of FIG. 5, 6
Blocks B1 to B6, 18 edges e1 to e18,
It is composed of 13 nodes n1 to n13, and the cyclic order in each of the blocks B1 to B6 is such that the lower left node is the delivery starting point and the clockwise direction from this node.

The circuit order determining unit 104 determines a block to start delivery, and determines the order of passing all the blocks from the block. At this time, the order search unit 103 searches for which block is a selection candidate.

First, the traveling order determination unit 104 will be described with reference to the flowchart shown in FIG. After each piece of information on the node, edge, and block is input from the input information storage unit 102, a start block list is created from the number of blocks and the block identifier of the block information in step S1. The starting block list may include all blocks as targets or ones that select blocks on the outer periphery of the area. An example of creating a start block list in the example of FIG. 5 is shown in FIG.

Next, in step S2, an unused starting block is selected. At this time, the block number of the selected start block is transferred to the memory 106 and a mark indicating that it has been used is added. FIG. 8 shows an example of marks transferred to the memory 106. Note that there is a start block that is not used here.

At this time (when the start block exists), the process proceeds from step S3 to S4, and the order search unit 103 is used to acquire the block list from the selected start block. The block list is a list showing the order of blocks to be delivered and the movement route between the blocks. As an example, FIG. 9 shows a list of blocks.

Next, in step S5, the evaluation value of the block list is calculated. This evaluation value usually evaluates how many parts only move without delivery when moving between blocks. Good The index for measuring this is the moving distance and the moving time, and is a linear combination of these two elements. After calculating the evaluation value, the process proceeds to step S6, and the block list obtained in step S4 and the evaluation value obtained in step S5 are stored in the memory 106.

The above steps S1 to S6 are repeated until it is determined in step S3 that all blocks have been used. If it is determined in step S3 that all blocks are marked, step S3
In step 7, out of the block list and the evaluation value group stored in the memory 106, the block list having the best evaluation value is output to the route expansion unit 105. At the same time, the memory 106
The start block list and the mark used are stored in the memory 106 are erased from the memory 106.

The above operation will be described with reference to FIG. 5, which is a specific example. First, the starting block list created in step S1 is shown in FIG. The block list is created in order from the first block of this start block list. As an example, it is assumed that the block B1 is selected. FIG. 8 shows the result of adding the mark of being used to the selected block B1.

Next, the order search unit 103 creates a block list. The details of this portion will be described later in detail, and only the result is shown here. Assuming that the block list output from the order search unit 103 is shown in FIG. 9, the evaluation value is obtained in step S5. Assuming that the evaluation value is a movement route that is generated when moving from block to block and is unrelated to delivery, in FIG.
, E11, e12, e15, e17 correspond to this. When the distances of these moving routes are calculated from the edge information (see FIG. 3), the value is “60”. This value and the block list are output in a list format as shown in FIG.
6 is stored.

The above operation is repeated, and finally the memory 10
FIG. 11 shows the block list group stored in FIG.
It is. In step S7, the route expansion unit 1 selects the list having the best evaluation value “60” from the block list group of FIG.
Output to 05.

Next, the order searching unit 103 will be described with reference to FIG.
Also, description will be made with reference to the flowchart shown in FIG. First, in step S11, a start block is registered at the beginning of the order list that is finally output to the cyclic order determination unit 104. This start block is the cyclic order determination unit 104.
It was given by. It should be noted that the subsequent registration in the ordered list is a write-once formula performed at the end of the list.

Next, in step S12, the total number of blocks is acquired from the information on nodes, edges, and blocks from the input information storage unit 102. Let B be the acquired number. Next, in step S13, the neighbor list NL is created. The adjacency list NL is a list showing which blocks are adjacent to each other. A method of creating this list will be described with reference to the flowchart shown in FIG.

First, in step S31, the total number of blocks is obtained from the block information obtained from the input information storage unit 102. Let B be the acquired number. Serial numbers are assigned to all blocks as B1 and B2.

Next, after the counter i is set to "1" in step S32, the block Bi is set in step S33.
Select At this time, blocks are selected in the order of serial numbers. Next, in step S34, the counter j is set to the counter i.
After setting to +1, the block Bi corresponding to this counter is selected (S35). In the selected two blocks, using the block information, it is checked whether there is an edge having a common node among the edges of both blocks (S36).

As a result of the examination, if there is an edge having a common node, the process proceeds to step S37, and the memory 106 stores the adjacency list as the block information identifier of the block Bi, the block information identifier of the block Bj, and the block representative points. Outputs an edge list indicating which edge should be used to connect. As a method of connecting at this time, for example, the Dijkstra method for generating the shortest path (reference: Goichi Shimauchi, Makoto Arisawa, Kohei Noshita, Hozumi Hamada, Masanori Fushimi: Algorithm Dictionary, pp455-456, Kyoritsu Publishing Co., Ltd.) Will be used. The structure of the list output to the memory 106 is shown in FIG.
It becomes as shown in.

Next, after adding "1" to the counter j in step S38, it is determined whether or not j is equal to or more than the total number of blocks (S39). If not, step S
The operations from 35 to S38 are repeated. If so, "1" is added to the counter i in step S40, and step S
When it is determined that the counter i is equal to or more than the total number of blocks B in 41, if not, steps S33 to S
The operations up to 41 are repeated. If not,
Since all the blocks have been checked, the operation is ended and the list stored in the memory 106 is output as the adjacency list NL (S42). The result of applying the process of FIG. 14 to FIG. 5 is shown in FIG.

After the neighbor list is created, the selected block S is set as the start block in step S14. Next, step S1
In step 5, "1" is subtracted from the total number of blocks B, and step S16
All the adjacent blocks of the start block S are acquired from the adjacent list NL described above. The number of adjacent blocks is C, and this number C and all adjacent block identifiers are stored in the memory 106. Also, the counter i is set to "1".

Regarding the adjacent blocks stored in the memory 106, which of the adjacent blocks has already been registered in the order list by steps S17 to S20,
Find out which block is not registered. In step S18, the unregistered block is registered in the candidate list G as a candidate block. At this time, not only the block but also a list of edges which are routes from the selected block to the candidate block are registered. An example of this candidate list is shown in FIG.

After checking whether or not all the adjacent blocks are registered in the order list (S20), it is determined whether or not the candidate list is empty (S21). If the candidate list is not empty, evaluation values up to the selected block are obtained for all candidate blocks in the candidate list, and the block O with the best evaluation is selected (S22). The evaluation value at this time is associated with the block registered in the candidate list. It is the sum of the lengths of the edges when the edge is traced from the representative point of the selected block to the representative point of the candidate block, or the sum of the times required to move from the representative point of the selected block to the representative point of the candidate block. .

Next, in step S23, the path from the selected block S to the block O in the candidate list G and the block O are registered in the order list, and the selected block S is changed to O in step S24. At this time, all the information stored in the memory 106 is erased by the operation in the selection block S.

After the change, the process returns to step S15 and the above operation is repeated. If the candidate list is empty in step S21, the adjacent range is changed (S25), and step S1 is executed again.
Returning to step 3, the above operation is repeated. The change of the adjoining range means that the adjacency condition is that the block located at the Manhattan distance 2 instead of the Manhattan distance 1 so far is adjoined. By changing the selection range, isolated blocks can be registered in the block list.

After repeating the above operation, all blocks are registered in the order list in step S26, and a block list that passes through all blocks at least once is created.
In step S27, the order list is output to the cyclic order determination unit 104, and the operation ends.

The above operation will be described with reference to FIG. 5, which is a specific example. The starting block is B1. First, in step S11, the start block B1 is registered in the order list.
As a result, the ordered list becomes as shown in FIG. Next, a neighbor list is created. The result is as shown in FIG. 16, as shown in the example of creating the neighbor list described above. Next, in step S12, the total number B of blocks is obtained as "6".

Next, the block B1 is set as the selected block S, and "1" is subtracted from B to be "5". Selection block S
If the neighbor block of B is obtained from the neighbor list, block B
2, B3. The two blocks B2 and B3 are stored in the memory 106. Then these two blocks B
It is checked whether or not B2 and B3 have been registered in the ordered list. Since only the block B1 is registered in the order list, both blocks are registered in the candidate list G. The data registered in the candidate list G at this time is as shown in FIG.

Next, since the candidate list G is not empty, the process proceeds to step S22, and the block having the best evaluation value is selected from the candidate list G. The evaluation value of the block B2 registered in the candidate list G is the block B which is the selected block S.
Since it is the sum of the evaluation values of the route from the representative point of 1 to the representative point of the block B2, the evaluation value of the edge e9 which is the route is viewed from the edge information. However, the evaluation value is the length here.

Then, the evaluation value of the candidate block B2 is "1".
0 ". Further, the evaluation value of the candidate block B3 is "2.
0 ". In this case, the smaller the evaluation value, the better. Therefore, the block B2 is selected. The selected block B2 and the route (edge group) from the block B1 to the block B2 are registered in the order list. The order list at this time is as shown in FIG.

Next, the selected block S is changed to B2, and the process returns to step S15. At this time, the candidate list G stored in the memory 104 and the block number stored in step S16 are deleted. The adjacent blocks in the block B2 are B1, B3 and B5 from FIG. These three blocks B1, B3, B5 are stored in the memory 106.

However, when it is checked in step S17 whether or not the block is a list registered in the order list, since the block B1 is already registered in the order list, the block B3 and the block B5 are respectively registered in the candidate list G. When the evaluation values of block B3 and block B5 are calculated,
Since both are "10", it is an appropriate block B
Select 3.

As a result of repeating such operations, FIG.
An order list as shown in (1) is generated, this is output to the cyclic order determination unit 104, and the operation ends. In this way, after the cyclic order determination unit 104 and the order search unit 103 have determined the block passage order in the corresponding graph, the path expansion unit 105 converts the block list, which is an ordered set of blocks and edges, into a set of nodes. It is converted and output to the output unit 107.

Here, the operation of the route expansion unit 105 will be described with reference to FIG.
This will be described with reference to the flowchart shown in FIG. First, in step S51, the block list given from the cyclic order determination unit 104 is stored in the memory 106, the element is checked from the head of the stored block list, and if the element is a block, it is determined from the block information. Convert to a set of edges. At this time, the blocks are converted into edges in the order of the edges stored in the block information. The converted result is stored in the memory 106 as an edge list.

After expanding all the blocks into edges, the edges are expanded into a set of nodes by using the edge information in step S52 to form a node list. At this time, the nodes are expanded while checking from the beginning so that the nodes of adjacent edges match. After expansion, this node list is output by the output unit 107.
(S53), and the operation ends.

The above operation will be described with reference to FIG. 5, which is a specific example. It is assumed that the generated block list is as shown in FIG. First, in step S51, the block list from the cyclic order determination unit 104 is stored in the memory 106, and it is determined from the head of the stored block list whether or not the element is a block. Since the head of the list in FIG. 20 is B1, which is a block, when expanded using block information, e4, e1, e5, e
It becomes 8. This is transferred to the memory 106.

The next element is e9, which is an edge, so it is transferred directly to memory 106 and added to the end of the previously expanded list. The next element is B2, which is a block, so it is expanded using the block information and added to the end of the list. The edge list obtained by repeating the above operation and converting all blocks into edges is shown in FIG.
As shown in FIG.

Next, in step S52, the edge list stored in the memory 106 is converted into a node list. That is, to explain using the edge list of FIG. 22, first, the head element of the edge list is expanded to a node using edge information. In this case, the edge e4 is a node having a representative point of the block, and therefore it is expanded in the order of the node n5 and the node n1. The expanded nodes are stored in the memory 106 as a node list.

Next, the edge e1 is the node n1 and the node n.
Expanded into two sets. Among them, the node n1 coincides with the end point node of the edge e4 developed immediately before. Therefore, in order to join, the edge e1 is expanded in the order of the node n1 and the node n2, and the node n1 is deleted.
The remaining node n2 is added to the end of the node list in the memory 106. When this is repeated, the memory 106
A node list as shown in FIG. 23 is formed therein. In step S53, this node list is transferred to the output unit 107, and the processing ends.

The output unit 107 forms a graph from the node information, edge information, and block information stored in the input information storage unit 102, and displays the order of passage through the graph from the obtained node list. As an example, FIG. 24 shows a display example in the example of FIG.

As described above, according to the above-described embodiment, compared with the conventional order determination method using one-stroke writing,
By carrying out the route based on the patrol in the block, it is possible to achieve a delivery route that can be routed in the order of addresses. Therefore, since the routes are arranged in the order of addresses, the route can be easily remembered and the route can be easily delivered, as compared with the case of constructing the route with one stroke. Further, the heuristic method is used instead of the brute force method of testing combinations that go around all blocks, and thus the calculation time can be greatly saved. Further, since the evaluation value can be changed relatively easily, a route that suits the operator's preference can be created.

[0052]

As described above in detail, according to the present invention, it is possible to provide a route determining device capable of determining a simple route which is somewhat redundant but easy to understand and easy to follow in a short time.

[Brief description of drawings]

FIG. 1 is a block diagram schematically showing the configuration of a route determination device according to an embodiment of the present invention.

FIG. 2 is a diagram showing a configuration example of node information stored in an input information storage unit.

FIG. 3 is a diagram showing a configuration example of edge information stored in an input information storage unit.

FIG. 4 is a diagram showing a configuration example of block information stored in an input information storage unit.

FIG. 5 is a diagram showing a specific example of a graph composed of node information, edge information, and block information.

FIG. 6 is a flowchart illustrating the operation of a cyclic route determination unit.

FIG. 7 is a diagram showing an example of a start block list.

FIG. 8 is a diagram showing an example of a use mark list.

FIG. 9 is a diagram showing an example of a block list output from an order search unit.

FIG. 10 is a diagram showing an example of a block list stored in a memory.

FIG. 11 is a diagram showing an example of a block list group stored in a memory.

FIG. 12 is a flowchart illustrating the operation of an order search unit.

FIG. 13 is a flowchart illustrating the operation of an order search unit.

FIG. 14 is a flowchart illustrating a neighbor list creation process.

FIG. 15 is a diagram showing an example of a structure and elements of a neighbor list.

FIG. 16 is a diagram showing an example of a created neighbor list.

FIG. 17 is a diagram showing an example of a candidate list.

FIG. 18 is a diagram showing an example of an order list in which start blocks are registered.

FIG. 19 is a diagram showing an example of an order list in which blocks with the highest evaluation are registered.

FIG. 20 is a diagram showing an example of a created order list.

FIG. 21 is a flowchart illustrating the operation of the route expansion unit.

FIG. 22 is a diagram showing an example of a developed edge list.

FIG. 23 is a diagram showing an example of an expanded node list.

FIG. 24 is a diagram showing a display example of a graph to which a determined route is added.

[Explanation of symbols]

101 ... Input unit (input unit), 102 ... Input information storage unit (storage unit), 103 ... Order search unit (order search unit), 104 ... Cyclic order determination unit (cyclic order determination unit), 105 ... ... Route development unit (route development means), 106
...... Memory (storing means), 107 ...... Output unit (output means), B1 to B6 ... Blocks, e1 to e18 ... Edges, n1 to n13 ... Nodes.

Claims (9)

[Claims] 1. An input unit for inputting graph information of a target area including edge information, node information, and block information, a storage unit for storing the graph information input by the input unit, and a storage unit for storing the graph information. An order search means for searching an order of going around all blocks from an arbitrary block based on the graph information; and a cyclic order of blocks which are constituent elements of the target area using the graph information stored in the storage means and the order search means. Cyclic order determining means for outputting an order list composed of blocks and edges, and path expanding means for expanding the order list output from the cyclic order determining means into a node sequence which is a set of nodes, A route determination device comprising: an output unit that visually outputs a node sequence obtained from the route expansion unit. 2. An input unit for inputting graph information of a target area composed of edge information, node information and block information, a storage unit for storing the graph information input by this input unit, and a storage unit stored in this storage unit. An order search means for searching an order of going around all blocks from an arbitrary block based on the graph information; and a cyclic order of blocks which are constituent elements of the target area using the graph information stored in the storage means and the order search means. And a cyclic order determining means for outputting an order list composed of blocks and edges, and an order list output from the cyclic order determining means using the graph information stored in the storage means as a set of nodes. A route expansion means for expanding the node sequence into a node sequence, and an output means for visually outputting the node sequence obtained from the route expansion means. A route determination device characterized by being provided. 3. The determination of the cyclic order of blocks, which is a constituent element of the target area in the cyclic order determination means, means that the representative point of each block is passed through in the target area that is determined in advance from the pass order inside the block. The route determination device according to claim 1 or 2, wherein the determination is performed using an evaluation value. 4. The expansion of the order list into the node sequence by the path expansion means is to replace the representative point of each block with a predetermined passage order inside the block. 2. The route determination device described in 2. 5. The passage order inside the block is an order starting from a representative point of the block and returning to the original representative point after passing through all of the inside of the block. 4. The route determination device described in 4. 6. The route determination device according to claim 3, wherein the evaluation value is a distance moved from a representative point of a block to a representative point of another block. 7. The route determination device according to claim 3, wherein the evaluation value is a time required to move from a representative point of a block to a representative point of another block. 8. The order of starting from the representative point of the block and returning to the original representative point after passing through all of the inside of the block is counterclockwise when viewed from the center of the block. 5. The route determination device described in 5. 9. The order of starting from the representative point of the block and returning to the original representative point after passing through all of the inside of the block is clockwise when viewed from the center of the block. 5. The route determination device described in 5.