A GRASP/Path Relinking algorithm for two- and three-dimensional multiple bin-size bin packing problems
A GRASP/Path Relinking algorithm for two- and three-dimensional multiple bin-size bin packing problems
复制标题
DOI：
10.1016/j.cor.2012.03.016
复制
发表时间：
2013-12
期刊：
影响因子：
--
通讯作者：
R. Alvarez-Valdés;F. Parreño;J. M. Tamarit
中科院分区：
文献类型：
--
作者：
R. Alvarez-Valdés;F. Parreño;J. M. Tamarit
三维多箱尺寸装箱问题（MBSBPP）是指当存在几种不同尺寸和成本的箱子时，如何将一组箱子装箱到一组箱子中的问题，目标是使装箱所用箱子的总成本最小化。首先，我们提出了一个GRASP算法，包括一个建设性的过程，一个后处理阶段和一些改进措施。获得的最佳解决方案，然后结合到一个路径重新链接过程中，我们已经开发了三个版本：静态，动态和进化。一个广泛的计算研究，使用二维和三维的情况下，显示的相对效率的替代品考虑的算法的每个阶段和我们的算法的良好性能与以前报道的结果相比。
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 bins used for packing the boxes. First we propose a GRASP algorithm, including a constructive procedure, a postprocessing phase and some improvement moves. The best solutions obtained are then combined into a Path Relinking procedure for which we have developed three versions: static, dynamic and evolutionary. An extensive computational study, using two- and three-dimensional instances, shows the relative efficiency of the alternatives considered for each phase of the algorithm and the good performance of our algorithm compared with previously reported results.