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

Improved scatter search algorithm for capacitated P-median problem

作　　者：徐先瑞[1] 李响[1] 李小杰[1] 

机构地区：[1]华东师范大学地理信息科学教育部重点实验室,上海200062

出　　处：《计算机工程与应用》2011年第20期28-30,104,共4页Computer Engineering and Applications

基　　金：国家自然科学基金重点项目(No.40730526);国家自然科学基金面上项目(No.40701142);上海市浦江人才计划资助课题(No.07PJ14035)

摘　　要：对解决约束P-中位问题已有的分散搜索算法进行改进。通过划分中心点服务范围的新方法指派需求点以构造初始解,用基于外包矩形的局部搜索方法来提高邻域解搜索的效率,结合路径重连算法,扩展邻域解的搜索范围,来提高解的质量。实验表明此算法能够得到优化且连续的解。To solve the capacitated p-median problem, an improved heuristic algorithm is proposed.Initial solutions are construtted 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.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]