# Solution Algorithms for the Capacitated Location Tree Problem with Interconnections
## 3 Problem Description and Formulation  
The Capacitated Location Tree Problem with Interconnection (CLTPI) focuses on optimizing the design of a distribution network to minimize the total cost. In this context, strategic decisions must be made regarding the placement of facilities, referred to as plants, to service a set of clients with specific demands. The network design must be robust. Hence, interconnections between facilities must be included to ensure service continuity, even in the event of a failure in any of them. Interconnections, defined as links between two facilities, are exclusively utilized in failure situations and are not part of the network's regular operation. They aim to maintain the supply in case of a failure in any facility, ensuring the system's reliability. Additionally, \begin{table}
\begin{tabular}{p{113.8 pt} p{113.8 pt} p{113.8 pt} p{113.8 pt}} \hline
**Problem** & **Characteristics** & **Authors** & **Solution Methods** \\ \hline Capacitated minimum & Tree-shaped network & [PERSON] and [PERSON] [7] & [PERSON]’s branch-and-bound \\ spanning tree & Capacitated links & [PERSON] et al. [19] & Multi-Exchange Neighborhood \\  & One source & [PERSON] et al. [20] & BRKGA \\  & No location & [PERSON] [21] & Branch-and-cut algorithm \\ \hline Capacitated facility & Capacitated facilities & [PERSON] et al. [22] & Exact Algorithm \\ location problem & Facility location & [PERSON] and [PERSON] [23] & Local Search \\  & Various sources & [PERSON] and [PERSON] [24] & Hybrid Firefly-GA \\  & No network & & \\ \hline Location-routing problems & Facility location & [PERSON] et al. [11] & Decomposition \\ over a tree network & No capacities & & \\  & Routing problem & & \\ \hline Capacitated Facility & Facility location & [PERSON] and [PERSON] [14] & MILP \\ Location/Network Problem & Capacitated facilities & & \\  & Star-shaped network & & \\  & Various sources & & \\ \hline Ring-Tree Facility & Facility location & [PERSON] et al. [16] & MILP \\ Location problem & Ring-shaped network & [PERSON] et al. [17] & Branch-and-Price \\  & One source & & \\ \hline Tree of Hubs & Facility location & [PERSON] et al. [18] & Integer Programming \\ Location Problem & No capacities & [PERSON] et al. [25] & Decomposition \\  & Tree-shaped network & [PERSON] et al. [26] & Benders decomposition \\ \hline \end{tabular}
\end{table} 
Table 1: Literature Review. Related Problems. the problem considers capacity constraints in both facilities and connections. Capacity constraints in facilities limit the amount of energy they can supply, while constraints on connections regulate energy flow between facilities and clients. The formulation and modeling of the problem are carried out using graphs, allowing for an efficient representation of the relationships between facilities and connections. However, it is relevant to note that this problem is NP-Hard, signifying that its complexity increases significantly as the numerical instance size to be solved grows. Despite an exhaustive literature review, no evidence of prior studies addressing the CLTPI has been found. It arises from the urgent need to design electrical networks for electric transportation systems capable of operating partially, even in the event of failures in power substations. In summary, the primary objective of the problem is to minimize the total cost of network design, considering the cost of opening the required facilities, and designing the network to meet the required demands of all clients. This involves respecting capacity constraints in facilities and connections while strategically creating interconnections between facilities to maintain continuous service, at least partially, in the case of a failure in any facility. The problem is formally defined with a complete directed graph, \(G=(V,A)\), where \(V\) is the set of vertices and \(A=(i,j)|i\in V,j\in V|i\
eq j\) is the set of arcs. The set \(V\) contains two subsets of vertices: (i) \(V_{p}\subset V\), the subset of plants, and (ii) \(V_{c}\subset V\), the subset of clients.