Comparison of GA Based Heuristic and GRASP Based Heuristic for Total Covering Problem ()
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.