Dispersed starting solutions in facility location: The case of the planar p-median problem

There are many planar multiple facilities location problems for which the optimal locations tend to be spread out. The most popular of these is the planar p-median problem. With this in mind, we propose several procedures to generate sparse configurations as starting solutions. The proposed procedures are easy to implement, and can be used as modules combined in different sequences within heuristics such as a recent trajectory-based procedure that we tested in this paper. The procedures are tested experimentally on a set of 24 large problem instances with up to 10,000 demand points and 100 facilities. We are able to demonstrate that the sparse starting solutions generated by the new procedures lead to significant improvements of final p-median solutions.