Solving the p-median problem with pos/neg weights by variable neighborhood search and some results for special cases

The p-median problem with positive and negative weights has been introduced by Burkard and Krarup. In this paper we discuss some special cases of this problem on trees and propose a variable neighborhood search procedure for general networks, which is in fact a modification of the one proposed by Hansen and Mladenovic for the p-median. We also compare the results with those obtained by a Tabu search procedure.