# Matheuristics and Column Generation for a Basic Technician Routing Problem
## 3 MILP Compact Formulations
### Four-Index MILP Formulation with Ordinality  
Many alternative MILP formulations can be designed with the formulation variants of sub-tours in TSP as analyzed in [68]. Similarly to the formulation of Fox-Gavish-Graves(FGG) [69], variables can be modeled with 4-index variables \(z_{i,j,n,k}\in\{0,1\}\), such that \(z_{i,j,n,k}=1\) if and only if the \(k\)-th job (\(k\in\llbracket 1,K_{i}\rrbracket\)) that is operated by technician \(i\) is job \(j\in\mathcal{J}_{i}\) and then the job (of depot) \(n\in\mathcal{N}_{i}\) is reached after intervention \(j\). Without time window constraints and without \(K_{i}\) upper bound on the number of intervention per route, this would induce a number of variables in \(O(\mathcal{I}\times\mathcal{J}^{3})\) instead of \(O(\mathcal{I}\times\mathcal{J}^{2})\) for the last MILP formulation. A first, the issue will be to analyze if the better quality LP relaxation compensates the increasing size of the model. The maximum number of interventions in a day \(K_{i}\) allows having \(O(K\times\mathcal{I}\times\mathcal{J}^{2})\) variables, with \(K=\max_{i}K_{i}\). With the variables of the previous formulation, there is the following relation. \[\forall i\in\mathcal{I},\forall j\in\mathcal{J}_{i},\forall n\in\mathcal{N}_{ i},\quad u_{i,j,n}=\sum_{k=1}^{K_{i}}z_{i,j,n,k} \tag{11}\]  
The following MILP formulation models TRPTW with variables \(z_{i,j,n,k}\) is as follows. \[\min_{z,I}\sum_{i\in\mathcal{I}}\sum_{j\in\mathcal{J}_{i}}\sum_{n \in\mathcal{N}_{i}}\sum_{k=1}^{K_{i}}D_{j,n}z_{i,j,n,k}+ \sum_{i\in\mathcal{I}}\sum_{j\in\mathcal{J}_{i}}\sum_{n\in \mathcal{N}_{i}}D_{i,j}z_{i,j,n,1}+\sum_{j\in\mathcal{J}}P_{j}\left(1-\sum_{i,j,k}z_{i,j,n,k}\right) \tag{12}\] \[\forall j\in\mathcal{J}, \sum_{n\in\mathcal{N}_{i}}\sum_{k=1}^{K_{i}}\sum_{i\in\mathcal{I}}z _{i,j,n,k}\leqslant 1\] (13) \[\forall i\in\mathcal{I},\forall j\in\mathcal{J}_{i}, \sum_{k=1}^{K_{i}}z_{i,j,k}\leqslant 0\] (14) \[\forall i\in\mathcal{I}, \sum_{j\in\mathcal{J}_{i}}\sum_{n\in\mathcal{N}_{i}}z_{i,j,n,1}\leqslant 1\] (15) \[\forall i\in\mathcal{I},\forall j\in\mathcal{J}_{i},\forall k \in\llbracket 1,K_{i}-1\rrbracket, \sum_{j^{\prime}\in\mathcal{J}_{i}}z_{i,j^{\prime},j,k}=\sum_{n \in\mathcal{N}_{i}}z_{i,j,n,k+1}\] (16) \[\forall j,j^{\prime}\in\mathcal{J}, t_{j}+L_{j}+T_{j,j^{\prime}}\leqslant t_{j^{\prime}}+\left(1-\sum_{k=1}^ {K_{i}}\sum_{i\in\mathcal{I}:j\in\mathcal{J}_{i}}z_{i,j^{\prime},k}\right) \cdot M_{j,j^{\prime}}^{1}\] (17) \[\forall i\in\mathcal{I},\forall j\in\mathcal{J}_{i}, T_{i}^{start}+T_{i,j}\leqslant t_{j}+\left(1-\sum_{n\in\mathcal{N}_{i}}z _{i,j,n,1}\right)\cdot M_{i,j}^{2}\] (18) \[\forall i\in\mathcal{I},\forall j\in\mathcal{J}_{i}, t_{j}+L_{j}+T_{i,j}\leqslant T_{i}^{end}+\left(1-\sum_{k=1}^{K_{i}}z _{i,j,k}\right)\cdot M_{i,j}^{3}\] (19) \[\forall j\in\mathcal{J}, t_{j}\in[T_{j}^{min},T_{j}^{max}] \tag{20}\]  
Note that the objective function is in three parts, and \(D_{j,n}z_{i,j,n,k}\) terms do not count the distance from the depot to the first jobs of technicians. Constraints (13) are straightforwardly equivalent to the previous elementarity constraints (2). Constraints (14) are implied by the definition of variables, \(z_{i,j,j,k}=0\) for each technician \(i\in\mathcal{I}\), \(j\in\mathcal{J}_{i}\) and \(k\in\llbracket 1,K_{i}\rrbracket\). Constraints (15) initialize flow constraints, as in (5); the difference is that flow initialization is written after the first job, and this flow is not anymore equal to one as there are no variables indicating straightforwardly if an empty route is chosen. In such case, all the variables related to the technician are zeros. Constraints (16) are the equivalent of previous flow constraints (4) for modeling routes for technician; the balance of flow is here considered regarding the ordinality \(k\). Constraints (17)-(19) express time windows constraints, respectively, between two consecutive jobs and for starting and finishing time of technicians, similarly with constraints (6)-(8). Constraint (17) is the same constraint set as (6) by using relations (11).