Anna Martinez-Gavara
Randomized heuristics for the Capacitated Clustering Problem
Martinez-Gavara, Anna; Landa-Silva, Dario; Campos, Vicente; Marti, Rafael
Authors
DARIO LANDA SILVA DARIO.LANDASILVA@NOTTINGHAM.AC.UK
Professor of Computational Optimisation
Vicente Campos
Rafael Marti
Abstract
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.
Citation
Martinez-Gavara, A., Landa-Silva, D., Campos, V., & Marti, R. (2017). Randomized heuristics for the Capacitated Clustering Problem. Information Sciences, 417, https://doi.org/10.1016/j.ins.2017.06.041
Journal Article Type | Article |
---|---|
Acceptance Date | Jun 28, 2017 |
Online Publication Date | Jul 1, 2017 |
Publication Date | Nov 1, 2017 |
Deposit Date | Aug 10, 2017 |
Publicly Available Date | Mar 29, 2024 |
Journal | Information Sciences |
Print ISSN | 0020-0255 |
Electronic ISSN | 1872-6291 |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 417 |
DOI | https://doi.org/10.1016/j.ins.2017.06.041 |
Keywords | Capacitated Clustering; Grasp; Matheuristic; Graph partitioning |
Public URL | https://nottingham-repository.worktribe.com/output/965664 |
Publisher URL | http://www.sciencedirect.com/science/article/pii/S002002551631725X?via%3Dihub |
Related Public URLs | http://www.cs.nott.ac.uk/~pszjds/research/files/dls_is2017.pdf |
Files
dls_is2017.pdf
(1.5 Mb)
PDF
Copyright Statement
Copyright information regarding this work can be found at the following address: http://creativecommons.org/licenses/by-nc-nd/4.0
You might also like
Evolving Deep CNN-LSTMs for Inventory Time Series Prediction
(2019)
Conference Proceeding
An agent based modelling approach for the office space allocation problem
(2018)
Conference Proceeding
Lookahead policy and genetic algorithm for solving nurse rostering problems
(2018)
Conference Proceeding
A genetic algorithm with composite chromosome for shift assignment of part-time employees
(2018)
Conference Proceeding
Downloadable Citations
About Repository@Nottingham
Administrator e-mail: digital-library-support@nottingham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search