Density Based Problem Space Search for the Capacitated Clustering p-Median Problem

Samad Ahmadi () and Ibrahim Osman ()

Annals of Operations Research, 2004, vol. 131, issue 1, 43 pages

Abstract: In the Capacitated Clustering Problem (CCP), a given set of n weighted points is to be partitioned into p clusters such that, the total weight of the points in each cluster does not exceed a given cluster capacity. The objective is to find a set of p centers that minimises total scatter of points allocated to them. In this paper a new constructive method, a general framework to improve the performance of greedy constructive heuristics, and a problem space search procedure for the CCP are proposed. The constructive heuristic finds patterns of natural subgrouping in the input data using concept of density of points. Elements of adaptive computation and periodic construction–deconstruction concepts are implemented within the constructive heuristic to develop a general framework for building efficient heuristics. The problem-space search procedure is based on perturbations of input data for which a controlled perturbation strategy, intensification and diversification strategies are developed. The implemented algorithms are compared with existing methods on a standard set of bench-marks and on new sets of large-sized instances. The results illustrate the strengths of our algorithms in terms of solution quality and computational efficiency. Copyright Kluwer Academic Publishers 2004

Keywords: capacitated clustering (p-median) problem; greedy density search; guided construction search method; metaheuristics; problem-space search (search for similar items in EconPapers)
Date: 2004
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://hdl.handle.net/10.1023/B:ANOR.0000039511.61195.21 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:131:y:2004:i:1:p:21-43:10.1023/b:anor.0000039511.61195.21

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/B:ANOR.0000039511.61195.21

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().