IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v191y2008i3p786-802.html
   My bibliography  Save this article

Solving circle packing problems by global optimization: Numerical results and industrial applications

Author

Listed:
  • Castillo, Ignacio
  • Kampas, Frank J.
  • Pintér, János D.

Abstract

A (general) circle packing is an optimized arrangement of N arbitrary sized circles inside a container (e.g., a rectangle or a circle) such that no two circles overlap. In this paper, we present several circle packing problems, review their industrial applications, and some exact and heuristic strategies for their solution. We also present illustrative numerical results using 'generic' global optimization software packages. Our work highlights the relevance of global optimization in solving circle packing problems, and points towards the necessary advancements in both theory and numerical practice.

Suggested Citation

  • Castillo, Ignacio & Kampas, Frank J. & Pintér, János D., 2008. "Solving circle packing problems by global optimization: Numerical results and industrial applications," European Journal of Operational Research, Elsevier, vol. 191(3), pages 786-802, December.
  • Handle: RePEc:eee:ejores:v:191:y:2008:i:3:p:786-802
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(07)00427-4
    Download Restriction: Full text for ScienceDirect subscribers only

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Fraser, Hamish J. & George, John A., 1994. "Integrated container loading software for pulp and paper industry," European Journal of Operational Research, Elsevier, vol. 77(3), pages 466-474, September.
    2. Hifi, Mhand & Paschos, Vangelis Th. & Zissimopoulos, Vassilis, 2004. "A simulated annealing approach for the circular cutting problem," European Journal of Operational Research, Elsevier, vol. 159(2), pages 430-448, December.
    3. Birgin, E. G. & Martinez, J. M. & Ronconi, D. P., 2005. "Optimizing the packing of cylinders into a rectangular container: A nonlinear approach," European Journal of Operational Research, Elsevier, vol. 160(1), pages 19-33, January.
    4. Wang, Huaiqing & Huang, Wenqi & Zhang, Quan & Xu, Dongming, 2002. "An improved algorithm for the packing of unequal circles within a larger containing circle," European Journal of Operational Research, Elsevier, vol. 141(2), pages 440-453, September.
    5. Dowsland, Kathryn A. & Dowsland, William B., 1992. "Packing problems," European Journal of Operational Research, Elsevier, vol. 56(1), pages 2-14, January.
    6. Erkut, Erhan, 1990. "The discrete p-dispersion problem," European Journal of Operational Research, Elsevier, vol. 46(1), pages 48-60, May.
    7. George, John A. & George, Jennifer M. & Lamar, Bruce W., 1995. "Packing different-sized circles into a rectangular container," European Journal of Operational Research, Elsevier, vol. 84(3), pages 693-712, August.
    8. Dyckhoff, Harald, 1990. "A typology of cutting and packing problems," European Journal of Operational Research, Elsevier, vol. 44(2), pages 145-159, January.
    9. Haessler, Robert W. & Sweeney, Paul E., 1991. "Cutting stock problems and solution procedures," European Journal of Operational Research, Elsevier, vol. 54(2), pages 141-150, September.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. T. Kubach & A. Bortfeldt & H. Gehring, 2009. "Parallel greedy algorithms for packing unequal circles into a strip or a rectangle," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 17(4), pages 461-477, December.
    2. Yaohua He & Yong Wu, 2013. "Packing non-identical circles within a rectangle with open length," Journal of Global Optimization, Springer, vol. 56(3), pages 1187-1215, July.
    3. Niblett, Matthew R. & Church, Richard L., 2015. "The disruptive anti-covering location problem," European Journal of Operational Research, Elsevier, vol. 247(3), pages 764-773.
    4. López, C.O. & Beasley, J.E., 2016. "A formulation space search heuristic for packing unequal circles in a fixed size circular container," European Journal of Operational Research, Elsevier, vol. 251(1), pages 64-73.
    5. Edwin Dam & Bart Husslage & Dick Hertog, 2010. "One-dimensional nested maximin designs," Journal of Global Optimization, Springer, vol. 46(2), pages 287-306, February.
    6. Galiev, Shamil I. & Lisafina, Maria S., 2013. "Linear models for the approximate solution of the problem of packing equal circles into a given domain," European Journal of Operational Research, Elsevier, vol. 230(3), pages 505-514.
    7. A. Grosso & A. Jamali & M. Locatelli & F. Schoen, 2010. "Solving the problem of packing equal and unequal circles in a circular container," Journal of Global Optimization, Springer, vol. 47(1), pages 63-81, May.
    8. Fu, Zhanghua & Huang, Wenqi & Lü, Zhipeng, 2013. "Iterated tabu search for the circular open dimension problem," European Journal of Operational Research, Elsevier, vol. 225(2), pages 236-243.
    9. Zeng, Zhizhong & Yu, Xinguo & He, Kun & Huang, Wenqi & Fu, Zhanghua, 2016. "Iterated Tabu Search and Variable Neighborhood Descent for packing unequal circles into a circular container," European Journal of Operational Research, Elsevier, vol. 250(2), pages 615-627.
    10. López, C.O. & Beasley, J.E., 2011. "A heuristic for the circle packing problem with a variety of containers," European Journal of Operational Research, Elsevier, vol. 214(3), pages 512-525, November.
    11. Hinostroza, Ignacio & Pradenas, Lorena & Parada, Víctor, 2013. "Board cutting from logs: Optimal and heuristic approaches for the problem of packing rectangles in a circle," International Journal of Production Economics, Elsevier, vol. 145(2), pages 541-546.
    12. Giorgio Fasano, 2013. "A global optimization point of view to handle non-standard object packing problems," Journal of Global Optimization, Springer, vol. 55(2), pages 279-299, February.
    13. Mustafa Çağlayan & János Pintér, 2013. "Development and calibration of a currency trading strategy using global optimization," Journal of Global Optimization, Springer, vol. 56(2), pages 353-371, June.
    14. Huang, Wenqi & Ye, Tao, 2011. "Global optimization method for finding dense packings of equal circles in a circle," European Journal of Operational Research, Elsevier, vol. 210(3), pages 474-481, May.
    15. repec:spr:compst:v:72:y:2010:i:2:p:205-216 is not listed on IDEAS
    16. János Pintér & Zoltán Horváth, 2013. "Integrated experimental design and nonlinear optimization to handle computationally expensive models under resource constraints," Journal of Global Optimization, Springer, vol. 57(1), pages 191-215, September.
    17. Zvi Drezner, 2010. "On the unboundedness of facility layout problems," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 72(2), pages 205-216, October.
    18. János Pintér & Frank Kampas, 2013. "Benchmarking nonlinear optimization software in technical computing environments," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 21(1), pages 133-162, April.
    19. Rodrigues, S. & Bauer, P. & Bosman, Peter A.N., 2016. "Multi-objective optimization of wind farm layouts – Complexity, constraint handling and scalability," Renewable and Sustainable Energy Reviews, Elsevier, vol. 65(C), pages 587-609.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:191:y:2008:i:3:p:786-802. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Dana Niculescu). General contact details of provider: http://www.elsevier.com/locate/eor .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.