基于禁忌搜索算法集装箱装载问题的的研究

《基于禁忌搜索算法集装箱装载问题的的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、沈阳工业大学硕士学位论文摘要集装箱装载问题(ContainerLoadingProblem，简称CLP)属于“切割和装入”问题，在数学理论上为NP完全问题，即不能在多项式时间内找到问题的最优解。CLP虽然求解困难，但随着计算机技术的发展，使用计算机辅助求解CLP成为可能，但因CLP本身特征，实际应用中无法采用纯数学方法，而是采用基于启发式的近似求解方法。计算机辅助布局优化能够有效提高空问装载效率，在铁路和远洋运输中能够降低运输成本，研究成果还可以推广到计算机内存分配等空间资源优化领域，因此有着重要

2、的实际意义。近年来CLP逐渐成为人们关注的焦点。本文绪论先对CLP的产生背景及实际意义进行论述，然后对其研究范畴和分类予以介绍，最后在查阅大量文献的基础上阐明了CLP的国内外发展现状。禁忌搜索算法(TabuSearch，简称TS)是近年来逐渐引起人们兴趣的一种现代启发式算法，因其特殊的“记忆”机制，表现出极好的全局寻优能力，在对一些复杂、困难问题的求解中取得了很好效果。本文从TS的原理、搜索技术以及收敛理论等方面进行说明。应用TS求解CLP在国内还没有相关研究，本文结合CLP的实际特征，提出了不同

3、于Bortfeldt和Gehring方法的新的编码、解码及邻域解构造方法；在解码中引入了新的空间合并策略，提高了集装箱利用率；应用“组合块”思想减少了剩余空间的零碎划分，降低了搜索代价；本文创造性的将TS应用于求解多箱装载问题，取得了理想效果。结果显示对于集装箱装载系统的应用有重要意义，本文给出了数据显示和图形显示两种方式。数据显示精确描述装载方案中物体顺序、位置等信息；图形显示提供了装载方案的可视化效果，更便于用户观察。实例分析部分通过对4个标准数据集进行测试，证明了用TS求解CLP的有效性和实

4、用性，同时讨论了算法中存在的优点与不足。最后对全文工作进行总结并对以后的研究方向进行了展望。关键词：集装箱装载问题，禁忌搜索，布局优化，胛完全问题，启发式算法基于禁忌搜索算法的集装箱装载问题研究ResearchonContainerLoadingProblemBasedonTabuSearchAbstractContainerloadingproblem(CLP)belongsto”cuttingandpacking”problemandaNPcompleteprobleminmathematic

5、s．Forthiscase，itcannotbeusedtogetthebestsolutioninpolynomialtime．AlthoughCLPiscomplex,withthedevelopmentofcomputerscience，CLPcanbesolved、撕tllthehelpofcomputer．OwningtotheattributeofCLPitself,CLPcannotbcdealtinonlypuremathematicwayinpractice．butinanapp

6、roximateway,suchasheuristicmethod．Computeraidedlayoutoptimizationcanimprovethecontainerloadingefficiency．Forthisreason,thetransportationcostof期ilwayandoceanshippingcanbecutdown．Andtheproductionofresearchcanbeextendedintospaceresourceallocation,such鹤co

7、mputermemoryallocation．Thus，CLPisbecomingastheresearchfocusinrecentyears．ThepaperintroductionfirstlydiscussesthegenerationbackgroundandpracticalmeaningofCLP，andthenexplainsthecategoryofCLP，atlastconcludestheresearchstatusinquoaccordingtoagreatdealofli

8、teratures。Tabusearchalgorithm(TS)isakindofmeta-heuristicalgorithms，andisfamousforitsspecial’’memory”mechanism．Ithasamazingabilitytosearchglobally．Goodresultsofsomedifficultandhardproblemshavebeenachievedforthisreason．ThepaperintroducesTSfrompr