An Improved Scatter Search Algorithm for Capacitated P-Median Problem

摘要：

This paper proposes a heuristic algorithm to solve the capacitated p-median problem. First,initial solutions are constructed by a new method of assigning demand points through delineating medians’ service areas,and then a local search method based on contour-rectangle is adopted to promote the efficiency of neighborhood solution search. Finally,the path re-linking algorithm is combined to expand the searching scope of neighborhood solution to improve the quality of solution. We have designed two groups of experiments to validate the proposed algorithm.

关键词： CPMP:Scatter Search:λ-Interchange Neighborhood Solution:Shift-Insertion

作者: Xianrui Xu Xiang Li Xiaojie Li Hui Lin

作者单位: Key Laboratory of Geographical Information Science,Ministry of Education East China Normal Universit Institute of Space and Earth Information Science The Chinese University of Hong Kong Hong Kong,China

会议类型: 国际会议

会议名称: 2010 2nd International Conference on Computer Engineering and Technology(2010年第二届计算机工程与技术国际会议 ICCET 2010)

会议地点: 成都

会议语种:英文

页码: 1054-1058

在线出版日期: 2010-04-16（万方平台首次上网日期，不代表论文的发表时间）