Mathematical model and efficient algorithms for object packing problem

被引：86

作者：

Chernov, N. ^{[1
]}

Stoyan, Yu. ^{[2
]}

Romanova, T. ^{[2
]}

机构：

[1] Univ Alabama Birmingham, Dept Math, Birmingham, AL 35294 USA

[2] Natl Acad Sci Ukraine, Dept Math Modeling, Inst Mech Engn Problems, Kharkov, Ukraine

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2010年 / 43卷 / 05期

基金：

美国国家科学基金会;

关键词：

Mathematical modeling; Cutting and packing; Optimization; Phi-function; No-Fit Polygon; POLYGONS; SEARCH;

D O I：

10.1016/j.comgeo.2009.12.003

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The article is devoted to mathematical models and practical algorithms for solving the cutting and packing (C&P) problem. We review and further enhance the main tool of our studies - phi-functions. Those are constructed here for 2D and 3D objects (unlike other standard tools, such as No-Fit Polygons, which are restricted to the 2D geometry). We also demonstrate that in many realistic cases the Phi-functions can be described by quite simple formulas without radicals and other complications. Lastly, a general Solution strategy using the phi-functions is Outlined and illustrated by several 2D and 3D examples. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：535 / 553

页数：19

共 33 条

[1]

Agarwal P.K., 2002, Computational Geometry Theory and Applications, V21, P29

[2] OPTIMAL ALLOCATION OF TWO-DIMENSIONAL IRREGULAR SHAPES USING HEURISTIC-SEARCH METHODS [J].

ALBANO, A ;

SAPUPPO, G .

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS, 1980, 10 (05) :242-248

[3]

[Anonymous], NONLINEAR PROGRAMMIN

[4]

ART RC, 1966, 36Y08 IBM CAMBR SCI

[5] Tools of mathematical modeling of arbitrary object packing problems [J].

Bennell, J. ;

Scheithauer, G. ;

Stoyan, Y. ;

Romanova, T. .

ANNALS OF OPERATIONS RESEARCH, 2010, 179 (01) :343-368

[6] Hybridising tabu search with optimisation techniques for irregular stock cutting [J].

Bennell, JA ;

Dowsland, KA .

MANAGEMENT SCIENCE, 2001, 47 (08) :1160-1172

[7] The geometry of nesting problems: A tutorial [J].

Bennell, Julia A. ;

Oliveira, Jose F. .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 184 (02) :397-415

[8] A comprehensive and robust procedure for obtaining the nofit polygon using Minkowski sums [J].

Bennell, Julia A. ;

Song, Xiang .

COMPUTERS & OPERATIONS RESEARCH, 2008, 35 (01) :267-281

[9] Orthogonal packing of rectangular items within arbitrary convex regions by nonlinear optimization [J].

Birgin, E. G. ;

Martinez, J. M. ;

Nishihara, F. H. ;

Ronconi, D. P. .

COMPUTERS & OPERATIONS RESEARCH, 2006, 33 (12) :3535-3548

[10] A new bottom-left-fill heuristic algorithm for the two-dimensional irregular packing problem [J].

Burke, Edmund ;

Hellier, Robert ;

Kendall, Graham ;

Whitwell, Glenn .

OPERATIONS RESEARCH, 2006, 54 (03) :587-601

← 1 2 3 4 →