An ant colony algorithm for the pos/neg weighted p-median problem

Research paper by Jafar Fathali, Hossein T. Kakhki, Rainer E. Burkard

Indexed on: 12 Aug '06Published on: 12 Aug '06Published in: Central European Journal of Operations Research


Let a graph G  =  (V, E) with vertex set V and edge set E be given. The classical graph version of the p-median problem asks for a subset \(X\subseteq V\) of cardinality p, so that the (weighted) sum of the minimum distances from X to all other vertices in V is minimized. We consider the semi-obnoxious case, where every vertex has either a positive or a negative weight. This gives rise to two different objective functions, namely the weighted sum of the minimum distances from X to the vertices in V\X and, differently, the sum over the minimum weighted distances from X to V\X. In this paper an Ant Colony algorithm with a tabu restriction is designed for both problems. Computational results show its superiority with respect to a previously investigated variable neighborhood search and a tabu search heuristic.