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.

Share and Cite:

Vijeyamurthy, C. and Panneerselvam, R. (2010) Comparison of GA Based Heuristic and GRASP Based Heuristic for Total Covering Problem. iBusiness, 2, 156-167. doi: 10.4236/ib.2010.22019.

1. Introduction

Consider a sales region of a product, which in turn has different customer regions. The company selling the product should fix necessary number of dealer points such that the customers in that sales region are fully served. The company may fix a maximum of say 5 km of distance for the customers to reach a given dealer point from his/her region (customer region). In this process, a given customer may be covered by more than one dealer point. The objective is to locate the minimum number of dealer points in the sales region under consideration such that those dealer points cover all the customers regions.

Here, the process of serving a customer region by a dealer point is called as covering that customer region by that dealer point. The word “cover” means that the location of a customer is well within the given upper limit for the distance from a facility-location from where that customer will be served. Here, the objective is to locate facilities at minimum number of sites to cover all the customers. Such problem is known as total covering problem [1].

Consider a problem in which dealer points are to be located to serve the customers in a sales region. Assume that there are six customer regions, which are to be covered by dealer points. In this problem, five potential locations are identified for locating dealer points. The distance matrix between the customer regions is as shown in Table 1.

Now, a distance criterion of say, 5 km is assumed. This means that no region in the sales region is beyond 5 km from a site where a dealer is located. Based on this assumption, a covering coefficient is defined as shown below.

Let,        , if

, otherwise where, cij is the covering coefficient for the customer region i and the potential dealer point j and dij is the distance between the customer region i and the potential dealer point j. Based on this definition of covering coefficient, the corresponding covering coefficient matrix is shown in Table 2.

A careful examination of the Table 2 reveals that if the potential site 1 and the potential site 3 are assigned with dealers, all the six customer regions in the sales regions will be fully covered. As per this coverage, the potential site 1 will cover the customer regions 1, 2 and 4 and the potential site 3 will cover the customer regions

Table 1. Distance matrix of locating dealer points (distance in km)

Table 2. Covering coefficients matrix of locating dealer points

1, 2, 3, 5 and 6. The customer regions 1 and 2 are covered by the facilities from both the selected potential sites. This is an example of multiple-coverage of some custommers by a set of facilities. The different examples of total covering problem are shown in Table 3. The total covering problem falls under combinatorial category. Hence, it is inevitable to design an efficient heuristic to obtain near optimal solution. In this paper, an attempt has been made to develop and compare a genetic algorithm based heuristic and a GRASP based heuristic for the total covering problem.

2. Review of Literature

The covering problem comes under the facilities location problem. The covering problem can be classified into total covering problem and partial covering problem. The objective of the total covering problem is to cover all the customers with the minimum number of facilities whereas the objective of the partial covering problem is to cover as many customers as possible with the minimum number of facilities without exceeding the limit on the utmost number of facilities to be operated as suggested by the management. In this research, the total covering problem is considered.

Toregas et al. [2] have developed a liner programming model to solve the traditional set covering problem with equal cost in the objective function. Patel [3] has used dynamic programming approach for locating rural social service centers for the Dharampur taluka in South Gujarat in India. Klastorin [4] has solved the conventional set-covering problem by mapping it into an assignment problem. Saatcioglu [5] has used a mathematical model for airport site selection based on Turkish data. Neebe [6]

Table 3. Examples of total covering problem

has developed a procedure for locating emergency-service facilities for all possible response distances. Panneerselvam [7] has developed a heuristic procedure for the total covering problem. Rajkumar and Panneerselvam [8] have improved the work of Panneerselvam [7]. Later, Panneerselvam [9] has developed an efficient heuristic for the total covering problem. O’kelly [10] demonstrated the use of covering problem for locating interacting hub facilities. Hubs are central facilities, which act as switching points in networks connecting a set of interacting nodes. Boffey [11] has discussed the location problems arising in computer networks.

Chan et al. [12] have developed a branch and bound algorithm with multiplier adjustment for the traditional set-covering problem. Chaovalitwongse, Berger-Wolf, Dasgupta and Ashley [13] have conducted a simulation study of their proposed algorithm to demonstrate that their combinatorial approach is reasonably accurate. The results suggests the proposed algorithm would pave a way to a new approach in computational populations genetics as it does not require any a priori knowledge about allele frequency, population size, mating system or family size distributions to reconstruct sibling relationships. To extract the minimum number of biologically consistent sibling groups, the proposed combinatorial approach is employed to formulate this minimization problem as a set covering problem.

