Abstract—Capacitated p-median problem (CPMP) is one of the popular discrete location problems. CPMP locates pfacilities between the candidate sites, in order to satisfy the customers' demands. Usually, in this kind of problems, according to increase of the number of customers and facilities, the solution time of problem will be increased exponentially, so this problem is an NP-hard problem. Therefore, in this paper, we propose a new hybrid algorithm to solve CPMP. In proposed method, k-means clustering algorithm will find a proper solution for Fixed Neighborhood Search (FNS) algorithm. Then, FNS algorithm improves the quality of obtained solutions for standard benchmark instances with facilities locations exchange and omitting the unsuitable candidates' sites. The computational results show the efficiency of the proposed algorithm in regard of the quality of solution.
Index Terms—Capacitated p-median problem, Fixed neighborhood search, k-means clustering.
Payman Kaveh is master of Industrial Engineering, Shahed University,Tehran, Iran (e-mail: email@example.com).
Ali Sabzevari Zadeh is master of Industrial Engineering, Shahed University, Tehran, Iran (e-mail: firstname.lastname@example.org).
Rashed Sahraeian is assistant professor, Shahed University, Tehran, Iran (email: Sahraeian@shahed.ac.ir).
Cite: Payman Kaveh, Ali Sabzevari Zadeh and Rashed Sahraeian, " Solving Capacitated P-median Problem by Hybrid K-means Clustering and FNS Algorithm," International Journal of Innovation, Management and Technology vol. 1, no. 4, pp. 405-410, 2010.