资源描述：
《基于最大最小蚁群算法的智能装载方法.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、山东农业大学学报(自然科学版),2014,45(3):366-371VOL.45NO.32014JournalofShandongAgriculturalUniversity(NaturalScienceEdition)doi:10.3969/j.issn.1000-2324.2014.03.009基于最大最小蚁群算法的智能装载方法葛玮,徐卫红,程海水江西广播电视大学,江西南昌330000摘要:三维装箱问题在现实生活中有着广泛的应用，是具有复杂约束的组合优化问题，理论上属于NP-hard问题。针对贪
2、心算法通常得到的是局部最优解以及基本蚁群算法存在不足等问题，本文首先给出了启发式装箱规则，然后结合最大最小蚁群算法对装载顺序进行优化，提出了一个求解三维装箱问题的混合蚁群算法，最后通过实验对比验证了该算法的有效性和优越性，并给出了三维效果展示图。关键词:三维装箱;启发式;最大最小蚁群算法中图法分类号:TP18文献标识码:A文章编号:1000-2324(2014)03-0366-06IntelligentLoadingMethodsBasedonMax-minAntColonyAlgorithmGEW
3、ei,XUWei-hong,CHENGHai-shuiJiangxiRadio&TVUniversity,Nanchang330000,ChinaAbstract:Threedimensionalcontainerloadingprobleminreallifehasawiderangeofapplications,anditisacombinationofcomplexconstrainedoptimizationproblemsbelongtoNP-hardinthetheory.Fortheg
4、reedyalgorithmusuallytogetalocaloptimalsolutionandthebasicantcolonyalgorithmdeficienciesandotherissues.FirstlythispapergaveaHeuristicsboxingrules,andthencombinedthemax-minantcolonyoptimizationalgorithmtooptimizetheloadingsequenceandproposedtosolveathre
5、e-dimensionalhybridantcolonyalgorithmforbinpackingproblem.Finallyvalidatedbyexperimentscomparingtheeffectivenessandsuperiorityofthealgorithm,andgaveafigureofthree-dimensionaldemonstration.Keywords:Threedimensionalcontainerloadingproblem;heuristics;max-
6、minantcolonyalgorithm装箱问题在现实生活中具有广泛应用，如切割加工业和运输业。高利用率的切割和装载可以节约大量成本。实际应用中由于不同的优化目标和装载约束，导致了不同种类的装箱问题。Dyckhoff和Finke概述了不同类型的装箱问题[1]。本文所处理的三维装箱问题是其中之一。三维装箱问题是具有复杂约束条件的组合优化问题，理论上属于NP-hard问题[2]，采用精确求解算法是不现实的，因此启发式求解方法成为理论研究和实际应用的首选。Ngoi[3]以及Bischoff[4]等提出了
7、一些启发式算法。Gehring[5]等将遗传算法应用到装箱问题中。Bortfeldt[6]等分别提出了禁忌搜索求解算法、混合遗传求解算法和基于分支定界的一个启发式算法。Moura等提出了一个随机自适应启发式算法GRASP[7].国内学者在三维装箱问题的研究上，也取得了不错的成果[8-14]，特别是黄文奇等提出了一种最大穴度的占角动作优先的拟人型求解算法[13]，张德富等将启发式算法和模拟退火算法相结合，提出了混合求解算法[14]。通过对上述文献的研究分析，发现启发式算法和一些智能算法以及二者的结合对
8、解决三维装箱问题很有效果。本文采用最大最小蚁群算法结合启发式算法对其进行优化，提出了一个有效的求解三维装箱问题的混合算法，克服了传统贪心算法容易陷入局部最优值的不足。1问题描述本文探讨的三维装箱问题的形式化定义：给定一个长方体容器C和一个待装箱的长方体箱子集合B{,...,}bb，容器C的长宽高分别为LWH,,，最大载重量Z，为每个箱子b的长宽高为1nilwh,,，重量为z。设S为B的一个子集，问题的目标是确定一个可行的放置箱子的方案，即选iiii择B的一个合适的子
