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