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.

Additional Metadata
Persistent URL dx.doi.org/10.1287/ijoc.1090.0376, hdl.handle.net/1765/118017
Journal I N F O R M S Journal on Computing: charting new directions in OR and CS
Rights No Subscription
Muter, I, Birbil, S.I, & Sahin, G. (2010). Combination of meta-heuristic and exact algorithms for solving set covering-type optimization problems. I N F O R M S Journal on Computing: charting new directions in OR and CS, 22(4), 603–619. doi:10.1287/ijoc.1090.0376