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