1、本科毕业设计（20届）求解三维装箱问题的遗传算法研究所在学院专业班级计算机科学与技术学生姓名学号指导教师职称完成日期年月I摘要【摘要】三维装箱问题是合理地选择需要租用的集装箱并将给定数量的木箱全部装进租用的集装箱中。木箱的装载方案和集装箱的选择方案都会对集装箱的空间利用率及租用的总成本产生很大的影响，所以如何在两方面进行有效的优化，是目前装箱问题上最需关注的话题。本文先对装箱问题及目前的研究现状进行了阐述，然后提出了单箱装箱问题的启发式算法，接着在此基础上，提出了多集装箱装箱问题的遗传算法，最后通过实例证明了该方法能得出该问题的较优解。【关键词】三维装箱问题；启发式算法；遗传算法。ABSTRA
2、CT【ABSTRACT】THREEDIMENSIONALPACKINGPROBLEMISAREASONABLECHOICEOFCONTAINERFORSTUFFINGAGIVENNUMBEROFBOXESWOODENBOXESLOADINGPROGRAMSANDTHEOPTIONSOFTHECONTAINERWILLHAVEAHUGEEFFECTONTHESPACEUTILIZATIONOFCONTAINERANDTHETOTALCOSTOFRENTINGSOHOWTOMAKEANEFFECTIVEOPTIMIZATIONONTHETWOASPECTSISTHEKEYPROBLEMNOWTHE
3、ARTICLEFOCUSESONPACKINGPROBLEMSANDCURRENTRESEARCHARESURVEYEDINDETAILASINGLEBOXPACKINGHEURISTICALGORITHMANDAGENETICALGORITHMONMULTICONTAINERLOADINGPROBLEMWEREPROPOSEDTHESIMULATIONRESULTSSHOWTHATTHEPROPOSEDALGORITHMSCANOBTAINTHEOPTIMUMSOLUTIONOFTHEPROBLEM【KEYWORDS】THREEDIMENSIONALPACKINGPROBLEM；HEURIS
4、TIC；GENETICALGORITHM。II目录摘要IABSTRACTI目录II1绪论111装箱问题112现有装箱问题的解决方法113课题研究内容22面向单箱装箱问题的启发式算法321单箱装箱要求322算法思想3221放置点介绍3222放置点的合并4223启发式算法423程序设计43基于遗传算法多集装箱装箱问题531遗传算法5311遗传算法的过程5312遗传算法的特点6313遗传算法的组成要素632求解多集装箱装箱问题的遗传算法设计8321编码设计8322遗传算子的设计8323适应度函数设计933程序设计9331算法流程大体介绍10332算法关键部分详细说明104仿真研究1241算例自动生成
5、程序1242测试算例12421层级1到层级2的装载13422层级2到层级3的装载135结论与展望1551结论1552展望15参考文献16致谢错误未定义书签。附录一算例自动生成源程序17附录二表41中的部分算例及输出结果2211绪论11装箱问题装箱问题通常指的是装载给定箱子集合的一个子集到容器中，使得被装载的箱子总体积最大。根据维数的不同，可分为一维装箱问题、二维装箱问题、三维装箱问题三种。一维装箱问题比较简单，已经没有研究的必要了，二维装箱问题目前虽然没有高效精确的算法，但很多学者都提出了比较高效的近似算法，也逐渐淡出了研究的邻域，而与现实生活密切相关的是三维装箱问题，许多物流公司都渴望拥有一
6、个比较有效的三维装箱软件，来降低实际装载运输的成本，而三维装箱问题是一个多约束条件下的组合优化问题，虽然一些学者提出了比较高效的近似算法，但都是基于某些约束条件的，所以仍然有必要研究特殊约束条件下的高效的三维装箱算法和更加通用的三维装箱算法。用数学方式来描述三维装箱问题，可以描述为给定N个物品，长宽高分别为LI、WI、HI（1，最后结果为子代802|567|9143子代986|130|5427一点交叉选择一个交叉点,子代在交叉点前面的基因从一个父代基因那里得到,后面的部分从另外一个父代基因那里得到。举例如下交叉前9父代A00000|011100父代B11100|000001交叉后子代00000
7、|000001子代11100|0111003变异算子。以概率PM交换染色体A中元素的顺序，而B中则随机产生一个变异位。323适应度函数设计遗传算法对一个解的好坏使用适应值的大小来评价的，适应值越大，解的质量越好，本文是从以下三方面进行考虑的1）空间利用情况函数。见公式32，其中BVI表示第一个被装载物品的体积，M为所有被装载物品的数量，CVI为第I个租用的集装箱体积，N为租用的集装箱的数量。11MIINIBVCRCVI（32）2）租用成本函数。见公式33，其中COSTI为第I个集装箱的租用费用，N表示租用的集装箱数量。1NIICTCOST（33）3）重心参考函数。见公式34，其中CH表示集装箱
8、高度，BWPI表示第I个物品的重心高度，BWI表示第I个物品的重量，M为装载的物品数量。该函数主要考察物品放置的稳定性和搬运的难易性。1115MIIIMIIBWBWPCHBWCGCH（34）根据惩罚函数和处理目标优化的加权系数法10，定义适应度函数为公式35，K1、K2、K3为权重，满足K1K2K31，CONST为常量，可以根据需求进行选择、改变。此外，当物品不能全部装载时，F直接赋为0。123/FKCRKCONSTCTKCG（35）33程序设计10331算法流程大体介绍基于遗传算法多集装箱装箱问题的算法流程如下1）从文件中读入相关数据木箱箱型个数、每个木箱箱型的尺寸、待装载的木箱个数、待装载
9、的木箱的箱型和重量、集装箱箱型的个数、每个集装箱箱型的尺寸最大载重及租用成本、群体大小、交叉概率、变异概率、遗传代数。2）产生初始群体。3）更新群体，通过交叉、变异产生新的个体和原来的个体组成在一起，计算每个个体的适应值，按适应值从大到小排序，只保留原始群体的个数，舍掉适应值较小的部分，遗传代数加一，当与文件中读入的遗传代数不相等，继续执行3）操作。4）将适应值最优的个体的相关数据输出到文件中，相关数据包括染色体编码、已装载木箱总体积、使用集装箱总体积、空间利用率、已装载木箱总重量、已装载木箱总个数及相应的木箱放置集装箱的编号和放置点的起始位置。332算法关键部分详细说明1）随机产生初始群体。
10、对于每个个体，假设染色体长度为M，先初始化一个集合，包含所有集装箱箱型编号，用数组模拟，产生一个小于M的随机数，从数组中将下标为这个随机数的值保存为TMP并删除，作为染色体第一维A的一部分，记D为物品总体积除以编号为TMP的集装箱体积，再随机随机产生一个小于DE的数K，作为染色体第二维B中的一部分，E视情况而定，通常取小于10即可。如此循环，直到集合为空，也就是数组的元素都删完了。2）轮盘赌算法。在交叉时两个父代通过轮盘赌进行选择，个体的适应值越大，被选择的概率也越大。记FI为第I个个体的适应值，FSUM为所有个体总适应值，SIZE为群体大小。其流程图见图32。11图32轮盘赌算法流程图3）部
11、分匹配交叉算法。记M为染色体的长度，B、E为随机产生的交叉区域，A1、A2数组分别表示两个父代染色体，F1、F2数组为标记数组，M1、M2数组为映射数组，I、P为中间变量，其流程图见图33。图33部分匹配交叉算法流程图124仿真研究41算例自动生成程序借鉴了EEBISCHOFF和MSWRATCLIFF11在论文ISSUESINTHEDEVELOPMENTOFAPPROACHESTOCONTAINERLOADING中提出的测试算例生成方法，其算法流程图见图43，其中AI为木箱尺寸的下界，BI为木箱尺寸的上界。图41算例自动生成算法流程图42测试算例图42是辅材清单模板，作为本文的测试算例。13图
12、42辅材清单模板421层级1到层级2的装载根据图41的信息，总共有19种待装载物品，5种集装箱箱型，待装载物品件数及每件物品的类型和重量都由前面介绍的程序自动生成，共生成了3类物品件数不同的算例，进行物品件数对结果影响的研究。将各参数设定如下，群体规模为200，交叉概率为05，变异概率为001，遗传代数为100，K1为08，K2为01，K3为01，CONST设为100，其对比结果见表41。表41物品件数不同的装载结果对比待装载物品个数空间利用情况租用总成本重心参考函数值运行时间440314845130009162705秒内10705125553150077430315秒内31004446248
13、400075909745秒内分析上表，发现空间利用率普遍不高，原因主要有两个1）物品种类较多，且规格相差较大，导致不能使用的碎片会增多，同时物品尺寸都较大，一旦有剩余空间不能使用，会对空间利用率造成较大影响；2）适应度函数不仅仅只关注空间利用情况，它还要考虑租用总成本的代价及重心参考的约束，导致在装载的过程中可能会选择使空间利用率降低但总体适应值提高的集装箱进行装载。此外，还有其他一些影响因素，如遗传代数、交叉概率等。422层级2到层级3的装载根据图42的信息，总共有5种待装载物品，3种集装箱箱型。用前面介绍的算例自动生成程序生成物品件数为300的算例，进行适应度函数中各权重的研究。将程序中各
14、参数设定如下，群体规模200，交叉概率05，变异概率001，遗传代数100，CONST设为200，其对比结果见表42。表42适应度函数中各权重研究结果对比14算例编号K1K2K3空间利用情况租用总成本重心参考函数值109010095879720805718202050500899231198061891230109008992311980618912401009091828221206428725080020949332214059877660900109537162120573275结合公式35对表42分析如下，根据算例1、2、3对比，在不考虑重心约束的情况下，K1值不变，随着K2的值增大，
15、租用总成本不断变小，下降趋势明显，同时空间利用率也逐渐下降，符合实际理论，因为K2是租用总成本的权重，K1是空间利用率的权重，K2增大，意味着K2与K1的比值也增大，也就是说适应度函数更侧重于租用总成本；再根据算例4、5、6对比，在不考虑租用总成本的情况下，K3值不变，随着K1值增大，空间利用率逐渐增大，上升趋势明显，重心有下降的趋势，但不是那么明显，与实际理论相符，道理同上。所以根据实际需求，当对集装箱的空间利用率更在意时，可提高K1的值；当对租用成本更为关心时，可提高K2的值；当物品放置的稳定性更要紧时，可以提高K3的值。但具体各权重增大多少才有意义，需要多次使用观察结果。155结论与展望
16、51结论本文通过对三维装箱问题及其求解过程进行简要的阐述，在满足一些约束条件的情况下，用C语言实现了从木箱到集装箱的装载算法。该装载算法主要由启发式算法和遗传算法两部分组成。通过对运行结果的分析和总结，本文得出以下几点结论1）启发式算法灵活、自由，方法简单实用，速度较快。2）在遗传算法的过程引进启发式策略往往能起到事半功倍的效果，除了加快收敛速度外，有时能得到更优解。52展望本文利用的启发式算法虽然能在大多数情况下取得较优的结果，但当木箱的尺寸复杂、难以类比时，还是会有较大的可能出现十分坏的候选解。所以，还有待于寻找更普遍化的启发式算法或者其他效率较高的近似算法。另外本文中所解决的三维装箱问题
17、的约束条件十分特殊，如木箱不能旋转且它的宽要对应集装箱的长，所以导致最后找不到可以类比的测试数据，这是本文的一大遗憾。16参考文献1HGEHRING,KMENSCHNER,MMEYERACOMPUTERBASEDHEURISTICFORPACKINGPOOLEDSHIPMENTCONTAINERSEUROPEJOURNALOFOPERATIONALRESEARCH1990,442772882JOHNSON,DSNEAROPTIMALBINPACKINGALGORITHMSTECHNICALREPORT,MACTR1091973,PROJECTMAC,MIT,CAMBRIDGE,MASS3YAN
18、GCHUANMIN,CHENSHAOWEIDISCONTINUOUSOPTIMIZATIONONTHECONTAINERIZATIONOFCUBICPACKAGEENGINEERING,1996,172694MANNCHENKSOLUTIONMETHODSFORTWOANDTHREEDIMENSIONALPACKINGPROBLEMSPHDTHESISKARLSRUHE,GERMANYKARLSRUHEUNIVERSITY,19895GEHRINGHACOMPUTERBASEDHEURISTICFORPACKINGPOOLEDSHIPMENTCONTAINERSEUROPEANJOURNALO
19、FOPERATIONALRESEARCH,1990,4422772886姜义东，查建中，何大勇集装箱装载矩形货物的布局研究J铁道学报，2000，22（6）13187何大勇，查建中，姜义东遗传算法求解复杂集装箱装载问题方法研究J软件学报，2001，12（9）138013858EEBISCHOFF,FJANETZ,MSWRATCLI,LOADINGPALLETSWITHNONIDENTICALITEMS,EUROPEANJOURNALOFOPERATIONALRESEARCH8419956816929刑文训，谢金星现代优化计算方法M北京清华大学出版社，1999，0810江保钏，熊伟清一种求解三维集
20、装箱装箱问题的混合遗传算法J2007,433620022211BISCHOFFEE,RATCLIFFMSISSUESINTHEDEVELOPMENTOFAPPROACHESTOCONTAINERLOADINGOMEGA,1995,23433739017附录一算例自动生成源程序INCLUDEINCLUDEINCLUDEINCLUDESTRUCTXIANGXINGDOUBLEL,W,H/长、宽、高DOUBLEV/体积INTM/个数D20STRUCTMUXIANGINTXIANGXINGDOUBLEGMX2000INTMAINSRANDUNSIGNEDTIMENULLINTN,A4,B4,L,TOT
21、NDOUBLETC,C,TMP,TMINN20/木箱箱型个数A0470A1270A2140A359/木箱尺寸的下界B02280B11480B22200B3120/木箱尺寸的上界L3/尺寸之间的差距上界TC14400540760130/木箱总体积的上界/木箱数据生成18INTI,PFORI0IDIWTMINDIWELSETMINDIHIFDIL/TMINDIWTMINDIWELSETMINDIHIFDIL/TMINLDIVA3RANDB3A31PUTS“PRINTF“集装箱箱型个数DN每个集装箱箱型的尺寸长、宽、高、最大承重N“,NFORI0INIPRINTF“D60LF60LF60LF50LF
22、50LFN“,I,DIL,DIW,DIH,DIV,10RAND10RETURN022附录二表41中的部分算例及输出结果输入木箱箱型个数19每个木箱箱型的尺寸长、宽、高047036016511080540355272554029036902702404270270165572554042067253603857725435560854043518096555403851052052055011520300300125405405701350030030014725360290151440540570161200490760171080360230181080360385木箱个数44木箱所属箱型和
23、重量00333164592168318222341143251451761025371444814504992710950411163612153413121441474291512151615271734771882719522201102174842216442314422404682553512615942723328572293523012643125632184773393513444862435164836622371418738257391057401628418297420187439627集装箱箱型个数5每个集装箱箱型的尺寸长、宽、高、最大承重0219010907101000
24、3001219010901160800035022200145025003601503219010902500300120410801080250024070输出集装箱的装载顺序及个数集装箱的装载顺序及个数1204322100已装载木箱总体积7299015168000000使用集装箱总体积23182913536000000空间利用率0314845租用总成本1300000000重心参考0916270已装载木箱总重量1546699707已装载木箱总个数44THEBOXINDEX20THEBOXIN1THELOCATIONX,Y,ZIS0000000,0000000,000000025THEBOXI
25、NDEX26THEBOXIN1THELOCATIONX,Y,ZIS0000000,0000000,355000000THEBOXINDEX30THEBOXIN1THELOCATIONX,Y,ZIS0000000,540000000,0000000THEBOXINDEX14THEBOXIN1THELOCATIONX,Y,ZIS0000000,540000000,355000000THEBOXINDEX34THEBOXIN1THELOCATIONX,Y,ZIS725000000,540000000,355000000THEBOXINDEX21THEBOXIN1THELOCATIONX,Y,ZIS0
26、000000,1080000000,0000000THEBOXINDEX1THEBOXIN1THELOCATIONX,Y,ZIS0000000,1080000000,560000000THEBOXINDEX13THEBOXIN1THELOCATIONX,Y,ZIS0000000,1515000000,0000000THEBOXINDEX15THEBOXIN1THELOCATIONX,Y,ZIS0000000,1515000000,570000000THEBOXINDEX6THEBOXIN1THELOCATIONX,Y,ZIS540000000,1515000000,0000000THEBOXI
27、NDEX39THEBOXIN1THELOCATIONX,Y,ZIS540000000,1515000000,550000000THEBOXINDEX1926THEBOXIN1THELOCATIONX,Y,ZIS0000000,0000000,0000000THEBOXINDEX25THEBOXIN1THELOCATIONX,Y,ZIS0000000,0000000,420000000THEBOXINDEX28THEBOXIN1THELOCATIONX,Y,ZIS0000000,540000000,0000000THEBOXINDEX9THEBOXIN1THELOCATIONX,Y,ZIS000
28、0000,540000000,420000000THEBOXINDEX3THEBOXIN1THELOCATIONX,Y,ZIS0000000,1080000000,0000000THEBOXINDEX32THEBOXIN1THELOCATIONX,Y,ZIS0000000,1080000000,385000000THEBOXINDEX10THEBOXIN1THELOCATIONX,Y,ZIS0000000,1440000000,0000000THEBOXINDEX33THEBOXIN1THELOCATIONX,Y,ZIS0000000,1440000000,385000000THEBOXIND
29、EX2THEBOXIN2THELOCATIONX,Y,ZIS0000000,0000000,0000000THEBOXINDEX11THEBOXIN2THELOCATIONX,Y,ZIS0000000,490000000,0000000THEBOXINDEX22THEBOXIN227THELOCATIONX,Y,ZIS0000000,980000000,0000000THEBOXINDEX35THEBOXIN2THELOCATIONX,Y,ZIS0000000,1470000000,0000000THEBOXINDEX40THEBOXIN2THELOCATIONX,Y,ZIS0000000,0
30、000000,0000000THEBOXINDEX12THEBOXIN2THELOCATIONX,Y,ZIS0000000,490000000,0000000THEBOXINDEX16THEBOXIN2THELOCATIONX,Y,ZIS0000000,490000000,570000000THEBOXINDEX43THEBOXIN2THELOCATIONX,Y,ZIS0000000,1030000000,0000000THEBOXINDEX4THEBOXIN2THELOCATIONX,Y,ZIS0000000,1030000000,385000000THEBOXINDEX27THEBOXIN
31、2THELOCATIONX,Y,ZIS655000000,1030000000,0000000THEBOXINDEX31THEBOXIN2THELOCATIONX,Y,ZIS0000000,1570000000,0000000THEBOXINDEX38THEBOXIN2THELOCATIONX,Y,ZIS655000000,1030000000,290000000THEBOXINDEX36THEBOXIN2THELOCATIONX,Y,ZIS0000000,1570000000,29000000028THEBOXINDEX37THEBOXIN0THELOCATIONX,Y,ZIS6550000
32、00,1030000000,580000000THEBOXINDEX18THEBOXIN2THELOCATIONX,Y,ZIS725000000,1570000000,0000000THEBOXINDEX7THEBOXIN0THELOCATIONX,Y,ZIS0000000,0000000,0000000THEBOXINDEX8THEBOXIN0THELOCATIONX,Y,ZIS0000000,0000000,290000000THEBOXINDEX23THEBOXIN0THELOCATIONX,Y,ZIS0000000,360000000,0000000THEBOXINDEX37THEBO
33、XIN0THELOCATIONX,Y,ZIS0000000,360000000,290000000THEBOXINDEX17THEBOXIN0THELOCATIONX,Y,ZIS0000000,720000000,0000000THEBOXINDEX29THEBOXIN0THELOCATIONX,Y,ZIS0000000,720000000,240000000THEBOXINDEX41THEBOXIN0THELOCATIONX,Y,ZIS0000000,990000000,0000000THEBOXINDEX0THEBOXIN0THELOCATIONX,Y,ZIS0000000,990000000,180000000THEBOXINDEX2429THEBOXIN0THELOCATIONX,Y,ZIS0000000,990000000,345000000THEBOXINDEX42THEBOXIN0THELOCATIONX,Y,ZIS0000000,990000000,510000000
