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

作者：Kalcsics Joerg^*

来源：Computers & Operations Research, 2011, 38(3): 674-682.

DOI：10.1016/j.cor.2010.08.002

• Multi-facility location problems
• Networks
• Finite dominating sets
• Planar arrangements

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 multifacility problem, we derive a new finite dominating set. To solve the problem, we present a straightforward 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.

• 出版日期2011-3