Two Neighbourhood-based Approaches for the Set Covering Problem

Main Article Content

Eduardo Meca Castro

Abstract

The Set Covering Problem is a well-known NP-complete problem which we address in this work. Due to its combinatorial nature heuristic methods, namely neighbourhood-based meta-heuristics, were used.
Based on the well-known algorithms GRASP, Simulated Annealing and Variable Neighbourhood Descend, along with a constructive heuristic based on a dynamic dispatching rule to generate initial feasible solutions, two approaches to the problem were formulated. The performance of both methods was assessed in 42 instances of the problem. Our best approach has an average deviation from the best-known solution of 0.23% and reached 0% for 26 instances under 40 minutes.

Downloads

Download data is not yet available.

Article Details