# Matheuristics and Column Generation for a Basic Technician Routing Problem
## 6 Computational Results
### Results with MILP-VND Local Search
#### 6.5.1 Impact of CG Initialization and Multi-Column Generation per Sub-Problem  
In this section, we analyze the results considering the standard Algorithm 5 with an exact resolution of sub-problems and generating one or several columns per sub-problem. The second variant is implemented by using the populate mode of Cplex with OPL; we note that it is possible to use all the columns with a negative reduced cost found using callbacks, which is not available with OPL but is now available in some MILP modeling interfaces and libraries such as PythonMIP or Julia JUMP. The generation of several columns is used at most for the five first iterations, and the remaining iterations are processed with the standard Algorithm 5 with at most one column generated per sub-problem. The maximal size of the population of Cplex is set to ten: at most, 10 new columns are added in the RMP.  
Figure 1 illustrates the convergence of integer and continuous RMP in both variants; the results for some small instances are given with the number of iterations to converge in Table 7. Figure 1 illustrates that CG is naturally stable for TRPTW, with a few degenerated iterations. Degenerescence occurs more frequently for VRPTW [11]. A reason is that the \(I\) sub-problems are highly heterogeneous with difference competence sets and location of depots; a degenerated iteration would induce the generation of \(I\) degenerate columns, whereas in VRPTW, only one sub-problem is generated when taking into account the symmetry among vehicles, and the probability of degenerate iteration is larger [11]. Figure 1 shows that integer and continuous RMP are very close; it happens for highly constrained instances and also with generation of few columns. It explains the high quality of the RMP_INT_HEUR heuristic.  
Figure 1: Illustration of the CG convergence of RMP and integer RMP for an instance with 40 jobs and 15 technicians with 20 different skills.  
Using several solution found by the MILP solver induces many benefits for the CG convergence: The difference in the quality of continuous and integer RMP is significant, and the dual variables have a less erratic convergence. This is a virtuous circle: Having better RMP values induce better dual values that generate more relevant columns. This explains how the experiments with only five iterations of aggressive CG produce such difference. The first iterations are the most unstable.  
Table 7 considers, furthermore, an initialization with the optimal integer solution. In many cases, the convergence value of the continuous RMP is obtained here, and there are only degenerated iterations with the optimal iterations. In such cases, the dual initial values are very good, but it is not sufficient to guarantee the fast convergence of the CG Algorithm 5. If the optimal initialization makes the number of iterations decrease on average, there exists some instances where there are more degenerate iterations with the optimal initialization than iterations starting from no column.  
These experiments validate the impact of having a multi-column generation even with an unstructured method of generating columns. The next section provides the results related to the structured method of generating several columns per sub-problem.