1 Introduction

Given an undirected weighted graph \(G=(V,E)\) with \(|V|=n\), the classical p-median problem seeks on this graph a set \(Y \subseteq V\) of p vertices in such a way that the sum of distances from all the vertices to their respective closest vertices in Y is minimized. The vertices of the graph can be considered as demand points and the vertices in Y as the location of facilities, the goal is to select the locations of p facilities to serve n demand points, so that the sum of the distances of demand points from their nearest facilities is minimized. We have used the vertices in set Y and facility locations interchangeably throughout this paper. The p-median problem and its variations can be used to model many real world situations, e.g., in locating public facilities, industrial plants and ware-houses. These are only a few examples from the long list of situations where this model can be applied. This model can also be used in applications related to cluster analysis, where points in an m-dimensional space can be regarded as user locations. p-median problem can also be posed in the form of a matrix as follows: Given a matrix D of dimension \(n \times n\), select p columns of D in a way such that the sum of minimum coefficients in each row within these p columns is as small as possible.

The classical p-median problem is shown to be \(\mathcal {NP}\)-hard by Kariv and Hakimi [26]. Because of this, applicability of exact methods is limited to small instances only, and we need heuristics to solve large instances. The first heuristic based on the greedy strategy for the classical p-median problem is proposed by Kuehn and Hamburger [27]. Another early heuristic is the interchange heuristic proposed by Teitz and Bart [40]. Since then numerous heuristic and metaheuristic approaches have been proposed, e.g., fast interchange heuristic [42], global/regional interchange algorithm [13], LEVEL-2 and LEVEL-3 heuristics [12], gamma heuristic [36], tabu search [35], variable neighborhood search [19], simulated annealing [11], genetic algorithms [1, 4, 14, 20], hybrid heuristic methods [33], a swap-based local search procedure [34], a parallel genetic algorithm [31], particle swarm optimization based approaches [29, 37] and an artificial bee colony algorithm [3]. A survey on metaheuristic approaches for the p-median problem can be found in [28].

A location problem with positive and negative weights on the vertices is useful in applications, where some facilities are non-attractive to some clients (facilities are obnoxious). Many obnoxious location problems are discussed and classified in Cappanera [8]. Interested readers can find the survey on obnoxious location problems in Carrizosa and Plastria [9] and Plastria [32]. Burkard and Krarup [7] proposed the first location model with positive and negative weights and also proved that the 1-median problem on a cactus with positive and negative vertex weights can be solved in linear time. Burkard et al. [5] observed that there exist two different models when p-median problem with positive/negative weights in graphs is considered. In the first model, referred to as P1, the sum of the minimum weighted distances is minimized. In the second model, referred to as P2, the sum of the weighted minimum distances is minimized.

Burkard et al. [5] developed an \(\mathcal {O}(n^2)\) algorithm for the 2-median problem on a tree. They also developed an \(\mathcal {O}(n \log n)\) algorithm for stars and an \(\mathcal {O}(n)\) algorithm for paths for first model (P1). They presented an \(\mathcal {O}(n^3)\) algorithm for the 2-median problem on a tree for the second model (P2) and showed that the complexity can be reduced to \(\mathcal {O}(n^2)\) if the medians are restricted to vertices. Burkard and Fathali [6] presented an algorithm for 3-median problem on a tree for second model (P2). There exists some heuristic methods also to solve the positive/negative weighted p-median problem on graphs. Fathali and Kakhki [17] developed a modified variable neighborhood search (MVNS). Fathali et al. [16] presented an ant colony optimization algorithm (ACO). A genetic algorithm (GA) for the positive/negative weighted p-median problem is proposed by Fathali [15]. ACO and GA are two best approaches known so far for the positive/negative weighted p-median problem.

