Capacitated clustering problems by hybrid simulated annealing and tabu search

Capacitated clustering problems by hybrid simulated annealing and tabu search

0.00 Avg rating0 Votes
Article ID: iaor19951111
Country: United Kingdom
Volume: 1
Issue: 3
Start Page Number: 317
End Page Number: 336
Publication Date: Jul 1994
Journal: International Transactions in Operational Research
Authors: ,
Keywords: clustering
Abstract:

The capacitated clustering problem 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 λ-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 100 customers indicate that the hybrid SA/TS algorithm out-performs previous simulated annealing algorithms, a simple tabu search and local descent algorithms.

Reviews

Required fields are marked *. Your email address will not be published.