基于遗传算法的多箱型三维装箱问题的研究

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

1、基于遗传算法的多箱型三维装箱问题的研究AGeneticAlgorithmforThree-DimensionalMultipleBin-SizeBinPackingProblems工程领域：软件工程作者姓名：白益维指导教师：路文焕企业导师：李国翚天津大学软件学院二零一七年十二月独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研宄工作和取得的研宄成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人己经发表或撰写过的研宂成果，也不包含为获得天津大学或其他教育机构的学位或证书而使用过的材料

2、一。与我同工作的同志对本研宂所做的任何贡献均己在论文中作了明确的说明并表示了谢意。学位论文作者签名：签字日期：＞７年卜月日）学位论文版权使用授权书本学位论文作者完全了解天津大学有关保留、使用学位论文的规定。特授权天津大学可以将学位论文的全部或部分内容编入有关数抿库讲行拾索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。（保密的学位论文在解密后适用本授权说明）学位论文作者签名：导师签名：丄矽＾：日签字日期签字日期

3、年１〇月７：年〇月日＾摘要装箱问题是典型的NP问题，在物流运输行业中最为常见。为了提高货物配载方案的生成效率，为人工配载提供理论支撑，联系工程应用实际，本文通过数学方法对多箱型三维装箱问题进行了描述，提出了求解该问题的算法。本文算法的核心是遗传算法，采用自然数编码，表示货物的摆放序列和摆放方式；自然选择算子采用精英与灾变混合机制；交叉算子采取以偏随机秘钥为基础的新机制，有效加快收敛速度。变异算子采用单点变异。为了能够准确评估个体，本文设计了一个基于空间的启发式装箱算法，根据摆放序列和摆放方式模拟装箱。考虑熵约束

4、、重心约束等条件，设计了合理的适应值函数，评估个体的适应值。最后，借鉴禁忌搜索的路径重连思想，实现多箱型混合装箱的目的。代码实现方面采用多线程，保证算法的响应速度。本文实现了完整的配载方案生成网站，并提供三维的可视化结果展示。以某物流公司的历史装箱清单为测试数据，给出了实验结果并进行了分析，证明了本文算法在一定意义上的有效性以及网站的可用性。关键词：装箱问题，遗传算法，偏随机秘钥，启发式算法，路径重连IABSTRACTPackingproblemisatypicalNP-Hardproblemandcommonly

5、metinthelogisticsindustry.Toimprovetheefficiencyofgeneratingacargostowageplanandprovidetheoreticalsupportforloading,wedescribethemultibin-sizebinpackingprobleminmathandproposeafeasiblealgorithmbasedontheengineeringapplication.Ouralgorithm’scoreisakindofgenetic

6、algorithm.TheGAusesnaturalnumbercodingwhichindicatestheorderofgoodsandthewaythatgoodsplaced.Thestrategyacceptedbyselectionoperatoriscombingeliteandcatastrophe.Crossoveroperator’smechanismisbasedonbiasedrandomkeyGA’s,whichacceleratesconvergenceeffectively.Mutat

7、ionoperatoradoptssingle-pointmutation.Toevaluateanindividual,wedesignaheuristicpackingmethodbasedonspacestrategyandthemethod’sinputisGA’scoding.Consideringtherestraintofcenterofgravityandentropy,weproposeanappropriatefitnessfunction.Finally,aPathRelinkingproce

8、dureinthecontextofTabuSearchisintroducedintoouralgorithmtoobtainabettersolutionwhichusesmulti-sizebins.Weusemulti-threadprogramingtoimplementouralgorithm,ensuringtheruntime.Inaddit