Advances in Operations Research
Volume 2009 (2009), Article ID 150624, 22 pages
Review Article

A Literature Review on Circle and Sphere Packing Problems: Models and Methodologies

1Université de Picardie Jules Verne, Laboratoire MIS, Axe Optimisation Discrète et Réoptimisation, 5 rue Moulin Neuf, 80000 Amiens, France
2Department of Statistics and Operations Research, Kuwait University, P. O. Box 5969, Safat 13060, Kuwait

Received 24 November 2008; Accepted 19 April 2009

Academic Editor: Imed Kacem

Copyright © 2009 Mhand Hifi and Rym M'Hallah. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


This paper reviews the most relevant literature on efficient models and methods for packing circular objects/items into Euclidean plane regions where the objects/items and regions are either two- or three-dimensional. These packing problems are NP hard optimization problems with a wide variety of applications. They have been tackled using various approaches-based algorithms ranging from computer-aided optimality proofs, to branch-and-bound procedures, to constructive approaches, to multi-start nonconvex minimization, to billiard simulation, to multiphase heuristics, and metaheuristics.