In this paper, we have proposed an artificial bee colony (ABC) algorithm based approach for the positive/negative weighted p-median problem. ABC algorithm is a new population based metaheuristic technique based on intelligent foraging behaviour of honey bee swarm, which has been applied successfully to solve numerous combinatorial optimization problems in diverse domains. Though there exists an ABC algorithm for the classical p-median problem [3], there exists no ABC algorithm for the positive/negative weighted p-median problem. Besides, the approach of [3] contains some design flaws (see Sect. 4.7). This has motivated us to develop the approach presented in this paper which is altogether different from the ABC approach presented in [3] for classical p-median problem. We have used two local search procedures in our ABC approach. In a bid to improve each solution generated by ABC algorithm, it is passed through an interchange based randomized local search. In addition, an interchange based exhaustive local search is applied on some of the best solutions obtained after the execution of ABC algorithm in an attempt to further improve them. We have compared our ABC approach with ACO and GA [15, 16] on the standard benchmark instances for the problem. Computational results show the effectiveness of our approach.

The remainder of this paper is structured as follows: Sect. 2 defines the positive/negative weighted p-median problem formally. In Sect. 3, we provide an overview of ABC algorithm. Section 4 presents our ABC approach to solve the positive/negative weighted p-median problem. Section 5 reports the computational results and compares our approach with other approaches available in the literature. Finally, Sect. 6 outlines some concluding remarks.

2 Formal problem definition

The classical p-median problem can be formally stated as follows. Let \(G = (V, E)\) be an undirected graph with vertex set \(V = \left\{ v_{1} , v_{2},\ldots , v_{n }\right\} \) and edge set E. The length of shortest path or distance from vertex \(v_{i}\) to vertex \(v_{j}\) is denoted as \(d(v_{i} , v_{j} )\). The problem is to choose a set Y containing p vertices of G, in such way that the sum of distances from all vertices to their closest vertices in Y is minimized, i.e., the solution is a subset \(Y = \left\{ y_{1} , y_{2},\ldots , y_{p }\right\} \) of V that minimizes

$$ \sum _{i=1}^n \min _{ j \in \{1,\ldots ,p\}} d(v_{i} , y_{j}) $$
(1)

In the weighted version of the problem, a weight \(w_{i}\) is associated with each vertex and the objective is to minimize the sum of weighted minimum distances, i.e.,

$$ \sum _{i=1}^n w_{i} \min _{ j \in \{1,\ldots ,p\}} d(v_{i} , y_{j}) $$
(2)

Burkard et al. [5] noted that two different models exist for p-median problem when weights on the vertices can be both positive and negative. In the first model (P1), the objective is to minimize the sum of the minimum weighted distances.

$$ O1(Y) = \sum _{i=1}^n \min _{j \in \{1,\ldots ,p\}} \left( w_{i}d\left( v_{i} , y_{j}\right) \right) $$
(3)

In the second model (P2), the objective is to minimize the sum of weighted minimum distances.

$$ O2(Y) = \sum _{i=1}^n w_{i} \min _{j \in \{1,\ldots ,p\}} d\left( v_{i} , y_{j}\right) $$
(4)

Please note that both models are equivalent when we have positive weights only.

3 Overview of ABC algorithm

The artificial bee colony (ABC) algorithm proposed by Karaboga [21] is a population based meta-heuristic algorithm, which is inspired by the intelligent behavior of the foraging honey bees. In a bee colony, there are three types of bees: employed, onlooker and scout. Employed bees are those bees which are currently exploiting a food source. The responsibility of the employee bees is to bring loads of nectar to the hive and share the information about their food sources with other bees waiting in the hive. The waiting bees are known as onlookers. The onlookers then choose a food source with a probability directly proportional to its quality and becomes employed. Scout bees search for new food sources in the vicinity of the hive and they become employed as soon as they find a new food source. An employed bee whose food source becomes empty will abandon that food source and becomes either a scout or an onlooker.

Inspired by the foraging bees’ behavior described above, Karaboga developed ABC algorithm. This algorithm was originally developed for solving optimization problems in continuous domain only, later, it has been extended to solve discrete optimization problems also. Since the development of first ABC algorithm [21], numerous variants of basic algorithm have been proposed, e.g. [2, 10, 23–25, 30, 38, 39, 41]. For a recent survey on ABC algorithm and its applications, one may refer to Karaboga et al. [22].

