A reactive GRASP with path relinking for capacitated clustering |
| |
Authors: | Yumin Deng Jonathan F Bard |
| |
Institution: | (3) Information Sci. Res. AT&T Labs Res., Florham Park, NJ 07932, USA |
| |
Abstract: | This paper presents a greedy randomized adaptive search procedure (GRASP) coupled with path relinking (PR) to solve the problem
of clustering n nodes in a graph into p clusters. The objective is to maximize the sum of the edge weights within each cluster such that the sum of the corresponding
node weights does not exceed a fixed capacity. In phase I, both a heaviest weight edge (HWE) algorithm and a constrained minimum
cut algorithm are used to select seeds for initializing the p clusters. Feasible solutions are obtained with the help of a self-adjusting restricted candidate list that sequentially guides
the assignment of the remaining nodes. At each major GRASP iteration, the list length is randomly set based on a probability
density function that is updated dynamically to reflect the solution quality realized in past iterations. In phase II, three
neighborhoods, each defined by common edge and node swaps, are explored to attain local optimality. The following exploration
strategies are investigated: cyclic neighborhood search, variable neighborhood descent, and randomized variable neighborhood
descent (RVND). The best solutions found are stored in an elite pool. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|