摘 要

装箱配载优化问题普遍存在于我们的生活当中，在物流配送、工业制造、计算机技术等多方面都有着广泛的应用。三维装箱优化问题在物流配送中的应用领域主要有集装箱配载、货运轮渡船舱配载、货车车厢装载、列车车厢装载等方面，这类优化问题求解过程也较为复杂。求解三维装箱优化问题的结果对物流配送活动有着直接而深刻的影响，物流成本、配送效率等都要受到装箱效果的制约。随着物流业的迅速发展壮大，学者们在装箱优化问题领域中的研究也日益深入。然而，目前装箱算法都有其局限性，性能都不够理想，还有提高改进的空间。因此，三维装箱优化问题的还有很大的研究空间，设计出快速有效的算法不仅是重要的理论研究问题，更具有重要的现实应用意义，为物流配送领域的发展解决障碍。

本文以三维装箱优化问题为研究对象，以提高装箱空间利用率和载重利用率为研究目标。文中首先了解归纳了研究背景和国内外研究现状，在此前人的研究基础上提出了本文的研究内容及研究方法，阐述了装箱问题和算法研究的内容，以此为理论基础而提出混合遗传模拟退火算法的思路。然后分析了装箱问题的约束条件并对相关约束条件进行数值处理，构建了三维装箱优化的数学模型，分析混合遗传模拟退火算法的实现步骤。最后利用MATLAB软件编写代码并利用前人文献中的数据信息进行了运算，验证了算法的可行性与有效性。

本文对计算结果进行了多方面的分析，结果表明本文设计的算法能有效提高容器的空间利用率和载重利用率。并且根据结果提出了本研究的不足之处以及有待改进提高的方面，由此对未来后续研究的进展方向提出了展望。

关键词：三维装箱优化 遗传算法 模拟退火算法 MATLAB

Abstract

Container loading optimization problem is pervasive in our daily life, widely applied in logistic distribution, industrial manufacturing, computer technology and many other. Application of three dimensional container loading problems in logistic distribution are mainly in container cargo, freight-run ferry cabin stowage, carriage loading, railcar loading,and this kind of optimization problem solution process is more complicated. Results for optimization of three dimensional packing problem has a direct and profound impact on logistic distribution activities, while logistic costs and efficiency of distribution are subject to packing effects of restricting. With the rapid development of the logistics industry, scholars research container loading optimization problem in more depth.However,algorithms in container loading at present have their limitation and their performance is not satisfying,badly possible for improvement. Therefore, there is spacious space for reaserch of optimization of three dimensional bin packing problem ,and designing a fast and effective algorithm is not only a important theory research issues but also is of great practical significance, sweeping logistic development obstacles.

This thesis is based on the study of optimization of three dimensional packing problems to improve the packing space utilization and loadweight utilization research objectives. This thesis ,first of all, summarizes the background of research and situation in home and abroad,put up with this reserch and its methods on the basis of previous studies, and describe the contents of bin packing problems and related algorithms, as a result of which theory of mixed genetic- simulated annealing algorithm is proposed on the basis of these ideas. Then analyzed the constraints of bin packing problem and process them numerically, building mathematical model for optimization of three dimensional loaidng and analyzing implementation steps of mixed genetic-simulated annealing algorithm.Finally, write code by MATLAB and run it with the data of previous literature to verify the feasibility and effectiveness of this algorithm.

Conducted a number of analyses on the operation results in this paper, the results show that this algorithm can improve the packing space utilization and loadweight utilization. And according to the results presented in this study, shortcomings as well as where to be improved is discussed, and prospect for future research is brought forward.

Key Words: three-dimensional bin packing utiliazetion; genetic algoritms; simulated annealing algorithm; MATLAB

目录

第1章 绪论 1

1.1 研究背景及意义 1

1.2 研究现状 1

1.3 本文架构 2

第2章 装箱问题的研究分析 4

2.1 装箱问题概述 4

2.2 算法概述 4

2.2.1 遗传算法 5

2.2.2 模拟退火算法 6

2.2.3 混合算法设计思路 6

2.3 本章小结 7

第3章 算法的设计 8

3.1 问题描述 8

3.2 问题假设 8

3.3 模型的建立 8

3.3.1变量表 8

3.3.2 装箱约束条件 9

3.3.3 约束条件的数值处理 9

3.3.4 目标函数的建立 11

3.3.5 装箱策略 12

3.4 遗传算法的设计 12

3.4.1 适应度函数 12

3.4.2 染色体编码 12

3.4.3 选择算子 14

3.4.4 交叉算子 14

3.4.5 变异算子 15

3.5 混合算法的设计 15

3.6 本章小结 17

第4章 算法的实现 19

4.1 算法工具 19

4.1.1 子函数的设计 20

4.1.2 算法的实现流程 20

4.2 程序运行 21

4.2.1 参数设置 21

4.2.2 程序运行 21

4.3 结果分析 24

4.4 经济性分析 25

4.5 本章小结 25

第5章 结论 26

5.1全文总结 26

5.2研究展望 26

参考文献 27

附录 29

致谢 32

第1章 绪论

1.1 研究背景及意义

由于市场经济和社会需求的不断发展扩大，物流行业得到了越来越多的关注，与物流相关的技术也有了更多应用和发展。如何降低物流成本以及提高物流效率，成为了一个重要而迫切的实际问题^[1]。

集装箱作为现代化运输工具，它的普遍使用大幅度提高了货物流通速度并优化了资源配置效率，使现代物流行业快速发展并进入一个全新的时代。装箱优化问题的应用背景很广泛^[2]。作为物流活动中的关键一环，装箱效果的优劣对提高装卸搬运的自动化水平、货物配载的优化程度以及运输配送的工作效率和规范业务流程起着十分重要的作用^[1][3]。而在实际操作中，装箱问题的应用则必须考虑各种限制约束条件，比如货物的稳定性、货物的装载顺序、容器的承载能力以及装卸货物的方便性等等^[4][5][6]。

为了找到能快速有效地实现全局最优化的算法，到目前为止，国内外大量学者对装箱优化问题进行了广泛探讨和深刻研究。然而在面对复杂的实际约束条件时，现有解决办法依然有待于改进，为此学者们也在努力研究期望能得到更好的方案。因此，研究装箱优化问题在提高物流水平方面有着积极的实践意义和重要的理论价值^[4]。

本课题基于实际的货物装载过程，结合实际情况给出一种高效的装箱优化方案，使空间利用率和载重利用率达到最佳。