Pelegrin, Redondo, Fernandez, Garcia and Ortigosa [14] have proposed genetic like algorithm, GASUB for finding the global optima to discrete location problems. The authors claim that the algorithm finds the predetermined number of global optima, if they exist, for a variety of discrete location problems. GASUB has been compared to MSH, the multi start substitution method and found that it gave better solutions than MSH. Alumur, Kara and Karasan [15] have classified and surveyed the hub location models, including the recent trends on hub location and provided a synthesis of the literature. The hub location problem is concerned with locating hub facilities and allocating demand nodes to hubs in order to route the traffic between origin-destination pairs. Hubs are special facilities that serve as switching, transshipment and sorting points in many—to—many distribution systems.

Marianov, Mizumori and Re Velle [16] proposed a new heuristic, called heuristic concentration—integer (HCI). The authors have applied the algorithm to the maximal availability location problem (MALP) and the solutions are compared to those obtained using linear programming with branch and bound. They claim that HCI could find good solutions to the problems in a reasonable time compared to LP-IP solutions. Francisco, Antonio and Glaydston [17] have presented a solution procedure for probabilistic model using column generation having constraint in waiting time, queue length for congested system with one or more servers per service center for the maximal covering location—allocation problems. The authors claim that the results were obtained in reasonable time. Batanovic, D. Petrovic and R. Petrovic [18] have considered the maximum covering location problems in networks in uncertain environments. They have proposed three new algorithms for choosing the best facility locations assuming that the demands at all nodes are equally important, the relative weights of demands at nodes are deterministic and weights of demand at nodes are imprecise. The algorithms are based on searching among potential facility nodes by applying comparison operations on discrete fuzzy sets.

The review of literature indicates that the researchers have developed mathematical models, branch and bound algorithms and heuristics. Since, the total covering problem comes under combinatorial category, the development of an efficient heuristic is inevitable. In this paper, the researchers have proposed a genetic algorithm based heuristic and a GRASP based heuristic for total covering problem and compared their performances.

3. Mathematical Model of Total Covering Problem

In general, all emergency/ essential service related situations are formulated as total covering problems.

A mathematical model of the total covering problem is presented below.

Let, m be the number of customers;

n be the number of potential sites;

cij be the covering coefficient for the customer i and potential site j Minimize

Subject to

for i = 1 to m.

wherexj = 1, if the potential site j is assigned with a facility;

= 0, otherwise, for j = 1, 2, 3,…, n.

The objective function minimizes the total number of sites selected for assigning facilities. The constraint i ensures that each customer is served/covered by at least one selected potential site which is assigned with a facility.

4. Development of Heuristics

The total covering problem falls under combinatorial category. Hence, it is inevitable to design an efficient heuristic to get near optimal solution. In this paper, the authors have made an attempt to develop a Genetic Algorithm (GA) based heuristic and a Greedy Randomized Adaptive Search Procedure (GRASP) based heuristic to obtain global optimum solution for the total covering problem.

4.1 GA Based Heuristic

Genetic algorithm is a meta-heuristic, which is used to find the solution to any combinatorial problem. It mimics the mechanism of selection and evolution. In order to achieve the objective, GA generates successive population of alternate solutions until obtaining a solution, which yields acceptable result. Within the generation of each successive operation, an improvement in the quality of the individual solution is achieved. Hence, GA can quickly move to a successful outcome without determining every possible solution to the problem. The procedure used in the genetic algorithm is based on the fundamental processes that control the evolution of biological organisms, namely, natural selection and reproduction.

Organism’s ability to survive within its environment is improved by the two processes as explained below.

1) Natural selection determines which organism has the opportunity of reproduction and survival within a population.

2) Reproduction involves genes from two separate individuals combining to form offspring that inherit the survival characteristics of their parents.

This section presents a genetic algorithm based heuristic for total covering problem. The genetic algorithm has two major operations, viz. crossover operation and mutation. Consider the covering coefficient matrix, which is already shown in Table 2 and the same is reproduced in Table 4.

4.1.1 Crossover Operation

In this section, the crossover operation which is performed on two chromosomes to produce offspring is presented. To explain this operation, the encoding of the given covering coefficient data into chromosomes is as presented below.

The 0-1 entries in each of the rows of the covering coefficient matrix are treated as a chromosome. A zero entry in a chromosome represents non-allocation of facility to the respective potential site and one entry in that chromosome represents allocation of facility to the respective potential site. So, the sequence of 0-1 entries in each chromo

Table 4. Covering Coefficients Matrix of Locating Dealers

some represents the values of the decision variable xj, for j = 1, 2, 3, …, n, where xj = 1 if the potential site j is assigned with a facility; otherwise, it is equal to 0 and n is the total number of potential sites. So, entries in each chromosome give one possible solution to the total covering problem.

Conflicts of Interest

The authors declare no conflicts of interest.

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.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.

  翻译: