# Matheuristics and Column Generation for a Basic Technician Routing Problem
## 1 Introduction  
If mathematical programming and especially Mixed Integer Linear Programming (MILP) are powerful frameworks for modeling a vast diversity of \(\mathcal{NP}\)-hard combinatorial optimization problems, including complex real-world optimization problems, the resolution with exact methods such as the Branch and Bound (B&B) algorithm is limited in practice for large instances of real-world applications [1]. Metaheuristics find good solutions of large optimization problems without optimality or quality proofs. Highly constrained instances of optimization problems are a major bottleneck of metaheuristics. Metaheuristics and mathematical programming approaches have complementary advantages and drawbacks, and it results in their hybridization, called _matheuristics_[2, 3]. Some matheuristics use exact methods to solve large neighborhoods of an exponential size, which tends to have fewer local minimums of a better quality than by using small neighborhoods [2, 4]. Solving the exact neighborhoods allows studying the quality of implied local minimums; such intermediate results are of interest for selecting which types of neighborhoods have to be carefully implemented in a local search heuristic [4]. Matheuristics allow designing many variants of heuristic operators; it takes profit of parallel implementation techniques [5]. Having also other complementary advantages and drawbacks, machine learning (ML) techniques are also recently considered in such hybridization schemes [6, 7]. Note that such hybridization can also provide dual bounds for large instances of optimization problems, using aggregation or decomposition techniques to compute dual bounds for heuristicallyreduced or decomposed problems with a proof that a dual bound of the original problem is computed despite the heuristic reduction [8; 9]. ML techniques are useful in this context for selecting the promising dual bound among many alternatives [9]. Such methodology is investigated for a variant of the Vehicle Routing Problem with Time Window (VRPTW), seeking to service customers in defined time windows with a fleet of vehicles. VRPTW is a widely studied problem in the operations research literature due to its numerous applications in transportation, distribution and logistics, with significant academic works in MILP formulations and metaheuristics [10]. Among the exact methods, Column Generation (CG) approaches are efficient for a large class of vehicle routing problems and are actively studied nowadays [11; 12]. CG approaches can be extended to CG heuristics or used in any hybrid heuristic to tackle large instances of vehicle routing problems [13; 14; 15]. Recently, the contribution of ML techniques for solving CG sub-problems is studied for some vehicle routing problems [16; 17]. This paper considers a variant of the VRPTW which is a common basis for many technician routing problems, as in [18; 19]. Site-dependency constraints model that customers can be served by only a subset of vehicles, which is related to the skills of technicians to engage in interventions. Contrary to VRPTW problems where each request must be served, we consider the possibility of realizing a subset of interventions by considering outsourcing costs. We consider, furthermore, multi-depot constraints: Technicians are starting and finishing their tours in different depots. Mathemuristics are investigated and compared to local search and exact approaches. New instances are proposed with relations between subsets of instances to analyze the impact of highly to weakly constrained instances in the solving capabilities of different optimization algorithms. This paper investigates how to design hybrid algorithms to solve this optimization problem efficiently. The remainder of this paper is structured as follows. Section 2 provides an overview of the problem statement and its state of the art. Section 3 presents two types of compact MILP formulations for the problem. Section 4 designs constructive and local search matheuristics by using compact MILP formulations.