The multi-facility median problem with Pos/Neg weights on general graphs

In this paper we discuss the multi-facility location problem on networks with positive and negative weights. As the finite dominating set for the single facility problem does not carry over to the multi-facility problem, we derive a new finite dominating set. To solve the problem, we present a straight-forward algorithm. Moreover, for the problem with just two new facilities, we show how to obtain a more efficient solution procedure by using planar arrangements. We present computational results to underline the efficiency of the improved algorithm and to test some approximations which are based on a reduced candidate set.