求解装箱问题的启发式算法研究

论文摘要

装箱问题是个在工业生产中经常碰到的问题,如集装箱的装载、板材的切割、集成电路的设计、报纸的排版等等。该问题又是NP完全问题,因此对该问题的研究有着重要的应用价值和理论意义。如果用精确算法求解装箱问题,势必带来计算量的组合爆炸,因此学者提出了很多求解该问题的启发式算法。本文首先研究了二维装箱问题,在总结前人工作的基础上,提出了解决二维矩形条装箱(2SP)的二分搜索启发式(BSHA)算法。首先,通过引入二分搜索把2SP问题转化成二维背包装箱问题(2KP)来求解。然后,针对2KP,本文提出了最小浪费优先策略,该策略通过记录点的方法来记录装填位置,并引入浪费面积、平整度等评价机制来评价某个物品放入某个位置的好坏程度。最后,利用随机局部搜索算法进一步改进计算的结果。本文对BSHA算法进行了大量的实例测试,结果表明,BSHA的求解质量优于目前优秀的算法,如GRASP、SPGAL、HRBB等,而且对于很多实例,BSHA都能在短时间内找到最优解。对于三维装箱问题,本文提出了组合启发式算法。首先提出了求解三维装箱问题的拟人启发式算法,该方法受生活中砌墙的思想启发而提出,是二维装箱的拟人启发式算法在三维装箱问题中的扩展,通过在装填过程中引入了参考箱子、参考线等概念来引导装填过程。最后,通过引入模拟退火算法来改善拟人启发式算法的结果。试验结果表明,我们的算法优于当前已知的优秀算法。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景及意义
• 1.2 国内外研究现状
• 1.3 本文的内容安排
• 第二章 启发式算法
• 2.1 启发式方法
• 2.2 模拟退火算法
• 第三章 二维矩形装箱算法研究
• 3.1 二维装箱问题综述
• 3.2 现有启发式算法
• 3.2.1 BL及BLF算法
• 3.2.2 BF算法
• 3.2.3 PH算法
• 3.3 二分搜索启发式算法
• 3.3.1 问题描述
• 3.3.2 二分搜索启发式算法
• 3.3.3 试验结果
• 3.4 本章小结
• 第四章 三维装箱算法研究
• 4.1 三维装箱问题综述
• 4.2 组合启发式算法
• 4.2.1 问题描述
• 4.2.2 拟人启发式算法
• 4.2.3 试验结果
• 4.3 本章小结
• 第五章 结论和进一步的工作
• 附录 A
• 参考文献
• 攻读硕士学位期间发表的论文
• 致谢