Improved Starting Solutions for the Planar p-Median Problem

Jack Brimberg ; Zvi Drezner

Yugoslav journal of operations research, Tome 31 (2021) no. 1, p. 45

Résumé

In this paper we present two new approaches for finding good starting solutions to the planar p-median problem. Both methods rely on a discrete approximation of the continuous model that restricts the facility locations to the given set of demand points. The first method adapts the first phase of a greedy random construction algorithm proposed for the minimum sum of squares clustering problem. The second one implements a simple descent procedure based on vertex exchange. The resulting solution is then used as a starting point in a local search heuristic that iterates between the well-known Cooper’s alternating locate-allocate method and a transfer follow-up step with a new and more effective selection rule. Extensive computational experiments show that (1) using good starting solutions can significantly improve the performance of local search, and (2) using a hybrid algorithm that combines good starting solutions with a "deep" local search can be an effective strategy for solving a diversity of planar p-median problems.

Détail

Classification : 90B85, 90C26
Keywords: Facility Location, Planar p-median, Continuous Location