Ant colony optimization for finding medians of weighted graphs

Abstract

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.

Citation

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