# Solution Algorithms for the Capacitated Location Tree Problem with Interconnections
## 2 Literature Review  
Network design problems have been widely studied in the literature. The minimum spanning tree (MST) can be considered the fundamental problem for network design that can be solved using polynomial-time algorithms like the ones proposed by [5, 6]. The MST considers a set of vertices that have to be connected through a network so that a commodity (electricity, information, water, etc.) can flow from any origin vertex to a destination one. When capacities restrict the flow through the network's links, the capacitated minimum spanning tree (CMST) arises [7]. By including such constraints, the problem becomes of the type NP-Hard, as [PERSON] showed in [8]. On the other hand, location problems have also been extensively studied in the literature. The most basic location problem is the \(p\)-median problem or uncapacitated facilities location problem (UFLP) [9]. In this problem, \(p\) facilities have to be open to serve a set of customers. In the capacitated version of the problem (capacitated facility location problem) [10], capacities are considered for plants, and each customer has a predefined demand to be delivered. The CLTPI can be considered a combination of the CMST and CFLP problems with additional constraints (interconnections). One of the most related research works to the CLTPI is by [PERSON] et al. [11], which presents three location-routing problems (LRPs) defined over tree-shaped graphs. LRPs have been widely studied in the literature. Interesting reviews of LRPs can be found in [12; 13]. The authors propose various LRPs defined over a tree-shaped road network (graph). The authors present several variants of the problem depending on the characteristics of customers' demand. In all the proposed variants, the best location has to be selected among a set of facilities at the graph's vertices, and customers are assigned to one selected facility. Finally, closed routes are designed using open facilities as depots while minimizing the total cost. The authors propose solution methods that first determine which facilities are open and assign the customers to such facilities. The optimal routing is then obtained by decomposing it into smaller subproblems associated with each open facility. Since the problem is defined over a tree-shaped graph, edges (the authors used a non-directed graph) are traversed precisely twice. A representation of the LRP variants proposed in this research work is presented in Figure 1. As mentioned before, these problems are LRPs and, therefore, different from the CLTPI. Another related problem is the Capacitated Facility Location/Network Problem (CFLNDP) [14], which arises from the CFLP. The CFLNDP considers a set of vertices representing clients with a given demand. A facility might be open at each client vertex and with a given capacity. Open facilities serve directly through a link to the clients assigned to the open facility. The authors consider an incomplete graph for the problem. The CFLNDP solutions are star-shaped networks originating from an open facility. In the CFLNDP, no capacity over the links is considered, and clients are served using direct links from the facilities. The main differences with the CLTPI are that there is no capacity over the links, there is no topological design of the network, all clients can open a facility, and the problem is defined over an incomplete graph. Another two problems in the context of tree and location problems are the Capacitated Ring Tree problem (CRTP) [15] and the Ring-Tree Facility Location problem (RTFLP) [16; 17]. Both problems consider a central depot to which the customers have to be connected by using a ring-tree-shaped network. Both problems consider two types of customers. Type 1 customers can be connected to the network by a tree or a ring, while type 2 customers need to be connected by rings. The rings are part of the inner level of the network, and trees are part of the outer level.