A heuristic for solving large bin packing problems in two and three dimensions

被引：25

作者：

Mack, Daniel ^{[1
]}

Bortfeldt, Andreas ^{[1
]}

机构：

[1] Fernuniv, Dept Informat Syst, D-58084 Hagen, Germany

来源：

CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH | 2012年 / 20卷 / 02期

关键词：

Bin packing; Heuristics; Single bin-size bin packing problem; SBSBPP; Single stock-size cutting stock problem; SSSCSP; SEARCH; ALGORITHMS;

D O I：

10.1007/s10100-010-0184-1

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The more-dimensional bin packing problem (BPP) considered here requires packing a set of rectangular-shaped items into a minimum number of identical rectangular-shaped bins. All items may be rotated and the guillotine cut constraint has to be respected. A straightforward heuristic is presented that is based on a method for the container loading problem following a wall-building approach and on a method for the one-dimensional BPP. 1,800 new benchmark instances are introduced for the two-dimensional and three-dimensional BPP. The instances include more than 1,500 items on average. Applied to these very large instances, the heuristic generates solutions of acceptable quality in short computation times. Moreover, the influence of different instance parameters on the solution quality is investigated by an extended computational study.

引用

页码：337 / 354

页数：18

共 29 条

[11] A lower bound for the non-oriented two-dimensional bin packing problem [J].