A local search heuristic for the (r|p)-centroid problem in the plane

In the (r|p)(r|p)-centroid problem, two players, called a leader and a follower, open facilities to service clients. Clients are identified with their location on the Euclidean plane. Facilities can be opened anywhere in the plane. At first, the leader opens p facilities. Later on, the follower opens r facilities. Each client patronizes the closest facility. Each player maximizes own market share. The goal is to find p   facilities for the leader to maximize his market share. It is known that this problem is Σ2P-hard. We develop a local search heuristic for this problem, based on the VNS framework. We apply the (r|Xp−1+1)(r|Xp−1+1)-centroid subproblem for finding the best neighboring solution according to the swap neighborhood. It is shown that this subproblem is polynomially solvable for fixed r. Computational experiments for the randomly generated test instances confirm the value of the approach.