Comparison of GA Based Heuristic and GRASP Based Heuristic for Total Covering Problem
ABSTRACT
This paper discusses the comparison of two different heuristics for total covering problem. The total covering problem is a facility location problem in which the objective is to identify the minimum number of sites among the potential sites to locate facilities to cover all the customers. This problem is a combinatorial problem. Hence, heuristic development to provide solution for such problem is inevitable. In this paper, two different heuristics, viz., GA based heuristic and GRASP based heuristic are compared and the best is suggested for implementation.
This paper discusses the comparison of two different heuristics for total covering problem. The total covering problem is a facility location problem in which the objective is to identify the minimum number of sites among the potential sites to locate facilities to cover all the customers. This problem is a combinatorial problem. Hence, heuristic development to provide solution for such problem is inevitable. In this paper, two different heuristics, viz., GA based heuristic and GRASP based heuristic are compared and the best is suggested for implementation.
KEYWORDS
Genetic Algorithm, GRASP, Total Covering Problem, Boolean Operators, Care and Share Operator
Genetic Algorithm, GRASP, Total Covering Problem, Boolean Operators, Care and Share Operator
Cite this paper
nullC. Vijeyamurthy and R. Panneerselvam, "Comparison of GA Based Heuristic and GRASP Based Heuristic for Total Covering Problem," iBusiness, Vol. 2 No. 2, 2010, pp. 156-167. doi: 10.4236/ib.2010.22019.
nullC. Vijeyamurthy and R. Panneerselvam, "Comparison of GA Based Heuristic and GRASP Based Heuristic for Total Covering Problem," iBusiness, Vol. 2 No. 2, 2010, pp. 156-167. doi: 10.4236/ib.2010.22019.
References
[1] R. Panneerselvam, “Production and Operations Management,” 2nd Edition, Prentice-Hall India (P) Ltd., New Delhi, 2005. [2] C. Toregas, R. Swain, C. Revelle and L. Bergman, “The Location of Emergency Service Facilities,” Operations Research, Vol. 19, No. 6, 1971, pp. 1363-1373. [3] N. R. Patel, “Location of Rural Social Service Centers in India,” Management Science, Vol. 25, No. 1, 1979, pp. 22-30. [4] T. D. Klastorin, “On the Maximal Covering Location Pro- blem and the Generalized Assignment Problem,” Management Science, Vol. 25, No.1, 1979, pp. 107-111. [5] O. Saatcioglu, “Mathematical Programming Model for Airport Site Selection,” Transportation Research-B, Vol. 16B, No. 6, 1982, pp. 435-447. [6] A. W. Neebe, “A Procedure for Locating Emergency- Service Facilities for All Possible Response Distances,” Journal of Operational Research Society, Vol. 39, No. 8, 1988, pp. 743-748. [7] R. Panneerselvam, “A Heuristic Algorithm for Total Covering Problem,” Industrial Engineering Journal, Vol. 19, No. 2, 1990, pp. 1-10. [8] G. Rajkumar and R. Panneerselvam, “An Improved Heuristic for Total Covering Problem,” Industrial Engineering Journal, Vol. 20, No. 8, 1991, pp. 4-7. [9] R. Panneerselvam, “Efficient Heuristic for Total Covering Problem,” Productivity, Vol. 36, No. 4, 1996, pp. 649- 657. [10] M. E. O’Kelly, “The Location of Interacting Hub Facilities,” Transportation Science, Vol.20, No.2, 1986, pp. 92- 106. [11] T. B. Boffey, “Location Problems Arising in Computer Networks,” Journal of Operational Research Society, Vol. 40, No. 4, 1989, pp. 347-354. [12] T. J. Chen and C. A. Yano, “A Multiplier Adjustment Approach for Set Partitioning Problem,” Operations Research, Vol. 40, No. 1, 1992, pp. 40-47. [13] W. A. Chaovalitwongse, T. Y. Berger-Wolf, B. Dasgupta and M. V. Ashley, “Set Covering Approach for Reconstruction of Sibling Relationships,” Optimization methods and software, Vol. 22, No. 1, 2007, pp. 11-24. [14] B. Pelegrin, J. L. Redondo, P. Fernandez, I. Garcia and P. M. Ortigosa, “GASUB: Finding Global Optima to Discrete Location Problems Genetic—Like Algorithm,” Journal of Global Optimization, Vol. 38, No. 2, 2007, pp. 249-264. [15] Sibel A. Alumur, Bahar Y. Kara and Oya E. Karasan, “The Design of Single Allocation in Complete Hub Ne- tworks,” Transportation Research B: Methodological, Vol. 43, No. 10, 2009, pp. 936-951. [16] V. Marianov, M. Mizumori and C. Re Velle, “The Heuristic Concentration—Integer and its Application to a Class of Location Problems,” Computers and Operations Research, Vol. 36, No. 5, 2009, pp. 1406-1422. [17] De A. C. Francisco, N. L. L. Antonio and M. R. Glaydston, “A Decomposition Approach for the Probabilistic Maximal Covering Location—Allocation Problem”, Computers and Operations Research, Vol. 36, No. 10, 2009, pp. 2729-2739. [18] V. Batanovic, D. Petrovic and R. Petrovic, “Fuzzy Logic Based Algorithms for Maximum Covering Location Problems,” Information Sciences, Vol. 179, No. 1-2, 2009, pp. 120-129. [19] T. A. Feo and M. G. C. Resende, “Greedy Randomized Adaptive Search Procedures,” Journal of Global Optimization, Vol. 6, 1995, pp. 109-133. [20] R. Panneerselvam, “Research Methodology,” Prentice- Hall India (P) Ltd., New Delhi, 2004.
[1] R. Panneerselvam, “Production and Operations Management,” 2nd Edition, Prentice-Hall India (P) Ltd., New Delhi, 2005. [2] C. Toregas, R. Swain, C. Revelle and L. Bergman, “The Location of Emergency Service Facilities,” Operations Research, Vol. 19, No. 6, 1971, pp. 1363-1373. [3] N. R. Patel, “Location of Rural Social Service Centers in India,” Management Science, Vol. 25, No. 1, 1979, pp. 22-30. [4] T. D. Klastorin, “On the Maximal Covering Location Pro- blem and the Generalized Assignment Problem,” Management Science, Vol. 25, No.1, 1979, pp. 107-111. [5] O. Saatcioglu, “Mathematical Programming Model for Airport Site Selection,” Transportation Research-B, Vol. 16B, No. 6, 1982, pp. 435-447. [6] A. W. Neebe, “A Procedure for Locating Emergency- Service Facilities for All Possible Response Distances,” Journal of Operational Research Society, Vol. 39, No. 8, 1988, pp. 743-748. [7] R. Panneerselvam, “A Heuristic Algorithm for Total Covering Problem,” Industrial Engineering Journal, Vol. 19, No. 2, 1990, pp. 1-10. [8] G. Rajkumar and R. Panneerselvam, “An Improved Heuristic for Total Covering Problem,” Industrial Engineering Journal, Vol. 20, No. 8, 1991, pp. 4-7. [9] R. Panneerselvam, “Efficient Heuristic for Total Covering Problem,” Productivity, Vol. 36, No. 4, 1996, pp. 649- 657. [10] M. E. O’Kelly, “The Location of Interacting Hub Facilities,” Transportation Science, Vol.20, No.2, 1986, pp. 92- 106. [11] T. B. Boffey, “Location Problems Arising in Computer Networks,” Journal of Operational Research Society, Vol. 40, No. 4, 1989, pp. 347-354. [12] T. J. Chen and C. A. Yano, “A Multiplier Adjustment Approach for Set Partitioning Problem,” Operations Research, Vol. 40, No. 1, 1992, pp. 40-47. [13] W. A. Chaovalitwongse, T. Y. Berger-Wolf, B. Dasgupta and M. V. Ashley, “Set Covering Approach for Reconstruction of Sibling Relationships,” Optimization methods and software, Vol. 22, No. 1, 2007, pp. 11-24. [14] B. Pelegrin, J. L. Redondo, P. Fernandez, I. Garcia and P. M. Ortigosa, “GASUB: Finding Global Optima to Discrete Location Problems Genetic—Like Algorithm,” Journal of Global Optimization, Vol. 38, No. 2, 2007, pp. 249-264. [15] Sibel A. Alumur, Bahar Y. Kara and Oya E. Karasan, “The Design of Single Allocation in Complete Hub Ne- tworks,” Transportation Research B: Methodological, Vol. 43, No. 10, 2009, pp. 936-951. [16] V. Marianov, M. Mizumori and C. Re Velle, “The Heuristic Concentration—Integer and its Application to a Class of Location Problems,” Computers and Operations Research, Vol. 36, No. 5, 2009, pp. 1406-1422. [17] De A. C. Francisco, N. L. L. Antonio and M. R. Glaydston, “A Decomposition Approach for the Probabilistic Maximal Covering Location—Allocation Problem”, Computers and Operations Research, Vol. 36, No. 10, 2009, pp. 2729-2739. [18] V. Batanovic, D. Petrovic and R. Petrovic, “Fuzzy Logic Based Algorithms for Maximum Covering Location Problems,” Information Sciences, Vol. 179, No. 1-2, 2009, pp. 120-129. [19] T. A. Feo and M. G. C. Resende, “Greedy Randomized Adaptive Search Procedures,” Journal of Global Optimization, Vol. 6, 1995, pp. 109-133. [20] R. Panneerselvam, “Research Methodology,” Prentice- Hall India (P) Ltd., New Delhi, 2004.