二维装箱问题启发式算法地研究

《二维装箱问题启发式算法地研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据厦门大学学位论文著作权使用声明㈣川㈣Ⅲ洲Ⅲ㈣1⋯ⅧIY2731072本人同意厦门大学根据《中华人民共和国学位条例暂行实施办法》等规定保留和使用此学位论文，并向主管部门或其指定机构送交学位论文(包括纸质版和电子版)，允许学位论文进入厦门大学图书馆及其数据库被查阅、借阅。本人同意厦门大学将学位论文加入全国博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编出版，采用影印、缩印或者其它方式合理复制学位论文。本学位论文属于：()1．经厦门大学保密委员会审查核定的保密学位论文，于年月日解密，解密后适用上述授权。(√)2．不保密，适用上述授权

2、。(请在以上相应括号内打“√"或填上相应内容。保密学位论文应是已经厦门大学保密委员会审定过的学位论文，未经厦门大学保密委员会审定的学位论文均为公开学位论文。此声明栏不填写的，默认为公开学位论文，均适用上述授权。)声明人(签名)：法饥褫象10f年年1月L日万方数据摘要二维装箱问题是一种组合优化问题，其目的是将二维长方形物体装入特定大小的二维箱子，使得所使用的箱子面积或者高度最小。装箱问题在晶片切割、货物装载、内存管理等有实际需求。对于二维条形装箱问题(铆o．diInensior谢strippacbngproblem，2DSPP)，现有的算法大多从一个限定的

3、空间出发，逐渐将长方形物体放入空间之间，并不断将空间切割成较小的空间。本文以另一种贪心算法思路解二维装箱问题。从现有物体中选择两个物体组合成一个新的物体，使得新的物体不会超过空间的大小，并使新物体浪费的空间最小。依此思路，能够在一定概率下获得一个不错的结果，重复多次运行可以使求得解的质量提升。对于上述贪心思路，其能够成功获得一个完整解的概率不大。因此从三个方面加以改进。一是使用随机概率选择相同最小浪费空间的物体组合：二是使用随机数确定当前搜索空间的大小；三是使用Path．Relinking算法从现有优秀部分解中组合产生新解。对于二维多箱子装箱问题(觚o·

4、diInensionalvariable—sizedbinpackingproblem，2DVSBPP)，问题的箱子大小可变，使得该问题比较难，目前有效的算法较少。本文以构造性启发式算法为基础，并使用模拟退火、二分搜索对解进行改进。对2DvSBPP大量的测试数据进行实验，提出的算法取得了良好的效果，优于现有的求解算法。关键词：装箱问题；贪心算法；Path-RelikiIlg；回溯；模拟退火万方数据AbstractTwo—dimensionalpackingprobl锄isacombinatoriaIoptimizadonproblem，itstarget

5、istopackseveraltwo—diIllensionalitemsintoaspecifiedt、vo-dimensionalbinorseveralbins，aIldminimizetheusedareaofmisbinortheusedheightofⅡlisbin．PackingproblemhaVe谢delyapplicationsincllipcu仕．mg，10adingofcargoandcomputermemorymanagement．Asmegeneralprocessofpacking，mostofcurrentalgoritl

6、lIIlsfortwo—dimensionalstrippackingproblem(2DSPP)startsfromalimitedspace，pacl(ingrectaIlgularitemsintot11espacesse(1uentially，arldsplitthespaceintosmallerspacesd嘶ngtheprOcessOfpacking．TllisanicIeusesagreedyalgorit

7、lmtosloVetwo—dimensionalpacl(ingproblem．Choosetwoitems丘Dmcurrentit

8、em1ist，andthencombiIlethe锕ochooseditemsintoanewitemsuchthattllenewitemwOn’texceedthewidtllaIldheightofspaCe，aJldthewaStespaceofnewitemisIIlinimal．Ast11ismethodcanacllieveagOodresultsometimes，therefore，mesolutioncanbeimproVedbyrepeatingmismemod．Butitsprobabilit)rachievinggoodsolut

9、ionissmall，somisanicleimproVes“s舢jthodin