# Matheuristics and Column Generation for a Basic Technician Routing Problem
## 2 Problem Statement and Related Work
### Related Problems in the Literature  
#### 2.2.1 Related Vehicle Routing Problems  
Some classical variants of VRPTW are sub-cases of TRPTW. In the instances of the literature, the VRPTW considers complete graphs: Each vehicle can visit each city [20]. The simplest variant of VRPTW considering that some jobs can be realized by only a subset \begin{table}
\begin{tabular}{c l} \hline \hline \(I\) & Number of technicians (or equivalently vehicles). \\ \hline \(J\) & Number of jobs (or equivalently customers, requests, or request location). \\ \hline \(n\in\mathcal{N}=\llbracket 1,J+I\rrbracket\) & Index and set for nodes, a node is a technician depot or a job location. \\ \hline \(j\in\mathcal{J}=\llbracket 1,J\rrbracket\) & Index and set for customers, the jobs for the technicians. \\ \hline \(i\in\mathcal{I}=\llbracket J+1,J+I\rrbracket\) & Index and set for technicians. \\ \hline \(\mathcal{J}_{i}\) & Subset of jobs that technician \(i\in\mathcal{I}\) can complete with skill constraints. \\ \hline \(\mathcal{N}_{i}=\mathcal{J}_{i}\cup\{i+J\}\) & Subset of nodes that technician \(i\in\mathcal{I}\) can visit (depot and skill constraints). \\ \hline \(L_{j}\) & Duration (amount of time) of job \(j\in\mathcal{J}\). \\ \hline \(P_{j}\) & Cost penalization if job \(j\in\mathcal{J}\) is not planned (or outsourcing cost). \\ \hline \(K_{i}\) & Upper bound for the number of jobs that technician \(i\in\mathcal{I}\) can process. \\ \hline \(D_{n,n^{\prime}}\) & Distance from the location of node \(n\in\mathcal{N}\) to the location of node \(n^{\prime}\in\mathcal{N}\). \\ \hline \(T_{n,n^{\prime}}\) & Transportation time from the location of node \(n\in\mathcal{N}\) to the location of node \(n^{\prime}\in\mathcal{N}\). \\ \hline \([T_{i}^{start},T_{i}^{end}]\) & Working time window for technician \(i\in\mathcal{I}\), to leave and come back to the depot. \\ \hline \([T_{j}^{min},T_{j}^{max}]\) & Time window for the beginning of job \(j\in\mathcal{J}\). \\ \hline \hline \end{tabular} N.B: \([a,b]=[a,b]\cap\mathbb{Z}\) denotes integer intervals in this table.  
\end{table} 
Table 1: Notation, sets, indexes and input parameters. of vehicles is the _Site-dependent_ VRPTW (SDVRPTW) [21]. The extension of the VRPTW considering several depots is known as _Multi-depot_ VRPTW (MDVRPTW) [22]. There is one major difference between TRPTW and a site dependent MDVRPTW: contrary to VRPTW extensions, it is feasible to serve any subset of the requests for TRPTW by considering outsourcing costs, i.e., penalties for interventions that are not realized. MDVRPTW and SDVRPTW are sub-problems of TRPTW considering the same transportation graph, high and equal outsourcing costs for jobs and upper bounds of any route visiting each customer (which can be calculated easily): If the optimal cost of such TRPTW is greater than the upper bound, the original MDVRPTW or SDVRPTW is not feasible; otherwise, we have an optimal solution visiting each customer. We note that such outsourcing costs or equivalently fictive vehicles with the penalization cost are used by CG approaches for VRPTW problems to ensure feasibility for CG iterations [23]. Skill VRPTW is another variant of the VRPTW inspired by technician routing applications [24; 25]. Skills model the ability of vehicles (or technicians) to proceed to specific locations (or intervention with specific qualification). Skills are equivalent to site-dependencies, and skills VRPTW and SDVRPTW have the same set of feasible solutions. Skill VRPTW is an extension of SDVRPTW, and costs of vehicle usage are increasing with skills, whereas costs depend only on traveled distance for SDVRPTW. Note that Heterogeneous Fleet VRPTW (HFVRPTW), where vehicles are differentiated in the travel time and costs, is a common extension for skills VRPTW and SDVRPTW [26]. Indeed, site-dependent constraints can be considered with infinite costs (or a trivial upper bound of any feasible solution) in a HFVRPTW.