# Matheuristics and Column Generation for a Basic Technician Routing Problem
## 7 Conclusions and Perspectives  
This work provided several results and offers different perspectives. The CG algorithm is efficient for computing dual and primal bounds for the TRPTW coherently with the results obtained for VRPTW problems. The LP relaxation of the DW extended formulation efficiently guides us toward primal solutions of an excellent quality.Matheuristics based on the compact ILP formulation may be inefficient even with combinations of large neighborhoods in a VND local search, contrary to [4], or with parallelization using a portfolio of matheuristics, contrary to [5]. We note also a similarity with [25]: improving the exact methods and MILP formulations is a first step before applying MILP models to matheuristics, and the first step is crucial for the efficiency of the resulting matheuristic. If CG heuristics are particularly efficient in terms of quality, the key point is to speed up and stabilize the convergence of the CG algorithm. Two matheuristic components are proposed and proven efficient for TRPTW. On the one hand, the heterogeneity of sub-problems allows a POPMUSIC decomposition to generate columns by avoiding redundancy in the served requests for a better re-combination in the RMP computation. ML techniques are used to generate appropriate partitions, illustrating the impact of hybridizing ML and ILP techniques. On the other hand, a Tabu matheuristic intensification for sub-problems avoids generating similar columns in neighbor iterations of the CG algorithm, decreasing the number of iterations to converge. POPMUSIC matheuristic is efficient for the first CG iterations where it is difficult to serve all the requests, whereas TS intensification remains efficient for the last phases of the CG algorithm where dual values are quite stable. For both schemes, heuristic solving schemes are designed to speed up the search of negative reduced cost columns, and light heuristics are firstly processed and then heavier matheuristics are used speed up the time of first CG iterations. A perspective would be to improve the exact solutions of such sub-problems for the validated CG scheme by using labelling algorithms. Note that TS intensification and many matheuristics are compatible with labelling algorithms; a perspective is to implement such matheuristics without using an MILP solver. Possessing many strategies and hybridizations for generating columns is a good characteristic with parallelization in a multi-core environment. We note that our final approach investigates and combines the three types of matheuristics for VRPTW problems in the taxonomy of [15]: _CG-based heuristics_ as a general framework, with computation of primal and dual bounds; _improvement heuristics_ with local search procedures to improve the integer RMP heuristics and to solve CG sub-problems); and _decomposition approaches_ to initialize CG and also in the sub-problem resolution of CG. In such hybridization, mathematical programming is hybridized with the trajectory of local search metaheuristics. A perspective is also to investigate the collaboration between CG heuristics and population metaheuristics. The aggressive CG scheme and benefits or diversification highlighted in this paper offer perspectives to solve CG sub-problems and generate several columns with GA, PSO or ACO heuristics. Recent advances for these population meta-heuristics are promising for such applications [80; 81; 82; 83]. Our instances are now public, and the graduations of difficulty and highly constrained instances with fewer possible neighbor moves are useful for challenging local search implementation. The first results with LocalSolver were already good, with some difficulties on highly constrained instances; we note that our instances are now in their benchmark instances to help the parametrization of their generic solver. This is a perspective for other generic codes with local search applied for vehicle routing problems.