In ABC algorithm also there are three types of bees, viz. employed, onlooker and scout with functions similar to their real counterparts. In ABC algorithm, the food sources represent the possible solutions to the problem under consideration and the quality of a food source represents the fitness of the represented solution. The employed bees are associated with food sources. Always, there is a one-to-one correspondence between food sources and employed bees, which means, the number of food sources is equal to the number of employee bees. Usually, but not always, the number of onlooker bees is also taken to be equal to number of employed bees. The ABC algorithm follows an iterative search process, which starts with associating the employee bees with randomly generated food sources (solutions), then it repeats through the cycles of the employed bee and onlooker bee phases.

In the employed bee phase, each employed bee generates a food source in the proximity of its associated food source and evaluates its quality. The method of determining a new food source in the proximity of a particular food source depends on the problem under consideration. If the quality of the new food source is better than the current one then the employed bee moves to the new food source leaving the old one. Otherwise, it remains at the old food source. When all the employed bees finish this process, then employed bee phase ends and onlooker bee phase begins.

Onlooker bee phase starts with sharing of information by employed bees about their food sources with the onlookers. Onlookers select the food sources according to their quality, i.e., higher the value of the fitness of the solution represented by a food source, higher will be the chances of its selection. As a result of such a selection, good quality food sources will get more chance for selection by the onlookers. After all onlookers select the food sources, they determine the food sources in the proximity of their selected food sources in a manner similar to the employed bees and evaluate their fitness. Among all the neighboring food sources generated by the onlookers who chose food source i and the food source i itself, the best quality food source is determined. This best food source will be updated as food source i for the next iteration. The onlooker bee phase ends once all food sources are updated, and then the next iteration of the ABC algorithm begins. The algorithm is repeated until the termination condition is satisfied.

If a solution associated with any employed bee does not improve over some specific number of iterations, then that food source is considered as exhausted and it is discarded by its associated employee bee and that employee bee becomes scout. Such scouts are converted back into employed bees by associating them with newly generated solutions. Usually, these new solutions are generated randomly in the same manner as initial employed bee solutions or by perturbing an existing solution.

Clearly, every solution is given a fair chance to improve itself in the employed bee phase. On the other hand, in the onlooker bee phase, because of the selection policy used by the onlookers as mentioned above good quality solutions get more chance to improve themselves in comparison to poor quality solutions. This inclination towards selecting good quality solutions may produce better quality solutions faster, as there are higher chances of finding even better solutions within the proximity of good solutions in comparison to poor ones. However, if a solution is locally optimal, then no better solution exists in its proximity and any attempt to improve it will be futile. The concept of scout bees helps in this situation. Instead of determining whether a solution is locally optimal or not with respect to the whole neighborhood which can be a computationally expensive process, a solution is deemed to be locally optimal if has not improved over certain number of iterations. This solution is discarded by making its associated employed bee a scout. A new solution is generated for this scout bee to make it employed again. Hence, the concept of scout bees helps in getting rid of solutions which has not improved since long and which can be locally optimal. For a search process to be robust, the balance between the exploration and exploitation must be maintained. In the ABC algorithm, employed bees and onlooker bees carry out the exploitation, whereas scout bees are responsible for exploration. The number of iterations without improvement in the ABC algorithm after which an employed bee leaves a solution and becomes a scout needs to be set appropriately so as to maintain a proper balance between exploration and exploitation.

4 ABC approach for the p-median problem with positive/negative weights

In this section, we present our ABC approach for the p-median problem with positive/negative weights. Subsequent subsections describe the salient features of our ABC approach.

4.1 Solution representation and fitness

We have represented a solution directly by the subset of vertices used for locating the facilities and used the objective function as the fitness function. So for model P1, fitness is determined using Eq. 3, whereas for model P2, fitness is determined using Eq. 4. Please note the less value of the fitness function means a more fit solution. The two models for the proposed p-median problem will differ in the assignment of demand points to the facilities. In model P1, vertices with positive weights are assigned to the nearest facility and vertices with negative weights are assigned to the farthest facility. On the other hand, in model P2 vertices with both positive and negative weights are assigned to the closest facility.

4.2 Food source selection for onlooker bees

