Abstract: To solve the capacitated p-median problem，an improved heuristic algorithm is proposed.Initial solutions are constructed by a new method of assigning demand points through dividing medians’ service areas.A local search method based on contour-rectangle is adopted to promote the efficiency of neighborhood solution search.The path re-linking algorithm is combined to expand the searching scope of neighborhood solution and to improve the quality of solution.Two groups of experiments are designed in view of the different questions to verify the proposed algorithm.

Key words: Capacitated P-Median Problem（CPMP）, scatter search, λ-interchange, neighborhood solution, shift-insertion

摘要：

对解决约束P-中位问题已有的分散搜索算法进行改进。通过划分中心点服务范围的新方法指派需求点以构造初始解，用基于外包矩形的局部搜索方法来提高邻域解搜索的效率，结合路径重连算法，扩展邻域解的搜索范围，来提高解的质量。实验表明此算法能够得到优化且连续的解。

关键词: 约束P-中位问题, 分散搜索算法, λ-交换, 邻域解, 替换插入