1、1毕业设计开题报告计算机科学与技术求解三维装箱问题的遗传算法研究一、选题的背景与意义装箱问题是物流企业在装卸环节上必须面对的一个核心问题，通常其装载的规模达到上千，而且非常频繁。如果能设计出一个有效的装载方案，提高装载的空间利用率，势必会给物流企业带来相当可观的利润。因此，研究出能够有效求解三维装箱问题的遗传算法，对物流企业来说，显得尤为重要。三维装箱问题属于NP问题，传统算法耗时极大不能满足实际应用的需求，所以目前学者都转向启发式搜索算法研究，尤其是遗传算法，但在国内还没有出现在效率和精度上都十分优秀的求解三维装箱问题的遗传算法。通过对国内外现有的求解三维装箱问题的遗传算法的考察，本课题的目
2、的是设计出一种能够满足实际应用需求的求解三维装箱问题的遗传算法，其中，如何进一步提高求解三维装箱问题的遗传算法的求解速度，是本课题需要解决的重点问题之一。二、研究的基本内容与拟解决的主要问题研究的基本内容1完成求解三维装箱问题的遗传算法的设计，包括适应度函数、遗传算子等；2画出求解三维装箱问题的遗传算法的流程图；3按流程图编码、调试；4完成求解三维装箱问题的遗传算法的程序编码、文献综述、外文翻译、等工作。拟解决的主要问题1适应度函数和遗传算子的设计；2提高遗传算法求解速度的方法和途径；3如何提高求解三维装箱问题的遗传算法的精度。2三、研究的方法与技术路线研究方法通过收集和查阅各种文献和资料，学
3、习求解三维装箱问题的遗传算法的原理、方法和应用，掌握目前求解三维装箱问题的遗传算法的研究和应用动态，了解求解三维装箱问题的遗传算法中存在的各种问题。学习和掌握求解三维装箱问题的遗传算法的设计理论和方法，通过比较和分析，提出求解三维装箱问题的遗传算法的设计和改进方案，确定求解三维装箱问题的遗传算法设计过程需要注意的各个方面问题。根据求解三维装箱问题的遗传算法的设计理论和方法，确定求解三维装箱问题的遗传算法的流程图。结合国内外文献，提出改进求解精度的方案，分析装箱的实现效率。最终完成求解三维装箱问题的遗传算法的设计工作。技术路线文献检索和阅读掌握求解三维装箱问题的遗传算法的设计方法求解三维装箱问题
4、的遗传算法的设计求解三维装箱问题的遗传算法的编码求解三维装箱问题的遗传算法的调试与修改撰写使用说明书答辩。四、研究的总体安排与进度第13周（2010112720101219）收集资料，完成文献综述第4周（2010122020101226）完成开题报告，完成开题答辩。第58周（201012272011116）参考国内外文献，设计求解三维装箱问题的遗传算法。第912周（2011021720110313）求解三维装箱问题的初步编码、调试。第1318周（2011031420110424）完成求解三维装箱问题的完整编码，撰写毕业论文。期间还将组织毕业设计的中期检查，执行“毕业设计（论文）中期黄牌警告制度
5、”。第1921周（2011042520110515）毕业设计资料整理，提交完整的毕业设计（论文）资料。第2223周（2011051620110527）毕业设计（论文）答辩准备、答辩、毕业设计成绩评定。五、主要参考文献31钟石泉,王雪莲多箱型三维装箱问题及其优化研究J计算机工程与应用，2009,45（22）1971992周明，孙树栋遗传算法原理及应用M北京国防工业出版社，20003方平,李娟求解装箱问题的遗传算法J南昌航空工业学院学报,1998,2（2）21244王长春，李锐，孙友基于遗传算法的军用集装箱装载优化J物流科技，2007，55HGEHRING,KMENSCHNER,MMEYERACO
6、MPUTERBASEDHEURISTICFORPACKINGPOOLEDSHIPMENTCONTAINERSEUROPEJOURNALOFOPERATIONALRESEARCH1990,442772886JOHNSON,DSNEAROPTIMALBINPACKINGALGORITHMSTECHNICALREPORT,MACTR1091973,PROJECTMAC,MIT,CAMBRIDGE,MASS7YANGCHUANMIN,CHENSHAOWEIDISCONTINUOUSOPTIMIZATIONONTHECONTAINERIZATIONOFCUBICPACKAGEENGINEERING,19
7、96,172698MANNCHENKSOLUTIONMETHODSFORTWOANDTHREEDIMENSIONALPACKINGPROBLEMSPHDTHESISKARLSRUHE,GERMANYKARLSRUHEUNIVERSITY,19899GEHRINGHACOMPUTERBASEDHEURISTICFORPACKINGPOOLEDSHIPMENTCONTAINERSEUROPEANJOURNALOFOPERATIONALRESEARCH,1990,44227728810姜义东，查建中，何大勇集装箱装载矩形货物的布局研究J铁道学报，2000，22（6）131811何大勇，查建中，姜义东
8、遗传算法求解复杂集装箱装载问题方法研究J软件学报，2001,12（9）1380138512EEBISCHOFF,FJANETZ,MSWRATCLI,LOADINGPALLETSWITHNONIDENTICALITEMS,EUROPEANJOURNALOFOPERATIONALRESEARCH8419956816924毕业设计文献综述计算机科学与技术求解三维装箱问题的遗传算法研究摘要对三维装箱问题进行了描述，阐述了研究求解三维装箱问题的遗传算法的意义。接着详细介绍了该算法的实现原理和研究现状，并通过对比和归纳，指出了目前存在的问题。最后在研究现状的基础上，提出了求解三维装箱问题的遗传算法的发展趋
9、势。关键词三维装箱问题；遗传算法；一、研究求解三维装箱问题的遗传算法的意义装箱问题是物流企业在装卸环节上必须面对的一个核心问题，装载方案的好坏将直接影响着企业的利润。因此，研究求解三维装箱问题的遗传算法，实现装箱问题的优化显得尤为重要。三维装箱问题即为物体在三维空间的摆放优化问题，可以描述为长、宽、高分别为LI、WI、HI的N个物体在多个集装箱中摆放，在满足一定的约束重心位置约束、单箱重量约束、单箱空间利用率约束条件下，使集装箱利用率最高1。由于装箱问题是NP问题，传统算法的复杂度会随着摆放物体的数量呈指数级别增加，不能应用到频繁而庞大的装载业务上。于是基于生物自然进化理论具备全局优化搜索能力
10、的遗传算法2被众多学者应用到装箱问题上。如今，管理工程、工业工程等领域中的一些问题例如人力资源分配、运输计划等均可建议为装箱3，所以寻找更准确、更有效的遗传算法是当今装箱问题研究者的心愿。二、求解三维装箱问题的遗传算法的研究现状1遗传算法的实现原理1）个体编码及解码将N个货物按体积从小到大排序并1至N编号，M个箱子1至M编号，物品横放编0，竖放编1，则解21、3、6、80、1、1、0可表示2号箱子中按0、1、1、0方位顺序放置1、3、6、8货物。2）适应度计算通过个体适应值的大小来评估群体中个体所对应装载方案的优劣，对于违反装载容积约束、装载质量约束和装载重心约束的个体，在求解其适应值的过程中
11、要给于相应的惩罚以确5保符合条件而较优的个体有较大的生存机会4。3实现过程选择合适的编码方式，产生初始群，计算初始群体的适应值，如果不满足条件再进行选择、交叉、变异、计算新一代群体的适应值，直到满足条件为止。结束的条件可以根据具体条件来选择，可以以一定的代数为结束条件，也可以以两代之间适应度之差小于某个固定的值为结束条件。2装箱问题的研究现状从20世纪70年代初开始，装箱问题就被广泛地关注和研究5。到80年代末，各种近似求解装箱问题的算法被提了出来，如下次适应、首次适应和调和算法等6。但这些算法都只针对一维、二维装箱问题，因为相比之下三维装箱问题的复杂性大得多，直到80年代后才出现了比较实用的
12、算法杨传民等人7通过全面枚举搜索方法来研究相同大小的立方体的装箱优化问题，使得求解的精度和效率上得到了提高。MANNCHEN8设计的树搜索算法，理论上对三维箱体布局有效，但随着布局箱体的增多，解空间剧增，所以计算效率不能满足实际需求。HGEHRING9提出在深度方向按层布局的启发式算法，提高了空间利用率和重心的平衡度。姜义东10等提出利用遍历三叉树结构的方法对空间进行分解，虽然有效避免了空间干涉现象，但无法处理更复杂的约束。何大勇、查建中等11在简单遗传算法的基础上做了改进，能处理多目标、多约束的问题；但在货物很多时，应用遗传算法对每件货物进行整数编码构成的染色体，基因数量多，规模巨大，再加上
13、众多约束条件，导致算法收敛非常慢，甚至大多数情况下得不到可行解。EEBISCHOFF12等人针对多种物品单托盘装载问题（只考虑空间和稳定性约束），从托盘缺少可用于支撑的垂直壁的特点和由底向上的摆放方式出发，提出了基于“平面”的算法。由底向上每次只放入一层最多由两种物品组成的水平层，迭代填充和生成平面、水平层，获得有效且具有高稳定性的布局模式。算法通过设定的规则选择合适的物品、平面、位置等布局参数，采用平面合并等方法提高平面利用率，进而生成一个较好的完整布局模式。虽然在摆放稳定性方面表现不错，但所得解的空间最优平均利用率不高。3遗传算法的研究现状进入90年代，遗传算法开始变得热门起来，尤其是在应
14、用研究上。随着它的应用领域扩大，利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更6工程化的应用方面。1991年DWHITEY在他的论文中提出了基于领域交叉的交叉算子（ADJACENCYBASEDCROSSOVER），这个算子是特别针对用序号表示基因的个体的交叉，并将其应用到了TSP问题中，通过实验对其进行了验证。DHACKLEY等提出了随即迭代遗传爬山法（STOCHASTICITERATEDGENETICHIL
15、LCLIMBING，SIGH）采用了一种复杂的概率选举机制，此机制中由M个“投票者”来共同决定新个体的值（M表示群体的大小）。实验结果表明，SIGH与单点交叉、均匀交叉的神经遗传算法相比，所测试的六个函数中有四个表现出更好的性能，而且总体来讲，SIGH比现存的许多算法在求解速度方面更有竞争力。2002年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同的遗传策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群间迁移算子来进行遗传信息交流，以解决经典遗传算法的收敛到局部最优值问题。2005年，江雷等针对并行遗传算法求解TSP问题,探讨了使用弹性策略来维持群体的多样性,使得算法跨过
16、局部收敛的障碍,向全局最优解方向进化13。4存在的问题遗传算法的准确性取决于初始解、适应度函数及其遗传算子，目前三维装箱问题的算法都只是在某一程度上逼近最优解，但仍需通过实践挖掘更有效的适应度函数、遗传算子等，此外，求解的过程中都把物品、箱子理想化为长方体以及不考虑一些约束条件，虽然这样降低了求解的复杂度，但与实际不符。三、求解三维装箱问题的遗传算法的发展趋势通过文献阅读和对国内外研究现状的分析和综合，我认为求解三维装箱问题的遗传算法的发展趋势如下1随着装箱模型渗入到各个行业，但行业间约束条件都大不相同，所以装箱软件可以向多元化发展，将来可以对各种可处理的问题进行建模，并接受相应的约束条件输入
17、，然后输出满意的解。2对于这些启发式算法，寻找更有效的参数、函数仍是重中之重。3在电脑运行处理速度变得更快的情况下，可考虑在传统算法与遗传算法之间折中，使得求解更加精确，但又不超出时间的下限。4随着人工智能技术的发展，像神经网络等一些智能学习算法也会在装箱问题有用武之地。四、参考文献1钟石泉,王雪莲多箱型三维装箱问题及其优化研究J计算机工程与应用，2009,745（22）1971992周明，孙树栋遗传算法原理及应用M北京国防工业出版社，20003方平,李娟求解装箱问题的遗传算法J南昌航空工业学院学报,1998,2（2）21244王长春，李锐，孙友基于遗传算法的军用集装箱装载优化J物流科技，20
18、07，55HGEHRING,KMENSCHNER,MMEYERACOMPUTERBASEDHEURISTICFORPACKINGPOOLEDSHIPMENTCONTAINERSEUROPEJOURNALOFOPERATIONALRESEARCH1990,442772886JOHNSON,DSNEAROPTIMALBINPACKINGALGORITHMSTECHNICALREPORT,MACTR1091973,PROJECTMAC,MIT,CAMBRIDGE,MASS7YANGCHUANMIN,CHENSHAOWEIDISCONTINUOUSOPTIMIZATIONONTHECONTAINERI
19、ZATIONOFCUBICPACKAGEENGINEERING,1996,172698MANNCHENKSOLUTIONMETHODSFORTWOANDTHREEDIMENSIONALPACKINGPROBLEMSPHDTHESISKARLSRUHE,GERMANYKARLSRUHEUNIVERSITY,19899GEHRINGHACOMPUTERBASEDHEURISTICFORPACKINGPOOLEDSHIPMENTCONTAINERSEUROPEANJOURNALOFOPERATIONALRESEARCH,1990,44227728810姜义东，查建中，何大勇集装箱装载矩形货物的布局研
20、究J铁道学报，2000，22（6）131811何大勇，查建中，姜义东遗传算法求解复杂集装箱装载问题方法研究J软件学报，2001,12（9）1380138512EEBISCHOFF,FJANETZ,MSWRATCLI,LOADINGPALLETSWITHNONIDENTICALITEMS,EUROPEANJOURNALOFOPERATIONALRESEARCH84199568169213HTTP/BAIKEBAIDUCOM/VIEW/45853HTM58本科毕业设计（20届）求解三维装箱问题的遗传算法研究9摘要【摘要】三维装箱问题是合理地选择需要租用的集装箱并将给定数量的木箱全部装进租用的集装箱
21、中。木箱的装载方案和集装箱的选择方案都会对集装箱的空间利用率及租用的总成本产生很大的影响，所以如何在两方面进行有效的优化，是目前装箱问题上最需关注的话题。本文先对装箱问题及目前的研究现状进行了阐述，然后提出了单箱装箱问题的启发式算法，接着在此基础上，提出了多集装箱装箱问题的遗传算法，最后通过实例证明了该方法能得出该问题的较优解。【关键词】三维装箱问题；启发式算法；遗传算法。ABSTRACT【ABSTRACT】THREEDIMENSIONALPACKINGPROBLEMISAREASONABLECHOICEOFCONTAINERFORSTUFFINGAGIVENNUMBEROFBOXESWOOD
22、ENBOXESLOADINGPROGRAMSANDTHEOPTIONSOFTHECONTAINERWILLHAVEAHUGEEFFECTONTHESPACEUTILIZATIONOFCONTAINERANDTHETOTALCOSTOFRENTINGSOHOWTOMAKEANEFFECTIVEOPTIMIZATIONONTHETWOASPECTSISTHEKEYPROBLEMNOWTHEARTICLEFOCUSESONPACKINGPROBLEMSANDCURRENTRESEARCHARESURVEYEDINDETAILASINGLEBOXPACKINGHEURISTICALGORITHMAND
23、AGENETICALGORITHMONMULTICONTAINERLOADINGPROBLEMWEREPROPOSEDTHESIMULATIONRESULTSSHOWTHATTHEPROPOSEDALGORITHMSCANOBTAINTHEOPTIMUMSOLUTIONOFTHEPROBLEM【KEYWORDS】THREEDIMENSIONALPACKINGPROBLEM；HEURISTIC；GENETICALGORITHM。10目录摘要9ABSTRACT9目录101绪论111装箱问题112现有装箱问题的解决方法113课题研究内容22面向单箱装箱问题的启发式算法321单箱装箱要求322算法思想
24、3221放置点介绍3222放置点的合并4223启发式算法423程序设计43基于遗传算法多集装箱装箱问题531遗传算法5311遗传算法的过程5312遗传算法的特点6313遗传算法的组成要素632求解多集装箱装箱问题的遗传算法设计8321编码设计8322遗传算子的设计8323适应度函数设计933程序设计9331算法流程大体介绍10332算法关键部分详细说明104仿真研究1241算例自动生成程序1242测试算例12421层级1到层级2的装载13422层级2到层级3的装载135结论与展望1551结论1552展望15参考文献16致谢错误未定义书签。附录一算例自动生成源程序1711附录二表41中的部分算例
25、及输出结果2211绪论11装箱问题装箱问题通常指的是装载给定箱子集合的一个子集到容器中，使得被装载的箱子总体积最大。根据维数的不同，可分为一维装箱问题、二维装箱问题、三维装箱问题三种。一维装箱问题比较简单，已经没有研究的必要了，二维装箱问题目前虽然没有高效精确的算法，但很多学者都提出了比较高效的近似算法，也逐渐淡出了研究的邻域，而与现实生活密切相关的是三维装箱问题，许多物流公司都渴望拥有一个比较有效的三维装箱软件，来降低实际装载运输的成本，而三维装箱问题是一个多约束条件下的组合优化问题，虽然一些学者提出了比较高效的近似算法，但都是基于某些约束条件的，所以仍然有必要研究特殊约束条件下的高效的三维
26、装箱算法和更加通用的三维装箱算法。用数学方式来描述三维装箱问题，可以描述为给定N个物品，长宽高分别为LI、WI、HI（1，最后结果为子代802|567|9143子代986|130|5427一点交叉选择一个交叉点,子代在交叉点前面的基因从一个父代基因那里得到,后面的部分从另外一个父代基因那里得到。举例如下交叉前9父代A00000|011100父代B11100|000001交叉后子代00000|000001子代11100|0111003变异算子。以概率PM交换染色体A中元素的顺序，而B中则随机产生一个变异位。323适应度函数设计遗传算法对一个解的好坏使用适应值的大小来评价的，适应值越大，解的质量越
27、好，本文是从以下三方面进行考虑的1）空间利用情况函数。见公式32，其中BVI表示第一个被装载物品的体积，M为所有被装载物品的数量，CVI为第I个租用的集装箱体积，N为租用的集装箱的数量。11MIINIBVCRCVI（32）2）租用成本函数。见公式33，其中COSTI为第I个集装箱的租用费用，N表示租用的集装箱数量。1NIICTCOST（33）3）重心参考函数。见公式34，其中CH表示集装箱高度，BWPI表示第I个物品的重心高度，BWI表示第I个物品的重量，M为装载的物品数量。该函数主要考察物品放置的稳定性和搬运的难易性。1115MIIIMIIBWBWPCHBWCGCH（34）根据惩罚函数和处理
28、目标优化的加权系数法10，定义适应度函数为公式35，K1、K2、K3为权重，满足K1K2K31，CONST为常量，可以根据需求进行选择、改变。此外，当物品不能全部装载时，F直接赋为0。123/FKCRKCONSTCTKCG（35）33程序设计10331算法流程大体介绍基于遗传算法多集装箱装箱问题的算法流程如下1）从文件中读入相关数据木箱箱型个数、每个木箱箱型的尺寸、待装载的木箱个数、待装载的木箱的箱型和重量、集装箱箱型的个数、每个集装箱箱型的尺寸最大载重及租用成本、群体大小、交叉概率、变异概率、遗传代数。2）产生初始群体。3）更新群体，通过交叉、变异产生新的个体和原来的个体组成在一起，计算每个
29、个体的适应值，按适应值从大到小排序，只保留原始群体的个数，舍掉适应值较小的部分，遗传代数加一，当与文件中读入的遗传代数不相等，继续执行3）操作。4）将适应值最优的个体的相关数据输出到文件中，相关数据包括染色体编码、已装载木箱总体积、使用集装箱总体积、空间利用率、已装载木箱总重量、已装载木箱总个数及相应的木箱放置集装箱的编号和放置点的起始位置。332算法关键部分详细说明1）随机产生初始群体。对于每个个体，假设染色体长度为M，先初始化一个集合，包含所有集装箱箱型编号，用数组模拟，产生一个小于M的随机数，从数组中将下标为这个随机数的值保存为TMP并删除，作为染色体第一维A的一部分，记D为物品总体积除
30、以编号为TMP的集装箱体积，再随机随机产生一个小于DE的数K，作为染色体第二维B中的一部分，E视情况而定，通常取小于10即可。如此循环，直到集合为空，也就是数组的元素都删完了。2）轮盘赌算法。在交叉时两个父代通过轮盘赌进行选择，个体的适应值越大，被选择的概率也越大。记FI为第I个个体的适应值，FSUM为所有个体总适应值，SIZE为群体大小。其流程图见图32。11图32轮盘赌算法流程图3）部分匹配交叉算法。记M为染色体的长度，B、E为随机产生的交叉区域，A1、A2数组分别表示两个父代染色体，F1、F2数组为标记数组，M1、M2数组为映射数组，I、P为中间变量，其流程图见图33。图33部分匹配交叉
31、算法流程图124仿真研究41算例自动生成程序借鉴了EEBISCHOFF和MSWRATCLIFF11在论文ISSUESINTHEDEVELOPMENTOFAPPROACHESTOCONTAINERLOADING中提出的测试算例生成方法，其算法流程图见图43，其中AI为木箱尺寸的下界，BI为木箱尺寸的上界。图41算例自动生成算法流程图42测试算例图42是辅材清单模板，作为本文的测试算例。13图42辅材清单模板421层级1到层级2的装载根据图41的信息，总共有19种待装载物品，5种集装箱箱型，待装载物品件数及每件物品的类型和重量都由前面介绍的程序自动生成，共生成了3类物品件数不同的算例，进行物品件数
32、对结果影响的研究。将各参数设定如下，群体规模为200，交叉概率为05，变异概率为001，遗传代数为100，K1为08，K2为01，K3为01，CONST设为100，其对比结果见表41。表41物品件数不同的装载结果对比待装载物品个数空间利用情况租用总成本重心参考函数值运行时间440314845130009162705秒内10705125553150077430315秒内31004446248400075909745秒内分析上表，发现空间利用率普遍不高，原因主要有两个1）物品种类较多，且规格相差较大，导致不能使用的碎片会增多，同时物品尺寸都较大，一旦有剩余空间不能使用，会对空间利用率造成较大影响；
33、2）适应度函数不仅仅只关注空间利用情况，它还要考虑租用总成本的代价及重心参考的约束，导致在装载的过程中可能会选择使空间利用率降低但总体适应值提高的集装箱进行装载。此外，还有其他一些影响因素，如遗传代数、交叉概率等。422层级2到层级3的装载根据图42的信息，总共有5种待装载物品，3种集装箱箱型。用前面介绍的算例自动生成程序生成物品件数为300的算例，进行适应度函数中各权重的研究。将程序中各参数设定如下，群体规模200，交叉概率05，变异概率001，遗传代数100，CONST设为200，其对比结果见表42。表42适应度函数中各权重研究结果对比14算例编号K1K2K3空间利用情况租用总成本重心参考
34、函数值109010095879720805718202050500899231198061891230109008992311980618912401009091828221206428725080020949332214059877660900109537162120573275结合公式35对表42分析如下，根据算例1、2、3对比，在不考虑重心约束的情况下，K1值不变，随着K2的值增大，租用总成本不断变小，下降趋势明显，同时空间利用率也逐渐下降，符合实际理论，因为K2是租用总成本的权重，K1是空间利用率的权重，K2增大，意味着K2与K1的比值也增大，也就是说适应度函数更侧重于租用总成本；再根
35、据算例4、5、6对比，在不考虑租用总成本的情况下，K3值不变，随着K1值增大，空间利用率逐渐增大，上升趋势明显，重心有下降的趋势，但不是那么明显，与实际理论相符，道理同上。所以根据实际需求，当对集装箱的空间利用率更在意时，可提高K1的值；当对租用成本更为关心时，可提高K2的值；当物品放置的稳定性更要紧时，可以提高K3的值。但具体各权重增大多少才有意义，需要多次使用观察结果。155结论与展望51结论本文通过对三维装箱问题及其求解过程进行简要的阐述，在满足一些约束条件的情况下，用C语言实现了从木箱到集装箱的装载算法。该装载算法主要由启发式算法和遗传算法两部分组成。通过对运行结果的分析和总结，本文得
36、出以下几点结论1）启发式算法灵活、自由，方法简单实用，速度较快。2）在遗传算法的过程引进启发式策略往往能起到事半功倍的效果，除了加快收敛速度外，有时能得到更优解。52展望本文利用的启发式算法虽然能在大多数情况下取得较优的结果，但当木箱的尺寸复杂、难以类比时，还是会有较大的可能出现十分坏的候选解。所以，还有待于寻找更普遍化的启发式算法或者其他效率较高的近似算法。另外本文中所解决的三维装箱问题的约束条件十分特殊，如木箱不能旋转且它的宽要对应集装箱的长，所以导致最后找不到可以类比的测试数据，这是本文的一大遗憾。16参考文献1HGEHRING,KMENSCHNER,MMEYERACOMPUTERBAS
37、EDHEURISTICFORPACKINGPOOLEDSHIPMENTCONTAINERSEUROPEJOURNALOFOPERATIONALRESEARCH1990,442772882JOHNSON,DSNEAROPTIMALBINPACKINGALGORITHMSTECHNICALREPORT,MACTR1091973,PROJECTMAC,MIT,CAMBRIDGE,MASS3YANGCHUANMIN,CHENSHAOWEIDISCONTINUOUSOPTIMIZATIONONTHECONTAINERIZATIONOFCUBICPACKAGEENGINEERING,1996,172694
38、MANNCHENKSOLUTIONMETHODSFORTWOANDTHREEDIMENSIONALPACKINGPROBLEMSPHDTHESISKARLSRUHE,GERMANYKARLSRUHEUNIVERSITY,19895GEHRINGHACOMPUTERBASEDHEURISTICFORPACKINGPOOLEDSHIPMENTCONTAINERSEUROPEANJOURNALOFOPERATIONALRESEARCH,1990,4422772886姜义东，查建中，何大勇集装箱装载矩形货物的布局研究J铁道学报，2000，22（6）13187何大勇，查建中，姜义东遗传算法求解复杂集装箱
39、装载问题方法研究J软件学报，2001，12（9）138013858EEBISCHOFF,FJANETZ,MSWRATCLI,LOADINGPALLETSWITHNONIDENTICALITEMS,EUROPEANJOURNALOFOPERATIONALRESEARCH8419956816929刑文训，谢金星现代优化计算方法M北京清华大学出版社，1999，0810江保钏，熊伟清一种求解三维集装箱装箱问题的混合遗传算法J2007,433620022211BISCHOFFEE,RATCLIFFMSISSUESINTHEDEVELOPMENTOFAPPROACHESTOCONTAINERLOADING
40、OMEGA,1995,23433739017附录一算例自动生成源程序INCLUDEINCLUDEINCLUDEINCLUDESTRUCTXIANGXINGDOUBLEL,W,H/长、宽、高DOUBLEV/体积INTM/个数D20STRUCTMUXIANGINTXIANGXINGDOUBLEGMX2000INTMAINSRANDUNSIGNEDTIMENULLINTN,A4,B4,L,TOTNDOUBLETC,C,TMP,TMINN20/木箱箱型个数A0470A1270A2140A359/木箱尺寸的下界B02280B11480B22200B3120/木箱尺寸的上界L3/尺寸之间的差距上界TC14
41、400540760130/木箱总体积的上界/木箱数据生成18INTI,PFORI0IDIWTMINDIWELSETMINDIHIFDIL/TMINDIWTMINDIWELSETMINDIHIFDIL/TMINLDIVA3RANDB3A31PUTS“PRINTF“集装箱箱型个数DN每个集装箱箱型的尺寸长、宽、高、最大承重N“,NFORI0INIPRINTF“D60LF60LF60LF50LF50LFN“,I,DIL,DIW,DIH,DIV,10RAND10RETURN022附录二表41中的部分算例及输出结果输入木箱箱型个数19每个木箱箱型的尺寸长、宽、高047036016511080540355
42、272554029036902702404270270165572554042067253603857725435560854043518096555403851052052055011520300300125405405701350030030014725360290151440540570161200490760171080360230181080360385木箱个数44木箱所属箱型和重量003331645921683182223411432514517610253714448145049927109504111636121534131214414742915121516152717347
43、71882719522201102174842216442314422404682553512615942723328572293523012643125632184773393513444862435164836622371418738257391057401628418297420187439627集装箱箱型个数5每个集装箱箱型的尺寸长、宽、高、最大承重02190109071010003001219010901160800035022200145025003601503219010902500300120410801080250024070输出集装箱的装载顺序及个数集装箱的装载顺序及个数1
44、204322100已装载木箱总体积7299015168000000使用集装箱总体积23182913536000000空间利用率0314845租用总成本1300000000重心参考0916270已装载木箱总重量1546699707已装载木箱总个数44THEBOXINDEX20THEBOXIN1THELOCATIONX,Y,ZIS0000000,0000000,000000025THEBOXINDEX26THEBOXIN1THELOCATIONX,Y,ZIS0000000,0000000,355000000THEBOXINDEX30THEBOXIN1THELOCATIONX,Y,ZIS000000
45、0,540000000,0000000THEBOXINDEX14THEBOXIN1THELOCATIONX,Y,ZIS0000000,540000000,355000000THEBOXINDEX34THEBOXIN1THELOCATIONX,Y,ZIS725000000,540000000,355000000THEBOXINDEX21THEBOXIN1THELOCATIONX,Y,ZIS0000000,1080000000,0000000THEBOXINDEX1THEBOXIN1THELOCATIONX,Y,ZIS0000000,1080000000,560000000THEBOXINDEX1
46、3THEBOXIN1THELOCATIONX,Y,ZIS0000000,1515000000,0000000THEBOXINDEX15THEBOXIN1THELOCATIONX,Y,ZIS0000000,1515000000,570000000THEBOXINDEX6THEBOXIN1THELOCATIONX,Y,ZIS540000000,1515000000,0000000THEBOXINDEX39THEBOXIN1THELOCATIONX,Y,ZIS540000000,1515000000,550000000THEBOXINDEX1926THEBOXIN1THELOCATIONX,Y,ZI
47、S0000000,0000000,0000000THEBOXINDEX25THEBOXIN1THELOCATIONX,Y,ZIS0000000,0000000,420000000THEBOXINDEX28THEBOXIN1THELOCATIONX,Y,ZIS0000000,540000000,0000000THEBOXINDEX9THEBOXIN1THELOCATIONX,Y,ZIS0000000,540000000,420000000THEBOXINDEX3THEBOXIN1THELOCATIONX,Y,ZIS0000000,1080000000,0000000THEBOXINDEX32TH
48、EBOXIN1THELOCATIONX,Y,ZIS0000000,1080000000,385000000THEBOXINDEX10THEBOXIN1THELOCATIONX,Y,ZIS0000000,1440000000,0000000THEBOXINDEX33THEBOXIN1THELOCATIONX,Y,ZIS0000000,1440000000,385000000THEBOXINDEX2THEBOXIN2THELOCATIONX,Y,ZIS0000000,0000000,0000000THEBOXINDEX11THEBOXIN2THELOCATIONX,Y,ZIS0000000,490
49、000000,0000000THEBOXINDEX22THEBOXIN227THELOCATIONX,Y,ZIS0000000,980000000,0000000THEBOXINDEX35THEBOXIN2THELOCATIONX,Y,ZIS0000000,1470000000,0000000THEBOXINDEX40THEBOXIN2THELOCATIONX,Y,ZIS0000000,0000000,0000000THEBOXINDEX12THEBOXIN2THELOCATIONX,Y,ZIS0000000,490000000,0000000THEBOXINDEX16THEBOXIN2THELOCATIONX,Y,ZIS0000000,490000000,570000000THEBOXINDEX43THEBOXIN2THELOCATIONX,Y,ZIS0000000,1030000000,0000000THEBOXINDEX4THEBOXIN2THELOCATIONX,Y,ZIS0000000,1030000000,385000000THEBOXINDEX27THEBOXIN2THELOCATIONX,Y,ZIS655000000,1030000000,00
