THREE ADD PROCEDURES FOR LOCATION IN THE PLANE

Søren Dahlerup, Søren Kruse Jacobsen and Henrik Juel

Abstract

We consider the p-median model in the plane with Euclidean distances. The paper addresses the problem of ADDing one new facility to a set of p-1 existing facilities in order to serve a given set of clients. Three ADD procedures are proposed; the first one is based on search for the subset of clients to be served by the new facility; the two next algorithms are based on geometric considerations; one with low storage demand and rather high computing time and, one with high storage demand and rather low computing time. The basic problem that arises when moving from the discrete case to the Euclidean plane is that the number of feasible locations for a new facility becomes infinite. It turns out however, that the maximum saving may be found by repeated applications of the classical Weiszfeld algorithm. Some computational experience is reported.

IMM Technical Report 13/95