Evolutionary Search Techniques to Solve Set Covering Problems

Set covering problem is a classical problem in computer science and complexity theory. It has many applications, such as airline crew scheduling problem, facilities location problem, vehicle routing, assignment problem, etc. In this paper, three different techniques are applied to solve set covering problem. Firstly, a mathematical model of set covering problem is introduced and solved by using optimization solver, LINGO. Secondly, the Genetic Algorithm Toolbox available in MATLAB is used to solve set covering problem. And lastly, an ant colony optimization method is programmed in MATLAB programming language. Results obtained from these methods are presented in tables. In order to assess the performance of the techniques used in this project, the benchmark problems available in open literature are used.

Authors:

• Darwin Gouwanda
• S. G. Ponnambalam

Keywords:

• Set covering problem
• genetic algorithm
• ant colony optimization
• LINGO.

References:

[1] J.E. Beasley and P.C. Chu, "A genetic algorithm for the set covering
problem", European Journal of Operational Research, vol. 94, 1996, pp.
392-404
[2] J.E. Beasley, "An algorithm for set covering problem", European
Journal of Operational Research, vol. 31, 1987, pp 85-93
[3] J.E. Beasley, "A Lagrangian heuristic for set covering problems", Naval
Research Logistics, Vol. 37, 1990, pp. 151-164
[4] S. Haddadi, "Simple Lagrangian heuristic for the set covering problem",
European Journal of Operational Research, vol. 97, 1997, pp 200-204
[5] U. Aickelin, "An indirect genetic algorithm for set covering problem"
Journal of Operational Research Society, vol. 53, 2002, pp. 1118-1126
[6] A. Monfroglio, "Hybrid heuristic algorithm for set covering",
Computers Operational Research, vol. 25, 1998, pp. 441-445
[7] J.F. Vasko and F.E. Wolf, " A heuristic concentration approach for
weighted set covering problems", Locator: ePublication of Location
Analysis, vol. 2, 2001, no. 1, pp. 1-14
[8] OR-Library: http://people.brunel.ac.uk/~mastjjb/jeb/orlib/scpinfo.html
[9] E. Balas, and A. Ho, "Set covering algorithms: using cutting planes,
heuristics and subgradient optimization: a computational study",
Mathematical Programming Study, vol. 12, 1980, pp. 300-304.
[10] Lindo System, Lingo 8.0 user-s manual, 2003
[11] The Mathworks, Matlab-s Genetic Algorithm and Direct Search Toolbox
User-s Guide, The Matworks, 2005, Massachusetts
[12] M. Gen, R. Cheng, Genetic Algorithms and Engineering Optimization,
John Wiley & Sons, 2000, Canada
[13] L. Lessing, I. Dumitrescu, and T. Stutzle, "A comparison between ACO
algorithms for the set covering problem", ANTS 2004, LNCS 3172, 2004,
pp. 1-12
[14] M. Rahoual, R. Hadji, and V. Bachelet, "Parallel ant system for the set
covering problem" ANTS 2002, LNCS 2463, 2002 pp. 262 - 267.