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

• DOI: 10.1007/s10100-006-0001-z
• Publication Date: 2006-08-11T08:12:52Z
• Authors: Jafar Fathali; Hossein T. Kakhki; Rainer E. Burkard
• Keywords: Cardinality (data modeling); Variable neighborhood search

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.