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

• 研究、探讨 • 上一篇    下一篇

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

徐先瑞,李 响,李小杰   

  1. 华东师范大学 地理信息科学教育部重点实验室,上海 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   

  1. 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

摘要:

对解决约束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