改进的求解约束P-Median问题的分散搜索算法

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (20): 28-30.

改进的求解约束P-Median问题的分散搜索算法

徐先瑞，李响，李小杰

华东师范大学地理信息科学教育部重点实验室，上海 200062

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-07-11 发布日期:2011-07-11

Improved scatter search algorithm for capacitated P-median problem

XU Xianrui，LI Xiang，LI Xiaojie

Key Laboratory of Geographic Information Science，Ministry of Education，East China Normal University，Shanghai 200062，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-07-11 Published:2011-07-11

摘要/Abstract

摘要：

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

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

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-Median问题的分散搜索算法[J]. 计算机工程与应用, 2011, 47(20): 28-30.

XU Xianrui，LI Xiang，LI Xiaojie. Improved scatter search algorithm for capacitated P-median problem[J]. Computer Engineering and Applications, 2011, 47(20): 28-30.

[1]	毛丽丽，张则强，朱立夏. 混合模拟退火及分散搜索优化过道布置问题[J]. 计算机工程与应用, 2018, 54(3): 243-249.
[2]	刘强,周育人. 分散搜索算法求解多目标优化问题[J]. 计算机工程与应用, 2008, 44(33): 66-68.