A Heuristic for the Two-Dimensional Irregular Bin Packing Problem with Limited Rotations

被引：5

作者：

Liu, Qiang ^{[1
]}

Zeng, Jiawei ^{[1
]}

Zhang, Hao ^{[1
]}

Wei, Lijun ^{[1
]}

机构：

[1] Guangdong Univ Technol, Guangdong Prov Key Lab Comp Integrated Mfg Syst, State Key Lab Precis Elect Mfg Technol & Equipmen, Guangzhou 510006, Peoples R China

来源：

TRENDS IN ARTIFICIAL INTELLIGENCE THEORY AND APPLICATIONS. ARTIFICIAL INTELLIGENCE PRACTICES, IEA/AIE 2020 | 2020年 / 12144卷

关键词：

Cutting and packing; Irregular bin packing; Heuristic; ALGORITHM; SEARCH;

D O I：

10.1007/978-3-030-55789-8_24

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

In this paper, we propose a heuristic for the two-dimensional irregular bin packing problems (2DIRBPP) with limited rotations. To solve the 2DIRBPP, we use the First Fit Decreasing (FFD) strategy to assign the pieces to the bins, then use the Bottom-Left algorithm and the pieces exchange method to place pieces into each bin, and finally perform a local search to improve the solution. The results show that our approach is competitive with all existing approaches on several sets of standard benchmark.

引用

页码：268 / 279

页数：12

共 14 条

[1] Jostle heuristics for the 2D-irregular shapes bin packing problems with free rotation [J].

Abeysooriya, Ranga P. ;

Bennell, Julia A. ;

Martinez-Sykora, Antonio .

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2018, 195 :12-26

[2] The irregular cutting-stock problem - a new procedure for deriving the no-fit polygon [J].

Bennell, JA ;

Dowsland, KA ;

Dowsland, WB .

COMPUTERS & OPERATIONS RESEARCH, 2001, 28 (03) :271-287

[3] Complete and robust no-fit polygon generation for the irregular stock cutting problem [J].

Burke, E. K. ;

Hellier, R. S. R. ;

Kendall, G. ;

Whitwell, G. .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 179 (01) :27-49

[4] A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering [J].

Elkeran, Ahmed .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2013, 231 (03) :757-769

[5] An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem [J].

Imamichi, Takashi ;

Yagiura, Mutsunori ;

Nagamochi, Hiroshi .

DISCRETE OPTIMIZATION, 2009, 6 (04) :345-361

[6] On genetic algorithms for the packing of polygons [J].

Jakobs, S .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 88 (01) :165-181

[7]

Johnson D. S., 1974, SIAM Journal on Computing, V3, P299, DOI 10.1137/0203025

[8] Extended local search algorithm based on nonlinear programming for two-dimensional irregular strip packing problem [J].

Leung, Stephen C. H. ;

Lin, Yangbin ;

Zhang, Defu .

COMPUTERS & OPERATIONS RESEARCH, 2012, 39 (03) :678-686

[9] An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles [J].

Liu, DQ ;

Teng, HF .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1999, 112 (02) :413-420

[10] A unified hyper-heuristic framework for solving bin packing problems [J].

Lopez-Camacho, Eunice ;

Terashima-Marin, Hugo ;

Ross, Peter ;

Ochoa, Gabriela .

EXPERT SYSTEMS WITH APPLICATIONS, 2014, 41 (15) :6876-6889

← 1 2 →