Combination of Metaheuristic and Exact Algorithms for Solving Set Covering-Type Optimization Problems

We propose a new generic framework for solving combinatorial optimization problems that can be modeled as a set covering problem. The proposed algorithmic framework combines metaheuristics with exact algorithms through a guiding mechanism based on diversification and intensification decisions. After presenting this generic framework, we extensively demonstrate its application to the vehicle routing problem with time windows. We then conduct a thorough computational study on a set of well-known test problems, where we show that the proposed approach not only finds solutions that are very close to the best-known solutions reported in the literature, but also improves them. We finally set up an experimental design to analyze the effects of different parameters used in the proposed algorithm.