Solving capacitated clustering problems

John M. Mulvey, Michael P. Beck

Research output: Contribution to journalArticle

97 Scopus citations

Abstract

This paper presents two effective algorithms for clustering n entities into p mutually exclusive and exhaustive groups where the 'size' of each group is restricted. As its objective, the clustering model minimizes the sum of distance between each entity and a designated group median. Empirical results using both a primal heuristic and a hybrid heuristic-subgradient method for problems having n ≤ 100 (i.e. 10 100 binary variables) show that the algorithms locate close to optimal solutions without resorting to tree enumeration. The capacitated clustering model is applied to the problem of sales force territorial design.

Original languageEnglish (US)
Pages (from-to)339-348
Number of pages10
JournalEuropean Journal of Operational Research
Volume18
Issue number3
DOIs
StatePublished - Dec 1984

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Keywords

  • Integer programming
  • cluster analysis
  • multivariate statistics

Fingerprint Dive into the research topics of 'Solving capacitated clustering problems'. Together they form a unique fingerprint.

  • Cite this