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 条
  • [31] Lower bounds for batched bin packing
    Balogh, Janos
    Bekesi, Jozsef
    Dosa, Gyorgy
    Epstein, Leah
    Levin, Asaf
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2022, 43 (03) : 613 - 629
  • [32] A Mathematical formulation and a lower bound for the three-dimensional multiple-bin-size bin packing problem (MBSBPP): A Tunisian industrial case
    Baazaoui, Mariem
    Hanafi, Said
    Kamoun, Hichem
    2014 INTERNATIONAL CONFERENCE ON CONTROL, DECISION AND INFORMATION TECHNOLOGIES (CODIT), 2014, : 219 - 224
  • [33] The two-dimensional finite bin packing problem. Part I: New lower bounds for the oriented case
    Marco A. Boschetti
    Aristide Mingozzi
    Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 2003, 1 : 27 - 42
  • [34] Two-layer heuristic for the three-dimensional bin design and packing problem
    Yang, Ying
    Wu, Zili
    Hao, Xiaodeng
    Liu, Huiqiang
    Qi, Mingyao
    ENGINEERING OPTIMIZATION, 2024, 56 (10) : 1601 - 1638
  • [35] Quick algorithm for the three-dimensional bin packing problem with support surface constraints
    Zhang, Ying
    Liu, Er-Chao
    Qi, Ming-Yao
    Jiaotong Yunshu Xitong Gongcheng Yu Xinxi/Journal of Transportation Systems Engineering and Information Technology, 2014, 14 (02): : 192 - 198
  • [36] The two-dimensional finite bin packing problem. Part I: New lower bounds for the oriented case
    Boschetti, Marco A.
    Mingozzi, Aristide
    4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2003, 1 (01): : 27 - 42
  • [37] Real-Polarized Genetic Algorithm for the Three-Dimensional Bin Packing Problem
    Dornas, Andre Homem
    Cruzeiro Martins, Flavio Vinicius
    Machry Sarubbi, Joao Fernando
    Wanner, Elizabeth Fialho
    PROCEEDINGS OF THE 2017 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (GECCO'17), 2017, : 785 - 792
  • [38] Adaptive Sequence-Based Heuristic for the Three-Dimensional Bin Packing Problem
    Oliveira, Oscar
    Matos, Telmo
    Gamboa, Dorabela
    LEARNING AND INTELLIGENT OPTIMIZATION, LION, 2020, 11968 : 69 - 76
  • [39] Improved lower bounds for the online bin packing problem with cardinality constraints
    Fujiwara, Hiroshi
    Kobayashi, Koji
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2015, 29 (01) : 67 - 87
  • [40] Improved lower bounds for the online bin packing problem with cardinality constraints
    Hiroshi Fujiwara
    Koji Kobayashi
    Journal of Combinatorial Optimization, 2015, 29 : 67 - 87
12345