JPH0746727A - Cable detour route setting method - Google Patents

Abstract

(57) [Summary] [Object] An object of the present invention is to provide an economical detour route of a cable using a heuristic method when a section without a conduit that can be accommodated occurs. [Construction] According to the present invention, when laying a laying cable in a loop, the laying route is sequentially selected between the demand generation point and the equipment center in the order of the required number of core wires at the demand ordering point (step 100), and the cable is routed. When there is a section where there is no empty pipeline to accommodate (step 110), another laying route that bypasses the section is searched (step 120), and the shortest route between the demand ordering point with a large number of required cores and the equipment center. The costs of all the laying routes that accommodate cables with the number of core wires that can accommodate the demand are compared (step 130), the laying route that minimizes the cost is extracted, and the laying mode is set (step 140).

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a cable detour route setting method, and more particularly to a communication cable for connecting equipment of a facility center user where an exchange is installed to provide a communication service, and for supplying power. The present invention relates to a cable detour route setting method for equipment installation, which determines a laying form of a power cable connecting a substation and user equipment.

[0002] When there is no spare equipment such as an empty pipeline in the base equipment of a specific section, immediately excavating the ground and frequently adding new equipment causes traffic congestion, etc., which is a social constraint. More unrealistic. Further, since frequent repetitive construction is uneconomical, it is desirable to effectively use other empty equipment.

[0003]

2. Description of the Related Art The complexity of setting a cable bypass route is
It depends largely on the cable laying style. As a conventional method of laying a cable, there are a method of setting in a star shape and a method of setting in a loop shape.

In the form adopted in the conventional telephone network, if the facility center and the user facility are connected in a star pattern, the well-known network flow problem can be solved. A method for solving this problem is, for example, "Maeda Watari et al.," Fundamentals of Modern Graph Theory ", pp.53-55, Ohmsha, (1978)". This method finds a short-circuit path between the equipment center and the user equipment in consideration of the empty capacity (number of empty pipelines), secures the minimum capacity in the path, and sets the number of cables. . To set the number of cables,
Sequentially, search for the shortest route for links with empty capacity,
Repeat until the required number of cables is secured. here,
Network refers to manholes and buildings (nodes)
Then, it is a representation of a pipeline or a toll road modeled by a side (link).

Further, in order to improve the reliability of the network and the like, a form of arranging the cable in a loop shape will be studied in the future. See JW Suurballe, "Disjoint Paths in a Networ
k ", Networks, 4, pp.125-145 (1974)".

This method of setting a loop-like route uses a shortest two-route algorithm that minimizes the sum of distances of two routes by finding two shortest routes and changing intersecting nodes and overlapping links. .

[0007] In addition, an algorithm that also considers capacity at the same time as a route (two-route flow algorithm) "Kishimoto et al.," Two route flows in undirected network ",
IEICE Transactions A, Vol.J75A, No.11, pp.1699-17
17,1992 ”.

[0008]

However, in the above-mentioned conventional method, when there is a section without an empty conduit capable of accommodating the cable, there is no clear method for diverting the cable to another section, and the designer is left to do so. Therefore, an appropriate empty pipeline is selected and a bypass cable laying route is set. For this reason, cables are concentrated and installed in a specific section, or the detouring distance becomes long, resulting in an uneconomical equipment configuration.

Also, regarding an algorithm for setting a loop-shaped route, an algorithm (two-route flow algorithm) that considers the capacity at the same time as the route has been proposed, but there is no algorithm for efficiently obtaining the optimum solution. .

The present invention has been made in view of the above-mentioned problems, and solves the above-mentioned problems of the prior art, and when a cable is routed in a loop, if there is a section in which there is no pipe line that can be accommodated, a heuristic The purpose is to provide an economical detour route for cables using various methods.

[0011]

FIG. 1 is a diagram for explaining the principle of the present invention.

