论文标题
改进了Planar P-Median问题的起始解决方案
Improved Starting Solutions for the Planar p-Median Problem
论文作者
论文摘要
在本文中，我们提出了两种新方法，以找到针对Planar P-Median问题的良好起始解决方案。两种方法都依赖于连续模型的离散近似，该模型将设施位置限制为给定的需求点集。第一种方法适应了针对最小正方形聚类问题总和提出的贪婪随机构造算法的第一阶段。第二个基于顶点交换实现了简单的下降程序。然后，将最终的解决方案用作本地搜索启发式的起点，在众所周知的库珀的交替定位分配方法和具有新的，更有效的选择规则的转移后续步骤之间迭代。广泛的计算实验表明，（1）使用良好的启动解决方案可以显着提高本地搜索的性能，并且（2）使用将良好的起始解决方案与“深”本地搜索结合在一起的混合算法可以是解决平面P-Median问题多样性的有效策略。
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 problem.
