An Efficient Dynamical Programming Algorithm for Bin Packing Problem

被引：0
作者：
Huyghe, Catherine [1 ]
Negre, Stephane [2 ]
Fontaine, Melanie [3 ]
机构：
[1] Univ Picardie Jules Verne, MIS, Amiens, France
[2] Univ Picardie Jules Verne, EPROAD, Amiens, France
[3] Univ Picardie Jules Verne, LTI, Amiens, France
来源：
2023 INTERNATIONAL CONFERENCE ON COMPUTATIONAL SCIENCE AND COMPUTATIONAL INTELLIGENCE, CSCI 2023 | 2023年
关键词：
bin packing problem; heuristic; dynamical programming; algorithm; lower bound;
D O I：
10.1109/CSCI62032.2023.00078
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
In this paper, we propose a very efficient algorithm to solve the 2 dimensional bin packing problem. The algorithm can automatically place thousands of objects in bins using less than 1 minute with very near optimal results on big size instances even if orientation of the objects is free.
引用
收藏
页码：443 / 449
页数：7
相关论文
共 50 条
[21]   A Hybrid Algorithm with Reduction Criteria for the Bin Packing Problem in One Dimension [J].
Perez, Joaquin ;
Castillo, Hilda ;
Vilarino, Darnes ;
Zavala, Jose C. ;
De la Rosa, Rafael ;
Ruiz-Vanoye, Jorge A. .
PROCEEDINGS OF THE INTERNATIONAL CONFERENCE OF NUMERICAL ANALYSIS AND APPLIED MATHEMATICS 2014 (ICNAAM-2014), 2015, 1648
[22]   A hybrid genetic algorithm with a new packing strategy for the three-dimensional bin packing problem [J].
Kang, Kyungdaw ;
Moon, Ilkyeong ;
Wang, Hongfeng .
APPLIED MATHEMATICS AND COMPUTATION, 2012, 219 (03) :1287-1299
[23]   LOWER BOUNDS AND REDUCTION PROCEDURES FOR THE BIN PACKING PROBLEM [J].
MARTELLO, S ;
TOTH, P .
DISCRETE APPLIED MATHEMATICS, 1990, 28 (01) :59-70
[24]   Algorithms for the bin packing problem with scenarios [J].
Borges, Yulle G. F. ;
de Lima, Vinicius L. ;
Miyazawa, Flavio K. ;
Pedrosa, Lehilton L. C. ;
de Queiroz, Thiago A. ;
Schouery, Rafael C. S. .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2024, 48 (04)
[25]   Efficient lower bounds and heuristics for the variable cost and size bin packing problem [J].
Crainic, Teodor Gabriel ;
Perboli, Guido ;
Rei, Walter ;
Tadei, Roberto .
COMPUTERS & OPERATIONS RESEARCH, 2011, 38 (11) :1474-1482
[26]   An exact algorithm for the type-constrained and variable sized bin packing problem [J].
Chunyang Zhou ;
Chongfeng Wu ;
Yun Feng .
Annals of Operations Research, 2009, 172 :193-202
[27]   Weighted quantum genetic algorithm for one-dimensional bin packing problem [J].
Han, Thae-Gyong ;
Kim, Nam-Chol ;
Ko, Myong-Chol ;
Ryom, Ju-Song ;
Ri, Su-Ryon .
QUANTUM INFORMATION PROCESSING, 2025, 24 (09)
[28]   Optimizing large scale bin packing problem with hybrid harmony search algorithm [J].
Adamuthe, Amol C. ;
Nitave, Tushar R. .
INTERNATIONAL JOURNAL OF INDUSTRIAL ENGINEERING COMPUTATIONS, 2021, 12 (02) :205-220
[29]   MODIFIED GENETIC AlGORITHM WITH VARIABLE-LENGTH CHROMOSOMES FOR BIN PACKING PROBLEM [J].
Yamamoto, Kyosuke ;
Yanagawa, Yoshinari ;
Arizono, Ikuo .
ICIM'2016: PROCEEDINGS OF THE 13TH INTERNATIONAL CONFERENCE ON INDUSTRIAL MANAGEMENT, 2016, :346-353
[30]   An exact algorithm for the type-constrained and variable sized bin packing problem [J].
Zhou, Chunyang ;
Wu, Chongfeng ;
Feng, Yun .
ANNALS OF OPERATIONS RESEARCH, 2009, 172 (01) :193-202
12345