To read this content please select one of the options below:

Ant colony optimization for finding medians of weighted graphs

A. Kaveh (Centre of Excellence for Fundamental Studies in Structural Engineering, Iran University of Science and Technology, Tehran, Iran Building and Housing Research Center, Tehran, Iran)
P. Sharafi (Building and Housing Research Center, Tehran, Iran)

Engineering Computations

ISSN: 0264-4401

Article publication date: 7 March 2008




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.



Kaveh, A. and Sharafi, P. (2008), "Ant colony optimization for finding medians of weighted graphs", Engineering Computations, Vol. 25 No. 2, pp. 102-120.



Emerald Group Publishing Limited

Copyright © 2008, Emerald Group Publishing Limited

Related articles