Randomized heuristics for the Capacitated Clustering Problem
In this paper, we investigate the adaptation of the Greedy Randomized Adaptive Search Procedure (GRASP) and Iterated Greedy methodologies to the Capacitated Clustering Problem (CCP). In particular, we focus on the effect of the balance between randomization and greediness on the performance of these...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Published: |
Elsevier
2017
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/44825/ |
| _version_ | 1848797006455111680 |
|---|---|
| author | Martinez-Gavara, Anna Landa-Silva, Dario Campos, Vicente Marti, Rafael |
| author_facet | Martinez-Gavara, Anna Landa-Silva, Dario Campos, Vicente Marti, Rafael |
| author_sort | Martinez-Gavara, Anna |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | In this paper, we investigate the adaptation of the Greedy Randomized Adaptive Search Procedure (GRASP) and Iterated Greedy methodologies to the Capacitated Clustering Problem (CCP). In particular, we focus on the effect of the balance between randomization and greediness on the performance of these multi-start heuristic search methods when solving this NP-hard problem. The former is a memory-less approach that constructs independent solutions, while the latter is a memory-based method that constructs linked solutions, obtained by partially rebuilding previous ones. Both are based on the combination of greediness and randomization in the constructive process, and coupled with a subsequent local search phase. We propose these two multi-start methods and their hybridization and compare their performance on the CCP. Additionally, we propose a heuristic based on the mathematical programming formulation of this problem, which constitutes a so-called matheuristic. We also implement a classical randomized method based on simulated annealing to complete the picture of randomized heuristics. Our extensive experimentation reveals that Iterated Greedy performs better than GRASP in this problem, and improved outcomes are obtained when both methods are hybridized and coupled with the matheuristic. In fact, the hybridization is able to outperform the best approaches previously published for the CCP. This study shows that memory-based construction is an effective mechanism within multi-start heuristic search techniques. |
| first_indexed | 2025-11-14T19:57:01Z |
| format | Article |
| id | nottingham-44825 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:57:01Z |
| publishDate | 2017 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-448252020-05-04T19:54:41Z https://eprints.nottingham.ac.uk/44825/ Randomized heuristics for the Capacitated Clustering Problem Martinez-Gavara, Anna Landa-Silva, Dario Campos, Vicente Marti, Rafael In this paper, we investigate the adaptation of the Greedy Randomized Adaptive Search Procedure (GRASP) and Iterated Greedy methodologies to the Capacitated Clustering Problem (CCP). In particular, we focus on the effect of the balance between randomization and greediness on the performance of these multi-start heuristic search methods when solving this NP-hard problem. The former is a memory-less approach that constructs independent solutions, while the latter is a memory-based method that constructs linked solutions, obtained by partially rebuilding previous ones. Both are based on the combination of greediness and randomization in the constructive process, and coupled with a subsequent local search phase. We propose these two multi-start methods and their hybridization and compare their performance on the CCP. Additionally, we propose a heuristic based on the mathematical programming formulation of this problem, which constitutes a so-called matheuristic. We also implement a classical randomized method based on simulated annealing to complete the picture of randomized heuristics. Our extensive experimentation reveals that Iterated Greedy performs better than GRASP in this problem, and improved outcomes are obtained when both methods are hybridized and coupled with the matheuristic. In fact, the hybridization is able to outperform the best approaches previously published for the CCP. This study shows that memory-based construction is an effective mechanism within multi-start heuristic search techniques. Elsevier 2017-11 Article PeerReviewed Martinez-Gavara, Anna, Landa-Silva, Dario, Campos, Vicente and Marti, Rafael (2017) Randomized heuristics for the Capacitated Clustering Problem. Information Sciences, 417 . pp. 154-168. ISSN 1872-6291 Capacitated Clustering; Grasp; Matheuristic; Graph partitioning http://www.sciencedirect.com/science/article/pii/S002002551631725X?via%3Dihub doi:10.1016/j.ins.2017.06.041 doi:10.1016/j.ins.2017.06.041 |
| spellingShingle | Capacitated Clustering; Grasp; Matheuristic; Graph partitioning Martinez-Gavara, Anna Landa-Silva, Dario Campos, Vicente Marti, Rafael Randomized heuristics for the Capacitated Clustering Problem |
| title | Randomized heuristics for the Capacitated Clustering Problem |
| title_full | Randomized heuristics for the Capacitated Clustering Problem |
| title_fullStr | Randomized heuristics for the Capacitated Clustering Problem |
| title_full_unstemmed | Randomized heuristics for the Capacitated Clustering Problem |
| title_short | Randomized heuristics for the Capacitated Clustering Problem |
| title_sort | randomized heuristics for the capacitated clustering problem |
| topic | Capacitated Clustering; Grasp; Matheuristic; Graph partitioning |
| url | https://eprints.nottingham.ac.uk/44825/ https://eprints.nottingham.ac.uk/44825/ https://eprints.nottingham.ac.uk/44825/ |