A Meta-Heuristic Algorithm for Set Covering Problem Based on Gravity
A new Meta heuristic approach called "Randomized gravitational emulation search algorithm (RGES)" for solving large size set covering problems has been designed. This algorithm is found upon introducing randomization concept along with the two of the four primary parameters -velocity- and -gravity- in physics. A new heuristic operator is introduced in the domain of RGES to maintain feasibility specifically for the set covering problem to yield best solutions. The performance of this algorithm has been evaluated on a large set of benchmark problems from OR-library. Computational results showed that the randomized gravitational emulation search algorithm - based heuristic is capable of producing high quality solutions. The performance of this heuristic when compared with other existing heuristic algorithms is found to be excellent in terms of solution quality.
[1] Aickelin, U., An indirect genetic algorithm for set covering problems,
Journal of the Operational Research Society 53, 1118-1126,2002.
[2] Almiana M, Pastor JT, An adaptation of SH heuristic to the location
set covering problem, European Journal of Operational Research;
100(3):586-93,1997
[3] Barry Lynn Webster, Solving combinatorial Optimization Problems using
a newalgorithm based on gravitational attraction, Ph.D., thesis, Melbourne,
Florida Institute of Technology, May 2004.
[4] Beasley J.E, An algorithm for set covering problems, European Journal
of Operational Research 31 85-93,1990
[5] Beasley J.E, A Lagrangean heuristic for set covering problems, Naval
Research Logistics ; 37(1):151-64,1990.
[6] Beasley J.E., Jornsten. K, Enhancing an algorithm for set covering
problems, European Journal of Operational Research 58, 293-300,1992.
[7] Beasley J.E, Chu PC, A genetic algorithm for the set covering problem,
EuropeanJournal of Operational Research; 94(2):392-404,1996.
[8] Brusco M.J.,.Jacobs L.W,.Thomson G.M, A morphing procedure to supplement
a simulated annealing heuristic for cost-and-coverage-correlated
set-covering problem, Annals of Operations Research 86, 611-627,1999.
[9] Caprara A. , Fischetti M. Toth ,P. ,D.vigo and Guida P.L., Algorithms
for railway crew management ,Mathematical programming 79 , 125 -
141,1997.
[10] Caprara A, Fischetti M, Toth P, A heuristic method for the set covering
problem, Operational Research; 47(5):730-743,1999.
[11] Ceria S., Nobili P., Sassano A, A Lagrangian-based heuristic for
large-scale set covering problems, Mathematical Programming 81, 215-
228,1998.
[12] Chvatal. V, A greedy heuristic for the set-covering problem,Mathematics
of Operations Research 4, 233-235,1979.
[13] Feo, T., Resende, M.G.C, A probabilistic heuristic for a computationally
difficult set covering problem. Operations ResearchLetters 8, 67-71,1989.
[14] Fisher M.L., Kedia P, Optimal solutions of set covering/partitioning
problems using dual heuristics, Management Science 36, 674-688,1990.
[15] Garey M.R. and. Johnson D.S, Computers and Intractability: A Guide
to the theory of NP-completeness , W.H.Freeman ,San Francisco,1979.
[16] Grossman T,Wool A, Computational experience with approximation
algorithms for the set covering problem. European Journal of Operational
Research; 101(1):81-92,1997.
[17] Guanghui Lan, Gail W. DePuy, Gary E. Whitehouse, An effective
and simple heuristic for the set covering problem, European Journal of
Operational Research 176, 1387-1403,2007.
[18] Haouari, M., Chaouachi, J.S., A probabilistic greedy search algorithm for
combinatorial optimization with application to the setcovering problem,
Journal of the Operational Research Society 53, 792-799,2002.
[19] Harche E and Thompson G.L., The column subtraction algorithm: An
exact method for solving weighted setcovering, packing and partitioning
problems, Computers and Operations Research 21, 689-705,1994.
[20] D. Holliday, R. Resnick, J. Walker, Fundamentals of physics, John Wiley
and Sons, 1993.
[21] Jacobs L.W. and Brusco M.J.,A simulated annealing based heuristic for
the set-covering problem, Working paper, Operations Management and
Information Systems Department, Northern Illinois University, Dekalb,
IL, 1993.
[22] Jacobs, L., Brusco, M., Note: A local-search heuristic for large setcovering
problems, Naval Research Logistics 42, 1129-1140.22,1995.
[23] I.R. Kenyon, General Relativity, Oxford University Press, 1990.
[24] Lessing L, Dumitrescu I, Sttzle T, A comparison between ACO algorithms
for the set covering problem, Lecture Notes in Computer Science;
3172;1-12,2004.
[25] Lopes FB, Lorena LA, Surrogate heuristic for set covering problems,
European Journal of Operational Research; 79(1):138-150,1994.
[26] R. Mansouri, F. Nasseri, M. Khorrami, Effective time variation of G in a
model universe with variable space dimension, Physics Letters 259,194-
200,1999.
[27] Ohlsson, M., Peterson, C., Soderberg, B., An efficient mean field
approach to the set covering problem, European Journal of Operational
Research 133, 583-595,2001.
[28] E. Rashedi, Gravitational Search Algorithm, M.Sc. Thesis, Shahid
Bahonar University of Kerman, Kerman, Iran, 2007.
[29] B. Schutz, Gravity from the Ground Up, Cambridge University Press,
2003.
[30] Sears,Francis W., Mark W.Zemansky and Hugh D. Young, University
Physics, 7th ed.Reading,MA.Addison - Wesley,1987.
[31] Solar M, Parada V, Urrutia R., A parallel genetic algorithm to solve
the set-covering problem, Computer Operational Research; 29(9):1221-
35,2002.
[32] Vasko, F.J., Wilson, G.R., An efficient heuristic for large set covering
problems, Naval Research Logistics Quarterly 31, 163-171,1984.
[33] Voudouris,chris and Edward Tsang, Guided Local Search, Technical
Report,CSM-247,Department of Computer Science,University of Essex,
UK,1995.
[34] Yagiura M, Kishida M, Ibaraki T., A 3-flip neighborhood local search
for the set covering problem, Technical Report 2004-001. Department
of Applied Mathematics and Physics, Graduate School of Informatics,
Kyoto University,2004
[1] Aickelin, U., An indirect genetic algorithm for set covering problems,
Journal of the Operational Research Society 53, 1118-1126,2002.
[2] Almiana M, Pastor JT, An adaptation of SH heuristic to the location
set covering problem, European Journal of Operational Research;
100(3):586-93,1997
[3] Barry Lynn Webster, Solving combinatorial Optimization Problems using
a newalgorithm based on gravitational attraction, Ph.D., thesis, Melbourne,
Florida Institute of Technology, May 2004.
[4] Beasley J.E, An algorithm for set covering problems, European Journal
of Operational Research 31 85-93,1990
[5] Beasley J.E, A Lagrangean heuristic for set covering problems, Naval
Research Logistics ; 37(1):151-64,1990.
[6] Beasley J.E., Jornsten. K, Enhancing an algorithm for set covering
problems, European Journal of Operational Research 58, 293-300,1992.
[7] Beasley J.E, Chu PC, A genetic algorithm for the set covering problem,
EuropeanJournal of Operational Research; 94(2):392-404,1996.
[8] Brusco M.J.,.Jacobs L.W,.Thomson G.M, A morphing procedure to supplement
a simulated annealing heuristic for cost-and-coverage-correlated
set-covering problem, Annals of Operations Research 86, 611-627,1999.
[9] Caprara A. , Fischetti M. Toth ,P. ,D.vigo and Guida P.L., Algorithms
for railway crew management ,Mathematical programming 79 , 125 -
141,1997.
[10] Caprara A, Fischetti M, Toth P, A heuristic method for the set covering
problem, Operational Research; 47(5):730-743,1999.
[11] Ceria S., Nobili P., Sassano A, A Lagrangian-based heuristic for
large-scale set covering problems, Mathematical Programming 81, 215-
228,1998.
[12] Chvatal. V, A greedy heuristic for the set-covering problem,Mathematics
of Operations Research 4, 233-235,1979.
[13] Feo, T., Resende, M.G.C, A probabilistic heuristic for a computationally
difficult set covering problem. Operations ResearchLetters 8, 67-71,1989.
[14] Fisher M.L., Kedia P, Optimal solutions of set covering/partitioning
problems using dual heuristics, Management Science 36, 674-688,1990.
[15] Garey M.R. and. Johnson D.S, Computers and Intractability: A Guide
to the theory of NP-completeness , W.H.Freeman ,San Francisco,1979.
[16] Grossman T,Wool A, Computational experience with approximation
algorithms for the set covering problem. European Journal of Operational
Research; 101(1):81-92,1997.
[17] Guanghui Lan, Gail W. DePuy, Gary E. Whitehouse, An effective
and simple heuristic for the set covering problem, European Journal of
Operational Research 176, 1387-1403,2007.
[18] Haouari, M., Chaouachi, J.S., A probabilistic greedy search algorithm for
combinatorial optimization with application to the setcovering problem,
Journal of the Operational Research Society 53, 792-799,2002.
[19] Harche E and Thompson G.L., The column subtraction algorithm: An
exact method for solving weighted setcovering, packing and partitioning
problems, Computers and Operations Research 21, 689-705,1994.
[20] D. Holliday, R. Resnick, J. Walker, Fundamentals of physics, John Wiley
and Sons, 1993.
[21] Jacobs L.W. and Brusco M.J.,A simulated annealing based heuristic for
the set-covering problem, Working paper, Operations Management and
Information Systems Department, Northern Illinois University, Dekalb,
IL, 1993.
[22] Jacobs, L., Brusco, M., Note: A local-search heuristic for large setcovering
problems, Naval Research Logistics 42, 1129-1140.22,1995.
[23] I.R. Kenyon, General Relativity, Oxford University Press, 1990.
[24] Lessing L, Dumitrescu I, Sttzle T, A comparison between ACO algorithms
for the set covering problem, Lecture Notes in Computer Science;
3172;1-12,2004.
[25] Lopes FB, Lorena LA, Surrogate heuristic for set covering problems,
European Journal of Operational Research; 79(1):138-150,1994.
[26] R. Mansouri, F. Nasseri, M. Khorrami, Effective time variation of G in a
model universe with variable space dimension, Physics Letters 259,194-
200,1999.
[27] Ohlsson, M., Peterson, C., Soderberg, B., An efficient mean field
approach to the set covering problem, European Journal of Operational
Research 133, 583-595,2001.
[28] E. Rashedi, Gravitational Search Algorithm, M.Sc. Thesis, Shahid
Bahonar University of Kerman, Kerman, Iran, 2007.
[29] B. Schutz, Gravity from the Ground Up, Cambridge University Press,
2003.
[30] Sears,Francis W., Mark W.Zemansky and Hugh D. Young, University
Physics, 7th ed.Reading,MA.Addison - Wesley,1987.
[31] Solar M, Parada V, Urrutia R., A parallel genetic algorithm to solve
the set-covering problem, Computer Operational Research; 29(9):1221-
35,2002.
[32] Vasko, F.J., Wilson, G.R., An efficient heuristic for large set covering
problems, Naval Research Logistics Quarterly 31, 163-171,1984.
[33] Voudouris,chris and Edward Tsang, Guided Local Search, Technical
Report,CSM-247,Department of Computer Science,University of Essex,
UK,1995.
[34] Yagiura M, Kishida M, Ibaraki T., A 3-flip neighborhood local search
for the set covering problem, Technical Report 2004-001. Department
of Applied Mathematics and Physics, Graduate School of Informatics,
Kyoto University,2004
@article{"International Journal of Engineering, Mathematical and Physical Sciences:64994", author = "S. Raja Balachandar and K. Kannan", title = "A Meta-Heuristic Algorithm for Set Covering Problem Based on Gravity", abstract = "A new Meta heuristic approach called "Randomized gravitational emulation search algorithm (RGES)" for solving large size set covering problems has been designed. This algorithm is found upon introducing randomization concept along with the two of the four primary parameters -velocity- and -gravity- in physics. A new heuristic operator is introduced in the domain of RGES to maintain feasibility specifically for the set covering problem to yield best solutions. The performance of this algorithm has been evaluated on a large set of benchmark problems from OR-library. Computational results showed that the randomized gravitational emulation search algorithm - based heuristic is capable of producing high quality solutions. The performance of this heuristic when compared with other existing heuristic algorithms is found to be excellent in terms of solution quality.
", keywords = "Set covering problem, velocity, gravitational force, Newton's law, meta heuristic, combinatorial optimization.", volume = "4", number = "7", pages = "1055-6", }
