多面体packing问题的并行启发式蚁群算法研究

《多面体packing问题的并行启发式蚁群算法研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、学校代码10530学号201431111821分类号TP391密级硕士学位论文多面体Packing问题的并行启发式蚁群算法研究学位申请人王梓键指导教师黎自强教授学院名称信息工程学院学科专业软件工程研究方向软件开发与项目管理二○一七年四月十日ThestudyontheparallelheuristicantcolonyalgorithmforpolyhedrapackingproblemCandidateWangZiJianSupervisorLiZiqiang(professor)CollegeSchoolof

2、InformationandEngineeringProgramSoftwareEngineeringSpecializationSoftwareDevelopmentandProjectManagementDegreeMasterofScienceUniversityXiangtanUniversityDateApril10th,2017湘潭大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表

3、或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权湘潭大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或,扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名：日期：年月日导师签名：日期：年月日摘要装箱问题

4、(ContainerLoadingProblem,CLP)在物流、多处理器调度、资源分配和包装等方面有着广泛的应用。本文研究多面体的装箱问题，该问题可描述为将若干不同形状的多面体放入固定矩形底的集装箱容器内，要求箱体高度尽可能小。从本质上看，集装箱装载问题为NP难问题。由于解空间为高维实数空间，且多面体的不相交判断计算量相当巨大，比其它Packing问题更难求解，甚至于一般的串行计算机无法在多项式时间内找到可行解。到目前为止，启发式、演化算法是解决这类组合优化问题的有效方法。但解决本文问题相关文献比较少，求解精

5、度和计算效率仍然有待提高，且都具有一定的局限性，如限制物体形状和物体放置方向，需要计算临界多面体等。本文在湖南省自然科学基金项目“三维静动态平衡约束多形状布局问题的全局协同优化机理与方法研究”的资助下，展开对该问题的研究，主要工作和创新描述如下：1、本文提出了一种新的IHAPE3D(Improved-HAPE3D)算法。（1）在重力势能的基础上，引入了另外两个方向的引力势能，进而基于最小势能原理重新定义了系统的势能表达式；(2)利用“平面分离定理”进行多面体干涉判断，采用GPU多线程并行计算物体的最优放置状态，

6、减少计算时间。实验结果表明：提出的方法提升了容器的空间利用率、减少了求解时间。2、本文提出一种多面体Packing问题的启发式蚁群算法。设计蚁群算法的动态信息素自适应更新规则，能避免蚁群迭代陷入于局部最优和提高大规模问题的搜索速度。通过实验对比，表明改进后的IHAPE3D算法与蚁群算法结合可以有效优化多面体装填顺序，相比已有的实验成果，进一步的提升了容器的空间利用率。本文以现实生活中的集装箱装载问题为背景，深入探究了三维空间中多面体Packing问题。首先提出了一种基于最小势能原理的Packing启发式算法，可

7、以根据给定条件高效地计算出Packing方案，再针对具体问题，混合了动态蚁群算法以进行优化，比较高效地解决了三维中多面体的Packing问题。希望本文能作为三维多面体Packing问题求解的阶段性成果，将来为更多类似的布局问题研究提供思路和参考。关键词：三维布局；多面体布局；蚁群算法；集装箱装载39AbstractThecontainerloadingproblemhaswidelyappliedtovariousareassuchaslogistics,multi-processorscheduling,re

8、sourceallocation,cuttingandpacking.Thispaperfocusesontheproblemofloadingpolyhedroninacontainer(CPLP).Theproblemmightbedescribedasfollows:packingseveraldifferent-sizedanddifferent-shapedpolyhedra