Premium
Capacitated Clustering Problems by Hybrid Simulated Annealing and Tabu Search
Author(s) -
Osman Ibrahim H.,
Christofides Nicos
Publication year - 1994
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/1475-3995.d01-43
Subject(s) - tabu search , simulated annealing , mathematical optimization , cluster analysis , computer science , schedule , constructive , guided local search , cluster (spacecraft) , algorithm , local search (optimization) , adaptive simulated annealing , mathematics , artificial intelligence , process (computing) , programming language , operating system
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 100 customers indicate that the hybrid SA/TS algorithm out‐performs previous simulated annealing algorithms, a simple tabu search and local descent algorithms.