TY - JOUR
T1 - Ant colony optimization for finding medians of weighted graphs
AU - Kaveh, A.
AU - Sharafi, P.
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
UR - http://handle.uws.edu.au:8081/1959.7/549031
U2 - 10.1108/02644400810855931
DO - 10.1108/02644400810855931
M3 - Article
SN - 0264-4401
VL - 25
SP - 102
EP - 120
JO - Engineering Computations
JF - Engineering Computations
IS - 2
ER -