多约束有色三维装箱问题的混合遗传算法研究

【摘要】：三维装箱问题研究历史悠久,是一个典型的NP完全难题,广泛存在于生产生活的各个角落,对国民经济的影响巨大,尤其存在于现代物流行业中。对物流企业来说,优化装载问题,提高箱体体积或载重利用率可以压缩企业成本,从而提高企业竞争力,因此三维装箱问题是现代物流所研究的一个重要问题。按装载目标可将三维装箱问题分为箱柜装载问题、容器装载问题和背包装载问题,其中箱柜装载问题是以最少数目限定规格的集装箱装入所有需要装入的货物为研究目标,是三维装箱问题一类重要的研究方向。本文以箱柜装载问题为主要研究对象,结合实际应用提出了多约束有色三维装箱问题。多约束有色三维装箱问题由多约束三维装箱问题和有色装箱问题组成,其中多约束三维装箱研究者颇多,主要为解决实际生活中货物摆放方式、装卸顺序、承受脆度不同而设计的一类三维装箱问题；而有色装箱是指装入同一个箱子的货物类型或者颜色要互异的一类装箱问题。多约束三维装箱问题是结合两类问题的综合问题。论文从多约束有色三维装箱问题的产生背景以及研究意义出发,对此类问题进行深度剖析,提出了从模型建立到混合遗传算法的一整套解决方案。解决方案首先包括多约束有色三维装箱问题模型的抽象,并在此基础上设计装箱过程中的定位规则,利用遗传算法的全局优化能力寻找近似最佳解。在子空间分解问题上本文提出了基于空间优化分解的空间分解方法,即箱体子空间的划分是基于即将装入未划分的空间的物品对该空间的利用率来决定的,并提出了一种的新的数据结构——改进型三叉树来表示此类空间划分,在子空间使用最佳合并策略进行合并,算例证明该方法的解质量高。此外在设计遗传算法解决此类问题时,将染色体划分为头部和尾部,分别表示箱子的装入顺序和摆放方式,其中头部和尾部的基因在交叉和变异的方式上也各不一样。最后对于多约束有色三维装箱问题,基于文中所提出的算法,编写了一套装箱辅助软件,用测试数据测试了算法的优劣,证明解决方案的有效性。
【关键词】：三维装箱 遗传算法 空间优化 组合优化
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP18