启发式算法求解二维矩形切割优化问题研究

发布时间：2022-12-21 23:38

　　二维矩形切割优化问题属于组合优化问题的范畴,已被证明为NP难问题。在化工业生产中,常常会涉及到原料或半成品的切割等工序。而二维矩形切割问题相对于单维和多维切割问题在工业界的应用最为广泛,有着诱人的发展前景。因此研究该问题对于提升企业经济效益和推动学术界理论研究都有着重要的价值。二维矩形切割优化问题是将标准尺寸的原料按照Guillotine切割方式切割成特定尺寸的成品,在此过程中会产生部分废料,优化的目标是最小化原料的总用量和最小化切割产生的废料,为此本文设计了求解该问题的一种迭代的带扰动机制和分支定界的启发式树搜索算法（IHTS-P）,通过深度优先搜索探索解空间,加入分支策略对解空间进行细分,而剪枝策略则是对无意义的解空间进行剪枝便于算法加速,为了提高求解优度和求解效率,本文还创新性地提出了迭代优化策略和禁忌扰动机制:通过迭代优化中每一轮的集中性的搜索来改善解空间,通过禁忌扰动机制来增强解的疏散性。利用源自工业界的多种真实算例对IHTS-P算法进行测试,并和本文提出的两种混合整数规划模型:完整模型（CM）、迭代模型（IM）测试结果进行对比,同时和最优解进行对比,以及在不同的运行时间下对... 

【文章页数】：83 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
1 绪论
    1.1 课题背景和意义
    1.2 国内外研究概况
    1.3 本文主要工作及结构安排
2 切割优化模型实现
    2.1 问题概述
    2.2 问题建模
    2.3 本章小结
3 求解TDRCO问题的启发式树搜索算法
    3.1 启发式树搜索算法概述
    3.2 整体算法框架
    3.3 解的表示
    3.4 启发式树搜索
    3.5 迭代优化
    3.6 扰动机制
    3.7 本章小结
4 实验结果分析
    4.1 测试方案设计
    4.2 测试算例分析
    4.3 参数设定
    4.4 实验结果对比
    4.5 本章小结
5 总结与展望
    5.1 总结
    5.2 展望
致谢
参考文献
附录 Ⅰ:测试数据



本文编号：3722992