多面体Packing问题的并行启发式蚁群算法研究——硕士论文

《多面体Packing问题的并行启发式蚁群算法研究——硕士论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学校代码学号分类号密级硕士学位论文多面体Packing问题的并行启发式蚁群算法研究学位申请人指导教师学院名称信息工程学院学科专业软件工程研究方向软件开发与项目管理年月日39摘要装箱问题(ContainerLoadingProblem,CLP)在物流、多处理器调度、资源分配和包装等方面有着广泛的应用。本文研究多面体的装箱问题，该问题可描述为将若干不同形状的多面体放入固定矩形底的集装箱容器内，要求箱体高度尽可能小。从本质上看，集装箱装载问题为NP难问题。由于解空间为高维实数空间，且多面体的不相交判断计算量相当巨大，比其它Packing问题更难求解，甚至于一般的串行计算机无法在多项式时间内

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

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

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

5、problemofloadingpolyhedroninacontainer(CPLP).Theproblemmightbedescribedasfollows:packingseveraldifferent-sizedanddifferent-shapedpolyhedraintoagivenboxcontainerwithfixedrectanglebase,theobjectiveistominimizetheheightofthecontainer.CPLPisnodoubtanNP-Hardproblem,whichcannotbesolvedwithinapolynomi

6、altimebyanaturalserialcomputer.Comparedwithotherpackingproblems,itismoredifficulttosolveforCPLP,becauseofitshighdimensionalrealsolutionspaceandalargeamountofnon-intersectedcalculation.Sofar,heuristicalgorithmandevolutionalgorithmarefeasibletosolveCPLP,butliteraturespublishedarefewandhaverespect

7、iverestrictedconditions(forexample,onlyfittingtoregular-shapedpolyhedron,norotatingthepolyhedron,computingtheno-fitpolyhedron).Howtoimprovethesolutionaccuracyandcalculationefficiencyhasbeentheproblemexploredbyscholars.Thispaperdis