Matheuristics to stabilize column generation: application to a technician routing problem

International audienceThis paper considers a simplified Technician Routing and Scheduling Problem with skill constraints, where a Column Generation (CG) heuristic was shown effective. This work proposes new CG schemes to stabilize the CG process and thus to accelerate the CG heuristics. Solving CG subproblems with matheuristics allows to diversify the column generation. Furthermore, a tabu search matheuristic allows to generate aggressively columns at each iteration. Both techniques imply a better stability of the CG scheme: the diversification is interesting for the first iterations whereas tabu intensification is especially useful for the last iterations. It implies a significant acceleration of the CG convergence. A perspective of these CG strategies proposed is an extension to other problems where CG induces independent and heterogeneous subprob-lems