摘 要 家具板材包装是家具板材运输过程中最为重要的一个环节，是指在一定的约束条件下，如包装箱内各层面积利用率、空间体积利用率、包装箱内板材高度限制、重量限制、重心约束等，将具有一定长度、宽度和高度的矩形板材合理的装入到装载箱内。家具板材包装属于典型的多约束条件优化组合问题，此类问题也称之为NP-hard问题。经典的 NP-hard 问题有集装箱装载问题、TSP 问题、车辆调度问题等。 家具板材装箱问题致力于提高板材装载箱整体载重利用率，减少装载箱使用的数量，以此降低物品运输的成本，这对当今快速发展的家具行业具有极其重要的意义。由于NP-hard问题十分复杂且极具应用价值，因此成为当今学术界研究的焦点。 近年来学术界提出了许多经典的优化组合算法用来解决NP-hard问题，如蚁群算法、模拟退火法、分布式估计算法、动态规划法、遗传算法等，然而由于现实约束条件以及物品组合的多样性，单一的优化组合算法不能很好的解决此类问题。针对上述问题，本文提出了一种基于启发式算法和混合遗传算法相结合的串级优化组合算法。前级利用基于人工装箱经验构造的启发式算法获得高质量的装箱解，并把 该解作为后级混合遗传算法的初始种群进行迭代变异，直至搜索到问题的最优解。本文把具有较强局部搜索能力的禁忌搜索算法作为传统遗传算法的变异算子构成混合遗传算法，以此克服传统遗传算法局部搜索能力弱，易于早熟的缺点，其次利用启发式算法为混合遗传算法提供质量较好的初始解，以此提高算法收敛速度。因此本文提出的串级算法相比于一般算法不仅获得解的质量高而且算法执行效率也比较高。 本文的第一章详述论文的研究背景、意义以及国内外的研究现状；第二章对家具板材包装问题进行概述，详解当前物品装载问题常用的算法并对各算法优缺点进行分析；第三章对家具板材装箱约束条件进行描述，根据优化目标和约束条件建立相应数学模型，重点设计了本文前级算法启发式算法，对启发式装载策略进行了深入设计，章节最后使用启发式算法对家具板材数据进行处理，得出装箱结果并对其进行分析；第四章对传统遗传算法和禁忌算法进行分析，结合它们各自特点提出本课题后级算法混合遗传算法，重点对混合遗传算法相关参数进行设计，并制定算法执行步骤，章节最后利用该算法进行实验分析；第五章把启发式算法同混合遗传算 法相结合为串级算法，对串级算法内相关参数进行改进，并利用串级算法对家具板材数据进行处理，得出包装结果同前述算法进行对比分析；最后对论文总结并进行展望。 通过对大量家具板材包装数据处理，对各种算法进行对比分析，可以得出：本论文提出的启发式算法和混合遗传算法相结合的串级算法相较于传统算法有效的提高了家具板材装箱的质量和算法运行效率，对家具板材装箱作业具有很强的实用性，对同类装箱问题也有很好地参照性。
关键词：家具板材装箱；NP-hard 问题；启发式算法；混合遗传算法；串级算法
汪金朋
指导教师姓名、职称： 廉迎战 副教授
学科(专业)或领域名称： 控制科学与工程
学 生 所 属 学 院： 自动化学院
论 文 答 辩 日 期： 2019 年 5 月 28 日
广东工业大学硕士学位论文
查看全文：