Two Neighbourhood-based Approaches for the Set Covering Problem
Article Sidebar
Published:
Apr 26, 2019
Issue:
Vol. 5 No. 1 (2019)
Keywords:
Neighbourhood-based Metaheuristics, Metaheuristics, Set Covering Problem, Optimization, Variable Neighbourhood Descent, Simulated Annealing, Greedy Randomized Adaptative Search Procedure
Main Article Content
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
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors grant the journal the rights to provide the article in all forms and media so the article can be used on the latest technology even after publication and ensure its long-term preservation.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).