# Matheuristics and Column Generation for a Basic Technician Routing Problem
## 3 MILP Compact Formulations
### First MILP Formulations
\[\min_{u_{i,n^{\prime}},t} \sum_{i\in\mathcal{I}}\sum_{n,n^{\prime}\in\mathcal{N}_{i}}D_{n,n ^{\prime}}u_{i,n,n^{\prime}}+\sum_{j\in\mathcal{J}}P_{j}\Bigg{(}1-\sum_{i\in \mathcal{I}}\sum_{n\in\mathcal{N}_{i}}u_{i,j,n}\Bigg{)} \tag{1}\] \[\forall n\in\mathcal{N}_{i}, \sum_{i\in\mathcal{I}}\sum_{n^{\prime}\in\mathcal{N}_{i}}u_{i,n, n^{\prime}}\leqslant 1\] (2) \[\forall i\in\mathcal{I},\forall j\in\mathcal{J}_{i}, u_{i,j,j}\leqslant 0\] (3) \[\forall i\in\mathcal{I},\forall n\in\mathcal{N}_{i}, \sum_{n^{\prime}\in\mathcal{N}_{i}}u_{i,n,n^{\prime}}=\sum_{n^{ \prime}\in\mathcal{N}_{i}}u_{i,n^{\prime},n}\] (4) \[\forall i\in\mathcal{I}, \sum_{n\in\mathcal{N}_{i}}u_{i,j,n}=1 \tag{5}\]  
\[\forall j,j^{\prime}\in\mathcal{J}, t_{j}+L_{j}+T_{j,j^{\prime}}\leqslant t_{j^{\prime}}+\left(1-\sum_{i\in \mathcal{I}}u_{i,j,j^{\prime}}\right)M^{1}_{j,j^{\prime}} \tag{6}\] \[\forall i\in\mathcal{I},\forall j\in\mathcal{J}_{i}, T^{start}_{i}+T_{i,j}\leqslant t_{j}+\left(1-u_{i,j,j}\right)M^{2}_{i,j}\] (7) \[\forall i\in\mathcal{I},\forall j\in\mathcal{J}_{i}, t_{j}+L_{j}+T_{i,j}\leqslant T^{end}_{i}+\left(1-u_{i,j,i} \right)\cdot M^{3}_{i,j}\] (8) \[\forall i\in\mathcal{I},\forall n,n^{\prime}\in\mathcal{N}_{i} u_{i,n,n^{\prime}}\in\{0,1\},t_{j}\in[T^{min}_{j},T^{max}_{j}] \tag{9}\]  
Infeasibilities due to time windows can written directly on variables \(u_{i,j,j^{\prime}}\) for \(j,j^{\prime}\in\mathcal{J}_{i}\) by following rules allowing the removal of variables that could be non zeros in the LP relaxation. If \(T^{min}_{j}+T_{j,j^{\prime}}+L_{j}>T^{max}_{j}\), then \(u_{i,j,j^{\prime}}=0\); it is not possible to reach intervention \(j^{\prime}\) on time after having realized intervention \(j\). If \(T^{start}_{i}+T_{i,j}>T^{max}_{j}\), it is not possible to reach location \(j\) on time by starting from depot \(i\), then \(u_{i,j,i}=0\). If \(T^{min}_{j}+T_{i,j}+L_{j}>T^{end}_{i}\), then \(u_{i,j,i}=0\); it is not possible to reach depot \(i\) on time if \(j\) is realized by technician \(i\). For both previous cases, it is actually unfeasible with triangle inequalities that technician \(i\) realizes intervention \(j\); all the variables \(u_{i,j,n}\) and \(u_{i,n,j}\) can be removed. If constraints (6)-(8) define integer solutions, such constraints are known to induce LP relaxations of a poor quality [67]. In the following, cuts are provided to improve significantly dual bounds without increasing too much the computation time for the dual bounds. Sub-tour cuts, such as in the Traveling Salesman Problem (TSP), can cut continuous solutions induced by the \"big M\" constraints. One can forbid firstly the sub-tours between two jobs \(j\) and \(j^{\prime}\) with constraints \(u_{i,j,j^{\prime}}+u_{i,j^{\prime},j}\leqslant 1\). Such cuts can be lifted, observing that cases \(u_{i,j,j^{\prime}}=u_{i,j^{\prime},j}=0\) are feasible here when the vehicle is not leaving the depot. It induces tighter cuts. \[\forall i\in\mathcal{I},\forall j<j^{\prime}\in\mathcal{J}_{i}, u_{i,j,j^{\prime}}+u_{i,j^{\prime},j}\leqslant 1-u_{i,j,i} \tag{10}\]  
Note that it is possible to have \(u_{i,j,i}=u_{i,i,j}=1\) when a technician does a single intervention in the route, and previous cuts cannot be extended for \(j,j^{\prime}\in\mathcal{N}_{i}\).