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 条
  • [41] New Lower Bounds for Certain Classes of Bin Packing Algorithms
    Balogh, Janos
    Bekesi, Jozsef
    Galambos, Gabor
    APPROXIMATION AND ONLINE ALGORITHMS, 2011, 6534 : 25 - 36
  • [42] New classes of fast lower bounds for bin packing problems
    Sándor P. Fekete
    Jörg Schepers
    Mathematical Programming, 2001, 91 : 11 - 31
  • [43] New classes of fast lower bounds for bin packing problems
    Fekete, SP
    Schepers, J
    MATHEMATICAL PROGRAMMING, 2001, 91 (01) : 11 - 31
  • [44] New lower bounds for certain classes of bin packing algorithms
    Balogh, Janos
    Bekesi, Jozsef
    Galambos, Gabor
    THEORETICAL COMPUTER SCIENCE, 2012, 440 : 1 - 13
  • [45] Heuristic algorithm for three-dimensional bin packing problems
    Tang, Xiao-Jun
    Cha, Jian-Zhong
    Tiedao Xuebao/Journal of the China Railway Society, 2003, 25 (06):
  • [46] Optimizing three-dimensional bin packing through simulation
    Dube, Erick
    Kanavathy, Leon R.
    PROCEEDINGS OF THE SIXTH IASTED INTERNATIONAL CONFERENCE ON MODELLING, SIMULATION, AND OPTIMIZATION: SCIENCE AND TECHNOLOGY FOR DEVELOPMENT IN THE 21ST CENTURY, 2006, : 1 - +
  • [47] A column generation-based heuristic for the three-dimensional bin packing problem with rotation
    Mahvash, Batoul
    Awasthi, Anjali
    Chauhan, Satyaveer
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2018, 69 (01) : 78 - 90
  • [48] Efficient lower bounds and heuristics for the variable cost and size bin packing problem
    Crainic, Teodor Gabriel
    Perboli, Guido
    Rei, Walter
    Tadei, Roberto
    COMPUTERS & OPERATIONS RESEARCH, 2011, 38 (11) : 1474 - 1482
  • [49] Approximation algorithms for the orthogonal Z-oriented three-dimensional packing problem
    Miyazawa, FK
    Wakabayashi, Y
    SIAM JOURNAL ON COMPUTING, 2000, 29 (03) : 1008 - 1029
  • [50] A three-dimensional bin packing problem with item fragmentation and its application in the storage location assignment problem
    Salamati-Hormozi, Hamid
    Kashan, Ali Husseinzadeh
    Ostadi, Bakhtiar
    4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2024, 22 (04): : 483 - 536
12345