基于混合整数规划的二维不规则排样算法研究

作     者：李锦瑞 

作者单位：燕山大学 

学位级别：硕士

导师姓名：郭保苏

授予年度：2021年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0802[工学-机械工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 080201[工学-机械制造及其自动化] 

主      题：二维不规则排样 临界多边形 混合整数规划 矢量叠加 启发式算法 

摘      要：二维不规则排样问题是一类经典的平面组合优化问题,广泛存在于航空航天、汽车、造船等先进制造业中。排样的核心目标是原材料利用率的最大化。研究高效的排样算法能有效减少原材料的消耗,提高制造业的自动化、智能化水平,具有显著的经济效益和社会效益。因此研究二维不规则排样问题具有重要意义。影响二维不规则排样结果的主要因素有两个,一个是样件的定位,另一个是样件的填充顺序。对于定位部分,现有的定位方法定位计算效率不高,且容易遗漏空腔或凹区域,造成空间浪费。对于填充顺序部分,单一启发式顺序优化算法易使解在局部最优处收敛。为了促进二维不规则排样问题在实际生产中的有效解决,本论文对二维不规则排样问题展开研究。针对现有问题,本论文对二维不规则排样问题的定位算法和顺序优化算法展开研究,提出一种基于混合整数规划的二维不规则排样模型,并设计混合启发式算法对所提出模型进行求解。论文的主要内容如下:（1）分析实际下料生产中轮廓图形的常用构建与表达方式,研究读取和转存CAD文件的原理,建立完整表达带空腔样件的数据结构,设计基于DXF文件的样件轮廓读取转存算法和任意曲线轮廓的多边形逼近算法,确保样件轮廓预处理后能有效地与排样定位和定序策略相结合。（2）分析二维不规则排样问题定位效率低和易遗漏空腔的问题,提出一种基于矢量叠加的临界多边形求解算法,能够快速找到样件所有可能的靠接位置,解决传统临界多边形求解算法易遗漏空腔或凹区域的问题,实现样件的快速、精确定位。（3）针对单一启发式的填充顺序优化算法易陷入局部最优解的问题,分析二维不规则排样问题的多个约束,提出一种基于混合整数规划的二维不规则排样模型。以遗传算法为框架,设计一种结合模型约束的混合启发式算法对该模型进行求解。（4）研究跨平台应用程序开发技术,基于“前端Electron后端Java的理念,基于Electron和Java开发二维不规则排样系统,通过调整排样参数进行排样,得出排样实例图与排样结果参数,验证本文提出排样算法的正确性及排样系统的可行性。