Solving the capacitated clustering problem with variable neighborhood search

Jack Brimberg (), Nenad Mladenović (), Raca Todosijević () and Dragan Urošević ()
Additional contact information
Jack Brimberg: Royal Military College of Canada
Nenad Mladenović: Mathematical Institute SANU
Raca Todosijević: Mathematical Institute SANU
Dragan Urošević: Mathematical Institute SANU

Annals of Operations Research, 2019, vol. 272, issue 1, No 14, 289-321

Abstract: Abstract Variable neighborhood search (VNS) is a proven heuristic framework for finding good solutions to combinatorial and global optimization problems. In this paper two VNS-based heuristics are proposed for solving the capacitated clustering problem. The first follows a standard VNS approach, and the second a skewed VNS that allows moves to inferior solutions. The performance of the two heuristics is assessed on benchmark instances from the literature. We also compare their performance against a recently published iterated VNS procedure. All VNS procedures outperform the state-of-the-art, but the Skewed VNS is best overall. This would suggest that using acceptance criteria before allowing moves to inferior solutions in Skewed VNS is preferable to the random shaking approach that is used in Iterated VNS to move to new regions of the solution space.

Keywords: Optimization; Clustering; Heuristic; Local search (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-017-2601-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:272:y:2019:i:1:d:10.1007_s10479-017-2601-5

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-017-2601-5

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().