طراحی شبکه دو سطحی با تجهیزات متوسط​​ : یک برنامه کاربردی برای سیستم های توزیع برق

We consider the two-level network design problem with intermediate facilities. This problem consists of designing a minimum cost network respecting some requirements, usually described in terms of the network topology or in terms of a desired flow of commodities between source and destination vertices. Each selected link must receive one of two types of edge facilities and the connection of different edge facilities requires a costly and capacitated vertex facility. We propose a hybrid decomposition approach which heuristically obtains tentative solutions for the vertex facilities number and location and use these solutions to limit the computational burden of a branch-and-cut algorithm. We test our method on instances of the power system secondary distribution network design problem. The results show that the method is efficient both in terms of solution quality and computational times.

Network design problems concern the selection of edges and vertices in a graph in order to satisfy, at minimum cost, some requirements, usually expressed in terms of the connectivity of the obtained network or its ability to allow a certain flow between source and demand vertices. Several variants of network design problems have been proposed in the literature. They differ in terms of the number of commodities that must be transported, the existence of vertex or edge capacities, the presence of fixed or variable costs and the restrictions on the desired graph topology, to cite a few characteristics. We consider that a single commodity must be transported from a root vertex to several demand vertices, via a radial network. There are two types of edge facilities which allow for the flow of the commodity, named primary and secondary. Primary edge facilities have higher fixed costs but smaller variable costs, when compared to secondary edge facilities. We call primary (secondary) flow, the flow of the commodity occurring in a primary (secondary) edge facility. The following additional restrictions must be respected: (a)The root vertex must be connected to the network only through primary edge facilities. (b) Demand vertices must be connected to the network only through secondary edge facilities. (c)Primary flow can be converted in secondary flow only in vertices containing a costly and capacitated vertex facility. Moreover, some vertices might not be able to receive such facilities. We name this problem the two-level network design problem with intermediate facilities (TLNDP-IF). The TLNDP-IF describes well an application in the context of electrical distribution networks. This problem will be detailed in the next section and is the main motivation for this work. Variants of the TLNDP-IF in which one or more of constraints (a)–(c) are slightly modified appear in many other network-engineering settings including, e.g., the design of telecommunication networks [1], [2], [3], [4], [5] and [6], the design of computer networks [7], [8] and [9] and the design of reverse logistics networks [10] and [11]. In the design of telecommunication networks, the goal is to deliver broadband network services such as high-speed internet access, telephony or cable TV. The two-level structure appears due to the availability of different technologies such as optical fibers and coaxial links and the fact that intermediate facilities must be used to connect both technologies. In general, the demand vertices are served with coaxial links which originate at intermediate facilities. The intermediate facilities are, in turn, connected to a central root vertex by means of optical fibers. The used intermediate facilities can be of many types depending on the required capacities and functions. The design problem objective is to minimize the total cost of edge and vertex facilities that are used. As this problem is proved to be NP-complete, the solution techniques usually rely upon heuristics that hierarchically decompose the problem into smaller subproblems [5]. Lagrangian relaxation [12] and [13] and branch-and-cut [14] approaches have also been used. In the design of computer networks, one is concerned with the definition of the topology of the network and with the traffic routing. The information must flow from central vertices to demand vertices through intermediate transmission facilities. The crucial decision is often where to install these intermediate facilities and how to connect them both to the central vertex(ices) (primary network) and to the demand vertices (secondary network). As before, a commodity or service has to be delivered from one or many source vertices to demand vertices through a two-level network, which has to be designed. In the primary part of the network, economies of scale induce the installation of large capacity edges—called the backbone or trunk network—while the delivery of the commodity to the demand vertices is made through less costly secondary edges, after a conversion is made in intermediate vertices. In these vertices a costly conversion capacitated facility must be installed. The quantity and location of these conversion vertices are also decisions that must be made during the network design. As mentioned before, most of the solution techniques for these problems are heuristic approaches since the majority of the applications define hard combinatorial optimization problems. Very frequently the problem hardness forces a suboptimal hierarchical decomposition scheme, which means that the problem is hierarchically split into smaller interdependent subproblems. Details on hierarchical network design problems modeling and solution techniques can be found in [15], [16] and [17]. In this work, we first propose a formal mathematical model for the TLNDP-IF. The model is used within a commercial MIP solver to obtain optimal solutions for small benchmark instances. In order to deal with real-world instances, the model is integrated into an efficient hybrid solution approach. We use a problem decomposition method which allows the obtention of good approximation for the locations of the conversion facilities by means of a Lagrangian surrogate technique. The heuristic solution is then used to restrict the number of candidate locations for the installation of intermediate facilities, in the flavor of what has been done in the context of vehicle-routing problems [18]. The restricted model is finally solved to optimality via a branch-and-cut method. In the next section we present the application that has motivated this work: the planning of power system secondary distribution networks. Then, in Section 3, a mixed-integer linear formulation is proposed for the problem. In Section 4, we describe the developed hybrid decomposition heuristics, which are tested in Section 5. The paper ends with some conclusions in Section 6.

We propose a hybrid decomposition approach for the planning of two-level networks in which the two levels must be interconnected through intermediate facilities. This problem arises in many network-engineering contexts. Our approach decomposes the problem in the location of the intermediate facilities, which is followed by routings in both network levels. Since the location of the intermediate facilities is a critical decision, we propose a hybrid exact–heuristic approach in which the heuristic solution is used to restrict the number of variables in the ‘exact’ part, obtaining a trade-off between solution quality and computational time. We test our algorithms in the planning of electricity distribution networks and the results show that the proposed methodologies are relevant, obtaining gains of up to 4.27% in real networks when compared to the results presented in previous works.