# Matheuristics and Column Generation for a Basic Technician Routing Problem
## 6 Computational Results
### Results with MILP-VND Local Search
#### 6.5.2 Impact of the Different CG Schemes and Stabilization Operators  
To understand the specific contributions of the different CG schemes, we provide here comparative analyses solving exactly sub-problems for small and mid-size instances and a proven termination of the CG algorithm. The following CG schemes are implemented and compared:  
* CG1: This is the standard CG scheme, as written in Algorithm 5;
* CG2: The standard CG scheme is followed by TS intensification to solve single technician sub-problems. It corresponds to Algorithm 8 with only partitions into singletons, with parameters \(k=3\) and \(N=5\);
* CG3: This is the POPMUSIC CG scheme without TS intensification, where sub-problems (36) are solved only using exact computations;
* CG4: This is the POPMUSIC CG scheme without TS intensification, where the sub-problems (36) are solved twice: Algorithm 7 provides the first solutions in a hierarchical manner, and a second phase optimizes the worst reduced cost (and, thus, balances \begin{table}
\begin{tabular}{l c c c} \hline \hline
**Instance** & **1 col per Sub-Problem** & **Multicol** & **Multicol + Warm Start** \\ \hline data\_3\_5\_10\_ex1 & 24 & 7 & 4 \\ data\_3\_5\_10\_ex2 & 13 & 5 & 7 \\ data\_3\_5\_10\_ex3 & 8 & 5 & 5 \\ data\_3\_5\_10\_ex4 & 11 & 6 & 5 \\ \hline data\_8\_5\_20\_ex1 & 21 & 9 & 7 \\ data\_8\_5\_20\_ex2 & 11 & 9 & 7 \\ data\_8\_5\_20\_ex3 & 38 & 15 & 12 \\ data\_8\_5\_20\_ex4 & 15 & 10 & 8 \\ \hline data\_15\_20\_40\_ex1 & 21 & 13 & 13 \\ data\_15\_20\_40\_ex2 & 19 & 11 & 9 \\ data\_15\_20\_40\_ex3 & 17 & 10 & 14 \\ data\_15\_20\_40\_ex4 & 21 & 11 & 11 \\ \hline data\_10\_3\_50\_ex1 & 54 & 21 & 22 \\ data\_15\_3\_50\_ex1 & 32 & 26 & 18 \\ \hline Total & 324 & 168 & 150 \\ \% iterations & 100 & 51.9\% & 46.3\% \\ \hline \hline \end{tabular}
\end{table} 
Table 7: Number of iterations for the convergence of CG algorithm to solve the LP relaxation of the extended formulation compared when only one column is generated per sub-problem, improvements with multi-column generation and providing an optimum of the MILP as the initial solution. the reduced costs) with a VND local search matheuristic, generating all the columns with a negatively reduced cost obtained from these two phases. * CGS: This corresponds to the strategy CG4 with TS intensification activated with \(K=3\) and \(M=5\). The dominant computational results are illustrated in Figure 2. The known hierarchies among CG schemes are significant: CG1 is significantly dominated by the other schemes, POPMUSIC and TS intensification induce a very significant acceleration in terms of CG convergence. Comparing CG3 and CG4 allows concluding that the optimization of the total reduced cost with diversification in sub-problems (36) induces a better CG convergence than the CG with the hierarchical decomposition of Algorithm 7. Combining POPMUSIC and TS intensification dominates the single stabilization strategies: POPMUSIC column generation is mostly useful for the first iterations in terms of recombining columns in the next RMP, where it can be difficult to find a solution allocating all the jobs (and, thus, paying no prohibitive penalty). TS intensification is crucial when dual variables have a relative stability, which is helpful for the latest phases of the CG convergence. When the dual variables are changing slightly, it is likely that there exist many columns of very good quality among neighbors of the optimal solution of the previous sub-problem. Aggressively using TS intensification prevents generating neighbors from the previous iterations in further iterations, which explains the gain when using TS intensification. To compute the extended LP relaxation to optimality, TS strategies are prominent for reducing the number of CG iterations. TS is particularly efficient for the final iterations of CG algorithm, but it is also useful in the first iterations with respect to having a deterministic scheme to aggressively generate solutions in the first iterations, as in the first experience of stabilization.