The present invention relates to an underground pipe facility for accommodating cables, wherein when laying a cable in a loop,
The laying route is sequentially selected between the demand generation point and the equipment center in descending order of the required number of core wires at the demand order point (step 10).
0) When a section in which an empty pipeline for accommodating cables disappears (Step 110), another laying route that bypasses the section is searched (Step 120), and a demand ordering point and equipment with a large number of required cores are installed. The costs of all the laying routes accommodating the cables with the number of cores capable of accommodating the demand through the shortest route through the center are compared (step 130), the laying route with the lowest cost is extracted, and the laying form is set (step). 140).

[0013]

According to the present invention, when there are no empty pipelines for accommodating cables (the number of empty pipelines = 0), the wiring form is
Find an alternative laying route, calculate the net cost of the laying route, and if the net cost is less than the minimum net cost, set it as a new laying route, so instead of simply searching for an alternative laying route, It is possible to search for cheap routes by comparing the costs of the required networks.

[0014]

Embodiments of the present invention will now be described in detail with reference to the drawings.

FIG. 2 shows a basic equipment configuration to which an embodiment of the present invention is applied. In the figure, points are composed of manholes and equipment centers. The equipment center is M0 and the manholes are M1 to M6.

Further, each manhole M1 to M6 holds information about the number of core wires to be wired from the manhole to the user, and is represented by D (Mi). Between each pipeline as a link, there are 11 sections from C1 to C11, and a management section C
Let S (Ci) be the number of empty pipelines of i.

In the actual infrastructure construction, cables have already been laid in order to provide services, but at the time of newly laying cables, only the number of empty pipelines is important information, and other information is It has no effect on the setting of the laying route.

The following is a detailed description of the cable detouring method for the network shown in FIG. 2 when the empty pipe runs out when the cable is laid, with reference to the flowcharts of FIGS. 3, 4, 5, and 7. However, in this embodiment, the maximum number of cores of the cable is set to 400, and when a cable exceeding this number is required, a plurality of cables are laid.

FIG. 3 shows a flowchart outlining one embodiment of the present invention.

Step 1) Input the network to be adapted. The number of empty pipelines in each pipeline section is S (C1) = 2, S (C2) = 2, S (C3) = 2, S (C4) = 1, S (C5) = 1, S (C6 ) = 2, S (C7) = 2, S (C8) = 2, S (C9) = 2, S (C10) = 2, S (C12) = 2 (1). Furthermore, the length of each section is also input at the same time, but here, for simplification, it is assumed that all are the same.

Step 2) Input the required number of core wires.

D (M1) = 400, D (M3) = 80
0, D (M4) = 600. Required cores for other manholes are 0
And

Step 3) A process for obtaining a laying form with the minimum net cost corresponding to the wiring form of the cable is executed. Details of this step will be described later.

Step 4) Finally, the processing result is output and the processing ends.

FIG. 4 shows a flow chart of a process for obtaining a laying form according to an embodiment of the present invention.

The flowchart shown in the figure shows an outline of step 3 in FIG.

First, it is judged whether the wiring form is an independent cable or a shared cable (step 30), and if it is an independent cable, processing 2 of FIG. 5 described later is performed (step 3).
1) On the other hand, in the case of a shared cable, processing 3 of FIG. 7 described later is performed (step 32).

By the process 2 or the process 3, the two routes for laying the cable and the net cost are calculated, and M of the intermediate work area is calculated.
Store in SIN (step 33). An unselected pipeline section in the laying route is selected by deleting any one pipeline section from the network (step 3).
4). Here, if there is another unselected section, the process is continued, and if there is no unselected section, the process ends. Delete the selected section of the installation route (Step 3)
6). If the wiring form is an independent cable, the same process 2 as in step 31 is performed again (step 38), and if it is a shared cable, the same process 3 as in step 32 is performed again (step 39), and laying is performed. When there are two routes (step 40), the network cost is compared with the minimum network cost (step 41), and when the network cost <the minimum network cost, the network cost is stored in the minimum network cost, The cable laying route is replaced (step 42), and the process of selecting an unselected pipeline section in step 34 is performed. If network cost ≧ minimum network cost, the pipeline section deleted in step 34 or step 36 is restored to the network, and the process proceeds to the processing of selecting an unselected pipeline section in step 34. .

