Packing a limited number of unequal circular objects in a rectangular container

Igor Litvinchev; Daniel Mosquera

First EAI International Conference on Computer Science and Engineering

Research Article

Packing a limited number of unequal circular objects in a rectangular container

Download1389 downloads

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.4108/eai.27-2-2017.152349,
    author={Igor Litvinchev and Daniel Mosquera},
    title={Packing a limited number of unequal circular objects in a rectangular container},
    proceedings={First EAI International Conference on Computer Science and Engineering},
    publisher={EAI},
    proceedings_a={COMPSE},
    year={2017},
    month={3},
    keywords={circle packing integer programming large scale optimization.},
    doi={10.4108/eai.27-2-2017.152349}
}

Igor Litvinchev
Daniel Mosquera
Year: 2017
Packing a limited number of unequal circular objects in a rectangular container
COMPSE
EAI
DOI: 10.4108/eai.27-2-2017.152349

Igor Litvinchev¹^,*, Daniel Mosquera²

1: aComplex Systems Department, Computing Center, Russian Academy of Sciences, Moscow, Russia, bFaculty of Mechanical and Electrical Engineering, Nuevo Leon Sate University, Monterrey, Mexico
2: bFaculty of Mechanical and Electrical Engineering, Nuevo Leon Sate University, Monterrey, Mexico

*Contact email: igorlitvinchev@gmail.com

Abstract

A problem of packing a limited number of unequal circular objects in a fixed size rectangular container is considered. The circular object is considered in a general sense, as a set of points that are all the same distance (not necessary Euclidean) from a center. The aim is to maximize the (weighted) number of objects placed into the container or minimize the waste. This problem has numerous applications in logistics, including production and packing for the textile, apparel, naval, automobile, aerospace and food industries. Frequently the problem is formulated as a nonconvex continuous optimization problem which is solved by heuristic techniques combined with local search procedures. We study a linear integer programming formulation based on approximating container by a regular grid. The nodes of the grid are considered as potential positions for assigning centers of the objects thus giving rise to a large scale linear 0-1 optimization problem with binary variables representing the assignment of centers to the nodes of the grid. Recursive packing allowing nesting circles inside one another is also considered. Numerical results are presented to demonstrate the efficiency of the proposed approach.

Keywords: circle packing integer programming large scale optimization.

Published: 2017-03-09
Publisher: EAI

: http://dx.doi.org/10.4108/eai.27-2-2017.152349