集装箱单箱混合装载优化.docx

文档介绍：集装箱单箱混合装载优化方法研究
学 院

工业自动化学院
专 业：
姓 名：
指导老师：
工业工程
蔡浩铨
学 号：
职 ch in order to attain the goals of optimizing loading layouts,changing freight modes and enhancing production efficiency.
Keywords: Bin-packing problem；Knapsack problem；Partical Swarm Optimization； Binary Tree theory of remaining space；Bottom-up left-justified algorithm


北京理工大学珠海学院2020届本科生毕业论文
目录
1 概述 1
1
2
2
2 原理及材料 3
BL算法简介 3
7
7
8
13
3 数学建模与MATLAB实现 16
16
A公司的货运装箱模式 17
19
： 19
： 23
24
25
4 算法测试 26
26
26
31
34
五、总结与展望 38
参考文献 40
致谢 42
附录 43
北京理工大学珠海学院2020届本科生毕业论文
1
1 概述

装箱问题是广泛存在与生产生活中的一类空间布局优化问题。它要求把若干个不可分割的物件放入容积相同的箱子当中，并要求使用的箱子数目最少。其子问题单箱问题（又称容器装在问题three-dimensional container-packing problems，3D-CPP）是指只使用一个箱子，通过对装载方法的设计使得装入物件的数目最大。
装箱问题是离散问题的复杂组合。解决问题的关键在于优化组合需要找到既满足约束又满足有限、离散的完整数学框架的适应度函数（目标函数）的最优解。组合优化问题由于大量局部最值点的存在，通常无法将其定义为一个可微、连续的问题。因而相对准确的说法是一个混合非线性，受多维约束局限的NP完全问题。对于NP完全问题的描述，同样适用于遍历问题、图像分割等多组合最优化问题上。
能否在有效时间内实施精确求解因为组合爆炸的缘故所以在NP完全问题上答案是否定的。目前学界所作的工作一般是针对优化算法去逼近求解以降低求解的难度，这就意味着装箱算法利用的都是近似算法。通过压缩搜索得到最优近似解以逼近最优解。
装箱问题根据约束的数目可分为一维装箱问题，二维装箱问题，三维装箱问题，多维装箱问题等。针对实际工作场景的不同，一维装箱问题只考虑体积这一约束；二维装箱问题这是考虑到布局当中的长和宽两个约束。而日常生产生活当中涉及最广的，也是研究结论相比之下较为贫乏的三维装箱问题。在二维装箱的基础上增加高度约束使得三维装箱问题的求解难度陡然上升****惯上学界一般把三维装箱问题分为以下三种：
(three-dimensional bin packing problem，3D-BPP)：已知数量类型不等的矩形箱子和给定统一规格的容器无限，最终选定方法，使得全部箱子得以装载同时被开启的容器最少；
(three-dimensional container-packing problems，3D-CPP)：要求在一个尺寸不限的容器当中将全部物品要装入，比对得出一个装填方法，使用的容器体积为最小，即是为最优。其变形就是单箱问题所描述的，只使用一个箱子，通过对装载方法的设计使得装入物件的数目最大；
(three-dimensional knapsack loading problems，3D-
北京理工大学珠海学院2020届本科生毕业论文
3
KLP)：给待装填的每个物件赋于价值，挑选其中部分装填并令装入容器中的箱子选择方案是总价值最大方案。在容积的约束之上增加了价值约束。
历经数十年的研究，三维