分布估计算法求解集装箱装载问题-论文.pdf

《分布估计算法求解集装箱装载问题-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第24卷第8期计算机技术与发展Vo1．24No．82014年8月COMPUTERTECHNOLOGYANDDEVELOPMENTAug．2014分布估计算法求解集装箱装载问题左先亮，郭莉莉，高尚(江苏科技大学计算机科学与工程学院，江苏镇江212003)摘要：集装箱装载是一个空间优化分解的布局问题，其约束条件多，属于典型的NP完全问题，求解难度大。在考虑实际应用中的约束条件下，使用三空间分割的布局方法对剩余空间进行分解，并采用空间合并原则将闲置空间与可用空间进行合并达到充分利用，并结合分布估计算法(

2、EDA)求解多约束装箱问题。分布估计算法采用统计学习的方法建立一个描述解分布的概率模型，再对概率模型进行随机采样产生新的种群，如此反复进行，实现种群的进化，最终获取最优解。实验仿真结果表明该算法应用于实际空间规划设计中具有重要的实际意义。关键词：集装箱装载；空间分割；分布估计算法；统计学习；概率模型中图分类号：TP301文献标识码：A文章编号：1673—629X(2014)08—0183—04doi：10．3969／j．issn．1673—629X．2014．08．043SolvingofCont

3、ainerLoadingProblembyEstimationofDistributionAlgorithmZUOXian-liang，GUtLi-li，GAOShang(SchoolofComputerScienceandEngineering，JiangsuUniversityofScienceandTechnology，Zhenjiang212003，China)Abstract：Containerloadingisalayoutproblemwithspaceoptimizationand

4、decomposition．Withmultipleconstraints，it’satypicalNP—completeproblemanddificulttoobtainalloptimalsolution．Consideringsomeconstraintsinpracticalapplications，adoptthememumsofthree-space-dividingtodecomposetheresidualspace，usethespatialmergeprincipletoco

5、mbinethefreespacewiththeusablespaceinordertoachievethefulluseofcontainer，andcombinedwiththeEstimationofDistributionAlgorithm(EDA)，solvethemulti—constrain·edpacingproblem．TheEDAestablishesaprobabilitymodelbystatisticallearningtodescribethedistributiono

6、fsolutions．Newpopula—tionsalegottenbysamplingtheprobabilitymodelrandomly．Thealgorithmisiteratedtorealizetheevolutionandfinallytogetthebestindividuals．Thesimulationresultsshowthatthealgorithmisofgreatsignificanceinthepracticalplanninganddesignofspace．K

7、eywords：containerloading；spacedividing；EstimationofDistributionAlgorithm(EDA)；statisticallearning；probabilitymodelO引言个关键性的问题：集装箱装载问题是指将不同尺寸的货物按照一定(1)物体装入容器的空间的分解方法，即布局问的约束条件装入具有一定容量的集装箱中，使其空间题；利用率和重量利用率达到最高。该问题是货物运输过(2)如何确定物体的装载顺序。程中的重要环节，如何给出一种合理的布局及

8、装载方目前常用的研究方法有数学规划法、图论法、启发式方法剖、蚁群算法、模拟退火算法、禁忌搜案，将提高集装箱的利用率以获得某种最佳效益，是集索算法⋯、遗传算法等。装箱装载问题的主要目标。文中将分布估计算法应用于三维装箱问题的求随着对集装箱装载问题研究的不断深入，目前大解，这对于将分布估计算法应用于实际空间规划设计部分是研究二维或三维矩形物体在矩形容器中的布中具有重要的实际意义。局。由于三维布局在数学上属于NP⋯完全问题，在短时间内找不到最优解。对于这样的问题，需要解决两收稿日期：20