For selecting a food source for an onlooker bee, we have employed the binary tournament selection method. In the binary tournament selection method, two food sources are selected randomly and their fitness is compared. The better of the two food sources as per their fitness is selected with the probability \(p_{onl}\). Otherwise, the worse of the two food sources is selected, i.e., the probability of selection of worse solution is \(1-p_{onl}\). The Pseudo-code for the binary tournament selection method is as follows:

figure a

4.3 Initial solution

The initial solution for our ABC algorithm is generated using the random method. One location for facility is selected at a time, randomly from the vertex set V and this process is repeated until p facilities are located.

4.4 Neighboring solution generation

Our neighboring solution generation process is inspired by the genetic operators used in [15]. To generate a solution \(Y^{\prime }\) in the neighborhood of solution Y, we choose another solution \(Y_{1}\) randomly from the population and copy those locations of facilities which are common in both solutions Y and \(Y_{1}\) into \(Y^{\prime }\). Then a fraction \(F_r\) (with \(F_r > 0.5\)) of the remaining locations for facilities are added from solution Y, and the rest are added from solution \(Y_{1}\). Here, \(F_r\) is a parameter to be determined empirically. To add a new location to the solution \(Y^{\prime }\), we always add the location which yields the smallest objective function value (assuming only that many facilities need to be opened). If the two solutions Y and \(Y_{1}\) are identical, i.e., all the facility locations in two solutions are same then there is no point in copying all the location to \(Y^{\prime }\) as doing so will produce another solution identical to Y and \(Y_{1}\). This situation is known as collision in ABC algorithm jargon [38]. If a collision occurs while generating a neighboring solution for an employee bee then original solution is abandoned and the concerned employee bee becomes a scout. Then a new solution is generated randomly in a fashion similar to an initial solution for this scout bee and its status is again changed back to employed by associating it with this new solution. This is done to get rid of one duplicate solution. If collision occurs while generating neighboring solution for an onlooker bee then another solution is chosen randomly. If again collision occurs then again a solution is chosen randomly. This process continues till a solution different from original solution is found. The reason behind handling the collision for an onlooker bee in a manner different from an employed bee lies in the fact that it is worthless to generate a solution randomly for an onlooker bee. This is so because an onlooker bee solution can survive only when it is better than the original solution and solutions of all other onlooker bees which are associated with this original solution. Obviously, it is highly improbable that a randomly generated solution is better than all these solutions.

In a bid to further improve the neighboring solution obtained through the afore-mentioned method, we have used 1-interchange heuristic. In this heuristic method, we replace one vertex in the solution \(Y^{\prime }\) by a vertex which is not present in it and which results in maximum reduction in objective function value. We randomly select one vertex in \(Y^{\prime }\) and find a vertex in \(\left\{ V - Y^{\prime }\right\} \), which results in maximum reduction in objective function value. This method is computationally expensive, because of the large number of fitness calculations performed each time it is applied. However, it aids more often than not in improving the quality of a solution. To balance the computational cost and degree of improvement, we have applied 1-interchange heuristic K times on every solution, where K is a parameter to be determined empirically.

4.5 Other features

If there is no improvement in the quality of a food source over a specified number of iterations say limit, then the employed bee associated with that food source leaves it and becomes a scout. This scout is associated with a newly generated food source so that it can become employed again. This food source is generated randomly in the same manner as an initial solution. After generating a food source, this scout again becomes employed. The limit is an important control parameter of ABC algorithm. An employed bee can also become a scout, as mentioned in Sect. 4.4 through collision. So the number of scouts in a particular iteration depends on these two conditions and there is no lower and upper limits on the number of scouts in an iteration.

figure b

4.6 Local search

Once the ABC algorithm finishes execution, a local search is applied on the L best solutions found by the ABC algorithm in a bid to further improve their solution quality. In this local search, each vertex y in a solution Y is tried to be exchanged one-by-one with a vertex not in Y so that the value of the objective function is reduced by the largest amount. This process is repeated till the objective function can not be improved further. The 1-interchange heuristic, where only K (\( < p\)) randomly chosen vertices instead of all are tried for exchange, can be considered as a lighter variant of this local search.

