New lower bounds for the three-dimensional orthogonal bin packing problem

被引：7
|
作者：
Liao, Chung-Shou [1 ]
Hsu, Chia-Hong [1 ]
机构：
[1] Natl Tsing Hua Univ, Dept Ind Engn & Engn Management, Hsinchu 300, Taiwan
来源：
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2013年 / 225卷 / 02期
关键词：
Combinatorial optimization; Bin packing; Lower bounds; Three dimensional; DUAL-FEASIBLE FUNCTIONS; REDUCTION PROCEDURES;
D O I：
10.1016/j.ejor.2012.10.024
中图分类号：
C93 [管理学];
学科分类号：
12 ; 1201 ; 1202 ; 120202 ;
摘要：
In this paper, we consider the three-dimensional orthogonal bin packing problem, which is a generalization of the well-known bin packing problem. We present new lower bounds for the problem from a combinatorial point of view and demonstrate that they theoretically dominate all previous results from the literature. The comparison is also done concerning asymptotic worst-case performance ratios. The new lower bounds can be more efficiently computed in polynomial time. In addition, we study the non-oriented model, which allows items to be rotated. (C) 2012 Elsevier B.V. All rights reserved.
引用
收藏
页码：244 / 252
页数：9
相关论文
共 50 条
  • [1] New lower bounds for the three-dimensional finite bin packing problem
    Boschetti, MA
    DISCRETE APPLIED MATHEMATICS, 2004, 140 (1-3) : 241 - 258
  • [2] New Lower Bounds for the Three-Dimensional Strip Packing Problem
    Hoffmann, Kirsten
    OPERATIONS RESEARCH PROCEEDINGS 2013, 2014, : 201 - 207
  • [3] Lower bounds for three-dimensional multiple-bin-size bin packing problems
    Alvarez-Valdes, R.
    Parreno, F.
    Tamarit, J. M.
    OR SPECTRUM, 2015, 37 (01) : 49 - 74
  • [4] Lower bounds for three-dimensional multiple-bin-size bin packing problems
    R. Alvarez-Valdes
    F. Parreño
    J. M. Tamarit
    OR Spectrum, 2015, 37 : 49 - 74
  • [5] The three-dimensional bin packing problem
    Martello, S
    Pisinger, D
    Vigo, D
    OPERATIONS RESEARCH, 2000, 48 (02) : 256 - 267
  • [6] Three-dimensional bin packing problem with variable bin height
    Wu, Yong
    Li, Wenkai
    Goh, Mark
    de Souza, Robert
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 202 (02) : 347 - 355
  • [7] A hybrid genetic algorithm with a new packing strategy for the three-dimensional bin packing problem
    Kang, Kyungdaw
    Moon, Ilkyeong
    Wang, Hongfeng
    APPLIED MATHEMATICS AND COMPUTATION, 2012, 219 (03) : 1287 - 1299
  • [8] Heuristic algorithms for the three-dimensional bin packing problem
    Lodi, A
    Martello, S
    Vigo, D
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2002, 141 (02) : 410 - 420
  • [9] The three-dimensional bin packing problem and its practical algorithm
    Jin, ZH
    Ito, T
    Ohno, K
    JSME INTERNATIONAL JOURNAL SERIES C-MECHANICAL SYSTEMS MACHINE ELEMENTS AND MANUFACTURING, 2003, 46 (01) : 60 - 66
  • [10] Three-dimensional Bin Packing Problem with heterogeneous batch constraints
    Koblasa, Frantisek
    Vavrousek, Miroslav
    Manlig, Frantisek
    MATHEMATICAL METHODS IN ECONOMICS (MME 2017), 2017, : 330 - 335
12345