Thumbnail
Access Restriction
Open

Author Osman, Ibrahim H. ♦ Christofides, Nicos
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Description The capacitated clustering problem (CCP) is the problem in which a given set of weighted objects is to be partitioned into clusters so that the total weight of objects in each cluster is less than a given value (cluster 'capacity'). The objective is to minimize the total scatter of objects from the 'centre ' of the cluster to which they have been allocated. A simple constructive heuristic, a R-interchange generation mechanism, a hybrid simulated annealing (SA) and tabu search (TS) algorithm which has computationally desirable features using a new non-monotonic cooling schedule, are developed. A classification of the existing SA cooling schedules is presented. The effects on the final solution quality of the initial solutions, the cooling schedule parameters and the neighbourhood search strategies are investigated. Computational results on randomly generated problems with size ranging from 50 to 1 0 0 customers indicate that the hybrid SA/TS algorithm out-performs previous simulated annealing algorithms, a simple tabu search and local descent algorithms.
International Transactions in Operational Research
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 1994-01-01