FIG. 5 shows a flowchart of the process (process 2) for determining the laying form according to the embodiment of the present invention.

First, sorting is performed in descending order of the required number of cords and stored in MSIN (step 311). At this time, the points to be stored are in the order of M3, M4, M1.

The maximum number of cores from MSIN (D (M
3) = 800) M3 is selected (step 312).

Since the points can be selected, the shortest two routes are set between M3 and M0 (step 314). If two routes cannot be set (step 315), a message to that effect is output (step 320), and all pipeline sections deleted in this process (process 2) are restored and the process ends (step 32).
1). In this example, two routes can be set and one route is M
0, M1, M2, M3, other routes are M0, M2, M6
One cable of 400 cores is wired in each path to be M3 (step 316). Pipe section C through which the cable passes
Since the number of empty pipe lines of 1, C6, C11, C2, C8 is 1 or more as shown in (1), the cable can be accommodated.

When one cable is accommodated, the number of empty pipelines in each pipeline section is S (C1) = 1, S (C2) = 1, S (C3) =
2, S (C4) = 1, S (C5) = 1, S (C6)
= 1, S (C7) = 1, S (C8) = 1, S (C
9) = 2, S (C10) = 2, S (C11) = 1 (step 319). Delete M3 from MSIN.

Next, from MSIN, the maximum number of cores (D
(M4) = 600) Select M4 and set two shortest routes between M4 and M0. By performing the same processing as described above, M0, M6, M3 and M4 are obtained for one route and M0, M5 and M4 are obtained for the other routes. At this time, a 300-core cable is laid on each route, but the pipeline sections C2, C
Since the number of empty conduits of 8, C3, C9, C10 is also 1 or more, a cable can be accommodated. When one cable is accommodated, the number of empty pipelines in each management section is: S (C1) = 1, S (C2) = 0, S (C3) = 1, S (C4) = 1, S (C5 ) = 1, S (C6) = 1, S (C7) = 1, S (C8) = 0, S (C9) = 1, S (C10) = 1, S (C11) = 1. Further, M4 is deleted from MSIN.

Subsequently, a point (D (M1) = 400) M1 having the largest number of cores is selected from MSIN, and two shortest routes are set between M1 and M0. At this time, one route is M
0, M1, and the other routes are M0, M6, M1. A 200-core cable is laid in each path. The pipeline sections that pass at this time are C1, C2, and C5, but the number of empty pipelines in C2 is S (C2) = 0, and the cable cannot be accommodated.

This explanatory view is shown in FIG. 6 (a). In the figure,
The cable 1-1 is a cable between M3 and M0, the cable 1-2 is M4 and M0, and the cable 1-3 is M1 and M0.
Is the cable. Since the pipeline section C2 is a cable with three lines and cannot be accommodated, it is necessary to set another two routes.

The suge route section C2 is deleted (step 32).
2) When another route is searched, one route is M0, M
1, M0, M5, M6, M1 can be obtained for other routes. At this time, since the number of empty pipelines in the pipeline section passing through is 1 or more, the cable can be accommodated as shown in FIG. 6B.
When one cable is accommodated in this route, the number of empty pipelines in each pipeline section is S (C1) = 0, S (C2) = 0, S
(C3) = 0, S (C4) = 0, S (C5) = 0, S
(C6) = 1, S (C7) = 1, S (C8) = 0, S
(C9) = 1, S (C10) = 1, S (C11) = 1. Delete M1 from MSIN.