Algorithm 2 provides the pseudo-code of our hybrid ABC approach where generate_neighbor(Y), 1-interchange(Y) and local_search(Y) are three functions that take as input a solution Y and return respectively a solution in the neighborhood of Y (first paragraph in Sect. 4.4), a solution obtained after applying 1-interchange heuristic on Y (second paragraph in Sect. 4.4), a solution obtained after applying local search on solution Y (Sect. 4.6). binary_tournament(\(e_{1},e_{2},\ldots ,e_{n_e}\)) is another function that selects a solution among employed bee solutions \(e_{1},e_{2},\ldots ,e_{n_e}\) using binary tournament selection method (Sect. 4.2) and returns the index of the solution selected.

4.7 Key points of difference with a related work

Basti and Sevkli [3] have proposed an artificial bee colony algorithm for the classical p-median problem. This subsection highlights the key differences between their approach and our proposed approach:

  • Basti and Sevkli [3] have used a real vector of length n to encode a solution in their ABC algorithm. To decode a solution from this real vector, indices corresponding to smallest p values in this vector are found and demand points corresponding to these indices are assumed to be the location of facilities. On the other hand, in our ABC algorithm, we have represented a solution directly by the subset of vertices used for locating the facilities, hence the length of a solution is equal to p (\(p<n\)). The encoding scheme of [3] suffers from problem of redundancy, i.e., the same solution can be encoded in many different ways. In fact, in the encoding scheme of [3], each solution can be represented in infinitely many ways. As ABC algorithm works in the space of encoded solutions, in the presence of redundancy, it has to search a larger space which can severely impair its performance. On the other hand, encoding scheme used by us does not suffer from the problem of redundancy as each solution is represented uniquely. The size of search space in [3] is infinite, whereas in our case it is \(n \atopwithdelims ()p\). Besides, the length of an encoded solution has an adverse impact on the efficiency of several operators associated with ABC algorithm. With respect to this aspect also, our encoding is better as \(p<n\).

  • Real vector encoding scheme of [3] incurs a decoding overhead to get the actual solution from its encoded version. In our case, no decoding overhead is incurred as each solution is represented directly by the subset of vertices used for locating the facilities

  • As Basti and Sevkli [3] used a real vector to encode a solution, they followed the original neighboring solution generation method proposed by Karaboga [21], i.e., a neighboring solution is generated by changing the value of one randomly chosen parameter of the original solution. On the other hand, our neighboring solution generation method is based on the assumption that if a vertex is present in one good solution then there are chances that the same vertex may appear in many good solutions. Hence, we have given maximum attention to those vertices which are common in original solution and randomly selected solution, followed by those vertices which are in one of these solutions.

  • Basti and Sevkli used roulette wheel selection method for selecting a solution for an onlooker bee. We have used binary tournament selection method for selecting a solution for an onlooker bee. Its an established fact that binary tournament selection method performs better than roulette wheel selection method and at the same time its computationally less expensive. In fact, it has roughly the same performance as rank selection method [18].

  • In their work, a greedy local search algorithm is applied on every solution generated by the ABC algorithm. While applying this local search on a solution, facility locations are considered one-by-one. The facility location in consideration is tried for replacement with all other non facility locations. The location that yields the least objective function value is retained and then the next facility location is considered. Our 1-interchange heuristic is similar. However, instead of trying all facilities one-by-one, only \(K < p\) facilities are tried for replacement to cut the computational cost. Facilities to be tried for replacement are selected randomly. In addition, in our work, another local search is applied on L best solutions obtained after the execution of ABC algorithm. This local search is also similar to the local search of Basti and Sevkli except for the fact that we keep applying this local search repeatedly as long as there is improvement in solution quality, i.e., our local search stops when a complete pass through the existing facility locations fails to improve the solution quality.

Table 1 The results for the test problems with positive weights
Full size table
Table 2 The average total CPU times (in seconds) for problems P1 and P2
Full size table

5 Computational results

