An adoptable location of utility network elements for processing and distribution of resources between consumers is a complex technical and economic problem. For its solution, it is necessary to take into account both the resource constraints as well as a plan of processing and distributing the resources among consumers, thus providing an e cient scheme for the functioning of a network to be designed. In this study the problem of the utility network design is treated by the hypernet approach according to the compatibility of di erent types of resources with allowance for their laying in the same track. Also, we study the reliability aspect of the designed utility network for obtaining the optimal laying of a reliable enough utility network on a given area with minimal costs. The performed numerical experiments show how the method proposed works.
Utility network is a composite geographically distributed system that performs such vital functions as providing consumers with energy and water resources, communication facilities, information, route network, tra c, and other services. It includes local authorities, economic objects and consumers, and, also, considers the nature of the relationship between them.
Currently, there is a signi cant number of published works related to
design and construction of networks for various purposes [
In: S. Belim et al. (eds.): OPTA-SCL 2018, Omsk, Russia, published at http://ceur-ws.org
of GIS-technologies applying in tracing and placing of linear objects is studied.
An application of splines in the optimization of the car roads tracing is treated
in [
In all the above mentioned papers, the utility network is considered to be a two-dimensional object located on a plane. However, such a two-dimensional representation of networks does not completely correspond to reality, since as the basis of the design and construction of the utility network underlies the interaction of, at least, two interrelated objects. Unlike its predecessors, in this work a utility network is treated as a hierarchical system, in which resources (gas, oil, water, etc.) are transferred from producers to consumers through the points of processing via communication (transport channels). Such systems are characterized by the existence of the so-called xed costs, which must be done regardless of the volume of production and processing of products.
For the simulation of various network objects, graphs and hypergraphs are
commonly used. As was mentioned above, in many areas of applications there
is a bunch of interconnected networks, forming a hierarchical structure. In such
cases it is completely inconvenient to use graphs and hypergraphs. Instead of
them, other network models are used [
For the problems of a utility network design we use the hypernet approach,
which makes it possible to operate with hierarchical, multilevel, and
heterogeneous networks. More speci cally, we study a simple case of hypernet | the
two-level network. It consists of a primary network, which represents a physical
network, and a secondary network, which represents a logical network,
embedded into a primary network. Our previous results on the hypernet using for the
utility network design are presented in [
Based on the hypernet approach, we solve the task of providing the
connectivity of given consumers with given sources on a given area with minimization
of laying and maintenance costs and within given constraints. As a result, we
propose a new method for the selection of routes for the laying of the utility
networks taking into account the compatibility of di erent types of resources for
placing them in the same track. For example, in one collector it is possible to
lay in one direction the heat communications, pressure water pipes and sewerage
systems, over ten communication cables and power cables with voltage up to 10
kV. However, the joint laying of gas pipelines and pipelines with combustible
substances is not permitted due to the fact that the distance between
communications of di erent purposes is normalized according to building codes and
regulations [
Also, we introduce an algorithm for obtaining not only the cheapest solution,
but reliable enough as well. Note that reliability analysis of hypernets is not a new
task, see, for example [
We use the classical de nitions from the hypernet theory [
De nition: hypernet is represented by the four sets: HN = (X; V; R; F ), where: X = fx1; x2; :::; xng { a set of nodes; V = fv1; v2; :::; vgg X X { a set of branches; R = fr1; r2; :::; rmg { a set of edges; F : R ! 2V { a mapping associating each item r 2 R with a path F (r) V .
These four sets determine the two graphs: P N = (X; V ) { a graph of a primary network; W N = (X; R) { a graph of a secondary network.
It is assumed that for the utility network laying, the following objects are given: D { s two-dimensional placement area; Ysource D { a set of point objects, which represents sources; Yconsumer D { a set of point objects, which represents consumers; Y = Ysource [Yconsumer { a set of point objects to be connected by linear facilities of various assignment.
Let us describe the utility network in terms of the hypernet theory.
In a primary network P N = (X; V ) we assume that: (v) { the length of v 2 V ; a(v) { the land cost (rent, taxes, etc.) of v 2 V ; b(v) { the cost of constructing (excavation) of v 2 V ;
1 { a discount factor of building costs (this factor is for bringing economic indicators of di erent years to comparable values).
In a secondary network W N = (Y; R) we assume the following: (r) = Pv2F (r) (v) { the length of r 2 R; c(r) { the cost of r 2 R, including its installation and laying between the corresponding elements of D;
2 { a discount factor of equipment costs; dv(r) { maintenance costs of linear facilities on plots v 2 F (r) for a chosen edge (route) r; T { a set of all types of utility resources. Thus, each edge r has the type type(r) 2 T .
As was said above, di erent resource types may be incompatible with each other for their laying in the same track. For the description of the compatibility of di erent types of resources, we introduce the following notation:
A binary relation CT 2 T T is de ned by the rule: if (t1; t2) 2 CT , then these types of resources can be placed in the same track, i.e. both of them can include the same branch.
Let M inCT (t1; : : : ; th) be the minimum number of disjoint subsets into which a subset of types ft1; : : : ; thg can be divided.
For example, if there are types ft1; t2; t3g such that (t1; t2); (t2; t3) 2 CT , but (t1; t3) 2= CT , then M inCT (t1; t2; t3) = 2, since these types can be divided into the subsets ft1; t2g and ft3g. 3
In the general case, the task of a utility network design can be formulated as a problem of providing the connectivity of given objects from Y = Ysource [ Yconsumer with minimization of the laying and maintenance costs. The obtained con guration determines the topology of the designed utility network.
As we said above, we use the hypernet approach, so the network structure is separated into a primary and a secondary networks. As a primary network, we consider a discrete analogue of the placement area D for the utility network. As a secondary network, we consider routes through branches for the laying of various utility systems.
The problem is to nd the hypernet HN , i.e. embed each path r 2 R in W N into the edges of the graph P N in such a way that all conditions and restrictions imposed on the utility network be met, and the functional below would take the minimum value:
Q(HN ) = X v2V 0 a(v) + b(v) 1 (v) M inCT (v) + (1) + X c(r) + r2R
X where v 2 V 0 V if 9r 2 R such that v 2 F (r). Let v 2 V 0 and v 2 F (ri); i = 1; h (r1; : : : ; rh 2 R), then M inCT (v) = M inCT (type(r1); : : : ; type(rh)).
This Section proposes an algorithm for obtaining an approximate solution of the problem stated. The basic idea of our algorithm is to nd an initial estimation of HN , its total cost (1), and to improve it further. The initial estimation is found by the \greedy" algorithm or the Floyd algorithm, which is commonly used for nding the shortest paths.
The cost of v 2 V is (a(v) + b(v) 1 + c(r) 2 + dv(r)) (v) (for the sake of simplicity c(r) 2 + dv(r) = const, 8r) for the Floyd and the Dijkstra algorithms in the primary network P N .
Below we outline the steps of the algorithm: Algorithm
Divide a set of types into incompatible subsets. repeat
Choose a subset of types T 0 with the maximum number of edges (return the values a(v), b(v) for all v 2 F (r) in the graph P N ).
repeat
Find all the shortest paths (xi; xj) i; j = 1; n, i 6= j in the graph P S = (X; V ) by the Floyd algorithm (type(xi; xj) 2 T 0).
Choose the minimal value from a set of the shortest paths, where (xi; xj) 2 R in the graph W N (the path (xi; xj) is not assigned for any r 2 R).
Assign the edge r 2 R to the shortest path (xi; xj) in the graph P N . a(v) := 0, b(v) := 0 for all v 2 F (r) in the graph P N (the costs of branches are zero for assigning a path).
until 8r 2 R in the graph W N , there is an assigned path (xi; xj) in the graph P N . until T 0 6= ;.
The greedy algorithm is approximate, therefore the solutions obtained are not always optimal. We can improve it if for an edge r 2 R we reassign new paths F (r). For example, a new path F (r) is cheaper if it includes a greater number of branches v 2 F (r) with zero cost (branches that have already been used for other edges r 2 R).
We can order the edges by a certain technique. Earlier we have considered
a few techniques [
We can use some iterations of the Stage 2 algorithm for nding better results. 5
For numerical experiments we have chosen the 10x10 grid as a primary network P N . The number of edges in W N for laying in P N varied from 10 up to 4000
Order ri 2 R by decreasing the costs (renumber them) and obtain the new list frig. repeat
\Delete" ri from the graph HS according to the list (i.e. 8vk 2 F (r), restore for a(vk) and b(vk) the initial values if vk is not included into other edges).
Find a new shortest path for ri in the graph P N by the Dijkstra algorithm. Assign it for ri.
a(v) := 0, b(v) := 0 for all v 2 F (ri) in the graph P N .
until All edges frig from the list are updated. (the abscissae axis). For a chosen number of edges nedges, we randomly place in the grid nedges sources and nedges consumers. As a result, a grid node can contain more than one object: source(s) and consumer(s). The random placement is carried out 10 times for a given nedges value. As a laying cost for nedges we take the average among the 10 values found.
We consider the set of resource types which has been mentioned as the example in the Section 2. Thus, we assume that there three di erent types of edges.
In Figure 1 the normalized costs are shown (i.e. we nd minimal cost and divide all the obtained values by it). The results show that the Greedy algorithm is more convenient for a small number of edges; otherwise the Floyd algorithm gives a better solution.
In Figure 2 we show the results of the previous numerical experiments for the
case of compatibility of all resources type for laying in same track [
In this Section, we improve the algorithm proposed in order to obtain not only
the cheapest, but also reliable enough solution. Most of the results presented
coincide with those from our previous publication [
Random graphs are commonly used for modeling the networks whose
elements are subject to random failures [
Another well-accepted network reliability measure is the 2-terminal
probabilistic connectivity [
Let us assume that branches (edges of the primary network) are subject to random failures that occur statistically independently with known probabilities pi, 1 i g.
The reliability of an edge r 2 R we de ne as
Rr(HN ) =
Y
If for an edge r 2 R the path F (r) has the endpoints a and b, we use the notation Rab(HN ) instead Rr(HN ). If for the nodes a and b there are more than one of such edges, we choose one with a maximum reliability value.
We consider the following reliability measure R(HN ), taking into account the fact that failures occur in the primary network, and all consumers should be connected with the corresponding sources:
R(HN ) = minfRab(HN )g; a 2 Ysource; b 2 Yconsumer: Therefore, R(HN ) is the minimum among all 2-terminal probabilistic connectivities Rab(HN ), where b is a consumer and a is a corresponding source.
Based on the two-stage algorithm, we propose a new algorithm with a reliability constraint. It is assumed that we are given a reliability threshold 0 < R0 1. The objective is to nd a su ciently reliable solution of problem (1). In other words, we nd a solution HS of problem (1) such that R(HS) R0. 7
In the case of the reliability constraint, we use the Ant Colony Algorithm [
Pij (t) =
ij ij P
ij ij l) has TimeToLive label (T T L(li))
T T L(li) =
Y v2P ath(li) p(v); where P ath(li) is the path of the ant li. If T T L(li) < R0, then ant li dies. { After nding an edge, each ant lays the pheromone on a branch. ij (t) =
Q=length(t) { In a set of the most frequent routes we nd the minimum and x it, so we decrease the cost of branches of the primary network.
Below in Figure 3 we present the numerical results of the algorithm proposed for pi = 0:99; 1 i g, R0 = 0:9. For the primary network P N we consider the 10x10 grid (jXj = 100), := 1; := 3; 0 := 1; Q := 50.
The number of edges was from 10 up to 100 in W N (the abscissae axis). Axis of ordinate is cost Q(HN ). The rst and the second algorithms are the Floyd and the Greedy respectively, without constraint (2). Therefore, the found value Q(HN ) is less than the result of FloydProb and AntColony (FloydProb is the Floyd algorithm with constraint (2)). Figure 2 shows that the AntColony results are better than the FloydProb results only for a small number of edges. The new approach to the utility network design has been studied. Based on the hypernet theory, we consider a natural-technical system of a land plot and a utility network within the framework of the uni ed mathematical model. As a result, we propose the new method to provide the connectivity between given consumers and corresponding sources with minimization of laying and maintenance costs and within given constraints. This method gives an appropriate solution with allowance for the compatibility of di erent types of resources for placing them in the same track.
For ensuring the reliability of a designed utility network, we, also, introduce the method for obtaining not only a cheap solution, but a reliable enough one as well assuming that failures occur in a primary (physical) network. As a reliability measure we consider the minimum among all 2-terminal probabilistic connectivities between each consumer and corresponding sources.
The conducted numerical experiments which show the applicability of the methods proposed are presented.