At this stage, the MISN becomes an empty set. Since the cable laying route satisfying all the required core wires has been set, the network cost is calculated (step 323), the cable laying route is stored (step 324), and all the pipeline sections deleted in the process 2 are stored. Restore (step 32)
5) Finish the process.

FIG. 7 shows a flowchart of the processing when the cable is shared according to an embodiment of the present invention.

First, sorting is performed in descending order of the required number of cords and stored in MSIN (step 381). At this time, the points to be stored are in the order of M3, M4, M1. M
The maximum number of cores from SIN (D (M3) = 800) M
3 is selected, and the shortest two routes are set between M3 and M0 (step 382). At this time, one route is M0, M
1, M2, M3, and other routes are M0, M2, M6, M3 (step 387). Since one 400-core cable is wired in the route, the pipe section C1 through which the cable passes
400 cores are added to the number of false cores of C6, C11, C2, and C8 (step 390).

For each pipeline section, the number of cable strands is calculated from the maximum number of core wires. If the number of provisional cores is equal to or larger than the maximum number of provisional cores, the quotient is set as a cable constant, and the remainder is stored in the number of provisional cores (step 391). Here, since 400 cores is the maximum number of core wires, one cable is required, and the residual is zero. Pipe sections C1 and C through which the cable passes
Since the number of empty conduits of 6, C11, C2, C8 is 1 or more, a cable can be accommodated. When one cable is accommodated, the number of empty pipelines in each pipeline section is: S (C1) = 1, S (C2) = 1, S (C3) = 2, S (C4) = 1, S ( C5) = 1, S (C6) = 1, S (C7) = 1, S (C8) = 1, S (C9) = 2, S (C10) = 2, S (C11) = 1 (step 392). M3 is deleted from MSIN (step 393).

Next, from MSIN, the maximum number of cores (D
(M4) = 600) Select M4 and set two shortest routes between M4 and M0. At this time, one route is M0,
M6, M3, M4, and other routes are M0, M5, M4. At this time, since a 300-core cable is laid in each path, the passage sections C2, C8, C3, C9, C1
Add 300 cores to the number of false cores.

For each pipeline section, the number of cable strands is calculated from the maximum number of core wires. The quotient is taken as the cable constant, and the remainder is stored in the number of false cores. Here, since 400 cores is the maximum number of core wires, the quotient is 0, and the number of cable threads is not added.
Remove M4 from MSIN.

Furthermore, a point (D (M1) = 400) M1 having the largest number of cores is selected from MSIN, and two shortest routes are set between M1 and M0. At this time, one route is M
0, M1, and other routes are M0, M6, M1. 200 cores are added to the number of false cores in the passage section. Calculate the number of cable lines from the maximum number of cores for each pipeline section.
The quotient is taken as the cable constant, and the remainder is stored in the number of false cores. Here, since 400 cores is the maximum number of cores, the pipeline section C
In No. 2, the number of false cores is 500, the quotient is 1, and the remainder is 100. However, since the number of empty pipelines is 1, it becomes impossible to accommodate the remaining cable. Therefore, M0, M6, M
Route 1 cannot be selected. Therefore, the pipeline sections C1, C
The number of false core lines of 2, C5 is returned to the state before selecting M4 (step 394), and the pipeline section C2 is deleted from the network (step 395).

Two routes that bypass the pipeline section C2 are searched for. One route is M0, M1, the other route is M0, M
5, M6, M1 are obtained. 200 cores are added to the number of false cores in the passage section. Calculate the number of cable lines from the maximum number of cores for each pipeline section. The quotient is taken as the cable constant, and the remainder is stored in the number of false cores. For this route,
It can be selected as a cable laying route because there are no more cables than the number of pipelines. MSIN to M1
To delete.

