# Matheuristics and Column Generation for a Basic Technician Routing Problem
## 2 Problem Statement and Related Work
### Problem Statement and Notation  
The variant of VRPTW considered in this paper, namely TRPTW for Technician Routing Problem with Time Windows, is described by using the terminology from [18]. The routing optimization concerns a set of \(I\) vehicles with \(J\) requests and denoted jobs or interventions, in different locations of customers. Interventions require the specific skills of technicians and have time window constraints on the arrival time of the technicians. In the following developments, a technician denotes equivalently a vehicle, as if each vehicle is driven by a single technician, and interventions require only one technician with the required qualifications. One may consider equivalently a technician team, which is defined a priori in the optimization, sharing the same vehicle and working together in the interventions, and there is no splitting of a technician team for realizing different interventions at the same time. The resulting skills of the technician team are mathematically equivalent to a skill set and a subset of interventions that can be realized, as if we have a fictive single technician with these resulting skills. For the sake of simplifying the presentation, the following developments consider one technician by vehicle, with skills associated to this technician. Furthermore, technicians are starting and finishing their tour in defined depots, with time-window constraints for leaving and going back to the depot.  
It is possible to plan only a subset of interventions; a penalty in the objective function is associated for each request that is not served. The objective function to minimize is the total length of vehicles' routes, adding penalties for the interventions that are not realized. Such objective function may be observed as a weighted sum optimization, considering the bi-objective minimization of routing costs and unserved requests. Here, a weighted sum optimization makes sense with relevant values of penalties. Some interventions may be outsourced and realized by other companies, and penalties correspond to outsourcing costs. Some interventions may be urgent, and they are preferred be realized within the time horizon with high penalty, whereas other interventions can be postponed for another day and have low penalties. Having high and equal penalties for jobs is equivalent to a hierarchical optimization that firstly maximizes the number of jobs that are planned and then minimizing the route lengths. Mathematically, it is feasible for the optimization problem to have empty routes and only penalization. However, finding routes that serve all the requests is a NP-hard decision problem.  
The notation for sets, indexes and input parameters is gathered in Table 1. The jobs are indexed with \(j\in\mathcal{J}=\llbracket 1,J\rrbracket\). The intervention of job \(j\) has to begin in time window \([T_{j}^{min},T_{j^{max}}^{max}]\), its duration is \(L_{j}\) and its outsourcing cost is \(P_{j}\). For the sake of unifying notation, we indexed technicians with \(i\in\mathcal{I}=\llbracket J+1,J+I\rrbracket\) and defined nodes \(n\in\mathcal{N}=\mathcal{I}\cup\mathcal{J}=\llbracket 1,J+I\rrbracket\) to index the different locations of jobs and depots for departure and arrival of technicians' routes. \(D_{n,n^{\prime}}\) and \(T_{n,n^{\prime}}\) denote, respectively, the kilometric distance and transportation time from the location of node \(n\) to its of node \(n^{\prime}\). Note that distances are calculated with Euclidean rules so that we have 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}}\). Technician \(i\in\mathcal{I}\) starts from his depot after \(T_{i}^{start}\) and must be back at his depot before \(T_{i}^{end}\). \(\mathcal{J}_{i}\) denotes the subset of jobs that technician \(i\) can complete.