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

Author Biography

Eduardo Meca Castro, INESC TEC; Universidade do Porto

INESC TEC - INESC Tecnologia e Ciência

Campus da Faculdade de Engenharia da Universidade do Porto

Rua Dr. Roberto Frias

Edifício I

4200-465 PORTO

Portugal

Programa Doutoral em Engenharia Eletrotécnica e de Computadores

Faculdade de Engenharia

Universidade do Porto

Rua Dr. Roberto Frias

4200-465 PORTO

Portugal