A new alternating heuristic for the (r | p)-centroid problem on the plane

In the (r vertical bar p)-centroid problem, two players, called leader and follower, open facilities to service clients. We assume that clients are identified with their location on the Euclidian plane, and facilities can be opened anywhere in the plane. The leader opens p facilities. Later on, the follower opens r facilities. Each client patronizes the closest facility. Our goal is to find p facilities for the leader to maximize his market share. For this Stackelberg game we develop a new alternating heuristic, based on the exact approach for the follower problem. At each iteration of the heuristic, we consider the solution of one player and calculate the best answer for the other player. At the final stage, the clients are clustered, and an exact polynomial-time algorithm for the (1 vertical bar 1)-centroid problem is applied. Computational experiments show that this heuristic dominates the previous alternating heuristic of Bhadury, Eiselt, and Jaramillo.