# Matheuristics and Column Generation for a Basic Technician Routing Problem
## 5 Dantzig-Wolfe Reformulation and CG Matheuristics
### Solving CG Sub-Problems  
To solve sub-problems (35) with respect to optimality, note that the CG sub-problem related to \(i\) is exactly the same as the VRPTW sub-problems with the jobs \(\mathcal{J}_{i}\). Constraint (35) can be formulated as an elementary shortest path problem with resource constraints (ESPPRC). If ESPPRC is a NP-complete problem, it is solved efficiently for reasonable instance sizes for VRP problems with labeling algorithms [23; 40]. With several technicians in sub-problems (36), the nature of sub-problem changes and exact labeling algorithms will be even more difficult. In this study, generic MILP solvers are used to solve exactly such sub-problems and to validate the contribution of such a decomposition scheme.  
However, the computations to optimality are required only to prove the optimality of the RMP at the last iteration. For the first CG iterations, we only need to generate negative reduced cost solutions. The exact computations are time consuming in Algorithm 5; it can be replaced by heuristics to generate quickly negative reduced cost solutions. The choice of algorithm at each iteration seeks for the good trade-off between computation time and quality (negativity) of the generated columns. This trade-off is dealt using different heuristics with different computation times. For instance, the heuristics of Section 4 apply. In Algorithm 2, specific sorts of jobs can be processed for CG sub-problems: One may consider firstly the jobs with the highest dual values \(\pi_{j}\), especially with the non-assigned jobs in the RMP with a maximal dual value \(\pi_{j}=P_{j}\), rather than the jobs with a low dual value. Hence, one may iterate in Algorithm 2 the decreasing values of \(\pi_{j}\). One may also consider \(\pi_{j}-D_{i,j}\) in order to take into account the remoteness of job \(j\).  
Sub-problems (36) can be solved to search columns with a negative reduced cost using matheuristics; the number of technician is restricted, and matheuristics restrict the size of MILP computations, removing jobs similarly to Section 4. The POPMUSIC CG scheme applies only for generating columns with a negative reduced cost. To prove the optimality of the RMP, Algorithm 5 applies for the remaining iterations.  
Algorithm 7, decomposes the search of columns with a negative reduced cost by using only computations with one technician. These decomposed sub-problems can also be solved as ESPPRC with [23]. This scheme allows generating the best individual columns as in Algorithm 5 and also good complementary columns for these best individual columns. The solutions of (35) with Algorithm 7 are uneven in the reduced costs following the order of priority of the technicians, whereas a straightforward matheuristic search applied to (35) would have a smoother repartition of the reduced costs. A stake of the computational experiments is to determine whether these two generation schemes are complementary or if one dominates the other. To generate both types of columns, Algorithm 7 can be applied to generate initial columns before a smoothing local search phase in order to optimize the objective function of (36) with a MILP-VND similar to Section 4.  
```
- \(\mathcal{I}_{0}\) a subset of technician.
- \(\mathcal{s}\) a cyclic permutation of \(\mathcal{I}_{0}\) with order\((s)=\mathcal{I}_{0}\).
- \(\sigma\), \(\pi\) the dual variables of the last RMP computation. Initialization:\(\mathcal{C}=\varnothing\), the columns to add in the RMP for each technician \(i\in\mathcal{I}_{0}\) :  Let \(i^{\prime}:=i\), \(\mathcal{J}_{0}:=\mathcal{J}\) for\(k=1\) to \(\mathcal{I}_{0}\) :  solve (35) for technician \(i^{\prime}\) with \((\sigma,\pi)\) values and the remaining jobs in \(\mathcal{J}_{0}\) if the solution induces a column with a negative reduced cost  add the column in \(\mathcal{C}\) remove the jobs of the column in \(\mathcal{J}_{0}\) \(i^{\prime}:=s(i_{0})\) endfor : endfor return\(\mathcal{C}\)
```  
**Algorithm 7** Diversification of sub-problem solutions