A scatter search heuristic for the capacitated clustering problem |
| |
Institution: | 1. IBM Research, Damastown Industrial Estate, Mulhuddart, Dublin 15, Ireland;2. Laboratoire Génie Industriel, Ecole Centrale Paris, Châtenay-Malabry 92290, France;3. LAMSADE, Université Paris Dauphine, Paris 75016, France;4. INSERM Cognitive Neuroimaging Unit, CEA Neurospin, Gif-sur-Yvette F-91191, France;1. LIAAD, INESC TEC, Faculdade de Economia, Universidade do Porto Rua Dr. Roberto Frias s/n, 4200-464, Porto, Portugal;2. Mathematical Optimization and Planning, Amazon.com, 333 Boren Avenue North, Seattle, WA 98109, USA;1. Department of Industrial Engineering, TOBB University of Economics and Technology, Ankara, Turkey;2. MIT-Zaragoza International Logistics Program, Zaragoza Logistics Center, Zaragoza, Spain |
| |
Abstract: | This paper proposes a scatter search-based heuristic approach to the capacitated clustering problem. In this problem, a given set of customers with known demands must be partitioned into p distinct clusters. Each cluster is specified by a customer acting as a cluster center for this cluster. The objective is to minimize the sum of distances from all cluster centers to all other customers in their cluster, such that a given capacity limit of the cluster is not exceeded and that every customer is assigned to exactly one cluster. Computational results on a set of instances from the literature indicate that the heuristic is among the best heuristics developed for this problem. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|