Multi-start methods for the capacitated clustering problem

Martinez-Gavara, Anna; Campos, Vicente; Landa-Silva, Dario; Marti, Rafael

Abstract

In this work, 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.

Citation

Martinez-Gavara, A., Campos, V., Landa-Silva, D., & Marti, R. (2017). Multi-start methods for the capacitated clustering problem. In Metaheuristics: Proceeding of the MIC and MAEB 2017 Conferences

• Conference Name: 12th Metaheuristics International Conference (MIC 2017)
• Start Date: Jul 4, 2017
• End Date: Jul 7, 2017
• Acceptance Date: Mar 27, 2017
• Publication Date: Jul 4, 2017
• Deposit Date: Aug 11, 2017
• Publicly Available Date: Aug 11, 2017
• Peer Reviewed: Peer Reviewed
• Book Title: Metaheuristics: Proceeding of the MIC and MAEB 2017 Conferences
• ISBN: 9788469742751
• Public URL: http://eprints.nottingham.ac.uk/id/eprint/44823
• Related Public URLs: http://mic2017.upf.edu/
• Copyright Statement: Copyright information regarding this work can be found at the following address: http://eprints.nottingh.../end_user_agreement.pdf
• Additional Information: Published in: Metaheuristics: Proceeding of the; MIC and MAEB 2017 Conferences, 4-7 July 2017, Barcelona, Spain, p. 926-928. Universitat Pompeu Fabra. ISBN: 978-84-697-4275-1.