Solving capacitated clustering problems

John M. Mulvey, Michael P. Beck

Research output: Contribution to journalArticlepeer-review

131 Scopus citations


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
Issue number3
StatePublished - Dec 1984

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management


  • Integer programming
  • cluster analysis
  • multivariate statistics


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

Cite this