装箱问题厂泛存在于工业领域,尤其是对于物流运输业和材料制造业,解决装箱问题的效率和效果直接影响到行业成本和收益。随着我国市场经济的发展,工业规模越来越大,装箱问题在商业活动中的作用将越来越受重视。解决装箱问题的算法作为一项提高资源利用率的关键性技术,在充分利用运输能力、减少材料损耗、保护自然资源等方面都有非常重要的意义。尽管物流业务和材料制造业都发展很快,但装箱软件的数量和质量却没有很大提高。至今为止,国内外许多学者对装箱问题已经进行了大量的研究,发表了各种解决该问题的方法。本文在前人研究的基础上,提出一种新的装箱算法,期望能够用新的方法,以更高的效率求解装箱问题。本文提出了一个高效求解三维装箱问题的启发式分层搜索算法。本文的工作包括:第一,基于块装载提出基础启发式算法,按照块选择算法确定每个阶段采用的块,以一种固定的放置方式装载块,直到无法继续放置物品;第二,提出了复合块的概念,与传统算法不同的是本文提出的复合块不只包含单一种类的物品,而是可以在一定的限制条件下包含任意种类任意数目的物品;第三,以深度优先搜索为基础进一步发展出分层搜索算法,在基础启发式的每一个装载阶段以分层搜索确定当前阶段的选择,使得搜索结果更接近最优解。本文采用了Bischoff和Ratcliff的1600个三维装箱问题测试数据对算法进行测试。实验结果表明,分层启发式搜索算法几乎在所有的测试数据上填充率都超过了目前已知的优秀算法。