Our hybrid ABC approach has been implemented in C and executed on a Linux based Intel Core i5 2400 system with 4 GB RAM running at 3.10 GHz. In all our computational experiments, the number of employed bees (\(n_e\)) is taken to be 25, the number of onlooker bees (\(n_o\)) is taken to be 50, \(p_{onl}\) is set to 0.85, limit is set to 50, \(F_r\) is set to \(\frac{2}{3}\), K is set to 2 and L is set to 5. Our hybrid ABC approach terminates after 100 iterations. All these parameter values were chosen empirically after a large number of trials.

We have compared our hybrid ABC approach with two best approaches, viz. GA [15] and ACO [16] approaches. For this comparison, we have used the same 40 test instances as used in Fathali [15] and Fathali et al. [16]. These instances are slightly modified version of the uncapacitated p-median problem instances available for download from OR-LibraryFootnote 1. Slight modification is done in these instances to accommodate negative weights. Vertices weights in these instances is restricted to \(\pm 1\) only. Further, the negative weight of \(-1\) is assigned to only the first 2 or first 5 or first 10 vertices and to all odd numbered vertices. The case where first 5 vertices have negative weights was considered in Fathali [15] only, whereas the case where first 2 vertices have negative weights was considered in Fathali et al. [16] only. All other cases are considered by both the papers. Hence, the results for GA and ACO are not available for instances with 2 negative weights and 5 negative weights respectively. Like GA and ACO approaches, we have executed our hybrid ABC approach 5 times on each instance and reported the average results.

Tables 1, 3, 4, 5, 6, 7, 8, 9 and 10 present the results of ABC algorithm on various types of instances and compare them with those of genetic algorithm (GA) and ant colony algorithm (ACO) methods. Table 1 reports the results of various approaches on instances with positive weights. This table also reports the average total CPU times in seconds of GA, ACO and ABC approaches on each instance with positive weights. However, for models P1 and P2, we have reported the total CPU time that is averaged over all the instances that are derived from the same instance of the uncapacitated p-median problem. This is done to ensure conformity with Fathali [15] and Fathali et al. [16]. Table 2 reports these times and next paragraph further explains how these times have been computed. Tables 3, 4, 5 and 6 report the results of various approaches for model P1 on instances with 2 negative weights, 5 negative weights, 10 negative weights and half negative weights respectively, whereas Tables 7, 8, 9 and 10 does the same for model P2. As mentioned already, performances of GA and ACO were not evaluated on instances with 2 negative weights and 5 negative weights respectively, and hence, Tables 3 and 7 report the results of ABC and ACO only, whereas Tables 4 and 8 report the results of ABC and GA only. Results for GA and ACO are taken from their respective papers. The columns under the common heading Objective function value report the objective function value averaged over 5 runs for various approaches, whereas columns under the common heading % Error report the relative error of various approaches on each instance. The relative error is defined as follows:

$$\frac{f- f_{O/B}}{\left| f_{O/B} \right| } \times 100 $$

where f is the objective function value obtained by the algorithm and \(f_{O/B} \) is the optimal or the best known value so far obtained. Optimal values are known only for the instances with positive weights. For other types of instances, proven optimal values are not known. Moreover, for some instances, our ABC approach has found a value better than the best known value. In such cases, we have replaced the best known value with new best known value found by our ABC algorithm. Such cases are reported in bold font in these tables.

As mentioned in the previous paragraph, Table 2 reports the average total CPU times in seconds of GA, ACO and ABC approaches for each of the two models (P1 and P2). The first three columns represents the problem number of the original uncapacitated p-median problem, number of nodes and number of centres. columns 4–7 report the average time for model P1 and columns 8–11 report the average time for the model P2. As explained earlier, performances of GA and ACO were not evaluated on instances with 2 negative weights and 5 negative weights respectively. Hence, to ensure fair comparison, we have computed average total CPU times for our approach in two ways. For comparison with the GA, the averages are computed using instances with 5 negative weights, 10 negative weights and half negative weights, whereas for comparison with ACO, the averages are computed using instances with 2 negative weights, 10 negative weights and half negative weights. Hence, we have two columns labelled ABC for each of the two models. Columns 5 and 9 report the time of ABC approach for comparison with GA, whereas columns 7 and 11 report the time of ABC approach for comparison with ACO. Again, the data for GA and ACO are taken from their respective papers.

