# Solution Algorithms for the Capacitated Location Tree Problem with Interconnections
## 4 CLTPI Solution Algorithms
### Decoder with Improvement Phase  
The BRKGA and PSO are general-purpose optimization algorithms and require a de-codification procedure to obtain solutions to a given problem. A cost-based decodification procedure is proposed and presented to obtain solutions for the CLTPI. This procedure is inspired by the one proposed in [21]. The decoder uses \(n=|V|\) variables, equal to the total number of vertices in the graph \(G\). Therefore, one variable is associated with each potential facility and each customer. The decoder receives, as input, \(\mathcal{X}_{p}\), \(\mathcal{X}_{cl}\), \(G\), \(n\), \(p\), \(cl\), \(b\), \(f\), \(Q\), \(d\), and \(c\). Following a description of each input item is presented. * \(\mathcal{X}_{p}\) is the key vector associated with the set of potential facilities in the set \(V_{p}\). * \(\mathcal{X}_{cl}\) is the key vector associated to the set of clients \(V_{c}\). * \(n\) is the total number of vertices in the graph \(G\); \(n=|V|\). * \(p\) is the number of potential locations for facilities; \(p=|V_{p}|\). * \(cl\) is the number of customers to serve; \(cl=n-p=|V_{c}|\). * \(d\) is the demand vector for the customer \(j\in V_{c}\). * \(c\) is the cost matrix for establishing a connection using the arc \((i,j)\in A\). * \(f\) is the opening cost for plants (facilities) in the set \(V_{p}\). * \(b\) is the capacity limit for plant (facilities) in the set \(V_{p}\). * \(Q\) is the maximum capacity of the connection links. * A subtree is a rooted arborescence with an origin at a client vertex, \(i\in V_{cl}\). Figure 4: Parallel PSO with restart. An \(s\)-tree, \(s\)-\(T_{k}\), is a particular case of a subtree with an origin at \(k\in V_{c}\), where \(k\) is directly connected (\(x_{pkk}=1\)) to an opened plant vertex, \(p\in V_{p}\). * \(MPR\) is the minimum number of facilities to open to cover the accumulated demand of all clients. MPR is computed using the variables \(y_{i}\) defined in Section 3 and is solved using the following optimization problem: Min \[\sum_{p\in V_{p}}y_{p}\] (9) subject to \[\sum_{p\in V_{p}}f_{p}y_{p}\geq\sum_{j\in V_{c}}d_{j}\] (10) \[y_{p}\in\{0,1\}\quad\forall p\in P\] (11)  
The cost-based decoder uses two key vectors. The first key vector is related to the potential facilities and the second to the clients. The decoder receives as input two key vectors, \(\mathcal{X}_{p}\) and \(\mathcal{X}_{c}\), of the size \(p\) and \(cl\), respectively. Both key vectors are arranged in ascending order. The core idea behind the cost-based decoder is to scan the vertices in increasing order of the random keys in the vectors \(\mathcal{X}_{p}\) and \(\mathcal{X}_{cl}\) and try to assign the scanned vertex \(i\) to its closest \(s\)-tree among the already-existing ones with enough available capacity. Here, the distance from the vertex \(i\) to the \(s\)-tree \(s\)-\(T_{k}\) is defined by the least \(c_{ij}\) value for \(j\in V(s\)-\(T_{k})\). As mentioned before, the cost-based decoder takes as input two random key vectors, \(\mathcal{X}_{p}\) and \(\mathcal{X}_{cl}\), the graph structure \(G=(V,A)\), the potential plant set \(V_{p}\), the client set \(V_{p}\), the demand vector \(d\), the capacity plant vector \(f\), and the minimum required plants \(MPR\) and returns an \(n\)-dimensional integer assignment vector, \(a\). When \(i\in V_{c}\), \(a(i)=k\) indicates that the vertex \(i\) is assigned to the \(s\)-tree \(s\)-\(T_{k}\), and \(a(i)=i\) indicates that the client \(i\) is directly connected to an open facility. When \(k\in V_{p}\), \(a(k)=k\) indicates that the plant \(k\) is open. The algorithm uses a vector, \(s\), to keep the residual capacities of opened plants and \(s\)-trees to avoid allocating more demand than that supported by plants and links. Finally, the vector \(r\) keeps a record of the plant to which an \(s\)-tree is directly connected. Algorithm 1 gives the pseudo-code of the cost-based assignment assignment decoder. In lines 1 and 2, the assignment vector \(a\), available capacity vector \(s\), and plant assignment vector \(r\) are initialized.