Bi-level hybrid local search approach for three-dimensional loading problem with balancing constraints

Abstract

This paper presents a bi-level hybrid local search (BHLS) algorithm for the three-dimensional loading problem with balancing constraints (3DLP-B), where several rectangular boxes with even densities but different sizes are loaded into a single cubic bin to meet the requirements of the space or capacity utilization and the balance of the center of gravity. The proposed algorithm hybridizes a novel framed-layout procedure in which the concept of the core block and its generation strategy are introduced. Once the block-loading sequence has been determined, we can load one block at a time by the designed construction heuristic. Then, the double-search is introduced; its external search procedure generates a list of compact packing patterns while its internal search procedure is used to search the core-block frames and their best distribution locations. The approach is extensively tested on weakly to strongly heterogeneous benchmark data. The results show that it has better performance in improving space utilization rate and balanced condition of the placement than existed techniques: the overall averages from 79.85% to 86.45% were obtained for the balanced cases and relatively high space-usage rate of 89.44% was achieved for the unbalanced ones.

摘要

带平衡约束的三维装载问题是指将一批具有不同尺寸和密度的匀质矩形物品合理装载于一个矩 形箱子,要求在满足装载重心平衡的条件下来实现箱子空间利用最大化目标,本文设计了一种双层混 合局域搜索算法(BHLS)对问题求解。算法将框架式布置思想和核心块生成策略结合起来,通过组合块 的构造及装载系列的优化,确定各物品单元的装填顺序和布局位置。设计的双层算法的外层搜索负责 合理装载模式的搜索,内层搜索用来确定各模式中的核心块及其最佳布局位置。使用包含物品尺寸差 异强弱不同的标准算例进行试验,结果表明算法对带平衡约束的算例可使平均装载率从79.85%提高 到86.45%,对不考虑平衡约束的算例也达到89.44%的较高平均装载率。