Ant colony optimization for finding medians of weighted graphs

Purpose - 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. Design/methodology/approach - 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. Findings - 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. Originality/value - 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.