Medians of a graph have many applications in engineering. Optimal locations for facility centers, distribution of centers and domain decomposition for parallel computation are a few examples of such applications. In this paper, a new ant system (AS) algorithm based on the idea of using two sets of ants, named active and passive ants is proposed for the problem of finding k‐medians of a weighted graph or the facility location problem on a network.
The structure of the algorithm is derived from two known heuristics; namely, rank‐based AS and max‐min ant system with some adjustments in pheromone updating and locating the ants on the graph nodes. The algorithms are designed with and without a local search.
An efficient algorithm for location finding, and the novel application of an ant colony system can be considered as the main contribution of this paper.
Combining two different tools; namely, graph theory and AS algorithm results in an efficient and accurate method for location finding. The results are compared to those of another algorithm based on the theory of graphs.
Emerald Group Publishing Limited
Copyright © 2008, Emerald Group Publishing Limited