Title | ||
---|---|---|
Greedy random adaptive memory programming search for the capacitated clustering problem |
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 the total scatter of points allocated to these centers. In this paper, we propose a merger of Greedy Random Adaptive Search Procedure (GRASP) and Adaptive Memory Programming (AMP) into a new GRAMPS framework for the CCP. A learning process is kept in charge of tracking information on the best components in an elite set of GRAMPS solutions. The information are strategically combined with problem-domain data to restart the construction search phase. At early stage of constructions, priorities are given to problem-domain data and progressively shifted towards generated information as the learning increases. GRAMPS is implemented with an efficient local search descent based on a restricted λ-interchange neighbourhood. Extensive experiments are reported on on a standard set of bench-marks from the literature and on a new set of large instances. The results show that GRAMPS has an efficient learning mechanism and is competitive with the existing methods in the literature. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1016/j.ejor.2003.08.066 | European Journal of Operational Research |
Keywords | Field | DocType |
Ant colony optimization,Adaptive memory programming,Density search,Capacitated clustering (p-median) problem,Greedy randomized adaptive search procedure,Guided construction search metaheuristic | Ant colony optimization algorithms,Random search,Mathematical optimization,GRASP,Swarm intelligence,Local search (optimization),Cluster analysis,Greedy randomized adaptive search procedure,Mathematics,Metaheuristic | Journal |
Volume | Issue | ISSN |
162 | 1 | 0377-2217 |
Citations | PageRank | References |
24 | 1.27 | 14 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Samad Ahmadi | 1 | 220 | 15.61 |
Ibrahim H. Osman | 2 | 815 | 94.23 |