# Matheuristics and Column Generation for a Basic Technician Routing Problem
## 6 Computational Results
### Instance Characteristics, Benchmarks and Analysis Methodology
#### 6.1.2 Analysis Methodology  
Instances were generated with relations among instances to analyze the trade-off between optimality and feasibility for the different optimization algorithms. Instances with \(d\in\llbracket 11,18\rrbracket\) are generated from instances with \(d-10\in\llbracket 1,8\rrbracket\) with a higher speed parameter. Hence, each feasible solution for an instance with \(d\in\llbracket 1,8\rrbracket\) is feasible for the corresponding instance with parameter \(10+d\),  
For each group of instances with fixed values of parameters \(a\) and \(b\) defined, a maximal number of competences are defined with \(c_{max}\). The other instances with \(c<c_{max}\) are defined from the one with \(c_{max}\): skills in the instance \(s\) are grouped modulo \(c\); if skill \(q\) is required in instance \(c_{max}\), the corresponding skill in instance \(c\) is \(q\) mod \(c\). Such reduction keeps the feasible solutions from the previous model and adds potentially new solutions. Hence, instances with \(c<c_{max}\) are less constrained than the original ones with \(c=c_{max}\) and have a better optimal value. In the case \(c=1\), there are no skill constraints, and the model is similar with a MDVRPTW. For computational analyses, we investigate the difficulty of instances regarding speed and competence parameters. This defines four datasets:  
* Dataset \(sc_{max}\) with minimal speed (\(d\in\llbracket 1,8\rrbracket\)) and maximal number of competences \(c_{max}\);
* Dataset \(5c_{max}\) with maximal speed (\(d\in\llbracket 11,18\rrbracket\)) and maximal number of competences \(c_{max}\);
* Dataset \(s1\) with minimal speed (\(d\in\llbracket 1,8\rrbracket\)) and no skill constraint (\(c=1\));
* Dataset \(S1\) with maximal speed (\(d\in\llbracket 11,18\rrbracket\)) and no skill constraint (\(c=1\)).  
Hence, datasets \(s1\) and \(S1\) are MDVRPTW instances, with a correspondence and more constrained instances due to speed with dataset \(s1\). Dataset \(S1\) is less constrained than the three other datasets. Original dataset \(sc_{max}\) is the more constrained dataset, comparable to the three other datasets. Comparing the difficulty induced for instances \(sc_{max}\) and \(S1\) allows analyzing the difficulty induced by speed and rare competence separately.  
In order to compare optimization algorithms in a given dataset, the following indicators are provided:  
* [noitemsep,topsep=0 pt]
* Fail: The number of instances where the maximal number of jobs is not scheduled;
* BKS: The number of instances where the Best Known Solution (BKS) is reached;
* Mean: The average gap for all the considered instances of the primal solution to the BKS;
* \(\sigma\): The standard deviation of the gaps between primal solution and BKS;
* Min: The minimum gaps between primal solution and BKS for all instances ;
* Q1: The first quartile of the gaps between primal solutions and BKS;
* Med: The median (or second quartile) of the gaps between primal solutions and BKS;
* Q3: The third quartile of the gaps between primal solutions and BKS;
* Max: The maximum gaps between primal solution and BKS for all instances.