Since MSIN is an empty set, it means that the cable laying route can be set for all demand generation points. First, all the pipeline sections deleted in the process 3 are restored (step 383). For each pipeline section, the number of cable strands is calculated from the number of provisional core wires, and the number of empty pipelines is set (step 384). From this, the number of empty pipeline conditions in each pipeline section is: S (C1) = 0, S (C2) = 0, S (C3) = 0, S (C4) = 0, S (C5) = 0, S (C6) = 1, S (C7) = 1, S (C8) = 0, S (C9) = 1, S (C10) = 1, S (C11) = 1.

Next, the network cost is calculated (step 38).
5), the cable laying route is set (step 386), and the process ends.

As described above, in the processing 2 and the processing 3, the cable laying route can be set in the given network in consideration of the detour route. Now, returning to the slow chart of FIG. 4, a procedure for obtaining an economical laying route will be described.

As a route bypassing C2 described above, M
0, M5, M4, M3, M6, M1 and M0, M5, M
There are 6, M2 and M1. As a procedure for selecting these routes, arbitrary pipeline sections are deleted one by one from the network (step 34), and processes 2 and 3 are executed according to the cable wiring mode. If there is no unselected pipeline section,
Processing accommodates.

For example, if C4 is deleted,
Alternative paths for M0, M5, M4, M3, M6, M1 are found. At this point, the network cost is calculated and compared with the already calculated minimum network cost (step 41). If the network cost is small, it is replaced with the minimum network cost (step 4).
2) If the network cost is large, the deleted pipeline section is restored to the network (step 43).

[Kishimoto et al., "Undirected Network 2
About Route Flow "IEICE Technical Paper A, Vol.
The algorithm of "J75-A, No.11, pp.1699-1717, 1992" is not limited to two routes, and any number of independent routes can be set. Therefore, the present invention can also be applied to the study of a cable laying route of three or more routes in consideration of multiple failures.

In addition, the two routes are searched in the order of the required number of core wires to search for an economical cable laying route. When detouring the same distance, detouring a thinner cable than a thick cable It is more economical to let them do it. According to the present invention, it is possible to easily change the detour setting more economically based on the evaluation based on the difference in the selection order.

In the embodiment of the present invention, the pipeline section is described as two routes, but the route is not limited to two routes, and any route can be set.

[0054]

As described above, according to the present invention, the two-route search is time-consuming in proportion to the square of the number of nodes, and as the number of nodes and the number of links increase and the network becomes complicated. , It takes a lot of time and effort for calculation.
For this reason, it seems that manual examination is not possible, so by programming the method shown here and executing it on a computer, it is possible to select an economical installation form from various cable installation routes. .

Further, it is possible to provide an economical cable laying route by eliminating the difference in design results depending on the skill of the designer.

[Brief description of drawings]

FIG. 1 is a diagram for explaining the principle of the present invention.

FIG. 2 is a block diagram of infrastructure equipment to which an embodiment of the present invention is applied.

FIG. 3 is a flowchart showing an outline of an embodiment of the present invention.

FIG. 4 is a flowchart of a process for determining a laying form according to an embodiment of the present invention.

FIG. 5 is a flowchart of a process when the cable is independent according to an embodiment of the present invention.

FIG. 6 is a diagram illustrating a cable in a pipeline section according to an embodiment of the present invention.

FIG. 7 is a flowchart of processing in the case of cable sharing according to an embodiment of the present invention.

[Explanation of symbols]

 M0 Equipment Center M1 to M6 Manhole C1 to C11 Pipe section 1-1 to 1-3 Cable

Claims (1)

[Claims] 1. In an underground pipe facility for accommodating cables, when laying a cable in a loop shape, a laying route is sequentially selected between a demand generation point and an equipment center in descending order of the required number of core wires at a demand ordering point. However, if there is a section where there is no empty pipeline for accommodating cables, another laying route that bypasses the section will be searched for and the demand will be accommodated by the shortest route between the demand ordering point with a large number of required cores and the facility center. A method for setting a cable detour route, which comprises comparing the costs of all the laying routes accommodating cables with the maximum number of core wires, extracting the laying route that minimizes the cost, and setting the laying mode.