Heuristic algorithms for the three-dimensional bin packing problem

被引：115

作者：

Lodi, A ^{[1
]}

Martello, S ^{[1
]}

Vigo, D ^{[1
]}

机构：

[1] Univ Bologna, Dipartimento Elettron Informat & Sistemist, I-40136 Bologna, Italy

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2002年 / 141卷 / 02期

关键词：

cutting; packing; heuristic algorithms; tabu search;

D O I：

10.1016/S0377-2217(02)00134-0

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

The Three-Dimensional Bin Packing Problem (3BP) consists of allocating, without overlapping, a given set of three-dimensional rectangular items to the minimum number of three-dimensional identical finite bins. The problem is NP-hard in the strong sense, and finds many industrial applications. We introduce a Tabu Search framework exploiting a new constructive heuristic for the evaluation of the neighborhood. Extensive computational results on standard benchmark instances show the effectiveness of the approach with respect to exact and heuristic algorithms from the literature. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：410 / 420

页数：11

共 8 条

[1]

Coffman, 1996, APPROXIMATION ALGORI

[2]

Coffman E. G., 1999, HDB COMBINATORIAL OP, P151

[3]

DYCKHOFF H, 1997, ANNOTATED BIBLIOGRAP, P393

[4]

FAERO O, 1999, GUIDED LOCAL SEARCH

[5] Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems [J].

Lodi, A ;

Martello, S ;

Vigo, D .

INFORMS JOURNAL ON COMPUTING, 1999, 11 (04) :345-357

[6]

LODI A, 2000, THESIS U BOLOGNA ITA

[7] The three-dimensional bin packing problem [J].

Martello, S ;

Pisinger, D ;

Vigo, D .

OPERATIONS RESEARCH, 2000, 48 (02) :256-267

[8]

Martello S., 1990, KNAPSACK PROBLEMS AL

← 1 →