## 4 Solution Algorithms
### Model Decomposition Scheme for Utilizing Efficient Lower Bound Rules for QSAP-C  
We reformulate the primal problem as a number of subproblems of LAP with computationally efficient algorithms by relaxing the capacity constraints of DCs (constraint (4)). The corresponding relaxed model (M2) of the original problem can be stated, as seen below, with its optimal solution defined as \(Z_{R}\). M2:  
\[Z_{R}=Min\ Z \tag{7}\]  
subject to Equations (2) and (3) and Equations (5) and (6)  
Similar to the problem decomposition scheme used in GLB, model M2 can be further decomposed into a sequence of generalized linear assignment problem (GLAP) with an optimal solution \(\pi_{kl}^{*}\) for each \((k,l)\in E^{B}\). The main idea of the decomposition is to fix the variable \(x_{kl}\) (assume that \(x_{kl}=1\)) and then solve the problem related to \(y_{l^{\prime}j}\) to obtain the second-stage cost. Thus, we can establish the following equations for each \((k,l)\in E^{B}\). M3:  
\[\pi_{kl}^{*}=\text{Min}\sum_{l^{\prime}\in L^{\prime}}\sum_{j\in l}f_{kj}d_{l ^{\prime}l^{\prime}}y_{l^{\prime}j}+\sum_{l^{\prime}\in L^{\prime}}\sum_{j\in l }f_{kj}d_{l^{\prime}j}y_{l^{\prime}j}=\text{Min}\sum_{l^{\prime}\in L^{\prime }}\sum_{j\in l}f_{kj}\Big{(}d_{ll^{\prime}}+d_{l^{\prime}j}\Big{)}y_{l^{ \prime}j} \tag{8}\]  
subject to Equations (3) and (6)  
These equations constitute a generalized assignment model M3, where the cost for each \((l^{\prime},j)\in E^{B}\) is \(f_{kj}\Big{(}d_{ll^{\prime}}+d_{l^{\prime}j}\Big{)}\). Figure 13 illustrates a feasible solution with \(x_{k\text{I}11}=1\) in the network as in Figure 4. When \(k=k1\) and \(l=l1\), a subnetwork can be obtained and the links \((k1,l1)\), \((l1,l^{\prime}1)\), \((l1,l^{\prime}2)\), \((l1,l^{\prime}3)\) are the existing links, the delivery stations \(J\) need to be assigned to exactly one distribution center. By solving these GLAPs (M3), the second-stage cost \(\pi_{kl}^{*}\) for each \((k,l)\in E^{B}\) is now obtained. Based on the transportation cost \(\sum_{j\in l}f_{kj}d_{kl}\) on the link \((k,l)\) (the first-stage cost) and second-stage cost \(\pi_{kl}^{*}\), the estimated cost for links \((k,l)\) becomes \(c_{kl}=\sum_{j\in l}f_{kj}d_{kl}+\pi_{kl}^{*}\). Then, we can solve the following generalized assignment model (M4) (Figure 14) to retrieve a lower bound of the relaxed model M2. The overall solution algorithm for obtaining this lower bound estimate is described in Algorithm 1. Figure 13: A feasible solution for \(x_{k\text{I}11}=1\). M4:  
\[Z_{LB}=\text{Min}\sum_{k\in K}\sum_{l\in L}\left(\sum_{j\in J}f_{kj}d_{kl}+\pi_{ kl}^{*}\right)x_{kl}=\text{Min}\sum_{k\in K}\sum_{l\in L}c_{kl}x_{kl} \tag{9}\]  
subject to Equations (2) and (5)  
```
Step 1: Initialization Read the input data, including nodes, links, and agents (flow) Step 2: Calculate the subsequent cost given the decision of \(x_{kl}\) For each link\((k,l)\in E^{\beta}\) solve the generalized assignment problem(M3) by calling the Gurobi solver and obtain the value of \(\pi_{kl}^{*}\) Step 3: Calculate the estimated cost \(c_{kl}\) on the link \((k,l)\in E^{B}\) For each link\((k,l)\in E^{B}\) \[c_{kl}=\sum_{j\in J}f_{kj}d_{kl}+\pi_{kl}^{*}\] Step 4: Solving the generalized assignment problem by optimizing \(x_{kl}\) According to the estimated cost \(c_{kl}\), solve the generalized assignment problem (M4) by calling the Gurobi solver and retrieve the lower bound estimate
```  
**Algorithm 1** GLB-based algorithm for obtaining the lower bound of the simplified problem(M2) without enforcing the capacity constraints of DCs. Connection between Traditional GLB for Standard QAP and Proposed Lower Bound Estimation Process for QSAP-C  
Compared with the GLB for standard QAP, we use the same cost-estimating framework to obtain the lower bound for QSAP-C. In the QAP, problems at two stages are LAPs and the cost is fixed as constant. In the QSAP-C, we need to solve GLAPs at two different stages and the flow-dependent cost is the product of distances and commodity flows.