Table 11 summarizes the results. This table reports for each approach on each instance group of 40, the number of instances for which the approach in question found result inferior to best known value (column W) and sumtotal of relative error (column TE). This table also report the number of instances in each instance group where our ABC approach found the new best known value (column BKV-I). Please note that for instances with positive weights both models are equivalent and optimal solutions are known. That is why a ‘−’ is placed for these instances under Model and BKV-I columns.

Table 3 The results of various approaches on instances with 2 negative weights under model P1
Full size table
Table 4 The results of various approaches on instances with 5 negative weights under model P1
Full size table
Table 5 The results of various approaches on instances with 10 negative weights under model P1
Full size table
Table 6 The results of various approaches on instances with half negative weights under model P1
Full size table
Table 7 The results of various approaches on instances with 2 negative weights under model P2
Full size table
Table 8 The results of various approaches on instances with 5 negative weights under model P2
Full size table
Table 9 The results of various approaches on instances with 10 negative weights under model P2
Full size table
Table 10 The results of various approaches on instances with half negative weights under model P2
Full size table
Table 11 Summary table
Full size table

From these tables, some interesting observation can be made. Results of different approaches vary according to the types of instances. ABC approach improves the best known values for more than 10 % of the instances (35 out of 320). Most of these instances are those with relatively large value of p. Barring few exception, there is not much difference in the performance of various approaches on the instances with small values of p. Only when the value of p is large, the performance of different approaches tend to differ significantly. However, none of the approaches can be considered as clearly superior to others on all types of instances with large value of p. The difficulty of various approaches on instances with large value of p can be explained theoretically also on the basis of the search space size. Actually, there are \({n \atopwithdelims ()p}\) solutions and for the fixed n, the number of solutions increase with increase in p till \(p = \lfloor \frac{n}{2} \rfloor \). All the values of p in the instances considered here is less than \(\lfloor \frac{n}{2} \rfloor \), and hence, the search space size increases with the increase in p for fixed n. As the approaches have to search a larger search space, they find these instances relatively difficult.

We can observe that our ABC approach performs better than ACO on 5 out of 7 instance groups in terms of total error, whereas reverse is true if we compare two approaches in terms of number of instances where an approach fails to reach the best known value. This shows that whenever ABC approach fails to reach the best known value, its solution is closer to best known value in comparison to the solution of ACO under similar situation. Overall, there are 62 and 66 instances (out of 280) where ACO and ABC fail to reach the best known value. ACO approach perform much worse in comparison to our ABC approach on instances with half negative weights under both the models, whereas it performs the best in comparison to ABC on instances with no negative weight.

On the other hand, GA fares better than ABC on both counts. There are 3 instance groups only where ABC performs better than GA in terms of total error, whereas on remaining 4 groups GA performs better. There is only one instance group where GA fails to reach the best known value on higher number of instances than ABC. However, GA performs much worse in comparison to ABC in terms of total error on instances with half negative weights under model P1.

As far as execution times of various approaches are concerned, GA and ACO approaches were executed on a 1.7 GHz Pentium 4 system which is different from the system used to execute our ABC approach. Therefore, execution times can not be compared precisely. However, a rough comparison can always be made. Even after compensating for differences in processing speed, we can safely say that our approach is faster than GA on most of the instances. However, ACO is faster than our approach.

6 Conclusions

In this paper, we have proposed an ABC algorithm based approach for solving the p-median problem with positive and negative weights. We have compared the results of our approach with two best approaches, viz. GA and ACO on the standard benchmark instances of the problem. Comparison with ACO approach is specially significant as both ABC and ACO are swarm intelligence based approaches. ABC approach is able to improve the best known values for slightly more than 10 % of the instances. Though the relative performance of different approaches vary according to the types of instances, the overall performance of GA is clearly better than ABC approach in terms of solution quality, but ABC approach is faster. On the other hand, ABC approach is much better than ACO approach on instances where half of the weights are negative under both the models, but at the expense of larger execution times.

As a future work, we would like to extend our ABC approach to capacitated p-median problem. Similar approaches can be designed for other related facility location problems also.