Lower bounds for three-dimensional multiple-bin-size bin packing problems
Lower bounds for three-dimensional multiple-bin-size bin packing problems
复制标题
DOI：
10.1007/s00291-013-0347-2
复制
发表时间：
2013-10
期刊：
影响因子：
2.7
通讯作者：
R. Alvarez-Valdés;F. Parreño;J. M. Tamarit
中科院分区：
文献类型：
--
作者：
R. Alvarez-Valdés;F. Parreño;J. M. Tamarit
三维多箱尺寸装箱问题（MBSBPP）是指当有几种不同尺寸和成本的箱子时，如何将一组箱子装箱到一组箱子中的问题，目标是使装箱所用箱子的总成本最小。我们提出了一个研究这个包装问题的下界。我们已经开发了新的界限的基础上整数规划的一些松弛的原问题的配方。这些公式是加强与逻辑的考虑。建议的界限进行了比较，与其他现有的界限在一个广泛的计算研究，包括二维和三维的情况下，多达100个箱子，其中一些来自文献和其他改编自经典装箱问题。所提出的界限改善了以前的界限的结果超过10%，但在一个更高的计算成本。
The three-dimensional multiple-bin-size bin packing problem (MBSBPP) is the problem of packing a set of boxes into a set of bins when several types of bins of different sizes and costs are available and the objective is to minimize the total cost of the bins used for packing the boxes. We present a study of lower bounds for this packing problem. We have developed new bounds based on integer programming formulations of some relaxations of the original problem. These formulations are enhanced with logical considerations. The proposed bounds are compared with other existing bounds in an extensive computational study, including two- and three-dimensional instances with up to 100 boxes, some of them taken from the literature and others adapted from the classical Bin Packing Problem. The proposed bounds improve the results of previous bounds by more than 10%, though at a higher computational cost.