## 3 Solution Approach
### Subgradient Algorithm  
For any given \(u\), the solution of the LR(\(u\)) gives a lower bound \(z_{u}\) for the original CLSP. To obtain the maximum lower bound, a subgradient algorithm [31] is proposed in this paper and, according to subgradient theory, \(\sum\limits_{i\in I}a_{i}x_{it}-C_{t}\) is a subgradient of function \(z_{u}\) at point \(u\). The Lagrange multipliers \(u\) can be updated with the formula  
\[u_{t}^{k+1}=\max\left\{0,u_{t}^{k}+s^{k}(\sum\limits_{i\in I}a_{i}x_{it}^{k}- C_{t})\right\},s^{k}=\frac{\eta^{k}(z^{best}-z_{u}^{k})}{\sum\limits_{t\in T }\left(\sum\limits_{i\in I}a_{i}x_{it}^{k}-C_{t}\right)^{2}} \tag{22}\]  
where \(x_{it}^{k}\) is the solution of \(LR\) (\(u^{k}\)), and \(z^{best}\) is the best upper bound found so far, \(\eta^{0}=2\). The subgradient algorithm is shown in Algorithm 3. ```
1:given a Lagrangian multiplier \(u^{k}\), \(k=0\);
2:loop
3:Arbitrarily select a subgradient from \(\partial(z_{u})\);
4:If any of the termination criteria are met, then stop; // see note 2 else
5:\(u^{k+1}=\max\left\{0,u^{k}+\theta_{k}s^{k}\right\}\); // see note 1
6:\(k=k+1\);
7:if\(k>N\) then stop;
8:end loop
9:
10:
11:\(u^{k+1}=\max\left\{0,u^{k}+\theta_{k}s^{k}\right\}\); // see note 1
12:\(u^{k+1}=\max\left\{0,u^{k}+\theta_{k}s



Notes. 1. Selection of \(\theta_{k}\):

1. \(\sum\limits_{k=1}^{\infty}\theta_{k}=\infty,\theta\to 0,k\rightarrow\infty\);

2. \(\theta_{k}=\theta_{0}\rho^{k},0<\rho<1\);

3. \(\theta_{k}=\frac{z_{UB}^{k}-z_{LB}^{k}}{\left\|s^{k}\right\|}\eta_{k}\). 2. Termination criteria:

1. Iterations: \(N\),
2. \(s^{k}=0\) or \(\left\|s^{k}\right\|\leq\varepsilon\),
3. \(\left\|z_{UB}^{k}-z_{LB}^{k}\right\|<\varepsilon\)
4. \(u^{k}\) or \(z(u^{k})\) does not change within a given number of iterations (e.g., 7). ### Lagrange Relaxation Algorithm

Based on the above description of the components of the Lagrange relaxation algorithm, now, we can give the complete Lagrange relaxation algorithm shown in Algorithm 4. ```
// Initialization
1:\(k=0\)
2:\(LB=-1\times 10^{10}\)//a sufficiently small lower bound
3:\(UB=1\times 10^{10}\)//a sufficiently large upper bound
4:\(Gap=1\times 10^{-2}\)//a dual gap percentage
5:\(K=5000\)//the maximum number of iterations
6:\(\eta_{k}=2.0\)//step size
7:\(u_{k}=0\)//Lagrangian multipliers
8:loop //main cycle beginning
9: Solve the Lagrangian relaxation \(LR\) (\(u_{k}\)) by W-W dynamic programming, and calculate the current lower bound \(Z_{LB}\left(u_{k}\right)\)
10: Solve the resulting transportation problem with the stepping-stone algorithm for the \(y\) from the solution of the current \(LR\) to obtain a \(Z_{LB}\left(u_{k}\right)\) if it is feasible  else {  Execute the fix-up heuristic  Solve the corresponding transportation problem using the stepping-stone algorithm }
11: Execute the local neighborhood search algorithm to increase the solution quality
12: if\(Z_{LB}\left(u_{k}\right)\geq Z_{LB}\), \(Z_{LB}=Z_{LB}\left(u_{k}\right)\)//updating low bounds
13: if\(Z_{LB}\left(u_{k}\right)\leq Z_{LB}\), \(Z_{LB}=Z_{LB}\left(u_{k}\right)\)//updating upper bounds
14: if\((Z_{UB}^{k}-Z_{LB}^{k})/Z_{UB}^{k}\leq Gap\), then stop
15:\(k\)++, if \(k\geq K\) then stop;
16: Update the Lagrangian multipliers with the subgradient algorithm
17:\(\eta_{k}=1/2^{\eta_{k}}\)//update the step size
18: continue;
19: end loop //main cycle ending
```

**Algorithm 4**Lagrange relaxation algorithm. ## 4 Computational Results

### Comparison Study

The Lagrange relaxation algorithm proposed in this paper has been implemented on a personal computer using the \(VC\)++ 6.0 programming language. Computational experiments for the benchmarks and randomly generated large-sized CLSPs are performed. The benchmarks are from the literature [23]. The data are listed in Table 9. The computational results are listed in Table 10.

The four approaches, LRFN (the proposed approach), LR (without the local neighborhood search), DS and LV, are compared, wherein the results of DS and LV are from the literature [23]. The LP relaxation and optimal solutions are from CPLEX 7.0.