集装箱单箱混合装载优化方法研究
摘
装箱问题非确定性项式完全问题（Nondeterministic Polynomial Complete Problem：NP）目前已广泛应日常生产生活中作涉体积重量布局等复杂目标约束问题求解程中存量局部极值点干扰目前该问题相关优化算法满意行解具体优化方法包括数值优化方法(Optimal Algorithms)构造法（Construction Algorithms）智优化算法等
文A公司例分析目前现货运特点采典背包模型建模分析利粒子群算法进行模型求解时分析A公司装箱装载模式简化特殊二维装箱问题建立数学模型结合装箱货物特点采结合剩余空间理二叉树思想粒子群优化BL算法运MATLAB进行模型求解优化装载布局更新货运模式提高生产效率
关键词：装箱问题背包问题粒子群算法剩余空间二叉树理佳适应算法
Abstract
Binpacking problem a complete NP problemis widely used in daily production and life As a complex multiobjective multiconstraint problem involving volume weight and layout with a large number ofinterferences by local extreme point in the solution process which can only be approximated At present the method mainly used for solving the packing problem can only rely on solving the nonNP problem to obtain an approximate optimal solution close to the optimal solution The main representatives are numerical optimization methods (optimal algorithms) construction algorithms (including NF approximation algorithms BF approximation algorithms etc) intelligent optimization algorithms represented by PSO GA etc This article uses Company A as an example to analyze its current freight operations and container loading modes Using the PSO (Partical Swarm Optimization)and the Bottomup leftjustified algorithm that combines the theory of remaining space and binary tree theory Limited to a special packing problem combined with the knapsack problem mathematical models are established for research in order to attain the goals of optimizing loading layoutschanging freight modes and enhancing production efficiency
Keywords Binpacking problemKnapsack problemPartical Swarm Optimization Binary Tree theory of remaining spaceBottomup leftjustified algorithm
目录
1 概述 1
11装箱问题概述 1
12装箱问题发展史 2
13研究目意义 2
2 原理材料 3
21 BL算法简介 3
22二叉树法剩余空间理 7
221二叉树法 7
222剩余空间理 8
223装箱序优化方法 13
3 数学建模MATLAB实现 16
31装箱问题数学建模 16
311 A公司货运装箱模式 17
32MATLAB实现 19
321BL算法思路： 19
322二叉树设计思路： 23
323PSO算法思路 24
33货运模式优化思路MATLAB实现 25
4 算法测试 26
41混合优化方法测试 26
411混合优化方法实例测试 26
412混合算法实际应 31
42计算速度分析 34
五总结展 38
参考文献 40
致谢 42
附录 43
1 概述
11装箱问题概述
装箱问题广泛存生产生活中类空间布局优化问题求干分割物件放入容积相箱子中求箱子数目少子问题单箱问题（称容器装问题threedimensional containerpacking problems3DCPP）指箱子通装载方法设计装入物件数目
装箱问题离散问题复杂组合解决问题关键优化组合需找满足约束满足限离散完整数学框架适应度函数（目标函数）优解组合优化问题量局部值点存通常法定义微连续问题相准确说法混合非线性受维约束局限NP完全问题NP完全问题描述样适遍历问题图分割等组合优化问题
否效时间实施精确求解组合爆炸缘NP完全问题答案否定目前学界作工作般针优化算法逼求解降低求解难度意味着装箱算法利似算法通压缩搜索优似解逼优解
装箱问题根约束数目分维装箱问题二维装箱问题三维装箱问题维装箱问题等针实际工作场景维装箱问题考虑体积约束二维装箱问题考虑布局中长宽两约束日常生产生活中涉广研究结相较贫乏三维装箱问题二维装箱基础增加高度约束三维装箱问题求解难度陡然升惯学界般三维装箱问题分三种：
1货柜装载问题(threedimensional bin packing problem3DBPP)：已知数量类型等矩形箱子定统规格容器限终选定方法全部箱子装载时开启容器少
2容器限定装载问题(threedimensional containerpacking problems3DCPP)：求尺寸限容器中全部物品装入出装填方法容器体积优变形单箱问题描述箱子通装载方法设计装入物件数目
3背包装填问题(threedimensional knapsack loading problems3DKLP)：装填物件赋价值挑选中部分装填令装入容器中箱子选择方案总价值方案容积约束增加价值约束
历数十年研究三维装箱问题解决较明确思路方目前较通行解法分两部分部分负责布局放置启发式算法部分利现代智算法优解搜索逼目前存高度约束求较弱三维装箱降维二维装箱算法思路
12装箱问题发展史
装箱问题研究开始普遍认距两百年前1831年高斯(Gauss)开始做研究布局问题工作20世纪70年代初物流运输业加速发展相关装箱问题引起学界广泛探讨研究[1] 发展时日已形成较固定通行思路般算法混合应布局放置早国外George等利层墙堆砌法[2]取较成果基础Gehring提出塔堆砌理念提出遗传算法运中[3]时Pisinger树搜索布置布局提供新思路[4]较流便国张德富彭煜朱文兴陈火旺等取力发展基块理念填充方法[5]黄文奇Zhang等递式启发式算法研究应[6]优解逼GehringBortfeldt利混合遗传算法Bortfeldt尝试利禁忌搜索算法运筹学中动态规划常分支定界法[7]续种适应算法应Moura等Reactive GRASP算法[8]算法探索未停止Hopper分BLBLF启发式布局算法GA等启发式搜索混合算法进行求解[9]目前言较通效果较张德富教授等提出混合模拟退火算法布局利块堆栈放置方案编码作装载序列利模拟退火算法出似优解
13研究目意义
装箱问题作类空间布局优化问题广泛存日常工业生产生活方方面面例二维装箱问题源服装材料印刷行业排料板材型材切割面料裁剪三维装箱运输行业典型集装箱装载应现实生活中材料包装包装分类
计算机科学处理器底层操作程例处理器资源务分配存调度理安排址文件等装箱问题研究成果提供实际效
长久装箱问题研究中运筹理CADCAM图形学工智等诸方面领域许新突破发展装箱问题产生思路方法学科结合开拓新发展空间关集装箱重性学界句话说：全球化新技术世界抹前集装箱已形力量世界连接起物流俗潜力量挖掘效益视作第三利润源收录日学者西修著作中观类历史发展进程离开两领域开发提供巨额利润：第原材料资源领域第二力资源相关研究成果已述两领域潜力挖掘殆利润开拓愈发困难相第三利润源常常忽视物流GDP贡献分低估目前丰京东物流领域取优异成绩越越公司开始意识第三利润源重性作第三利润源缺重环集装箱装箱问题潜力巨值深入研究
2 原理材料
21 BL算法简介
BL法（bottomup leftjustified）装箱问题中种常见似装载算法BL算法前提整装箱程中物品允许斜放然开始装箱
物品A进入箱子B序：（1）A紧挨箱子B右角落直移动物件（物件边者箱子B底边）相切直A移动止（2）左移动A物件（物件边者箱子B左边）相切直 A左移动止（3）重复（1）（2）直物品A位置固定移动
面应实例说明BL算法步骤假设箱子边长10米正方形箱子放物品尺寸矩形计8件具体尺寸表21示：
表21 物品尺寸
物品名称
长度（单位：米）
宽度（单位：米）
1
5
1
2
5
3
3
2
2
4
5
3
5
3
1
6
6
5
7
7
3
8
5
4
根输出结果终完成十物品装箱箱子两现中箱子248号物品装载程简说明装载程：
首先物品2紧容器右壁落继续移动左移动直移动图21 2物件装载程：
图21 2物件装载程
然4号物品放入先假定4号物件横放方式装箱方法具体流程见图22 4物件装箱程
图22 4物件装箱程
箱子8样序装入终新开启箱子装箱完成效果见图23 248装箱程
图23 248装箱程
剩余装货物1356763571序装入
图24 剩余货品装箱示：
图24 剩余货品装箱
述实例发现BL算法然较高效实现物件装箱程箱体存量空白空间未空白空间相继续装箱图23中见便样尺寸体积物品2物品4装载方横竖摆放位置集装箱堆砌利会效果外装箱结果稳定性方面足BL算法常常诟病某装载结果例图25示橙色块明显存重心位置偏离形心继导致稳定性足易造成货品运输程中损耗
图25 装载位置
22二叉树法剩余空间理
221二叉树法
计算机科学中广泛存n叉树应现行少关二维装箱设计研究采二叉树结构般利二叉树法装箱较理想结果图（见图26 理想二叉树装载图）：
图26 理想二叉树装载图
首先容器部紧左壁放入物体固定该物体位置生成坐标物体根节点剩余空白区域划分两子空间物体接着装箱利算法两子树空间进行搜索寻找容纳物体空白区域装入生成节点两子树（子空间）直循环递直容器空间填满者剩余空白区域法容纳件物品止底面填满底面布局断增高直高度约束者重量约束中满足便终止算法输出结果装箱完成
具体通方法实现图27示：
图27 子树产生图
图出子树空间根已放物品节点进划分针新物品装箱通常情况毗邻前物品装箱形式装入装载方式消耗剩余面积相空间前提紧挨着装箱箱物品重心集中前普通BL算法相拥相较稳定性
典二叉树算法取较成果前提统计装入货品分取均宽度高度根验取sqrt系数分相结果正方形普适性实际装箱问题言高时查阅相关文献时发现二叉树理更适已知装载物件数目体积寻找箱子容器容纳全部物件求容器体积问题次设计涉装箱问题原节点生成二叉树更生成新空白空间容纳装载物件非优先考虑剩余空白空间通常二叉树结合较紧密FF算法次设计BL算法显然合适剩余空间理补充完善显必次设计汲取二叉树算法思想应剩余空间划分中
222剩余空间理
剩余空间理前装箱算法优化程重理成果研究关装箱空间分割装箱位置选择通装载剩余空间划分生成新装箱子问题递穷直空间法容纳新箱子视装箱完成质思想点接二叉树划分
装箱空间分割法指箱子放入空间剩余空间划分更子空间方法通常见装箱问题进行观察难发现子空间划分数装箱问题维数相二维装箱问题中剩余空间划分数2引学界通说法视S2空间S3右空间划分方法图28 二维剩余空间划分法示：
图28 二维剩余空间划分法
图见剩余空间面积相S2S3容纳物品类型完全
方法：S1水方分割剩余空间两子空间显然容纳更细长物件
方法二：根S1竖直方分割剩余空间两子空间适合装载较方正物件剩余面积相情况划分方式集装箱利效率着重影响
三维空间划分少研究三维装箱问题视带高度约束二维装箱问题延伸实际划分时候二维装箱问题两分割方分割出子空间高度约束存样两切割方（二维装箱问题前提规定斜着放置）三分割子空间样切割目剩余空间较块整体形式存提高装箱利率时保证货物货物保证装箱稳定性三维约束引二维装箱样例子容器放入S1划分方法图29 三维剩余空间划分法示：
图29 三维剩余空间划分法
方法：S1水方分割剩余空间三子空间学界称空间S1右空间S2前空间S3观察发现子空间S1S2较方正空间S2高度S1容纳等底面积更长高物件S3狭长空间适合装载宽度高度较物件
方法二：S1竖直方分割剩余空间三子空间样空间S1右空间S2前空间S3观察发现次子空间S1S2较狭长空间S2高度S1容纳等底面积更宽高物件S3方正空间适合装载长度宽度较物件
三维装箱问题剩余空间理剩余体积相情况集装箱利效率划分方式息息相关
适宜装载物件：
结合剩余空间理重心更集中认集装箱尺寸长远长宽时候面积相前提：
优先放置物件中面积较（利减少剩余空间）长宽差较物件吻合剩余空间采集装箱长宽差时优先放置类型较方正物件面编写完成适应度函数较部分需考量质量部分该部分PSO粒子群算法完成高度约束较弱前提次设计三维降带高度约束二维结合BL算法装填模式出装填思路：
1容器中蓝色物件放入节点剩余空白划分生成两子树空间12（图210 次装箱图示）：
2
图210 次装箱图示
2利粒子群算法搜索子树空间12剩余物件面积长宽作较较出适宜装载物件黄色物件放入较放入剩余空间更子空间放入中然黄色物件节点划分剩余空白区域生成两子树空间1’2’（图211 二次装箱图示）
2’
1’
图211 二次装箱图示
’
3利粒子群算法搜索子树空间1’2’剩余物件面积长宽作较较出适宜装载物件绿色物件放入较放入剩余空间更子空间放入中然绿色物件节点剩余空白区域生成两子树空间1’’2’’（图212 三次装箱图示）
’
2’’’
1’’
图212 三次装箱图示
循环递穷直剩余子空间法容纳剩余件物品法继续填充止理想装填效果图214 完整理想装箱图示：
图214 完整理想装箱图示
总结思路次装载次装箱节点生成两子空间生成两新装箱子问题第二货物装入时继续分割成前右三空间粒子群算法检索尺寸匹配剩余空间物件装入递循环确定货物全部装载完毕者剩余空间已法装载货物时PSO检索方案中装载面积剩余面积方案该方案似优解生成方案底面布置直叠加高度直等汽车荷重者超出集装箱高度限制混合装箱方法
保证装载效果前提该算法思路保证右角固定物件前提量提高物件摆放稳定性剩余空间利率
223装箱序优化方法
文选择粒子群算法实现装箱序优化粒子群优化美国社会心理学家James Kennedy电气工程师Russell1995年提出种优化算法针解决问题解粒子群中具粒子代表性应通单粒子简单动作组信息交互实现快速反应智解决粒子群算法具备原理编程简单收敛速度快收敛效果等优点广泛应工程功优化函数处理建筑理测量等许领域
粒子群算法建模原理种类：
粒子群优化算法源鸟群猎食方式原理组鸟群已知中该组中鸟知道身前位置食物距离相区域中机搜索食物知找寻象实施效方法策略搜索距离鸟类周围前食物区域
进行优化粒子群算法时鸟类均视粒子两者应解决优化问题解潜藏区域粒子中定约束适应度函数中粒子赋予优化函数决定适应度值值提社会性原鸟类族群中意味着粒子具备决定飞行方距离速度
根适应度高粒子（佳粒子）指引算法求余粒子佳解空间中搜索
粒子群算法会定解空间中机初始化粒子群通目标问题函数变量数解确定扩展空间维数旦确定粒子初始速度位置会根适应度反复迭代找佳解次迭代中粒子会通路径首先单粒子体循环中搜索单体优粒子视作体极值然回种群中种群中粒子迭代群体优粒子全局极值提取群体中部分利作单体邻居粒子体极值全局极值时处邻居粒子中极值称局部极值两者取样容量差衍生出两种方法处理差异前者称全局粒子群针种群中粒子外便算法提取局部粒子群
前粒子群优化算法类言分基标准粒子群优化算法压缩种群容量压缩粒子群算法采离散粒子离散粒子群算法值提粒子学性重视算法中变异环节显尤重变异环节非必少约束数目维数均高时候简化变异流程步骤：
算法重环节参数设置第步需算法迭代次数粒子飞行速度问题变量数目标函数进行设置信息定位整空间赋予初始位置速度机值进行搜索时飞行速度定数获修正般公式：设初始化位置初始化飞翔速度分XV：VX*(VmaxVmin)+Vmin
假设目前目标搜索空间D维中群落N粒子组成第i粒子表示D维量：
第i粒子飞行速度D维量记作：
第i粒子迄止搜索优位置称体极值记：
整粒子群迄止搜索优位置全局极值记：
搜索两优值时候迭代规律更新速度位置：
公式（21）
中：C1C2称加速常数获社会性学力子二者区C1针象粒子获体学力C2赋予粒子社会学力般想较解C1C2取值常数通常设置惯通常取C1C22取值范围[01]范围r1r2均均匀机数vij粒子速度（i12D）
Vmax户定义目作限制粒子速度常数增加粒子飞行机性求解范围更广准度更高需取两介01间机数r1r2速度方程设置通常需包含三部分
首先反映粒子运动惯惯性动量部分代表粒子维持身先前运动趋势般作第部分紧接着粒子需反映身搜索路径回忆记录次迭代寻优佳位置认知部分建立迫粒子序运动体历史优位置迫粒子获寻优求解趋势社会部分针全局求解避免陷入局部优早收敛单体粒子需协合作互相知优位置路径粒子获量验会出现群聚极值历史验值逼趋势
述粒子实质优化问题PSO中解代表处搜索空间中鸟优化函数会赋予粒子通约束函数确定适应度值时扩充矩阵中粒子具确定飞行方距离速度解空间中粒子会前佳粒子进行搜索求解优解迭代开始前会先机组粒子（机解）初始化PSO粒子通次迭代中踪体社会分极值更新身搜寻路径首体优解xBest称体极限极限前样容量扩充整总体搜寻发现总极限（群体极限）gBest两者中进行外邻居粒子选择跳庞杂烦冗总体样位置定位佳粒子周围较出邻居粒子极值似视全局极值
般粒子群算法流程图215 粒子群算法流程图示：
图215 粒子群算法流程图
次设计通PSO检索子空间中适应度函数高方案遍历递完毕输出方案视优解
3 数学建模MATLAB实现
31装箱问题数学建模
设定长方体集装箱C长宽高分LWH容积VVL*W*H
底面积SSL*W侧面积S’S’W*H前面积S’’S’’K*H集装箱极限荷重Q
设装物品集合B｛B1B2Bn｝中第i物品Bi应长宽高分LiWiHi
装载程中已装载体积BVi通公式（1）计算：
BViBiϵBLi∗Wi∗Hii12…n#1
公式（1）空间利率CV表示公式（2）：
CVi1nBViV∗100#2
二维装箱已装载面积BSi（包含SS’S’’）：
(3)
二维装箱面积利率CS：
CSi1nBSiS∗100#4
重量适应度函数公式（5）表示：
CQ (5)
装载货物重量超集装箱荷重Q法继续装载重量适应度函数等0出适应度函数：
三维装箱：
Fxk1CV+k2CQ#6
二维装箱：
Fxk1CS+k2CQ#7
中k1 k2加权系数根公司实际情况选
311 A公司货运装箱模式
着国国民济发展钢板生产量逐渐增长资料显示作钢材四类中重组成部份钢板产量占国钢材生产总量半
A公司家集钢材制造批发零售型公司营板型弹簧丝等钢材品种中钢板营业务公司总业务60％涉钢材直接相关中包括普通碳素钢优质碳素钢合金结构钢工具钢锈钢弹簧钢等钢板种宽厚表面积扁材料填充时具特殊特性根厚度钢板分薄板厚板两类型类钢板密度计算方便里取8gcm3
利冷轧者热轧等常见加工技术制成薄钢板具024mm厚度5001400mm宽度钢板薄钢板应范围广泛根途薄钢板轧制成材料钢坯应机械汽车工业航空航天工业外酸洗镀锌镀锡等流程薄钢板搪瓷工业电气工业等行业处见身影公司A轧制直接提供薄钢板业务环节
厚度等4毫米钢板总称厚钢板没较精确描述定义实际工作中厂家惯细分出中板指厚度20毫米钢板厚度20毫米60毫米钢板称厚板时应特殊领域特厚板指厚度超60毫米钢板类钢板必须特殊厚板轧制机中进行轧制便获数值较厚度厚钢板宽度较统般06mm30mm通常根途般常汽车钢板复合钢板厚钢板分类分桥梁造船工程钢板锅炉高压容器钢板等等
市面通汽车弹簧钢板原料钢板裁剪切割常标准集装箱40＇GP运载送货
目前A公司营钢带种类进行调查分类编号出十种钢材畅销钢板装箱频繁分进行编号表表3111（取薄钢板厚度4mm厚钢板密度8mm）
表31
名称
长（mm）
宽（mm）
薄钢板1#
5000
1000
薄钢板2#
2000
1000
薄钢板3#
2000
1000
薄钢板4#
3000
1000
厚钢板1#
5000
3000
厚钢板2#
5000
2000
厚钢板3#
3000
3000
厚钢板4#
2000
2000
厚钢板5#
3000
3000
厚钢板6#
7000
2000
定常普通箱40＇GP
尺寸（长x宽x高）12032mm×2352mm×2393mm
载重28吨
设定长方体集装箱C长宽高分L102mW235mH24m
设箱子C容积VVL*W*H57528m³
底面积SSL*W102*2352397㎡
侧面积S’S’W*H235*24564㎡
前面积S’’S’’L*H102*242448㎡
集装箱极限荷重QQ28t
薄钢板1号2号3号4号
厚钢板1号2号3号4号5号6号
构成装箱物品集合B元素分编号转换单位物品尺寸表32
表32
编号（元素名称）
元素尺寸（长宽） (单位：米)
1
(51)
2
(53)
3
(22)
4
(21)
5
(21)
6
(52)
7
(31)
8
(33)
9
(52)
10
(72)
货物批发零售A公司需矿场采购类矿石原料炼制钢板种矿石原料质量体积相带济收益高低矿石装箱满足体积重量限制前提实现效益化目前A公司亟提高货运装箱模式
32MATLAB实现
混合算法思路：
原始布局空间集装箱空载状态视空载状态二叉树根节点视次迭代剩余空间行域粒子群算法遍历选择集合B中检索尺寸匹配剩余空间物体装入装箱程步骤中利算法物品包装箱中位置降距离左移动距离进行计算第步位置确定继续左走行直法移动视装箱完毕结合A公司货运特点减少约束数目简化实验步骤降低难度高度约束较弱三维装箱简化二维装箱摆放方式造成利率差异交剩余空间计算较选择放入物体BiBi集合B中剩余空间二叉树划分S2S3两独立子空间次S2S3作前布局空间（装载）诉步骤继续分解直集合B空集者剩余空间法容纳集合B中意元素装箱完毕
321BL算法思路：
知道矩形四条边密闭构成四条邻边相互垂直边相互行判断箱子装载程中否重叠首先箱子矩形分解四条线段四坐标矩形长宽已知情况需知道右角坐标便矩形四条边四点表示出
妨设矩形长L宽W右角坐标（xy）
四顶点分左角（xLy）左角（xLyW）右角坐标已知右角坐标（xyw）里选择右角坐标基准（xy）BL算法特性箱子停容器左边边逼右角坐标置容器空间部旦右角座标超出容器范围视载文判物品间否出现相交问题里暂略边描述般采两顶点坐标格式[leftxleftyrightxrighty]利方法矩形分左右四条边图31 矩形坐标分解示：
图31 矩形坐标分解
判断装箱程中矩形否继续移动箱子间否会重合导致装箱失败前提判断矩形边否移动中相交发现两矩形条边相交两矩形必定相交首先需设计判函数判断两条直线移动否会相交果相交相交距离少
BL算法装箱右角开始放入然竖直降继续降便左移动直继续左移动便竖直降重复循环直位置固定算法第步需判定箱子否继续降第二步骤判定箱子否继续左移
里参考传统BL算法制定编码思路传统BL算法整体步骤分三部分：1判否会相交2计算物品低端边坐标3计算降距离针三部分首先需矩形分解干线段矩形间相交重叠情况利线段间相交重叠情况进行判断需明确装箱程中矩形线段会出现状况：
1水直线判：
直线相交分5种情况：
1）左方相交2）左方相交3）右方相交4）右方相交5）line1完全包含line2（line2完全包含line1）
根文分析利四坐标表示装箱矩形拆分四条线段条线段需两坐标表示
妨分解水线段坐标设：[leftxleftyrightxrighty]通设置指针判断线段间否存相交情况果存相交情况通坐标计算两条直线竖直距离
五种情况进行简分析：
情况1左方相交时line1完全line2左方时竖直距离两坐标差两条线段竖直移动会相交
情况2line2line1右方第种情况两条线段竖直移动会相交
情况3line2line1左方线段存重合移存相交性
情况4line1完全line2右方线段作竖直移动会出现相交情况
情况5line2完全line1包含1左右端横坐标均2左右端横坐标12相交会出现竖直方移动
2竖直直线判：
竖直线段位置关系样分5种情况：
1）方相交2）方相交3）方相交4）方相交5）line1完全包含line2（line2完全包含line1）
样利四坐标矩形定位分解成线段条线段需两坐标表示
妨分解竖直线段坐标设：[topxtopybottomxbottomy]利flag值判断否存相交情况时果线段相交输出水距离
样五种情况进行简分析：
第种情况line1完全line2方两条线段移会相交
第二种情况line2line1方时移会重合
第三种情况line1line2方两条线段移会相交
第四种情况line2完全line1方移法相交
第五种情况line1完全包含line2
目前止竖直水线段移动相交状况判移动距离计算矩形箱子完整描诉需顶点坐标降距离左移距离
3顶点坐标：
获矩形四顶点坐标需获中点坐标矩形长宽水方：
利顶点坐标标注增加定物品长度L宽度W作条件BL算法特性决定需定位点物品左角顶点坐标步降距离作铺垫单独拎出左右两端点坐标表示端水线
竖直方：
根物品右角顶点坐标利物品长度L宽度W需利求出物品左端竖直线段两端坐标[topxtopybottomxbottomy]
BL算法特性物品左端竖直线段两端进行定位先求物品左角顶点坐标求出物品左角顶点坐标时结合水方降距离求出竖直方左移距离做铺垫
4移动距离：
降距离：
汇总述坐标移动距离需数组储存较装载已装载物品间坐标长宽落距离
获取完目前箱子中物品坐标通Y坐标进行降序排列目前顶层物品端线段坐标通集装箱径做减法分次装载完成物品剩余降高度降高度应满足等剩余降高度约束果出现目前降（装载）高度剩余高度应转判右边剩余空间否满足述相交条件判断否放置容器右侧
BL算法右角开始装入果相交条件满足算法会直接物品降容器底端
满足相交条件时选择箱子降高度中值
补充句箱子时空装入物品样会降底端
5左移距离：
思路利线段判条件指针表示相交情况找flag指相交路径样降序较出输出竖直线段彼距离
利定位物品左端竖直线段两端坐标BL算法特性右角坐标X坐标降序排列求降序排列右角坐标整合次重新降序排列X坐标通集装箱径做减法分次装载完成物品剩余左移长度左移距离应满足等剩余左移距离约束果出现目前左移（装载）距离剩余长度应转判方剩余空间否满足述相交条件判断否放置容器方判中满足相交条件直接移动容器左端
满足相交条件时选择箱子左移距离中值
完成入箱装载货物降左移算法需右角坐标前文中提需通右角坐标记录时货物位置通位置目前排列序列
物品箱子中右方落左方移动进行定位输出坐标目前装箱序列进行判断通左角顶点坐标辨否存重合现象果序列排布重合视装箱失败重新循环判断
MATLAB程序详见附录
322二叉树设计思路：
二叉树结合剩余空间理目前集装箱剩余面积装状态进行安排调度BL算法排布前提断剩余空间划分迭代出子空间直物品装载完毕者容器穷止Parents应两children两子树
提取二叉树编程思路：
首先应该明确前提二叉树循环终止条件：
1） 容器中剩余体积0
2） 遍历装载箱子适应度函数值满足剩余空间
3） 装载箱子标记已装载状态
终止条件满足装箱继续时候：箱子放入空间中搜索适应空间输出适应度值找适合放置箱子BL算法定位直位置固定右角坐标itemRP妨设（xy）剩余空间划分时已装载箱子视节点二叉树生成两剩余空间S2S3左右子树剩余空间分作约束空间面积二维空间剩余面积划分中存两划分方法应面积表示方法相妨简单表示形式：
建立左子树（剩余空间S2）
S2X*(WY)者S2L*(WY)
建立右子树（剩余空间S3）
S3(LX)*W 者S3(LX)*(WY)
已装载箱子需装箱子集合中编号获新装箱子集合子集更新子空间LW坐标数组重复述程直满足终止条件中跳出循环完成装箱方案
MATLAB程序详见附录
323PSO算法思路
二叉树剩余空间BF算法解决放置找出适应度函数函数优解里采PSO算法
首先输入定量：
种群初始化模块初始化粒子群种群A集装箱装载品类复杂加快收敛速度选Dim10
适应度值适应度函数求出表示模块计算粒子群体适应度值降维二维装箱取二维装箱适应度函数公式（42）
利公式粒子模块进行更新定适应度函数分求xbestgbest表示粒子适应度值更新单佳粒子组佳粒子
粒子机组（机解）初始化PSO佳解通搜索断迭代时粒子通踪体极值群体极值次循环中断更新身位置 单极值xBest粒子身公式迭代学找粒子体优解相应极值整前总体找优解全局极值（组极值）gBest样全部种群外压缩样容量仅利部分佳粒子邻居粒子空间中进行搜索邻居极值出极值似全局极值
时次设计采简单PSO算法考虑变异前提速度更新迭代公式公式21：
（21）
接需数组储存迭代数致需定义装箱方案应装箱方案重量数组存储粒子极值数组等
限制函数二维装箱适应度函数公式42
值提粒子群算法中常常涉许常量参数中W惯性子C1作加速子时粒子赋予体学子C2作社会学子粒子获社会学力C1C2取常数时较解般设置 惯通常取C1C22实验次调试情况发现C1C215w08情况取效果佳
MATLAB程序详见附录
33货运模式优化思路MATLAB实现
里货运模式针A公司矿场采购类矿石原料炼制钢板种矿石原料质量体积相带济收益高低里需方法矿石装箱满足体积重量限制前提实现效益化丰富补充A公司货运装箱模式
问题分类结背包算法提取数学模型已知容量G背包求物品装载价值排列组合需面装载象n重量W1—Wn应价值V1— Vn物品满足背包容量约束前提包总价值
针体积价值三维装箱问题（背包问题）里然采PSO算法背包问题进行数学建模定n体积aj应价值分cj物品箱子总容量b求价值箱子集合子集
MATLAB程序详见附录
4 算法测试
41混合优化方法测试
411混合优化方法实例测试
文提边长10正方形箱子7矩形物品物品长度宽度表示进行混合优化方法测试
表41
物品名称
长度（米）
宽度（米 ）
1
5
1
2
5
3
3
2
2
4
5
3
5
3
1
6
6
5
7
7
3
8
5
4
原普通BL算法输出方案图24 剩余货品装箱示：
图24 剩余货品装箱
通混合装箱算法输出方案图41 优化算法装箱示：
图41 优化算法装箱
通普通BL算法算法中装载物品13567采混合装载方法样集装箱装载物品135678剩余空间利效率提高20
接利MATLAB通生成机物品测试次设计混合算法实际应效算法进行50次模拟出数记录
详细见表42：
表42
实验序号
物品尺寸（长宽）
文算法箱体利率
文方法装载编码
BL法箱体利率
BL法装置编码
1
(43)(44)(44)(52)(24)(43)(25)(15)(42)(34)
823
1234569
68
1247810
2
(53)(51)(11)(55)(14)(42)(33)(14)(22)(24)
895
12345678910
65
134689
10
3
(53)(54)(43)(25)(54)(15)(32)(34)(52)(54)
951
23456789
92
124689
10
4
(52)(53)(25)(44)(24)(25)(34)(54)(13)(51)
884
1234567910
862
235678910
5
(22)(53)(45)(41)(21)(35)(35)(54)(12)(21)
791
1245678910
72
1234567910
6
(43)(25)(15)(42)(34)(43)(44)(44)(52)(24)
843
1234569
801
2346910
7
(25)(15)(42)(34)(52)(54)(34)(52)(54)(34)
754
3456789
736
123578
10
8
(55)(51)(33)(53)(24)(33)(41)(14)(24)(22)
667
12345689
702
123456789
9
(42)(34)(35)(51)(11)(55)(41)(33)(24)(22)
894
12357910
82
123468910
10
(42)(33)(14)(12)(24)(22)(54)(44)(41)(55)
784
1234569
743
234567
11
(53)(45)(41)(21)(35)(12)(35)(54)(11)(22)
877
2345678910
82
13467910
12
(35)(54)(12)(54)(34)(15)(22)(54)(42)(34)
851
1234567910
832
13567910
13
(11)(55)(14)(33)(41)(22)(42)(53)(54)(43)
832
134567810
828
24567810
14
(25)(45)(15)(32)(43)(52)(54)(21)(41)(22)
724
14568910
732
2348910
15
(14)(12)(24)(32)(22)(42)(24)(12)(13)(11)
963
12345678910
963
12345678910
16
(54)(12)(54)(35)(25)(44)(24)(52)(33)(44)
839
123456710
81
245678910
17
(43)(25)(15)(54)(42)(41)(21)(35)(32)(13)
767
1245689
733
123567910
18
(12)(53)(14)(12)(24)(32)(54)(54)(41)(11)
948
23456789
976
123456789
19
(45)(53)(34)(32)(11)(21)(51)(45)(31)(12)
887
1234567910
784
234567910
20
(35)(54)(11)(22)(15)(54)(42)(15)(35)(32)
791
1245678910
707
123478910
21
(32)(31)(15)(54)(42)(51)(41)(21)(45)(33)
854
1234678910
798
235678910
22
(31)(51)(22)(45)(51)(32)(41)(33)(21)(52)
982
12345678910
982
12345678910
23
(24)(12)(13)(15)(45)(14)(12)(21)(35)(45)
967
12345678910
967
12345678910
24
(34)(42)(41)(11)(22)(31)(52)(55)(42)(53)
919
1234568910
92
1234568910
25
(55)(25)(45)(33)(53)(34)(32)(31)(14)(12)
943
1234678910
843
23456789
26
(53)(51)(11)(55)(14)(42)(33)(14)(22)(24)
956
12345678910
956
12345678910
27
(53)(54)(43)(25)(54)(15)(32)(34)(52)(54)
945
23456789
927
123567810
28
(52)(53)(25)(44)(24)(25)(34)(54)(13)(51)
872
1234567910
761
1367910
29
(22)(53)(45)(41)(21)(35)(35)(54)(12)(21)
791
1245678910
756
245678910
30
(43)(25)(15)(42)(34)(43)(44)(44)(52)(24)
85
1234589
85
1234579
31
(25)(15)(42)(34)(52)(54)(34)(52)(54)(34)
755
3456789
689
1234567
32
(55)(51)(33)(53)(24)(33)(41)(14)(24)(22)
669
12345689
67
12345689
33
(42)(34)(35)(51)(11)(55)(41)(33)(24)(22)
898
12357910
90
12357910
34
(42)(33)(14)(12)(24)(22)(55)(44)(41)(55)
779
1234569
764
1235678
35
(53)(45)(41)(21)(35)(12)(35)(54)(11)(22)
894
2345678910
846
1345678910
36
(35)(54)(12)(54)(34)(15)(22)(54)(42)(34)
852
1234567910
799
123458910
37
(11)(55)(14)(33)(41)(22)(42)(53)(54)(43)
816
134567810
761
1235689
38
(25)(45)(15)(32)(43)(52)(54)(21)(41)(22)
728
14568910
714
12345789
39
(14)(12)(24)(32)(22)(42)(24)(12)(13)(51)
972
12345678910
95
123456789
40
(54)(12)(54)(35)(25)(44)(24)(52)(43)(44)
847
123456710
787
12345678
41
(43)(25)(15)(54)(42)(41)(21)(35)(32)(23)
762
1245689
753
1235678
42
(12)(53)(14)(12)(24)(32)(54)(54)(41)(11)
98
2345678910
97
23456789
43
(24)(12)(13)(15)(45)(14)(12)(21)(35)(45)
100
12345678910
100
12345678910
44
(34)(42)(41)(11)(22)(31)(52)(55)(42)(53)
921
1234568910
90
1234567910
45
(55)(25)(45)(33)(53)(34)(32)(31)(14)(22)
936
1234678910
936
12345678910
46
(53)(51)(11)(55)(14)(42)(33)(14)(22)(24)
972
12345678910
972
12345678910
47
(53)(54)(43)(25)(54)(15)(32)(34)(52)(54)
954
23456789
915
13456789
48
(52)(53)(25)(44)(24)(25)(34)(54)(13)(51)
897
1234567910
847
123456710
49
(22)(53)(45)(41)(21)(35)(35)(54)(12)(21)
778
1245678910
758
12456789
50
(43)(25)(15)(42)(34)(43)(44)(44)(52)(24)
835
1234569
824
1234579
通50次输出数进行记录整理出均箱体利率8672相目前普通BL算法827左右利率少提高（见图42 装载效率分析图 ）通折线图知优化算法装载效率曲线致原始算法基达次设计求
图42 装载效率分析图
412混合算法实际应
A公司目前产品引例：
取常普通箱40＇GP尺寸12032mm(长)x2352mm(宽)x2393mm(高)载重28吨
设定长方体集装箱C长宽高分L102mW235mH24m
设箱子C容积VVL*W*H57528m³
底面积SSL*W102*2352397㎡
侧面积S’S’W*H235*24564㎡
前面积S’’S’’L*H102*242448㎡
集装箱极限荷重QQ28t
薄钢板1#薄钢板2#薄钢板3#薄钢板4#
厚钢板1#厚钢板2#厚钢板3#厚钢板4#厚钢板5#厚钢板6#构成装箱物品集合B元素分编号转换单位物品尺寸表4110
表43
编号（元素名称）
（长宽）（LiWi）
1
(51)
2
(53)
3
(22)
4
(21)
5
(21)
6
(52)
7
(31)
8
(33)
9
(52)
10
(72)
批次设置两辆货车运载：
目前A公司采取面积降序装载方式终方案图43 现行装载图示：
图43 现行装载图
装载货物36910剩1245789需换种型号集装箱者进行切割实现装箱效率化装箱效率77
采混合算法终输出方案图44 优化装载图示：
图44 优化装载图
选择装箱物品13456710剩289需换种型号集装箱者进行切割实现装箱效率化两箱效率达85
货运模式：
假设现10种货品编号1~10体积分：09040612150708065072046
相应价值55 21 47 775 5 34 61 45 37
集装箱体积100
荷重28t钢板密度取8gcm38tm3
1表示装入0表示装
出gbest
1 0 0 1 1 1 1 0 0 0
选择装载14567
通述程约束数变量数时候利三维背包问题数学模型解决A公司货运问题取较成果
42计算速度分析
样利MATLAB通生成机物品测试次设计混合算法实际应效记录运算时间
具体数表44示：
表44
实验序号
物品尺寸（长宽）
优化算法时
传BL法计算时
1
(43)(44)(44)(52)(24)(43)(25)(15)(42)(34)
354
316
2
(53)(51)(11)(55)(14)(42)(33)(14)(22)(24)
283
253
3
(53)(54)(43)(25)(54)(15)(32)(34)(52)(54)
312
28
4
(52)(53)(25)(44)(24)(25)(34)(54)(13)(51)
478
43
5
(22)(53)(45)(41)(21)(35)(35)(54)(12)(21)
398
36
6
(43)(25)(15)(42)(34)(43)(44)(44)(52)(24)
412
37
7
(25)(15)(42)(34)(52)(54)(34)(52)(54)(34)
389
347
8
(55)(51)(33)(53)(24)(33)(41)(14)(24)(22)
365
335
9
(42)(34)(35)(51)(11)(55)(41)(33)(24)(22)
402
359
10
(42)(33)(14)(12)(24)(22)(54)(44)(41)(55)
354
317
11
(53)(45)(41)(21)(35)(12)(35)(54)(11)(22)
405
36
12
(35)(54)(12)(54)(34)(15)(22)(54)(42)(34)
451
402
13
(11)(55)(14)(33)(41)(22)(42)(53)(54)(43)
374
35
14
(25)(45)(15)(32)(43)(52)(54)(21)(41)(22)
346
323
15
(14)(12)(24)(32)(22)(42)(24)(12)(13)(11)
311
278
16
(54)(12)(54)(35)(25)(44)(24)(52)(33)(44)
432
397
17
(43)(25)(15)(54)(42)(41)(21)(35)(32)(13)
365
335
18
(12)(53)(14)(12)(24)(32)(54)(54)(41)(11)
327
292
19
(45)(53)(34)(32)(11)(21)(51)(45)(31)(12)
351
304
20
(35)(54)(11)(22)(15)(54)(42)(15)(35)(32)
403
378
21
(32)(31)(15)(54)(42)(51)(41)(21)(45)(33)
452
409
22
(31)(51)(22)(45)(51)(32)(41)(33)(21)(52)
374
34
23
(24)(12)(13)(15)(45)(14)(12)(21)(35)(45)
345
323
24
(34)(42)(41)(11)(22)(31)(52)(55)(42)(53)
317
293
25
(55)(25)(45)(33)(53)(34)(32)(31)(14)(12)
432
395
26
(53)(51)(11)(55)(14)(42)(33)(14)(22)(24)
322
295
27
(53)(54)(43)(25)(54)(15)(32)(34)(52)(54)
448
4
28
(52)(53)(25)(44)(24)(25)(34)(54)(13)(51)
368
33
29
(22)(53)(45)(41)(21)(35)(35)(54)(12)(21)
402
367
30
(43)(25)(15)(42)(34)(43)(44)(44)(52)(24)
369
336
31
(25)(15)(42)(34)(52)(54)(34)(52)(54)(34)
365
329
32
(55)(51)(33)(53)(24)(33)(41)(14)(24)(22)
4
357
33
(42)(34)(35)(51)(11)(55)(41)(33)(24)(22)
345
312
34
(42)(33)(14)(12)(24)(22)(55)(44)(41)(55)
313
285
35
(53)(45)(41)(21)(35)(12)(35)(54)(11)(22)
405
361
36
(35)(54)(12)(54)(34)(15)(22)(54)(42)(34)
459
423
37
(11)(55)(14)(33)(41)(22)(42)(53)(54)(43)
372
332
38
(25)(45)(15)(32)(43)(52)(54)(21)(41)(22)
346
309
39
(14)(12)(24)(32)(22)(42)(24)(12)(13)(51)
318
283
40
(54)(12)(54)(35)(25)(44)(24)(52)(43)(44)
43
395
41
(43)(25)(15)(54)(42)(41)(21)(35)(32)(23)
355
316
42
(12)(53)(14)(12)(24)(32)(54)(54)(41)(11)
314
28
43
(24)(12)(13)(15)(45)(14)(12)(21)(35)(45)
389
347
44
(34)(42)(41)(11)(22)(31)(52)(55)(42)(53)
324
289
45
(55)(25)(45)(33)(53)(34)(32)(31)(14)(22)
405
389
46
(53)(51)(11)(55)(14)(42)(33)(14)(22)(24)
433
386
47
(53)(54)(43)(25)(54)(15)(32)(34)(52)(54)
371
336
48
(52)(53)(25)(44)(24)(25)(34)(54)(13)(51)
321
296
49
(22)(53)(45)(41)(21)(35)(35)(54)(12)(21)
311
277
50
(43)(25)(15)(42)(34)(43)(44)(44)(52)(24)
332
31
统计出优化算法均时37298s传统BL算法时325s优化算法极值搜索计算时稍增相距详见图45时启发式智算法（见图46）装载效率略低着相明显速度优势保证没牺牲装箱效率时缩短运算排布时间
图45 运算时
图46 启发式算法效率
五总结展
次装箱方法优化实实程中见货运集装箱布局分布产生量剩余空间浪费受车间中货物底盘装载问题启发萌生种研究种约束少效果算法念头作工业生产交通运输方面中常见搬运装载模式货物底盘物流存储运输等方面发挥巨效利箱子形状完全相求时箱子底盘边作相互行二维装箱问题数特点约束重合A公司货物钢板发现两者具高度相似性身目标约束优化问题约束会求解难度解数爆炸增长二维装箱问题求解难度三维装箱问题低萌生弱化约束数降维简化装箱想法
开始装箱问题进行研究时候第步首先问题分类着手
针装箱问题分类问题运输生产中两种常见集装箱装载方式种常见快递邮政定限数量容器装载物品数量定通装箱方法模式安排容器利率高二相反情况常见公司送货物流定数量定容器装载物品数量通常容器倍数目远远超现容器承载力需调度安排限集装箱空间装载货物限度利集装箱提高装载率称单集装箱问题
分类实种理想化模型实际生产中更遇第2类问题单箱装载问题结合实践活动手头资料涉算法思路相次设计课题选择针集装箱单箱装载问题
实际工作时发现A公司货运货模式存问题未做次货车货物做价值化结数学模型属装箱问题子问题定篇幅提供种优化算法提供种优化思路目终A公司济效益提高
贯彻次设计始终难题算法MATLAB编程实现学科四年学中接触编程皮毛次设计需花费量时间进行编程语言算法理念学时间限制想法结写成程序存少问题参数调试直没优阶段
实际装箱观察总结选择BF算法算法程序冗长情况数目庞实际装箱序相算法
缩短搜索时长提高搜索效率通俗易懂利期维护修改选择PSO粒子群算法核心理简单计算效果良新颖算法设计时长限制选简单粒子群算法目标变量基数迭代次数较少情况简单粒子群算法然发挥出错效果
N叉树剩余空间部分装箱问题新研究成果算法更加贴合潮流尝试添加混合算法中常常出现坐标变动容易导致空间划分错误直接装箱序列出错装箱失败总结编写程序时候身装箱情况考虑周坐标算法存漏洞导致部分程序量优化空间果方面进行深入研究该部分应重点研究学点
通MATLABGUI程序设计装箱结果组合视化程序移植目前装箱问题优化效果检验重手段途径囿知识储备设计时长次毕业设计没做GUI部分期MATLAB深入学熟练掌握GUI设计应结合问题深层理解秉承工业工程优化止境理念优化算法断改善提高
参考文献
[1] 陈希王宁生基遗传算法车间设备虚拟布局优化技术研究[J]东南学报200434(5)
[2] George J ARobinson D F A heuristic for packing boxes into a container Computers and Operations Research 19807(3) 147156
[3] Bortfeldt AGehring H A tabu search algorithm for weakly heterogeneous container loading problems OR Spectrum199820(4) 237250
[4] PISINGERDA tree search heuristic for the container loading problem IJJRicerca Operativa 1998283148
[5] 张德富彭煜朱文兴陈火旺求解三维装箱问题混合模拟退火算法计算机学报200932(11) 21472156
[6] YuLiang Wu Wenqi Huang Siuchung Lau CK Wong An effective qusibuman based heuristic for solving the rectangle packing problem[J] European Joumal of Operational Research2002 141 341358
[7] Bortfeldt A Gehring H A tabu search algorithm for weakly heterogeneous container loading problems OR Spectrum199820(4) 237250
[8] Moura A OliveiraJ F A GRASP approach to the containerloading problem IEEE Intelligent Systems 200520(4)5057
[9] Hopper ETurton BCH An empirical investigation of metaheuristic and heuristic algorithms for a 2D packing problem European Journal of Operational Research 2001128(1)3457
[10] Shi X H Liang Y C Lee H P et al An improved GA and a novel PSOGAbased hybrid algorithm[J] Information Processing Letters 2005 93(5)p255261
[11] Clerc M Kennedy J The particle swarm explosion stability and convergence in a multidimensional complex space[J] IEEE Transactions on Evolutionary Computation 2002 6(1)073
[12] 张德富彭煜张丽丽求解三维装箱问题层启发式搜索算法[J]计算机学报201235(12)25532561
[13] Zhu W Lim A A new iterativedoubling GreedyLookahead algorithm for the single container loading problem[J] European Journal of Operational Research 2012222(3)408417
[14] 刘胜 凤华 吕宜生等 求解三维装箱问题启发式正交二叉树搜索算法[D] 计算机学报 2015 38(8)15301543
[15] Coffman EGjun Garey MR Johnson DS Approximation algorithms for binpacking an updated survey[M] Approximation algorithms for NPhard problems PWS Publishing Co 1996
[16] Khuri S Back T Heitkotter J An evolutionary approach to combinational optimization problem[ A] Proe of 22nd Annual Computer Science Conference [ C] New York Phoenix AZ ACM Press 1998 6673
[17] Chatterjee A Siarry P Nonlinear Inertia Weight Variation[J]．Computers and operations Research200633(3)859871
[18] 梁旭黄明宁涛等现代智优化混合算法应第二版[M]北京：电子工业出版社20144251
[19] 雷英杰张善文李续武等遗传算法工具箱应[M]西安：西安电子科技学出版社20054560
[20] 周雪刚 非凸优化问题全局优化算法[D] 长沙：中南学博士学位文 2010112
[21] 易树 郭伏基础工业工程[M] 北京机械工业出版社 2006
水直线判：
Line_Judgement
设函数Line_Judgement判断竖直移动两条线段否会相交果相交计算输出两条线段竖直距离
function [flagHD]Line_Judgement(line1line2)
情况1左方相交时line1完全line2左方时竖直距离两坐标差两条线段竖直移动会相交
if line1(3) flag0
HDline1(2)line2(2)时竖直距离两坐标差
情况二line2line1右方第种情况两条线段竖直移动会相交
elseif (line1(3)>line2(1))&&(line1(3) flag1
HDline1(2)line2(2)
情况三line2line1左方线段存重合移存相交性
elseif (line1(1)>line2(1))&&(line1(1) flag1
HDline1(2)line2(2)
情况四line1完全line2右方竖直移动会相交情况
elseif line1(1)>line2(3)
flag0
HDline1(2)line2(2)
第五种情况line2完全line1包含1左端横坐标2左端横坐标12相交会出现竖直方移动
elseif (line1(1)line2(3))
flag1
HDline1(2)line2(2)
else
flag1
HDline1(2)line2(2)
end
End
顶点坐标：
Point_Coor
利顶点坐标标注增加定物品长度L宽度W作条件Point_Coor函数求[lxlyrxry]
设物品右角顶点坐标二维数组RPXY时定义二维数组Item储存物品长宽 定义RBPXY物品右角顶点坐标LBPXY 物品左角顶点坐标[lxlyrxry]端水线坐标：
function BottomLinePoint_Coor(ItemRPXY)
RBPXY[RPXY(1)RPXY(2)item(2)] LBPXY[RPXY(1)item(1)RPXY(2)item(2)]
BottomLine[LBPXYRBPXY]
End
降距离计算：
Down_H
设item物品长度宽度表示矩阵[长度宽度]
Itemi维数组（i表示已装载箱子数目）表示已装载箱子长度宽度[长度宽度]
itemRP：时物品右角顶点坐标[xy]
RPNXY：分配二维数组检索完毕已放箱子中物品右角顶点坐标存储格式Item
输出dH：箱子中位置物品降高度直作判条件前剩余空间否满足装载物品进行判断输出dH正负分代表目前剩余空间容纳剩余空间容纳
部分函数说明：size（）：获取矩阵行数列数
sort({＇descend＇})：降序排列
aH[] 储存满足相交条件降距离数组
function MaxDownHDown_H(itemItemitemRPRPNXY)
BottomLinePoint_Coor(itemitemRP) Point_Coor
求物品端水线段标示[leftxleftyrightxrighty]
RP_NUMsize(RPNXY1) 获取数组行数出箱子物品数目
if RP_NUM~0
sRPNXYsort(RPNXY3{＇descend＇}) RPNXYY坐标降序排列
sRBPNXYsRPNXY
sRBPNXY(2)sRPNXY(2)Item(sRPNXY(1)1) RPNXYY坐标降序排列左角顶点坐标
topLine[sRBPNXY(23)sRPNXY(23)] 物品Y坐标降序排列物品端水线段左右两端坐标[leftxleftyrightxrighty]
循环流程
aH[] 定数组储存
While i
[flagHD]Line_Judgement(BottomLinetopLine(i))
if (flag1)&&(HD>0)
aH[aHHD]
end
End
果相交条件满足表明装入BF算法直接降箱子底端
if isempty(aH)
downHitemRP(2)item(2)
else 果存满足相交条件物品降距离aH中值
downHmin(aH)
end
else
downHitemRP(2)item(2) 时箱子空物品放置底端
End
End
箱子装载左移距离进行计算：
利指针f表示相交情况
指针指相交路径输出竖直线段彼距离
SLine_Judgement
竖直线段位置关系分5种情况：1）方相交2）方相交3）方相交4）方相交5）line1完全包含line2
输入第条线段line1：[topxtopybottomxbottomy]
输入第二条线断line2：[topxtopybottomxbottomy]
输出flag：指针等零者表示相交情况前者相交者相交输出hd：相交正反负数
function [flagHD]SLine_Judgement(line1line2)
第种情况line1完全line2方两条线段移会相交
if line1(4)>line2(2)
flag0
HDline1(1)line2(1)
第二种情况line2line1方时移会重合
elseif (line1(4)line2(4))
flag1
HDline1(1)line2(1)
第三种情况line1line2方两条线段移会相交
elseif (line1(2)line2(4))
flag1
HDline1(1)line2(1)
第四种情况line2完全line1方意移法相交
elseif line1(2) flag0
HDline1(1)line2(1)
第五种情况line1完全包含line2
elseif (line1(4)line2(2))
flag1
HDline1(1)line2(1)
（ else
flag1
HDline1(1)line2(1)）
end
end
顶点坐（水）：
Point_Coor2
根物品右角顶点坐标利物品长度L宽度WPoint_Coor2函数求出物品物品左端竖直线段两端坐标[topxtopybottomxbottomy]
设物品右角顶点坐标二维数组RPXY时定义二维数组item输入
储存物品长宽 定义LUPXY物品左顶点坐标LBPXY 物品左角顶点坐标：
输出leftLine：物品左端竖直线段两端坐标表示[topxtopybottomxbottomy]
function leftLinePoint_Coor2(itemRPXY)
LUPXY[RPXY(1)item(1)RPXY(2)] 物品左角顶点坐标
LBPXY[RPXY(1)item(1)RPXY(2)item(2)] 物品左角顶点坐标
leftLine[LUPXYLBPXY]
End
左移距离计算：
Left_W
设item物品长度宽度表示矩阵[长度宽度]
Itemi维数组（i表示已装载箱子数目）表示已装载箱子长度宽度[长度宽度]
itemRP：时物品右角顶点坐标[xy]
RPNXY：设二维数组存储前箱子中物品右角顶点坐标表示[长度宽度]
输出LeftW：物品item箱子意位置降高度时利降高度进行装箱判果LeftW正数装入前剩余空间果负数装入前箱子剩余空间
部分函数说明：size（）：获取矩阵行数列数
sort({＇descend＇})：降序排列
aw[] 储存满足相交条件左移距离数组
function MaxLeftWLeft_W(itemItemitemRPRPNXY)
leftLinePoint_Point_Coor2(itemitemRP) 物品左端竖直线段两端坐标[topxtopybottomxbottomy]
RP_NUMsize(RPNXY1) 通数组行数提取箱子物品数目
循环体
if RP_NUM~0
sRPNXYsort(RPNXY2{＇descend＇}) RPNXYX坐标降序排列
sRBPNXYsRPNXY
sRBPNXY(3)sRPNXY(3)Item(sRPNXY(1)2) RPNXYX坐标降序排列右角顶点坐标
rightLine[sRPNXY(23)sRBPNXY(23)] 物品X坐标降序排列右端线段两端坐标变[topxtopybottomxbottomy]
循环体
aW[] 定数组储存相交情况左移距离
for i1RP_NUM
注释函数 [flagHD]SLine_Judgement(leftLinerightLine(i))
if (flag1)&&(HD>0)
aW[aWHD]
end
end
果存满足相交条件物品直接移动箱子左端
if isempty(aW)
leftWitemRP(1)item(1)
else 果物品满足相交条件左移距离aW中值
leftWmin(aW)
end
else
leftWitemRP(1)item(1)
end
End
坐标：
Update_itemRPFPos
利述函数计算出itemRPdownHleftWitemitemRPRPNXY
输出itRPXYFRP： 物品item箱子中降左移确定位置坐标进行定位输出
提函数：
zeros数组zeros(MN) 者 zeros([MN])：生成M行N列零矩阵
function itRPXYUpdate_itemRP(itemRPdownHleftW)
itRPXYzeros(12)
itRPXY(2)itemRP(2)downH y坐标
itRPXY(1)itemRP(1)leftW x坐标
End
function finalRPFPos(itemItemitemRPRPNXY)
物品位置法改变跳出循环
while 1
downHdownHAtPoint(itemItemitemRPRPNXY) 计算物品item箱子itemRP位置处降高度
leftW0
itemRPUpdate_itemRP(itemRPdownHleftW) 更新物品item前位置右角顶点坐标
downH0
leftWleftWAtPoint(itemItemitemRPRPNXY) 计算物品item箱子itemRP位置处左移动距离
itemRPUpdate_itemRP(itemRPdownHleftW) 更新物品item前位置右角顶点坐标
if (downH0)&&(leftW0)
FRPitemRP
break
end
end
End
目前装箱序列进行判断通左角顶点坐标辨否存重合现象果序列排布重合flagOL1视装箱失败
Item(RPNXY(i1))长度
Item(RPNXY(i1))宽度
Item(RPNXY(i1))左角顶点坐标
function flagOLoverlap(itemItemitemRPRPNXY)
flagOL0 初始化存重合情况
itemLBP[itemRP(1)item(1)itemRP(2)item(2)] 左角顶点坐标
A[itemLBPitem]
numsize(RPNXY1) 箱子中物品数目
if num>0
for i1num
SbxItem(RPNXY(i1)1)
SbyItem(RPNXY(i1)2)
LBPXY[RPNXY(i2)SbxRPNXY(i3)Sby] B[LBPXYSbxSby]
arearectint(AB) 判断条件利AB两者计算输出面积关系
果两者复合橡胶条件满足列关系
if area>0
flagOL1
break
end
end
end
end
二叉树编程思路：
集装箱空箱容积构成元胞数组
clear
clc
close all
for item1：n
if 容积 return
Else
When箱子放入空间中
搜索适应空间
BL算法直位置固定
右角坐标itemRP妨设（xy）
计算S2S3
建立左子树（剩余空间S2）
S2X*(WY) S2L*(WY)
||
建立右子树（剩余空间S3）
S3(LX)*W S3(LX)*(WY)
集合B｛｝已放入Bi编号
BL算法更新LWitemRP
itemitem+1
end
PSO算法程序：
初始化种群
Dim10维度
xSize20 种群数
maxgen200 迭代次数
c115c215 加速子
w08 定义惯性子
Drepmat(dxSize1) d扩展成30*10矩阵
Wrepmat(wxSize1) w扩展30*10矩阵
xround(rand(xSizeDim)) 机30*10矩阵
vrand(xSizeDim) 机30*10速度矩阵
xbestzeros(xSizeDim) 单粒子初始佳位置
fxbestzeros(xSize1) xbext适应度
gbestzeros(1Dim) 全局优解
fgbest0 获适应度关全局优极值
iter0
while iter iteriter+1
fxFX粒子适应度公式（42）
for i1xSize
if w>Q
fx(i)0超重量适应度0 果适应度函数带重量约束时PSO编程时带
End
end
for i1xSize
if fxbest(i) fxbest(i)fx(i)
xbest(i)x(i)
end
end
if fgbest [fgbestg]max(fxbest)
gbestxbest(g) 存粒子佳适应度
end
for i1xSize
if x(i)gbest
x(i)round(rand(1Dim)) 记录已优位置粒子赋予新值防止陷入局部优解
end
end
R1rand(xSizeDim)
R2rand(xSizeDim)
vv*w+c1*R1*(xbestx)+c2*R2*(repmat(gbestxSize1)x)速度迭代公式PSO核心公式产生新速度
xx+v
for i1xSize 更新粒子群位置
for j1Dim
if x(ij)<05
x(ij)0
else x(ij)1 粒子位置（01）两种状态边缘化处理
end
end
end
End
fgbest
sgbestsum((s*gbest)＇)
disp(gbest)
输出算法程图
figure
plot(maxgenfgbest)
xlabel(＇粒子循环代目＇)
ylabel(＇适应函数取值＇)
货运模式编程思路：
n＝10
aj[]体积数组
cj[]价指数组
gj[]重量数组
b背包容积限制
w背包重量限制
a[]体积数组
c[]价值数组
Dim20设定粒子维数
xSize100初始种群数目
MaxIt100迭代次数值
c11
c21
w08根验判断取惯性系数08
Arepmat(axSize1)a扩展成30*10矩阵
Crepmat(cxSize1)c扩展成30*10矩阵
Grepmat(gxSize1)g扩展
xzeros(rand(xSizeDim))生成01矩阵标记粒子初始位置
vzeros(xSizeDim)定义初速度
xbestrand(xSizeDim)单粒子初始佳位置
fxbestrand(xSize1)xbest适应度
gbestzeros(1Dim)初始优解
fgbest0第次先群体优值赋0
迭代循环算法
iter0
while iter iteriter+1
fxsum((C*x)＇)统计目前背包物品价值
sxsum((A*x)＇)统计目前背包物品体积
gxsum((G*x)＇)统计目前背包物品价值质量
for i1xSize
if sx(i)>b||gx(i)>w
fx(i)0包物品体积超限制时期适应度设置1
end
end
for i1xSize
if fxbest(i) fxbest(i)fx(i)
xbest(i)x(i)
end
end
if fgbest [fgbestg]max(fxbest)
gbestxbest(g)
end
for i1xSize
if x(i)gbest
x(i)round(rand(1Dim))
end
end
R1rand(xSizeDim)
R2rand(xSizeDim)
vv*w+c1*R1*(xbestx)+c2*R2*(repmat(gbestxSize1)x)速度迭代公式产生新速度
xx+v更新粒子群位置
for i1xSize
for j1Dim
if x(ij)<05
x(ij)0
else x(ij)1
end
end
End
End
fgbest
sgbestsum((a*gbest)＇)
gbest
机物品生成：
命令：Bin[1010] 方便计算记箱子长度宽度10
itemNum10 物品数目
Itemceil(05*Bin(1)*rand(itemNum2))机生成10物品
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
集装箱单箱混合装载优化方法研究
摘
装箱问题非确定性项式完全问题（Nondeterministic Polynomial Complete Problem：NP）目前已广泛应日常生产生活中作涉体积重量布局等复杂目标约束问题求解程中存量局部极值点干扰目前该问题相关优化算法满意行解具体优化方法包括数值优化方法(Optimal Algorithms)构造法（Construction Algorithms）智优化算法等
文A公司例分析目前现货运特点采典背包模型建模分析利粒子群算法进行模型求解时分析A公司装箱装载模式简化特殊二维装箱问题建立数学模型结合装箱货物特点采结合剩余空间理二叉树思想粒子群优化BL算法运MATLAB进行模型求解优化装载布局更新货运模式提高生产效率
关键词：装箱问题背包问题粒子群算法剩余空间二叉树理佳适应算法
Abstract
Binpacking problem a complete NP problemis widely used in daily production and life As a complex multiobjective multiconstraint problem involving volume weight and layout with a large number ofinterferences by local extreme point in the solution process which can only be approximated At present the method mainly used for solving the packing problem can only rely on solving the nonNP problem to obtain an approximate optimal solution close to the optimal solution The main representatives are numerical optimization methods (optimal algorithms) construction algorithms (including NF approximation algorithms BF approximation algorithms etc) intelligent optimization algorithms represented by PSO GA etc This article uses Company A as an example to analyze its current freight operations and container loading modes Using the PSO (Partical Swarm Optimization)and the Bottomup leftjustified algorithm that combines the theory of remaining space and binary tree theory Limited to a special packing problem combined with the knapsack problem mathematical models are established for research in order to attain the goals of optimizing loading layoutschanging freight modes and enhancing production efficiency
Keywords Binpacking problemKnapsack problemPartical Swarm Optimization Binary Tree theory of remaining spaceBottomup leftjustified algorithm
目录
1 概述 1
11装箱问题概述 1
12装箱问题发展史 2
13研究目意义 2
2 原理材料 3
21 BL算法简介 3
22二叉树法剩余空间理 7
221二叉树法 7
222剩余空间理 8
223装箱序优化方法 13
3 数学建模MATLAB实现 16
31装箱问题数学建模 16
311 A公司货运装箱模式 17
32MATLAB实现 19
321BL算法思路： 19
322二叉树设计思路： 23
323PSO算法思路 24
33货运模式优化思路MATLAB实现 25
4 算法测试 26
41混合优化方法测试 26
411混合优化方法实例测试 26
412混合算法实际应 31
42计算速度分析 34
五总结展 38
参考文献 40
致谢 42
附录 43
1 概述
11装箱问题概述
装箱问题广泛存生产生活中类空间布局优化问题求干分割物件放入容积相箱子中求箱子数目少子问题单箱问题（称容器装问题threedimensional containerpacking problems3DCPP）指箱子通装载方法设计装入物件数目
装箱问题离散问题复杂组合解决问题关键优化组合需找满足约束满足限离散完整数学框架适应度函数（目标函数）优解组合优化问题量局部值点存通常法定义微连续问题相准确说法混合非线性受维约束局限NP完全问题NP完全问题描述样适遍历问题图分割等组合优化问题
否效时间实施精确求解组合爆炸缘NP完全问题答案否定目前学界作工作般针优化算法逼求解降低求解难度意味着装箱算法利似算法通压缩搜索优似解逼优解
装箱问题根约束数目分维装箱问题二维装箱问题三维装箱问题维装箱问题等针实际工作场景维装箱问题考虑体积约束二维装箱问题考虑布局中长宽两约束日常生产生活中涉广研究结相较贫乏三维装箱问题二维装箱基础增加高度约束三维装箱问题求解难度陡然升惯学界般三维装箱问题分三种：
1货柜装载问题(threedimensional bin packing problem3DBPP)：已知数量类型等矩形箱子定统规格容器限终选定方法全部箱子装载时开启容器少
2容器限定装载问题(threedimensional containerpacking problems3DCPP)：求尺寸限容器中全部物品装入出装填方法容器体积优变形单箱问题描述箱子通装载方法设计装入物件数目
3背包装填问题(threedimensional knapsack loading problems3DKLP)：装填物件赋价值挑选中部分装填令装入容器中箱子选择方案总价值方案容积约束增加价值约束
历数十年研究三维装箱问题解决较明确思路方目前较通行解法分两部分部分负责布局放置启发式算法部分利现代智算法优解搜索逼目前存高度约束求较弱三维装箱降维二维装箱算法思路
12装箱问题发展史
装箱问题研究开始普遍认距两百年前1831年高斯(Gauss)开始做研究布局问题工作20世纪70年代初物流运输业加速发展相关装箱问题引起学界广泛探讨研究[1] 发展时日已形成较固定通行思路般算法混合应布局放置早国外George等利层墙堆砌法[2]取较成果基础Gehring提出塔堆砌理念提出遗传算法运中[3]时Pisinger树搜索布置布局提供新思路[4]较流便国张德富彭煜朱文兴陈火旺等取力发展基块理念填充方法[5]黄文奇Zhang等递式启发式算法研究应[6]优解逼GehringBortfeldt利混合遗传算法Bortfeldt尝试利禁忌搜索算法运筹学中动态规划常分支定界法[7]续种适应算法应Moura等Reactive GRASP算法[8]算法探索未停止Hopper分BLBLF启发式布局算法GA等启发式搜索混合算法进行求解[9]目前言较通效果较张德富教授等提出混合模拟退火算法布局利块堆栈放置方案编码作装载序列利模拟退火算法出似优解
13研究目意义
装箱问题作类空间布局优化问题广泛存日常工业生产生活方方面面例二维装箱问题源服装材料印刷行业排料板材型材切割面料裁剪三维装箱运输行业典型集装箱装载应现实生活中材料包装包装分类
计算机科学处理器底层操作程例处理器资源务分配存调度理安排址文件等装箱问题研究成果提供实际效
长久装箱问题研究中运筹理CADCAM图形学工智等诸方面领域许新突破发展装箱问题产生思路方法学科结合开拓新发展空间关集装箱重性学界句话说：全球化新技术世界抹前集装箱已形力量世界连接起物流俗潜力量挖掘效益视作第三利润源收录日学者西修著作中观类历史发展进程离开两领域开发提供巨额利润：第原材料资源领域第二力资源相关研究成果已述两领域潜力挖掘殆利润开拓愈发困难相第三利润源常常忽视物流GDP贡献分低估目前丰京东物流领域取优异成绩越越公司开始意识第三利润源重性作第三利润源缺重环集装箱装箱问题潜力巨值深入研究
2 原理材料
21 BL算法简介
BL法（bottomup leftjustified）装箱问题中种常见似装载算法BL算法前提整装箱程中物品允许斜放然开始装箱
物品A进入箱子B序：（1）A紧挨箱子B右角落直移动物件（物件边者箱子B底边）相切直A移动止（2）左移动A物件（物件边者箱子B左边）相切直 A左移动止（3）重复（1）（2）直物品A位置固定移动
面应实例说明BL算法步骤假设箱子边长10米正方形箱子放物品尺寸矩形计8件具体尺寸表21示：
表21 物品尺寸
物品名称
长度（单位：米）
宽度（单位：米）
1
5
1
2
5
3
3
2
2
4
5
3
5
3
1
6
6
5
7
7
3
8
5
4
根输出结果终完成十物品装箱箱子两现中箱子248号物品装载程简说明装载程：
首先物品2紧容器右壁落继续移动左移动直移动图21 2物件装载程：
图21 2物件装载程
然4号物品放入先假定4号物件横放方式装箱方法具体流程见图22 4物件装箱程
图22 4物件装箱程
箱子8样序装入终新开启箱子装箱完成效果见图23 248装箱程
图23 248装箱程
剩余装货物1356763571序装入
图24 剩余货品装箱示：
图24 剩余货品装箱
述实例发现BL算法然较高效实现物件装箱程箱体存量空白空间未空白空间相继续装箱图23中见便样尺寸体积物品2物品4装载方横竖摆放位置集装箱堆砌利会效果外装箱结果稳定性方面足BL算法常常诟病某装载结果例图25示橙色块明显存重心位置偏离形心继导致稳定性足易造成货品运输程中损耗
图25 装载位置
22二叉树法剩余空间理
221二叉树法
计算机科学中广泛存n叉树应现行少关二维装箱设计研究采二叉树结构般利二叉树法装箱较理想结果图（见图26 理想二叉树装载图）：
图26 理想二叉树装载图
首先容器部紧左壁放入物体固定该物体位置生成坐标物体根节点剩余空白区域划分两子空间物体接着装箱利算法两子树空间进行搜索寻找容纳物体空白区域装入生成节点两子树（子空间）直循环递直容器空间填满者剩余空白区域法容纳件物品止底面填满底面布局断增高直高度约束者重量约束中满足便终止算法输出结果装箱完成
具体通方法实现图27示：
图27 子树产生图
图出子树空间根已放物品节点进划分针新物品装箱通常情况毗邻前物品装箱形式装入装载方式消耗剩余面积相空间前提紧挨着装箱箱物品重心集中前普通BL算法相拥相较稳定性
典二叉树算法取较成果前提统计装入货品分取均宽度高度根验取sqrt系数分相结果正方形普适性实际装箱问题言高时查阅相关文献时发现二叉树理更适已知装载物件数目体积寻找箱子容器容纳全部物件求容器体积问题次设计涉装箱问题原节点生成二叉树更生成新空白空间容纳装载物件非优先考虑剩余空白空间通常二叉树结合较紧密FF算法次设计BL算法显然合适剩余空间理补充完善显必次设计汲取二叉树算法思想应剩余空间划分中
222剩余空间理
剩余空间理前装箱算法优化程重理成果研究关装箱空间分割装箱位置选择通装载剩余空间划分生成新装箱子问题递穷直空间法容纳新箱子视装箱完成质思想点接二叉树划分
装箱空间分割法指箱子放入空间剩余空间划分更子空间方法通常见装箱问题进行观察难发现子空间划分数装箱问题维数相二维装箱问题中剩余空间划分数2引学界通说法视S2空间S3右空间划分方法图28 二维剩余空间划分法示：
图28 二维剩余空间划分法
图见剩余空间面积相S2S3容纳物品类型完全
方法：S1水方分割剩余空间两子空间显然容纳更细长物件
方法二：根S1竖直方分割剩余空间两子空间适合装载较方正物件剩余面积相情况划分方式集装箱利效率着重影响
三维空间划分少研究三维装箱问题视带高度约束二维装箱问题延伸实际划分时候二维装箱问题两分割方分割出子空间高度约束存样两切割方（二维装箱问题前提规定斜着放置）三分割子空间样切割目剩余空间较块整体形式存提高装箱利率时保证货物货物保证装箱稳定性三维约束引二维装箱样例子容器放入S1划分方法图29 三维剩余空间划分法示：
图29 三维剩余空间划分法
方法：S1水方分割剩余空间三子空间学界称空间S1右空间S2前空间S3观察发现子空间S1S2较方正空间S2高度S1容纳等底面积更长高物件S3狭长空间适合装载宽度高度较物件
方法二：S1竖直方分割剩余空间三子空间样空间S1右空间S2前空间S3观察发现次子空间S1S2较狭长空间S2高度S1容纳等底面积更宽高物件S3方正空间适合装载长度宽度较物件
三维装箱问题剩余空间理剩余体积相情况集装箱利效率划分方式息息相关
适宜装载物件：
结合剩余空间理重心更集中认集装箱尺寸长远长宽时候面积相前提：
优先放置物件中面积较（利减少剩余空间）长宽差较物件吻合剩余空间采集装箱长宽差时优先放置类型较方正物件面编写完成适应度函数较部分需考量质量部分该部分PSO粒子群算法完成高度约束较弱前提次设计三维降带高度约束二维结合BL算法装填模式出装填思路：
1容器中蓝色物件放入节点剩余空白划分生成两子树空间12（图210 次装箱图示）：
2
图210 次装箱图示
2利粒子群算法搜索子树空间12剩余物件面积长宽作较较出适宜装载物件黄色物件放入较放入剩余空间更子空间放入中然黄色物件节点划分剩余空白区域生成两子树空间1’2’（图211 二次装箱图示）
2’
1’
图211 二次装箱图示
’
3利粒子群算法搜索子树空间1’2’剩余物件面积长宽作较较出适宜装载物件绿色物件放入较放入剩余空间更子空间放入中然绿色物件节点剩余空白区域生成两子树空间1’’2’’（图212 三次装箱图示）
’
2’’’
1’’
图212 三次装箱图示
循环递穷直剩余子空间法容纳剩余件物品法继续填充止理想装填效果图214 完整理想装箱图示：
图214 完整理想装箱图示
总结思路次装载次装箱节点生成两子空间生成两新装箱子问题第二货物装入时继续分割成前右三空间粒子群算法检索尺寸匹配剩余空间物件装入递循环确定货物全部装载完毕者剩余空间已法装载货物时PSO检索方案中装载面积剩余面积方案该方案似优解生成方案底面布置直叠加高度直等汽车荷重者超出集装箱高度限制混合装箱方法
保证装载效果前提该算法思路保证右角固定物件前提量提高物件摆放稳定性剩余空间利率
223装箱序优化方法
文选择粒子群算法实现装箱序优化粒子群优化美国社会心理学家James Kennedy电气工程师Russell1995年提出种优化算法针解决问题解粒子群中具粒子代表性应通单粒子简单动作组信息交互实现快速反应智解决粒子群算法具备原理编程简单收敛速度快收敛效果等优点广泛应工程功优化函数处理建筑理测量等许领域
粒子群算法建模原理种类：
粒子群优化算法源鸟群猎食方式原理组鸟群已知中该组中鸟知道身前位置食物距离相区域中机搜索食物知找寻象实施效方法策略搜索距离鸟类周围前食物区域
进行优化粒子群算法时鸟类均视粒子两者应解决优化问题解潜藏区域粒子中定约束适应度函数中粒子赋予优化函数决定适应度值值提社会性原鸟类族群中意味着粒子具备决定飞行方距离速度
根适应度高粒子（佳粒子）指引算法求余粒子佳解空间中搜索
粒子群算法会定解空间中机初始化粒子群通目标问题函数变量数解确定扩展空间维数旦确定粒子初始速度位置会根适应度反复迭代找佳解次迭代中粒子会通路径首先单粒子体循环中搜索单体优粒子视作体极值然回种群中种群中粒子迭代群体优粒子全局极值提取群体中部分利作单体邻居粒子体极值全局极值时处邻居粒子中极值称局部极值两者取样容量差衍生出两种方法处理差异前者称全局粒子群针种群中粒子外便算法提取局部粒子群
前粒子群优化算法类言分基标准粒子群优化算法压缩种群容量压缩粒子群算法采离散粒子离散粒子群算法值提粒子学性重视算法中变异环节显尤重变异环节非必少约束数目维数均高时候简化变异流程步骤：
算法重环节参数设置第步需算法迭代次数粒子飞行速度问题变量数目标函数进行设置信息定位整空间赋予初始位置速度机值进行搜索时飞行速度定数获修正般公式：设初始化位置初始化飞翔速度分XV：VX*(VmaxVmin)+Vmin
假设目前目标搜索空间D维中群落N粒子组成第i粒子表示D维量：
第i粒子飞行速度D维量记作：
第i粒子迄止搜索优位置称体极值记：
整粒子群迄止搜索优位置全局极值记：
搜索两优值时候迭代规律更新速度位置：
公式（21）
中：C1C2称加速常数获社会性学力子二者区C1针象粒子获体学力C2赋予粒子社会学力般想较解C1C2取值常数通常设置惯通常取C1C22取值范围[01]范围r1r2均均匀机数vij粒子速度（i12D）
Vmax户定义目作限制粒子速度常数增加粒子飞行机性求解范围更广准度更高需取两介01间机数r1r2速度方程设置通常需包含三部分
首先反映粒子运动惯惯性动量部分代表粒子维持身先前运动趋势般作第部分紧接着粒子需反映身搜索路径回忆记录次迭代寻优佳位置认知部分建立迫粒子序运动体历史优位置迫粒子获寻优求解趋势社会部分针全局求解避免陷入局部优早收敛单体粒子需协合作互相知优位置路径粒子获量验会出现群聚极值历史验值逼趋势
述粒子实质优化问题PSO中解代表处搜索空间中鸟优化函数会赋予粒子通约束函数确定适应度值时扩充矩阵中粒子具确定飞行方距离速度解空间中粒子会前佳粒子进行搜索求解优解迭代开始前会先机组粒子（机解）初始化PSO粒子通次迭代中踪体社会分极值更新身搜寻路径首体优解xBest称体极限极限前样容量扩充整总体搜寻发现总极限（群体极限）gBest两者中进行外邻居粒子选择跳庞杂烦冗总体样位置定位佳粒子周围较出邻居粒子极值似视全局极值
般粒子群算法流程图215 粒子群算法流程图示：
图215 粒子群算法流程图
次设计通PSO检索子空间中适应度函数高方案遍历递完毕输出方案视优解
3 数学建模MATLAB实现
31装箱问题数学建模
设定长方体集装箱C长宽高分LWH容积VVL*W*H
底面积SSL*W侧面积S’S’W*H前面积S’’S’’K*H集装箱极限荷重Q
设装物品集合B｛B1B2Bn｝中第i物品Bi应长宽高分LiWiHi
装载程中已装载体积BVi通公式（1）计算：
BViBiϵBLi∗Wi∗Hii12…n#1
公式（1）空间利率CV表示公式（2）：
CVi1nBViV∗100#2
二维装箱已装载面积BSi（包含SS’S’’）：
(3)
二维装箱面积利率CS：
CSi1nBSiS∗100#4
重量适应度函数公式（5）表示：
CQ (5)
装载货物重量超集装箱荷重Q法继续装载重量适应度函数等0出适应度函数：
三维装箱：
Fxk1CV+k2CQ#6
二维装箱：
Fxk1CS+k2CQ#7
中k1 k2加权系数根公司实际情况选
311 A公司货运装箱模式
着国国民济发展钢板生产量逐渐增长资料显示作钢材四类中重组成部份钢板产量占国钢材生产总量半
A公司家集钢材制造批发零售型公司营板型弹簧丝等钢材品种中钢板营业务公司总业务60％涉钢材直接相关中包括普通碳素钢优质碳素钢合金结构钢工具钢锈钢弹簧钢等钢板种宽厚表面积扁材料填充时具特殊特性根厚度钢板分薄板厚板两类型类钢板密度计算方便里取8gcm3
利冷轧者热轧等常见加工技术制成薄钢板具024mm厚度5001400mm宽度钢板薄钢板应范围广泛根途薄钢板轧制成材料钢坯应机械汽车工业航空航天工业外酸洗镀锌镀锡等流程薄钢板搪瓷工业电气工业等行业处见身影公司A轧制直接提供薄钢板业务环节
厚度等4毫米钢板总称厚钢板没较精确描述定义实际工作中厂家惯细分出中板指厚度20毫米钢板厚度20毫米60毫米钢板称厚板时应特殊领域特厚板指厚度超60毫米钢板类钢板必须特殊厚板轧制机中进行轧制便获数值较厚度厚钢板宽度较统般06mm30mm通常根途般常汽车钢板复合钢板厚钢板分类分桥梁造船工程钢板锅炉高压容器钢板等等
市面通汽车弹簧钢板原料钢板裁剪切割常标准集装箱40＇GP运载送货
目前A公司营钢带种类进行调查分类编号出十种钢材畅销钢板装箱频繁分进行编号表表3111（取薄钢板厚度4mm厚钢板密度8mm）
表31
名称
长（mm）
宽（mm）
薄钢板1#
5000
1000
薄钢板2#
2000
1000
薄钢板3#
2000
1000
薄钢板4#
3000
1000
厚钢板1#
5000
3000
厚钢板2#
5000
2000
厚钢板3#
3000
3000
厚钢板4#
2000
2000
厚钢板5#
3000
3000
厚钢板6#
7000
2000
定常普通箱40＇GP
尺寸（长x宽x高）12032mm×2352mm×2393mm
载重28吨
设定长方体集装箱C长宽高分L102mW235mH24m
设箱子C容积VVL*W*H57528m³
底面积SSL*W102*2352397㎡
侧面积S’S’W*H235*24564㎡
前面积S’’S’’L*H102*242448㎡
集装箱极限荷重QQ28t
薄钢板1号2号3号4号
厚钢板1号2号3号4号5号6号
构成装箱物品集合B元素分编号转换单位物品尺寸表32
表32
编号（元素名称）
元素尺寸（长宽） (单位：米)
1
(51)
2
(53)
3
(22)
4
(21)
5
(21)
6
(52)
7
(31)
8
(33)
9
(52)
10
(72)
货物批发零售A公司需矿场采购类矿石原料炼制钢板种矿石原料质量体积相带济收益高低矿石装箱满足体积重量限制前提实现效益化目前A公司亟提高货运装箱模式
32MATLAB实现
混合算法思路：
原始布局空间集装箱空载状态视空载状态二叉树根节点视次迭代剩余空间行域粒子群算法遍历选择集合B中检索尺寸匹配剩余空间物体装入装箱程步骤中利算法物品包装箱中位置降距离左移动距离进行计算第步位置确定继续左走行直法移动视装箱完毕结合A公司货运特点减少约束数目简化实验步骤降低难度高度约束较弱三维装箱简化二维装箱摆放方式造成利率差异交剩余空间计算较选择放入物体BiBi集合B中剩余空间二叉树划分S2S3两独立子空间次S2S3作前布局空间（装载）诉步骤继续分解直集合B空集者剩余空间法容纳集合B中意元素装箱完毕
321BL算法思路：
知道矩形四条边密闭构成四条邻边相互垂直边相互行判断箱子装载程中否重叠首先箱子矩形分解四条线段四坐标矩形长宽已知情况需知道右角坐标便矩形四条边四点表示出
妨设矩形长L宽W右角坐标（xy）
四顶点分左角（xLy）左角（xLyW）右角坐标已知右角坐标（xyw）里选择右角坐标基准（xy）BL算法特性箱子停容器左边边逼右角坐标置容器空间部旦右角座标超出容器范围视载文判物品间否出现相交问题里暂略边描述般采两顶点坐标格式[leftxleftyrightxrighty]利方法矩形分左右四条边图31 矩形坐标分解示：
图31 矩形坐标分解
判断装箱程中矩形否继续移动箱子间否会重合导致装箱失败前提判断矩形边否移动中相交发现两矩形条边相交两矩形必定相交首先需设计判函数判断两条直线移动否会相交果相交相交距离少
BL算法装箱右角开始放入然竖直降继续降便左移动直继续左移动便竖直降重复循环直位置固定算法第步需判定箱子否继续降第二步骤判定箱子否继续左移
里参考传统BL算法制定编码思路传统BL算法整体步骤分三部分：1判否会相交2计算物品低端边坐标3计算降距离针三部分首先需矩形分解干线段矩形间相交重叠情况利线段间相交重叠情况进行判断需明确装箱程中矩形线段会出现状况：
1水直线判：
直线相交分5种情况：
1）左方相交2）左方相交3）右方相交4）右方相交5）line1完全包含line2（line2完全包含line1）
根文分析利四坐标表示装箱矩形拆分四条线段条线段需两坐标表示
妨分解水线段坐标设：[leftxleftyrightxrighty]通设置指针判断线段间否存相交情况果存相交情况通坐标计算两条直线竖直距离
五种情况进行简分析：
情况1左方相交时line1完全line2左方时竖直距离两坐标差两条线段竖直移动会相交
情况2line2line1右方第种情况两条线段竖直移动会相交
情况3line2line1左方线段存重合移存相交性
情况4line1完全line2右方线段作竖直移动会出现相交情况
情况5line2完全line1包含1左右端横坐标均2左右端横坐标12相交会出现竖直方移动
2竖直直线判：
竖直线段位置关系样分5种情况：
1）方相交2）方相交3）方相交4）方相交5）line1完全包含line2（line2完全包含line1）
样利四坐标矩形定位分解成线段条线段需两坐标表示
妨分解竖直线段坐标设：[topxtopybottomxbottomy]利flag值判断否存相交情况时果线段相交输出水距离
样五种情况进行简分析：
第种情况line1完全line2方两条线段移会相交
第二种情况line2line1方时移会重合
第三种情况line1line2方两条线段移会相交
第四种情况line2完全line1方移法相交
第五种情况line1完全包含line2
目前止竖直水线段移动相交状况判移动距离计算矩形箱子完整描诉需顶点坐标降距离左移距离
3顶点坐标：
获矩形四顶点坐标需获中点坐标矩形长宽水方：
利顶点坐标标注增加定物品长度L宽度W作条件BL算法特性决定需定位点物品左角顶点坐标步降距离作铺垫单独拎出左右两端点坐标表示端水线
竖直方：
根物品右角顶点坐标利物品长度L宽度W需利求出物品左端竖直线段两端坐标[topxtopybottomxbottomy]
BL算法特性物品左端竖直线段两端进行定位先求物品左角顶点坐标求出物品左角顶点坐标时结合水方降距离求出竖直方左移距离做铺垫
4移动距离：
降距离：
汇总述坐标移动距离需数组储存较装载已装载物品间坐标长宽落距离
获取完目前箱子中物品坐标通Y坐标进行降序排列目前顶层物品端线段坐标通集装箱径做减法分次装载完成物品剩余降高度降高度应满足等剩余降高度约束果出现目前降（装载）高度剩余高度应转判右边剩余空间否满足述相交条件判断否放置容器右侧
BL算法右角开始装入果相交条件满足算法会直接物品降容器底端
满足相交条件时选择箱子降高度中值
补充句箱子时空装入物品样会降底端
5左移距离：
思路利线段判条件指针表示相交情况找flag指相交路径样降序较出输出竖直线段彼距离
利定位物品左端竖直线段两端坐标BL算法特性右角坐标X坐标降序排列求降序排列右角坐标整合次重新降序排列X坐标通集装箱径做减法分次装载完成物品剩余左移长度左移距离应满足等剩余左移距离约束果出现目前左移（装载）距离剩余长度应转判方剩余空间否满足述相交条件判断否放置容器方判中满足相交条件直接移动容器左端
满足相交条件时选择箱子左移距离中值
完成入箱装载货物降左移算法需右角坐标前文中提需通右角坐标记录时货物位置通位置目前排列序列
物品箱子中右方落左方移动进行定位输出坐标目前装箱序列进行判断通左角顶点坐标辨否存重合现象果序列排布重合视装箱失败重新循环判断
MATLAB程序详见附录
322二叉树设计思路：
二叉树结合剩余空间理目前集装箱剩余面积装状态进行安排调度BL算法排布前提断剩余空间划分迭代出子空间直物品装载完毕者容器穷止Parents应两children两子树
提取二叉树编程思路：
首先应该明确前提二叉树循环终止条件：
1） 容器中剩余体积0
2） 遍历装载箱子适应度函数值满足剩余空间
3） 装载箱子标记已装载状态
终止条件满足装箱继续时候：箱子放入空间中搜索适应空间输出适应度值找适合放置箱子BL算法定位直位置固定右角坐标itemRP妨设（xy）剩余空间划分时已装载箱子视节点二叉树生成两剩余空间S2S3左右子树剩余空间分作约束空间面积二维空间剩余面积划分中存两划分方法应面积表示方法相妨简单表示形式：
建立左子树（剩余空间S2）
S2X*(WY)者S2L*(WY)
建立右子树（剩余空间S3）
S3(LX)*W 者S3(LX)*(WY)
已装载箱子需装箱子集合中编号获新装箱子集合子集更新子空间LW坐标数组重复述程直满足终止条件中跳出循环完成装箱方案
MATLAB程序详见附录
323PSO算法思路
二叉树剩余空间BF算法解决放置找出适应度函数函数优解里采PSO算法
首先输入定量：
种群初始化模块初始化粒子群种群A集装箱装载品类复杂加快收敛速度选Dim10
适应度值适应度函数求出表示模块计算粒子群体适应度值降维二维装箱取二维装箱适应度函数公式（42）
利公式粒子模块进行更新定适应度函数分求xbestgbest表示粒子适应度值更新单佳粒子组佳粒子
粒子机组（机解）初始化PSO佳解通搜索断迭代时粒子通踪体极值群体极值次循环中断更新身位置 单极值xBest粒子身公式迭代学找粒子体优解相应极值整前总体找优解全局极值（组极值）gBest样全部种群外压缩样容量仅利部分佳粒子邻居粒子空间中进行搜索邻居极值出极值似全局极值
时次设计采简单PSO算法考虑变异前提速度更新迭代公式公式21：
（21）
接需数组储存迭代数致需定义装箱方案应装箱方案重量数组存储粒子极值数组等
限制函数二维装箱适应度函数公式42
值提粒子群算法中常常涉许常量参数中W惯性子C1作加速子时粒子赋予体学子C2作社会学子粒子获社会学力C1C2取常数时较解般设置 惯通常取C1C22实验次调试情况发现C1C215w08情况取效果佳
MATLAB程序详见附录
33货运模式优化思路MATLAB实现
里货运模式针A公司矿场采购类矿石原料炼制钢板种矿石原料质量体积相带济收益高低里需方法矿石装箱满足体积重量限制前提实现效益化丰富补充A公司货运装箱模式
问题分类结背包算法提取数学模型已知容量G背包求物品装载价值排列组合需面装载象n重量W1—Wn应价值V1— Vn物品满足背包容量约束前提包总价值
针体积价值三维装箱问题（背包问题）里然采PSO算法背包问题进行数学建模定n体积aj应价值分cj物品箱子总容量b求价值箱子集合子集
MATLAB程序详见附录
4 算法测试
41混合优化方法测试
411混合优化方法实例测试
文提边长10正方形箱子7矩形物品物品长度宽度表示进行混合优化方法测试
表41
物品名称
长度（米）
宽度（米 ）
1
5
1
2
5
3
3
2
2
4
5
3
5
3
1
6
6
5
7
7
3
8
5
4
原普通BL算法输出方案图24 剩余货品装箱示：
图24 剩余货品装箱
通混合装箱算法输出方案图41 优化算法装箱示：
图41 优化算法装箱
通普通BL算法算法中装载物品13567采混合装载方法样集装箱装载物品135678剩余空间利效率提高20
接利MATLAB通生成机物品测试次设计混合算法实际应效算法进行50次模拟出数记录
详细见表42：
表42
实验序号
物品尺寸（长宽）
文算法箱体利率
文方法装载编码
BL法箱体利率
BL法装置编码
1
(43)(44)(44)(52)(24)(43)(25)(15)(42)(34)
823
1234569
68
1247810
2
(53)(51)(11)(55)(14)(42)(33)(14)(22)(24)
895
12345678910
65
134689
10
3
(53)(54)(43)(25)(54)(15)(32)(34)(52)(54)
951
23456789
92
124689
10
4
(52)(53)(25)(44)(24)(25)(34)(54)(13)(51)
884
1234567910
862
235678910
5
(22)(53)(45)(41)(21)(35)(35)(54)(12)(21)
791
1245678910
72
1234567910
6
(43)(25)(15)(42)(34)(43)(44)(44)(52)(24)
843
1234569
801
2346910
7
(25)(15)(42)(34)(52)(54)(34)(52)(54)(34)
754
3456789
736
123578
10
8
(55)(51)(33)(53)(24)(33)(41)(14)(24)(22)
667
12345689
702
123456789
9
(42)(34)(35)(51)(11)(55)(41)(33)(24)(22)
894
12357910
82
123468910
10
(42)(33)(14)(12)(24)(22)(54)(44)(41)(55)
784
1234569
743
234567
11
(53)(45)(41)(21)(35)(12)(35)(54)(11)(22)
877
2345678910
82
13467910
12
(35)(54)(12)(54)(34)(15)(22)(54)(42)(34)
851
1234567910
832
13567910
13
(11)(55)(14)(33)(41)(22)(42)(53)(54)(43)
832
134567810
828
24567810
14
(25)(45)(15)(32)(43)(52)(54)(21)(41)(22)
724
14568910
732
2348910
15
(14)(12)(24)(32)(22)(42)(24)(12)(13)(11)
963
12345678910
963
12345678910
16
(54)(12)(54)(35)(25)(44)(24)(52)(33)(44)
839
123456710
81
245678910
17
(43)(25)(15)(54)(42)(41)(21)(35)(32)(13)
767
1245689
733
123567910
18
(12)(53)(14)(12)(24)(32)(54)(54)(41)(11)
948
23456789
976
123456789
19
(45)(53)(34)(32)(11)(21)(51)(45)(31)(12)
887
1234567910
784
234567910
20
(35)(54)(11)(22)(15)(54)(42)(15)(35)(32)
791
1245678910
707
123478910
21
(32)(31)(15)(54)(42)(51)(41)(21)(45)(33)
854
1234678910
798
235678910
22
(31)(51)(22)(45)(51)(32)(41)(33)(21)(52)
982
12345678910
982
12345678910
23
(24)(12)(13)(15)(45)(14)(12)(21)(35)(45)
967
12345678910
967
12345678910
24
(34)(42)(41)(11)(22)(31)(52)(55)(42)(53)
919
1234568910
92
1234568910
25
(55)(25)(45)(33)(53)(34)(32)(31)(14)(12)
943
1234678910
843
23456789
26
(53)(51)(11)(55)(14)(42)(33)(14)(22)(24)
956
12345678910
956
12345678910
27
(53)(54)(43)(25)(54)(15)(32)(34)(52)(54)
945
23456789
927
123567810
28
(52)(53)(25)(44)(24)(25)(34)(54)(13)(51)
872
1234567910
761
1367910
29
(22)(53)(45)(41)(21)(35)(35)(54)(12)(21)
791
1245678910
756
245678910
30
(43)(25)(15)(42)(34)(43)(44)(44)(52)(24)
85
1234589
85
1234579
31
(25)(15)(42)(34)(52)(54)(34)(52)(54)(34)
755
3456789
689
1234567
32
(55)(51)(33)(53)(24)(33)(41)(14)(24)(22)
669
12345689
67
12345689
33
(42)(34)(35)(51)(11)(55)(41)(33)(24)(22)
898
12357910
90
12357910
34
(42)(33)(14)(12)(24)(22)(55)(44)(41)(55)
779
1234569
764
1235678
35
(53)(45)(41)(21)(35)(12)(35)(54)(11)(22)
894
2345678910
846
1345678910
36
(35)(54)(12)(54)(34)(15)(22)(54)(42)(34)
852
1234567910
799
123458910
37
(11)(55)(14)(33)(41)(22)(42)(53)(54)(43)
816
134567810
761
1235689
38
(25)(45)(15)(32)(43)(52)(54)(21)(41)(22)
728
14568910
714
12345789
39
(14)(12)(24)(32)(22)(42)(24)(12)(13)(51)
972
12345678910
95
123456789
40
(54)(12)(54)(35)(25)(44)(24)(52)(43)(44)
847
123456710
787
12345678
41
(43)(25)(15)(54)(42)(41)(21)(35)(32)(23)
762
1245689
753
1235678
42
(12)(53)(14)(12)(24)(32)(54)(54)(41)(11)
98
2345678910
97
23456789
43
(24)(12)(13)(15)(45)(14)(12)(21)(35)(45)
100
12345678910
100
12345678910
44
(34)(42)(41)(11)(22)(31)(52)(55)(42)(53)
921
1234568910
90
1234567910
45
(55)(25)(45)(33)(53)(34)(32)(31)(14)(22)
936
1234678910
936
12345678910
46
(53)(51)(11)(55)(14)(42)(33)(14)(22)(24)
972
12345678910
972
12345678910
47
(53)(54)(43)(25)(54)(15)(32)(34)(52)(54)
954
23456789
915
13456789
48
(52)(53)(25)(44)(24)(25)(34)(54)(13)(51)
897
1234567910
847
123456710
49
(22)(53)(45)(41)(21)(35)(35)(54)(12)(21)
778
1245678910
758
12456789
50
(43)(25)(15)(42)(34)(43)(44)(44)(52)(24)
835
1234569
824
1234579
通50次输出数进行记录整理出均箱体利率8672相目前普通BL算法827左右利率少提高（见图42 装载效率分析图 ）通折线图知优化算法装载效率曲线致原始算法基达次设计求
图42 装载效率分析图
412混合算法实际应
A公司目前产品引例：
取常普通箱40＇GP尺寸12032mm(长)x2352mm(宽)x2393mm(高)载重28吨
设定长方体集装箱C长宽高分L102mW235mH24m
设箱子C容积VVL*W*H57528m³
底面积SSL*W102*2352397㎡
侧面积S’S’W*H235*24564㎡
前面积S’’S’’L*H102*242448㎡
集装箱极限荷重QQ28t
薄钢板1#薄钢板2#薄钢板3#薄钢板4#
厚钢板1#厚钢板2#厚钢板3#厚钢板4#厚钢板5#厚钢板6#构成装箱物品集合B元素分编号转换单位物品尺寸表4110
表43
编号（元素名称）
（长宽）（LiWi）
1
(51)
2
(53)
3
(22)
4
(21)
5
(21)
6
(52)
7
(31)
8
(33)
9
(52)
10
(72)
批次设置两辆货车运载：
目前A公司采取面积降序装载方式终方案图43 现行装载图示：
图43 现行装载图
装载货物36910剩1245789需换种型号集装箱者进行切割实现装箱效率化装箱效率77
采混合算法终输出方案图44 优化装载图示：
图44 优化装载图
选择装箱物品13456710剩289需换种型号集装箱者进行切割实现装箱效率化两箱效率达85
货运模式：
假设现10种货品编号1~10体积分：09040612150708065072046
相应价值55 21 47 775 5 34 61 45 37
集装箱体积100
荷重28t钢板密度取8gcm38tm3
1表示装入0表示装
出gbest
1 0 0 1 1 1 1 0 0 0
选择装载14567
通述程约束数变量数时候利三维背包问题数学模型解决A公司货运问题取较成果
42计算速度分析
样利MATLAB通生成机物品测试次设计混合算法实际应效记录运算时间
具体数表44示：
表44
实验序号
物品尺寸（长宽）
优化算法时
传BL法计算时
1
(43)(44)(44)(52)(24)(43)(25)(15)(42)(34)
354
316
2
(53)(51)(11)(55)(14)(42)(33)(14)(22)(24)
283
253
3
(53)(54)(43)(25)(54)(15)(32)(34)(52)(54)
312
28
4
(52)(53)(25)(44)(24)(25)(34)(54)(13)(51)
478
43
5
(22)(53)(45)(41)(21)(35)(35)(54)(12)(21)
398
36
6
(43)(25)(15)(42)(34)(43)(44)(44)(52)(24)
412
37
7
(25)(15)(42)(34)(52)(54)(34)(52)(54)(34)
389
347
8
(55)(51)(33)(53)(24)(33)(41)(14)(24)(22)
365
335
9
(42)(34)(35)(51)(11)(55)(41)(33)(24)(22)
402
359
10
(42)(33)(14)(12)(24)(22)(54)(44)(41)(55)
354
317
11
(53)(45)(41)(21)(35)(12)(35)(54)(11)(22)
405
36
12
(35)(54)(12)(54)(34)(15)(22)(54)(42)(34)
451
402
13
(11)(55)(14)(33)(41)(22)(42)(53)(54)(43)
374
35
14
(25)(45)(15)(32)(43)(52)(54)(21)(41)(22)
346
323
15
(14)(12)(24)(32)(22)(42)(24)(12)(13)(11)
311
278
16
(54)(12)(54)(35)(25)(44)(24)(52)(33)(44)
432
397
17
(43)(25)(15)(54)(42)(41)(21)(35)(32)(13)
365
335
18
(12)(53)(14)(12)(24)(32)(54)(54)(41)(11)
327
292
19
(45)(53)(34)(32)(11)(21)(51)(45)(31)(12)
351
304
20
(35)(54)(11)(22)(15)(54)(42)(15)(35)(32)
403
378
21
(32)(31)(15)(54)(42)(51)(41)(21)(45)(33)
452
409
22
(31)(51)(22)(45)(51)(32)(41)(33)(21)(52)
374
34
23
(24)(12)(13)(15)(45)(14)(12)(21)(35)(45)
345
323
24
(34)(42)(41)(11)(22)(31)(52)(55)(42)(53)
317
293
25
(55)(25)(45)(33)(53)(34)(32)(31)(14)(12)
432
395
26
(53)(51)(11)(55)(14)(42)(33)(14)(22)(24)
322
295
27
(53)(54)(43)(25)(54)(15)(32)(34)(52)(54)
448
4
28
(52)(53)(25)(44)(24)(25)(34)(54)(13)(51)
368
33
29
(22)(53)(45)(41)(21)(35)(35)(54)(12)(21)
402
367
30
(43)(25)(15)(42)(34)(43)(44)(44)(52)(24)
369
336
31
(25)(15)(42)(34)(52)(54)(34)(52)(54)(34)
365
329
32
(55)(51)(33)(53)(24)(33)(41)(14)(24)(22)
4
357
33
(42)(34)(35)(51)(11)(55)(41)(33)(24)(22)
345
312
34
(42)(33)(14)(12)(24)(22)(55)(44)(41)(55)
313
285
35
(53)(45)(41)(21)(35)(12)(35)(54)(11)(22)
405
361
36
(35)(54)(12)(54)(34)(15)(22)(54)(42)(34)
459
423
37
(11)(55)(14)(33)(41)(22)(42)(53)(54)(43)
372
332
38
(25)(45)(15)(32)(43)(52)(54)(21)(41)(22)
346
309
39
(14)(12)(24)(32)(22)(42)(24)(12)(13)(51)
318
283
40
(54)(12)(54)(35)(25)(44)(24)(52)(43)(44)
43
395
41
(43)(25)(15)(54)(42)(41)(21)(35)(32)(23)
355
316
42
(12)(53)(14)(12)(24)(32)(54)(54)(41)(11)
314
28
43
(24)(12)(13)(15)(45)(14)(12)(21)(35)(45)
389
347
44
(34)(42)(41)(11)(22)(31)(52)(55)(42)(53)
324
289
45
(55)(25)(45)(33)(53)(34)(32)(31)(14)(22)
405
389
46
(53)(51)(11)(55)(14)(42)(33)(14)(22)(24)
433
386
47
(53)(54)(43)(25)(54)(15)(32)(34)(52)(54)
371
336
48
(52)(53)(25)(44)(24)(25)(34)(54)(13)(51)
321
296
49
(22)(53)(45)(41)(21)(35)(35)(54)(12)(21)
311
277
50
(43)(25)(15)(42)(34)(43)(44)(44)(52)(24)
332
31
统计出优化算法均时37298s传统BL算法时325s优化算法极值搜索计算时稍增相距详见图45时启发式智算法（见图46）装载效率略低着相明显速度优势保证没牺牲装箱效率时缩短运算排布时间
图45 运算时
图46 启发式算法效率
五总结展
次装箱方法优化实实程中见货运集装箱布局分布产生量剩余空间浪费受车间中货物底盘装载问题启发萌生种研究种约束少效果算法念头作工业生产交通运输方面中常见搬运装载模式货物底盘物流存储运输等方面发挥巨效利箱子形状完全相求时箱子底盘边作相互行二维装箱问题数特点约束重合A公司货物钢板发现两者具高度相似性身目标约束优化问题约束会求解难度解数爆炸增长二维装箱问题求解难度三维装箱问题低萌生弱化约束数降维简化装箱想法
开始装箱问题进行研究时候第步首先问题分类着手
针装箱问题分类问题运输生产中两种常见集装箱装载方式种常见快递邮政定限数量容器装载物品数量定通装箱方法模式安排容器利率高二相反情况常见公司送货物流定数量定容器装载物品数量通常容器倍数目远远超现容器承载力需调度安排限集装箱空间装载货物限度利集装箱提高装载率称单集装箱问题
分类实种理想化模型实际生产中更遇第2类问题单箱装载问题结合实践活动手头资料涉算法思路相次设计课题选择针集装箱单箱装载问题
实际工作时发现A公司货运货模式存问题未做次货车货物做价值化结数学模型属装箱问题子问题定篇幅提供种优化算法提供种优化思路目终A公司济效益提高
贯彻次设计始终难题算法MATLAB编程实现学科四年学中接触编程皮毛次设计需花费量时间进行编程语言算法理念学时间限制想法结写成程序存少问题参数调试直没优阶段
实际装箱观察总结选择BF算法算法程序冗长情况数目庞实际装箱序相算法
缩短搜索时长提高搜索效率通俗易懂利期维护修改选择PSO粒子群算法核心理简单计算效果良新颖算法设计时长限制选简单粒子群算法目标变量基数迭代次数较少情况简单粒子群算法然发挥出错效果
N叉树剩余空间部分装箱问题新研究成果算法更加贴合潮流尝试添加混合算法中常常出现坐标变动容易导致空间划分错误直接装箱序列出错装箱失败总结编写程序时候身装箱情况考虑周坐标算法存漏洞导致部分程序量优化空间果方面进行深入研究该部分应重点研究学点
通MATLABGUI程序设计装箱结果组合视化程序移植目前装箱问题优化效果检验重手段途径囿知识储备设计时长次毕业设计没做GUI部分期MATLAB深入学熟练掌握GUI设计应结合问题深层理解秉承工业工程优化止境理念优化算法断改善提高
参考文献
[1] 陈希王宁生基遗传算法车间设备虚拟布局优化技术研究[J]东南学报200434(5)
[2] George J ARobinson D F A heuristic for packing boxes into a container Computers and Operations Research 19807(3) 147156
[3] Bortfeldt AGehring H A tabu search algorithm for weakly heterogeneous container loading problems OR Spectrum199820(4) 237250
[4] PISINGERDA tree search heuristic for the container loading problem IJJRicerca Operativa 1998283148
[5] 张德富彭煜朱文兴陈火旺求解三维装箱问题混合模拟退火算法计算机学报200932(11) 21472156
[6] YuLiang Wu Wenqi Huang Siuchung Lau CK Wong An effective qusibuman based heuristic for solving the rectangle packing problem[J] European Joumal of Operational Research2002 141 341358
[7] Bortfeldt A Gehring H A tabu search algorithm for weakly heterogeneous container loading problems OR Spectrum199820(4) 237250
[8] Moura A OliveiraJ F A GRASP approach to the containerloading problem IEEE Intelligent Systems 200520(4)5057
[9] Hopper ETurton BCH An empirical investigation of metaheuristic and heuristic algorithms for a 2D packing problem European Journal of Operational Research 2001128(1)3457
[10] Shi X H Liang Y C Lee H P et al An improved GA and a novel PSOGAbased hybrid algorithm[J] Information Processing Letters 2005 93(5)p255261
[11] Clerc M Kennedy J The particle swarm explosion stability and convergence in a multidimensional complex space[J] IEEE Transactions on Evolutionary Computation 2002 6(1)073
[12] 张德富彭煜张丽丽求解三维装箱问题层启发式搜索算法[J]计算机学报201235(12)25532561
[13] Zhu W Lim A A new iterativedoubling GreedyLookahead algorithm for the single container loading problem[J] European Journal of Operational Research 2012222(3)408417
[14] 刘胜 凤华 吕宜生等 求解三维装箱问题启发式正交二叉树搜索算法[D] 计算机学报 2015 38(8)15301543
[15] Coffman EGjun Garey MR Johnson DS Approximation algorithms for binpacking an updated survey[M] Approximation algorithms for NPhard problems PWS Publishing Co 1996
[16] Khuri S Back T Heitkotter J An evolutionary approach to combinational optimization problem[ A] Proe of 22nd Annual Computer Science Conference [ C] New York Phoenix AZ ACM Press 1998 6673
[17] Chatterjee A Siarry P Nonlinear Inertia Weight Variation[J]．Computers and operations Research200633(3)859871
[18] 梁旭黄明宁涛等现代智优化混合算法应第二版[M]北京：电子工业出版社20144251
[19] 雷英杰张善文李续武等遗传算法工具箱应[M]西安：西安电子科技学出版社20054560
[20] 周雪刚 非凸优化问题全局优化算法[D] 长沙：中南学博士学位文 2010112
[21] 易树 郭伏基础工业工程[M] 北京机械工业出版社 2006
水直线判：
Line_Judgement
设函数Line_Judgement判断竖直移动两条线段否会相交果相交计算输出两条线段竖直距离
function [flagHD]Line_Judgement(line1line2)
情况1左方相交时line1完全line2左方时竖直距离两坐标差两条线段竖直移动会相交
if line1(3)
HDline1(2)line2(2)时竖直距离两坐标差
情况二line2line1右方第种情况两条线段竖直移动会相交
elseif (line1(3)>line2(1))&&(line1(3)
HDline1(2)line2(2)
情况三line2line1左方线段存重合移存相交性
elseif (line1(1)>line2(1))&&(line1(1)
HDline1(2)line2(2)
情况四line1完全line2右方竖直移动会相交情况
elseif line1(1)>line2(3)
flag0
HDline1(2)line2(2)
第五种情况line2完全line1包含1左端横坐标2左端横坐标12相交会出现竖直方移动
elseif (line1(1)
flag1
HDline1(2)line2(2)
else
flag1
HDline1(2)line2(2)
end
End
顶点坐标：
Point_Coor
利顶点坐标标注增加定物品长度L宽度W作条件Point_Coor函数求[lxlyrxry]
设物品右角顶点坐标二维数组RPXY时定义二维数组Item储存物品长宽 定义RBPXY物品右角顶点坐标LBPXY 物品左角顶点坐标[lxlyrxry]端水线坐标：
function BottomLinePoint_Coor(ItemRPXY)
RBPXY[RPXY(1)RPXY(2)item(2)] LBPXY[RPXY(1)item(1)RPXY(2)item(2)]
BottomLine[LBPXYRBPXY]
End
降距离计算：
Down_H
设item物品长度宽度表示矩阵[长度宽度]
Itemi维数组（i表示已装载箱子数目）表示已装载箱子长度宽度[长度宽度]
itemRP：时物品右角顶点坐标[xy]
RPNXY：分配二维数组检索完毕已放箱子中物品右角顶点坐标存储格式Item
输出dH：箱子中位置物品降高度直作判条件前剩余空间否满足装载物品进行判断输出dH正负分代表目前剩余空间容纳剩余空间容纳
部分函数说明：size（）：获取矩阵行数列数
sort({＇descend＇})：降序排列
aH[] 储存满足相交条件降距离数组
function MaxDownHDown_H(itemItemitemRPRPNXY)
BottomLinePoint_Coor(itemitemRP) Point_Coor
求物品端水线段标示[leftxleftyrightxrighty]
RP_NUMsize(RPNXY1) 获取数组行数出箱子物品数目
if RP_NUM~0
sRPNXYsort(RPNXY3{＇descend＇}) RPNXYY坐标降序排列
sRBPNXYsRPNXY
sRBPNXY(2)sRPNXY(2)Item(sRPNXY(1)1) RPNXYY坐标降序排列左角顶点坐标
topLine[sRBPNXY(23)sRPNXY(23)] 物品Y坐标降序排列物品端水线段左右两端坐标[leftxleftyrightxrighty]
循环流程
aH[] 定数组储存
While i
[flagHD]Line_Judgement(BottomLinetopLine(i))
if (flag1)&&(HD>0)
aH[aHHD]
end
End
果相交条件满足表明装入BF算法直接降箱子底端
if isempty(aH)
downHitemRP(2)item(2)
else 果存满足相交条件物品降距离aH中值
downHmin(aH)
end
else
downHitemRP(2)item(2) 时箱子空物品放置底端
End
End
箱子装载左移距离进行计算：
利指针f表示相交情况
指针指相交路径输出竖直线段彼距离
SLine_Judgement
竖直线段位置关系分5种情况：1）方相交2）方相交3）方相交4）方相交5）line1完全包含line2
输入第条线段line1：[topxtopybottomxbottomy]
输入第二条线断line2：[topxtopybottomxbottomy]
输出flag：指针等零者表示相交情况前者相交者相交输出hd：相交正反负数
function [flagHD]SLine_Judgement(line1line2)
第种情况line1完全line2方两条线段移会相交
if line1(4)>line2(2)
flag0
HDline1(1)line2(1)
第二种情况line2line1方时移会重合
elseif (line1(4)
flag1
HDline1(1)line2(1)
第三种情况line1line2方两条线段移会相交
elseif (line1(2)
flag1
HDline1(1)line2(1)
第四种情况line2完全line1方意移法相交
elseif line1(2)
HDline1(1)line2(1)
第五种情况line1完全包含line2
elseif (line1(4)
flag1
HDline1(1)line2(1)
（ else
flag1
HDline1(1)line2(1)）
end
end
顶点坐（水）：
Point_Coor2
根物品右角顶点坐标利物品长度L宽度WPoint_Coor2函数求出物品物品左端竖直线段两端坐标[topxtopybottomxbottomy]
设物品右角顶点坐标二维数组RPXY时定义二维数组item输入
储存物品长宽 定义LUPXY物品左顶点坐标LBPXY 物品左角顶点坐标：
输出leftLine：物品左端竖直线段两端坐标表示[topxtopybottomxbottomy]
function leftLinePoint_Coor2(itemRPXY)
LUPXY[RPXY(1)item(1)RPXY(2)] 物品左角顶点坐标
LBPXY[RPXY(1)item(1)RPXY(2)item(2)] 物品左角顶点坐标
leftLine[LUPXYLBPXY]
End
左移距离计算：
Left_W
设item物品长度宽度表示矩阵[长度宽度]
Itemi维数组（i表示已装载箱子数目）表示已装载箱子长度宽度[长度宽度]
itemRP：时物品右角顶点坐标[xy]
RPNXY：设二维数组存储前箱子中物品右角顶点坐标表示[长度宽度]
输出LeftW：物品item箱子意位置降高度时利降高度进行装箱判果LeftW正数装入前剩余空间果负数装入前箱子剩余空间
部分函数说明：size（）：获取矩阵行数列数
sort({＇descend＇})：降序排列
aw[] 储存满足相交条件左移距离数组
function MaxLeftWLeft_W(itemItemitemRPRPNXY)
leftLinePoint_Point_Coor2(itemitemRP) 物品左端竖直线段两端坐标[topxtopybottomxbottomy]
RP_NUMsize(RPNXY1) 通数组行数提取箱子物品数目
循环体
if RP_NUM~0
sRPNXYsort(RPNXY2{＇descend＇}) RPNXYX坐标降序排列
sRBPNXYsRPNXY
sRBPNXY(3)sRPNXY(3)Item(sRPNXY(1)2) RPNXYX坐标降序排列右角顶点坐标
rightLine[sRPNXY(23)sRBPNXY(23)] 物品X坐标降序排列右端线段两端坐标变[topxtopybottomxbottomy]
循环体
aW[] 定数组储存相交情况左移距离
for i1RP_NUM
注释函数 [flagHD]SLine_Judgement(leftLinerightLine(i))
if (flag1)&&(HD>0)
aW[aWHD]
end
end
果存满足相交条件物品直接移动箱子左端
if isempty(aW)
leftWitemRP(1)item(1)
else 果物品满足相交条件左移距离aW中值
leftWmin(aW)
end
else
leftWitemRP(1)item(1)
end
End
坐标：
Update_itemRPFPos
利述函数计算出itemRPdownHleftWitemitemRPRPNXY
输出itRPXYFRP： 物品item箱子中降左移确定位置坐标进行定位输出
提函数：
zeros数组zeros(MN) 者 zeros([MN])：生成M行N列零矩阵
function itRPXYUpdate_itemRP(itemRPdownHleftW)
itRPXYzeros(12)
itRPXY(2)itemRP(2)downH y坐标
itRPXY(1)itemRP(1)leftW x坐标
End
function finalRPFPos(itemItemitemRPRPNXY)
物品位置法改变跳出循环
while 1
downHdownHAtPoint(itemItemitemRPRPNXY) 计算物品item箱子itemRP位置处降高度
leftW0
itemRPUpdate_itemRP(itemRPdownHleftW) 更新物品item前位置右角顶点坐标
downH0
leftWleftWAtPoint(itemItemitemRPRPNXY) 计算物品item箱子itemRP位置处左移动距离
itemRPUpdate_itemRP(itemRPdownHleftW) 更新物品item前位置右角顶点坐标
if (downH0)&&(leftW0)
FRPitemRP
break
end
end
End
目前装箱序列进行判断通左角顶点坐标辨否存重合现象果序列排布重合flagOL1视装箱失败
Item(RPNXY(i1))长度
Item(RPNXY(i1))宽度
Item(RPNXY(i1))左角顶点坐标
function flagOLoverlap(itemItemitemRPRPNXY)
flagOL0 初始化存重合情况
itemLBP[itemRP(1)item(1)itemRP(2)item(2)] 左角顶点坐标
A[itemLBPitem]
numsize(RPNXY1) 箱子中物品数目
if num>0
for i1num
SbxItem(RPNXY(i1)1)
SbyItem(RPNXY(i1)2)
LBPXY[RPNXY(i2)SbxRPNXY(i3)Sby] B[LBPXYSbxSby]
arearectint(AB) 判断条件利AB两者计算输出面积关系
果两者复合橡胶条件满足列关系
if area>0
flagOL1
break
end
end
end
end
二叉树编程思路：
集装箱空箱容积构成元胞数组
clear
clc
close all
for item1：n
if 容积
Else
When箱子放入空间中
搜索适应空间
BL算法直位置固定
右角坐标itemRP妨设（xy）
计算S2S3
建立左子树（剩余空间S2）
S2X*(WY) S2L*(WY)
||
建立右子树（剩余空间S3）
S3(LX)*W S3(LX)*(WY)
集合B｛｝已放入Bi编号
BL算法更新LWitemRP
itemitem+1
end
PSO算法程序：
初始化种群
Dim10维度
xSize20 种群数
maxgen200 迭代次数
c115c215 加速子
w08 定义惯性子
Drepmat(dxSize1) d扩展成30*10矩阵
Wrepmat(wxSize1) w扩展30*10矩阵
xround(rand(xSizeDim)) 机30*10矩阵
vrand(xSizeDim) 机30*10速度矩阵
xbestzeros(xSizeDim) 单粒子初始佳位置
fxbestzeros(xSize1) xbext适应度
gbestzeros(1Dim) 全局优解
fgbest0 获适应度关全局优极值
iter0
while iter
fxFX粒子适应度公式（42）
for i1xSize
if w>Q
fx(i)0超重量适应度0 果适应度函数带重量约束时PSO编程时带
End
end
for i1xSize
if fxbest(i)
xbest(i)x(i)
end
end
if fgbest
gbestxbest(g) 存粒子佳适应度
end
for i1xSize
if x(i)gbest
x(i)round(rand(1Dim)) 记录已优位置粒子赋予新值防止陷入局部优解
end
end
R1rand(xSizeDim)
R2rand(xSizeDim)
vv*w+c1*R1*(xbestx)+c2*R2*(repmat(gbestxSize1)x)速度迭代公式PSO核心公式产生新速度
xx+v
for i1xSize 更新粒子群位置
for j1Dim
if x(ij)<05
x(ij)0
else x(ij)1 粒子位置（01）两种状态边缘化处理
end
end
end
End
fgbest
sgbestsum((s*gbest)＇)
disp(gbest)
输出算法程图
figure
plot(maxgenfgbest)
xlabel(＇粒子循环代目＇)
ylabel(＇适应函数取值＇)
货运模式编程思路：
n＝10
aj[]体积数组
cj[]价指数组
gj[]重量数组
b背包容积限制
w背包重量限制
a[]体积数组
c[]价值数组
Dim20设定粒子维数
xSize100初始种群数目
MaxIt100迭代次数值
c11
c21
w08根验判断取惯性系数08
Arepmat(axSize1)a扩展成30*10矩阵
Crepmat(cxSize1)c扩展成30*10矩阵
Grepmat(gxSize1)g扩展
xzeros(rand(xSizeDim))生成01矩阵标记粒子初始位置
vzeros(xSizeDim)定义初速度
xbestrand(xSizeDim)单粒子初始佳位置
fxbestrand(xSize1)xbest适应度
gbestzeros(1Dim)初始优解
fgbest0第次先群体优值赋0
迭代循环算法
iter0
while iter
fxsum((C*x)＇)统计目前背包物品价值
sxsum((A*x)＇)统计目前背包物品体积
gxsum((G*x)＇)统计目前背包物品价值质量
for i1xSize
if sx(i)>b||gx(i)>w
fx(i)0包物品体积超限制时期适应度设置1
end
end
for i1xSize
if fxbest(i)
xbest(i)x(i)
end
end
if fgbest
gbestxbest(g)
end
for i1xSize
if x(i)gbest
x(i)round(rand(1Dim))
end
end
R1rand(xSizeDim)
R2rand(xSizeDim)
vv*w+c1*R1*(xbestx)+c2*R2*(repmat(gbestxSize1)x)速度迭代公式产生新速度
xx+v更新粒子群位置
for i1xSize
for j1Dim
if x(ij)<05
x(ij)0
else x(ij)1
end
end
End
End
fgbest
sgbestsum((a*gbest)＇)
gbest
机物品生成：
命令：Bin[1010] 方便计算记箱子长度宽度10
itemNum10 物品数目
Itemceil(05*Bin(1)*rand(itemNum2))机生成10物品
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
