# Matheuristics and Column Generation for a Basic Technician Routing Problem
## 2 Problem Statement and Related Work
### Algorithms for Solving Related Problems
#### 2.3.2 Solving Technical Routing Problems  
Efficient algorithms for solving technician routing problems are similar to the ones for VRPTW extensions. Since recently, technician routing problems were mostly solved by heuristics. An ALNS algorithm was proposed to solve a TRSP as a SDVRPTW extension [31]. A simple Iterated Local Search (ILS) has been proposed for the same problem and showed excellent results in short solving time [32]. Population meta-heuristics showed also excellent results for technician routing problems. Multi-attribute VRPTW is an extension that is also a basis for technician routing problems; hybrid GAs were shown to be efficient [51]. A Particle Swarm Optimization (PSO) algorithm was proven efficient for solving a TRSP [52]. An ACO heuristic was designed to solve efficiently a multi-period workforce scheduling and routing problem with dependent tasks [53].  
Recent progresses in MILP solving allow considering exact methods for technician routing problems with CG algorithms, B&P and B&C&P approaches [54; 55; 56]. In the previously mentioned TRP with site-dependencies, two approaches considered a matheuristic using an MILP set covering formulations [33; 57]. In such cases, an MILP computation selects routes among routes that are calculated by heuristics, similarly with the master problem of the CG algorithm. In such cases, the columns are generated by using only heuristics and without using reduced costs, a parallel ALNS for [33] and an hybridization of ALNS and Variable Neighborhood Descent (VND) for [57].  
Due to the large diversity of specific technician routing problems that were studied [30], we focus in the following on algorithms solving VSC 2018-2019 [19] and the ROADEF Challenge 2007 [18]. For such problems, several studies deal with exactly the same optimization problem and public instances; it allows relevant comparisons. The winner of VSC 2018-2019 used a trajectory local search heuristic, which is a hybridization of ALNS and Variable Neighborhood Search (VNS) [58]. A similar quality of results was obtained with a set partitioning matheuristic \"Columnwise neighborhood search\" [59]. Competitive results were also obtained with a population hyper-heuristic [60] and by using an iterated local search using several neighborhood search operators and destroy/repair heuristics [61].  
The winner of the ROADEF Challenge 2007 considered a three phase matheuristic [48]. A preprocessing phase estimates the number of technicians required in each team through the first MILP. Then, a second MILP computes a lower bound allowing job preemption. Multiple solutions are constructed by iteratively solving a third MILP by matching formulation with different parameter values but without introducing randomness. This approach was improved after by [62]. Another two-step decomposition matheuristic provided good results and is ranked fifth [63]. Trajectory heuristics provided also excellent results, with ranks 2, 3 and 4, local search with multiple neighborhoods and operators for [64], ALNS for [65] and Greedy randomized adaptive search procedure (GRASP) for [66].