# Matheuristics and Column Generation for a Basic Technician Routing Problem
## 3 MILP Compact Formulations
### First MILP Formulations  
We define binary variables \(u_{i,n,n^{\prime}}\in\{0,1\}\) for each technician \(i\in\mathcal{I}\) and each pair of nodes \((n,n^{\prime})\in\mathcal{N}^{2}\), where \(u_{i,n,n^{\prime}}=1\) if and only if technician \(i\) proceeds to node \(n^{\prime}\) immediately after node \(n\). For each technician \(i\), such definition unifies routes between jobs locations \(u_{i,j,j^{\prime}}\) for each pair of jobs \((j,j^{\prime})\in\mathcal{J}^{2}\), a route between depot and job location, respectively, \(u_{i,i,j}=1\) and \(u_{i,j,i}=1\), is defined to perform intervention \(j\in\mathcal{J}\) as the first or last job of the day and \(u_{i,i,i}=1\) is the case where technician \(i\) has no job in his working day. With such a definition, we need only to consider variables \(u_{i,n,n^{\prime}}\) for each technician \(i\in\mathcal{I}\) and each pair of nodes \((n,n^{\prime})\in(\mathcal{J}_{i}\cup\{i\})^{2}=\mathcal{N}_{i}^{2}\), and the other variables are zeros with skill constraints and definition of departure and arrival depots. Furthermore, we introduce continuous variables \(t_{j}\) by representing the start time for job \(j\), bounded with the time-windows constraints. It results in the following MILP compact formulation below. The objective (1) for minimizing is composed of two linear expressions of variables \(u_{i,n,n^{\prime}}\), the total length of the routes and the penalties for postponed or outsourced jobs \(j\) having zero values for variables \(u_{i,n,j}\) for all \(i\in\mathcal{I}\) and \(n\in\mathcal{N}\). Constraints (3) are implied by the definition of variables, \(u_{i,i,j}=0\) for each technician \(i\in\mathcal{I}\) and each job \(j\in\mathcal{J}\). Constraints (2) are elementary constraints: Each intervention is realized at most one; it can be postponed or outsourced if variables \(u_{i,n,j}\) are zeros for \(i\in\mathcal{I}\) and \(n\in\mathcal{N}\). With triangle inequality, it is sub-optimal to visit a customer twice or more times. Indeed, having triangle inequalities \(D_{n,n^{\prime}}+D_{n^{\prime},n^{\prime\prime}}\geqslant D_{n,n^{\prime\prime}}\) and \(T_{n,n^{\prime}}+T_{n^{\prime},n^{\prime\prime}}\geqslant T_{n,n^{\prime\prime}}\), removing jobs planned twice, is still a feasible solution, and it decreases the objective function; there is an optimal solution allocating exactly one technician per job. Elementarity constraints are necessary here in the MILP model as multiple visits induce a negative penalization and, thus, a high bonus in the objective function. Constraints (4) are flow conservation constraints for modelling routes for technicians: the flow leaving and the flow arriving to a node for technician \(i\) is the same flow that is leaving from the node. Constraints (5) initialize flow constraints;there is exactly one arc leaving from a depot, and it can be \(u_{i,j,i}=1\) in the case of an empty route for technician \(i\) so that, in any case, the leaving flow is exactly one. Note that constraints (4) and (5) imply that \(\sum_{n\in\mathcal{N}_{i}}u_{i,n,i}=1\) for all technician \(i\), which is a one value flow for going back to the depot; such constraints are not necessary. Constraints (2) can be seen as flow capacity constraints. Constraints (6)-(8) express time windows constraints, respectively, between two consecutive jobs and for the starting and finishing time of technicians. With constraints (6)-(8), the formulation does not require any sub-tour constraints. Coefficients \(M^{1}_{j,j^{\prime}}\), \(M^{2}_{i,j}\) and \(M^{3}_{i,j}\) can be chosen as follows: \(M^{1}_{j,j^{\prime}}=T^{max}_{j}+L_{j}+T_{j,j^{\prime}}-T^{min}_{j^{\prime}}\), \(M^{2}_{i,j}=T^{start}_{i}+T_{i,j}-\tilde{T}^{min}_{j}\) and \(M^{3}_{i,j}=T^{max}_{j}+L_{j}+T_{i,j}-T^{end}_{i}\).