改进动态规划算法求解同尺寸物品的装箱问题

1

作者 陈燕 刘秋鹏 胡小春 《机械设计与制造》 北大核心 2024年第9期125-129,135,共6页

装箱问题是在一个容量有限的箱内尽可能多的装入各类物品。文中研究同尺寸的物品装箱问题,在一个集装箱中装入大小规格一致的小箱,使集装箱的空间利用率最大,即装入的小箱数量最多。采用分层装载思想和同质条带的布局方式设计装箱方案,... 装箱问题是在一个容量有限的箱内尽可能多的装入各类物品。文中研究同尺寸的物品装箱问题,在一个集装箱中装入大小规格一致的小箱,使集装箱的空间利用率最大,即装入的小箱数量最多。采用分层装载思想和同质条带的布局方式设计装箱方案,利用改进的动态规划算法求解层装的布局问题,使用背包算法求解同质条带内的小箱布局问题。与已有文献算法相比,文中算法的运行速度更快,得到的装箱方案更便捷,利于装箱操作,而且在一定程序上提高了装箱率。使用国际标准尺寸的集装箱和随机尺寸的物品小箱进行实验,结果表明文中算法比传统的动态规划算法有更好的求解效果,可适用于实际的集装箱物品装载。 展开更多

关键词 三维集装箱 动态规划 同尺寸物体装载 装箱问题 分层装载 背包问题

下载PDF 职称材料

基于最大最小蚁群算法的智能装载方法 被引量：2

2

作者 葛玮 徐卫红 程海水 《山东农业大学学报（自然科学版）》 CSCD 北大核心 2014年第3期366-371,共6页

三维装箱问题在现实生活中有着广泛的应用,是具有复杂约束的组合优化问题,理论上属于NP-hard问题。针对贪心算法通常得到的是局部最优解以及基本蚁群算法存在不足等问题,本文首先给出了启发式装箱规则,然后结合最大最小蚁群算法对装载... 三维装箱问题在现实生活中有着广泛的应用,是具有复杂约束的组合优化问题,理论上属于NP-hard问题。针对贪心算法通常得到的是局部最优解以及基本蚁群算法存在不足等问题,本文首先给出了启发式装箱规则,然后结合最大最小蚁群算法对装载顺序进行优化,提出了一个求解三维装箱问题的混合蚁群算法,最后通过实验对比验证了该算法的有效性和优越性,并给出了三维效果展示图。 展开更多

关键词 三维装箱 启发式 最大最小蚁群算法

下载PDF 职称材料

求解三维装箱问题的混合模拟退火算法 被引量：65

3

作者 张德富 彭煜 +1 位作者 朱文兴 陈火旺 《计算机学报》 EI CSCD 北大核心 2009年第11期2147-2156,共10页

提出了一个高效求解三维装箱问题(Three Dimensional Container Loading Problem 3D-CLP)的混合模拟退火算法.三维装箱问题要求装载给定箱子集合的一个子集到容器中,使得被装载的箱子总体积最大.文中介绍的混合模拟退火算法基于三个重... 提出了一个高效求解三维装箱问题(Three Dimensional Container Loading Problem 3D-CLP)的混合模拟退火算法.三维装箱问题要求装载给定箱子集合的一个子集到容器中,使得被装载的箱子总体积最大.文中介绍的混合模拟退火算法基于三个重要算法:(1)复合块生成算法,与传统算法不同的是文中提出的复合块不只包含单一种类的箱子,而是可以在一定的限制条件下包含任意种类的箱子.(2)基础启发式算法,该算法基于块装载,可以按照指定装载序列生成放置方案.(3)模拟退火算法,以复合块生成和基础启发式算法为基础,将装载序列作为可行放置方案的编码,在编码空间中采用模拟退火算法进行搜索以寻找问题的近似最优解.文中采用1500个弱异构和强异构的装箱问题数据对算法进行测试.实验结果表明,混合模拟退火算法的填充率超过了目前已知的优秀算法. 展开更多

关键词 三维装箱 启发式算法 模拟退火

下载PDF 职称材料

求解三维装箱问题的启发式正交二叉树搜索算法 被引量：32

4

作者 刘胜 朱凤华 +1 位作者 吕宜生 李元涛 《计算机学报》 EI CSCD 北大核心 2015年第8期1530-1543,共14页

文中提出了一种求解三维装箱问题的启发式二叉树搜索算法,首先将所有箱子组合成多个优条,每个优条中的箱子沿容器高度方向排成一列;接着开始构建二叉树,其根节点表示空的装箱方案,每个树节点沿长度方向增加一排优条形成左子树节点,沿宽... 文中提出了一种求解三维装箱问题的启发式二叉树搜索算法,首先将所有箱子组合成多个优条,每个优条中的箱子沿容器高度方向排成一列;接着开始构建二叉树,其根节点表示空的装箱方案,每个树节点沿长度方向增加一排优条形成左子树节点,沿宽度方向增加一排优条形成右子树节点,二叉树必须扩展到所有叶子节点都无法再放入任何剩余的箱子为止,所有叶子节点中填充率最高的装箱方案即为最终结果.该算法满足三维装箱的3个著名的约束条件.在多样性最强的测试算例中,该文方法相对于现有最优秀装箱算法装箱率有显著提高. 展开更多

关键词 三维装箱 启发式算法 二叉树

下载PDF 职称材料

求解三维装箱问题的多层树搜索算法 被引量：21

5

作者 刘胜 沈大勇 +3 位作者 商秀芹 赵红霞 董西松 王飞跃 《自动化学报》 EI CSCD 北大核心 2020年第6期1178-1187,共10页

提出了一种求解三维装箱问题的多层树搜索算法,该算法采用箱子–片–条–层–实体的顺序生成装载方案,装载方案由实体表示.该算法由3层搜索树构成.第1层为三叉树,每个树节点的3个分叉分别对应向实体中填入XY面平行层、XZ面平行层、YZ面... 提出了一种求解三维装箱问题的多层树搜索算法,该算法采用箱子–片–条–层–实体的顺序生成装载方案,装载方案由实体表示.该算法由3层搜索树构成.第1层为三叉树,每个树节点的3个分叉分别对应向实体中填入XY面平行层、XZ面平行层、YZ面平行层;第2层为二叉树,每个树节点的两个分叉分别对应向层内装载两个相互垂直的最优条;第3层为四叉树,用于将同种的多个箱子生成片.在同时满足摆放方向约束和完全支撑约束的前提下,该算法求解BR12~BR15得到的填充率高于现有装箱算法. 展开更多

关键词 三维装箱 墙构造 水平层构造 多层树

下载PDF 职称材料

基于动作空间的三维装箱问题的确定性高效率求解算法 被引量：20

6

作者 何琨 黄文奇 《计算机学报》 EI CSCD 北大核心 2014年第8期1786-1793,共8页

三维装箱问题要求将有限个三维矩形物体尽可能多地装入到一个三维矩形箱子中,使得箱子的填充率即体积利用率最大.在求解三维装箱问题的穴度算法的基础之上,进一步做了以下改进:(1)将当前剩余空间中可能放入的每个体积最大的三维矩形虚... 三维装箱问题要求将有限个三维矩形物体尽可能多地装入到一个三维矩形箱子中,使得箱子的填充率即体积利用率最大.在求解三维装箱问题的穴度算法的基础之上,进一步做了以下改进:(1)将当前剩余空间中可能放入的每个体积最大的三维矩形虚拟物体所对应的空间定义为动作空间,在动作空间内放入物体并使穴度的定义体现放入物体与动作空间的吻合程度;(2)在物体放入位置的选择上直接体现"金角银边草肚皮"的思想,每一步只选择最靠近箱子边缘的一个动作空间来装载物体;(3)结合捆绑策略,将形状大小相同的物体捆绑为一个较大的矩形块进行放入,对捆绑块形状大小的选择为在不超出动作空间的前提下尽量用物体填满该空间的两至三个维度.实验结果表明,改进后的穴度算法在付出很少的开销代价的情况下显著地提高了箱子的填充率. 展开更多

关键词 三维布局 装箱 启发式 动作空间 穴度

下载PDF 职称材料

基于K-means的航空行李快速装箱算法 被引量：9

7

作者 张长勇 吴智博 王艳芳 《包装与食品机械》 CAS 北大核心 2019年第3期38-42,4,共6页

以航空行李装箱为研究对象,提出了一种高效算法。基于K-means聚类从体积、质量两方面考察每件行李,按实际需求将行李分为若干小类,拆散一个强异构问题为多个弱异构问题,结合“砌墙式”思想,设计了“面填充”与“箱填充”两阶段码放策略... 以航空行李装箱为研究对象,提出了一种高效算法。基于K-means聚类从体积、质量两方面考察每件行李,按实际需求将行李分为若干小类,拆散一个强异构问题为多个弱异构问题,结合“砌墙式”思想,设计了“面填充”与“箱填充”两阶段码放策略。采用实际旅客行李数据与国际经典算例(B R1~BR7)试验,证明了布局的合理性与效率的突出优势。并且,K-means聚类的引入使算法具有解算时间随异构性的增强而降低的优良特性,架起了机器学习算法与传统装箱问题的桥梁。 展开更多

关键词 航空行李 三维布局 快速装箱 K-MEANS聚类 组合优化

下载PDF 职称材料

基于K-means与关键点的组合行李码放算法 被引量：7

8

作者 张长勇 吴智博 《包装工程》 CAS 北大核心 2019年第9期90-95,共6页

目的为了解决当前航空行李码放流程中存在的劳动密集、效率低下的问题,开展行李码放算法研究。方法搭建含有重量、体积和货舱空间约束的航空行李码放数学模型,采用聚类、排序、关键点构建策略,设计一种K-means聚类与"关键点"... 目的为了解决当前航空行李码放流程中存在的劳动密集、效率低下的问题,开展行李码放算法研究。方法搭建含有重量、体积和货舱空间约束的航空行李码放数学模型,采用聚类、排序、关键点构建策略,设计一种K-means聚类与"关键点"思想相结合的组合式算法。结果采用100件真实旅客行李数据进行了实验,结果表明算法给出的布局方案规划合理,垛型左右两侧质量之差低于1%,满足了货舱的空间约束与载重平衡约束。结论算法具备在复杂环境下得到优良布局方案的能力,K-means聚类的引入也将机器学习领域的聚类算法引入装箱问题,架起了机器学习算法与传统装箱算法的桥梁,为今后装箱问题算法的设计提供了一条新思路。 展开更多

关键词 航空行李 三维装箱 K-MEANS聚类 组合算法

下载PDF 职称材料

基于混合遗传算法的杂货船装载优化问题 被引量：7

9

作者 朱莹 向先波 杨运桃 《中国舰船研究》 CSCD 北大核心 2015年第6期126-132,共7页

杂货船的装载问题属于典型的三维装箱问题,在分析杂货船装载问题的特点的基础上,以船舱空间利用率最大为目标,建立杂货船装载问题的数学模型。针对模型特点,提出一种结合启发式算法和遗传算法的混合遗传算法,设计一种新的三空间划分方法... 杂货船的装载问题属于典型的三维装箱问题,在分析杂货船装载问题的特点的基础上,以船舱空间利用率最大为目标,建立杂货船装载问题的数学模型。针对模型特点,提出一种结合启发式算法和遗传算法的混合遗传算法,设计一种新的三空间划分方法,并对此算法进行仿真试验验证。以文献[3]的一组经典测试数据为实例,经与同类装箱问题中的同类型算法进行对比分析,发现空间利用率达到了92.94%,与其他算法的结果相比具有明显的优势,验证了优化算法的有效性。 展开更多

关键词 杂货船 三维装箱 启发式算法 遗传算法

下载PDF 职称材料

基于混合智能算法的航空集装箱多目标装载优化

10

作者 张长勇 张春婷 《包装工程》 CAS 北大核心 2024年第15期215-225,共11页

目的针对航空集装箱多目标装载优化问题,综合提升航空货物的装载效率,降低装载成本,确保装载安全。方法结合航空货物装载实际情况,将容积利用率、载重利用率和重心偏移量作为优化目标,充分考虑载重、体积等7类约束,构建航空集装箱多目... 目的针对航空集装箱多目标装载优化问题,综合提升航空货物的装载效率,降低装载成本,确保装载安全。方法结合航空货物装载实际情况,将容积利用率、载重利用率和重心偏移量作为优化目标,充分考虑载重、体积等7类约束,构建航空集装箱多目标装载优化模型。设计一种混合智能算法对该模型进行求解,先采用三空间分割策略结合改进遗传算法生成初步装载方案,再结合大规模多目标进化算法深度优化,综合考虑各目标函数值,生成最终的装载方案。结果采用国际BR算例和真实货物数据进行测试,实验结果表明,针对BR算例中不同异构型货物的平均填充率超过93%,在真实货物装载下,平均容积利用率和载重利用率分别为90.56%、76.40%,平均重心偏移量不超过5 cm。结论所提出的装载算法对航空集装箱多目标装载场景具有良好的适应性,有助于提升航空货物的运输效率和运输安全性。 展开更多

关键词 三维装箱 集装箱装载 多目标优化 三空间分割

下载PDF 职称材料

求解集装箱装载问题的混合蚁群模拟退火算法

11

作者 李想 袁锐波 杨灏泉 《包装工程》 CAS 北大核心 2024年第11期163-174,共12页

目的针对物流行业中存在的大规模、复杂、多规格货物的集装箱装载问题,提出一种基于塔装载启发式算法、二维装载点启发式算法、蚁群模拟退火算法的混合算法。方法首先,采用塔装载启发式算法将三维待装箱装载成塔集,即将三维装箱问题降... 目的针对物流行业中存在的大规模、复杂、多规格货物的集装箱装载问题,提出一种基于塔装载启发式算法、二维装载点启发式算法、蚁群模拟退火算法的混合算法。方法首先,采用塔装载启发式算法将三维待装箱装载成塔集,即将三维装箱问题降为二维装箱问题,有效降低集装箱的装载规模;其次,蚁群算法通过融入信息素选择更新策略,并利用自适应信息素挥发系数来提升算法整体的收敛速度,同时结合模拟退火算法对每代优秀路径集进行局部搜索,避免算法因收敛过快而陷入局部最优;最后,将蚁群模拟退火算法与二维装载点启发式算法相结合,优化每座塔的装载顺序和放置姿态,寻找最优的装载方案。结果实验证明,在250组算例中,采用混合算法后,集装箱的平均空间利用率为90.92%,优于其他3种对比算法。结论设计的混合蚁群模拟退火算法适用于解决大规模集装箱装载问题。 展开更多

关键词 三维装箱 大规模集装箱装载 启发式算法 蚁群算法 模拟退火算法

下载PDF 职称材料

基于优先保持策略遗传算法的三维装箱问题 被引量：6

12

作者 陈元文 《包装工程》 CAS 北大核心 2021年第15期211-218,共8页

目的针对以空间利用率最大为目标的三维装箱问题,设计基于优先保持策略的改进遗传算法,并对其进行求解。方法首先,在分析现有相关研究存在不足的基础上,提出优先保持策略的基本改进理念;其次,针对问题特点,设计改进遗传算法的基本流程,... 目的针对以空间利用率最大为目标的三维装箱问题,设计基于优先保持策略的改进遗传算法,并对其进行求解。方法首先,在分析现有相关研究存在不足的基础上,提出优先保持策略的基本改进理念;其次,针对问题特点,设计改进遗传算法的基本流程,重点对交叉和变异的详细实现进行介绍;最后,通过实验仿真的方式,对求解结果和算法性能进行对比分析。结果实验证明,在所用算例中,算法的求解结果优于对比算法约14%,且收敛更为稳定,时耗满足一般需求。结论文中算法具有较优异的迭代性能。 展开更多

关键词 三维装箱 优先保持策略 遗传算法 实验仿真

下载PDF 职称材料

基于货物组合的三维装箱启发式算法 被引量：5

13

作者 王祎楼 《物流工程与管理》 2018年第12期73-75,共3页

以三维多层货物装载布局问题为研究对象,结合货物装载的实际需要,综合考虑集装箱的重心约束、独占性约束、总体积约束、载重量约束等,将最大化集装箱的空间利用率作为首要优化目标、最大化载重率为次要目标,建立了集装箱三维装载模型,... 以三维多层货物装载布局问题为研究对象,结合货物装载的实际需要,综合考虑集装箱的重心约束、独占性约束、总体积约束、载重量约束等,将最大化集装箱的空间利用率作为首要优化目标、最大化载重率为次要目标,建立了集装箱三维装载模型,并采用启发式算法,引入货物块的概念将具有相同特征的货物组合成为新的长方体货物快,以达到更高的空间利用率。实例证明该算法与模型能够快速制定合理的货物装载布局方案,有效求解三维装箱问题。 展开更多

关键词 三维装箱 货物块 启发式算法 空间利用率

下载PDF 职称材料

集装箱船装载问题的混合遗传智能优化算法 被引量：4

14

作者 朱莹 向先波 +1 位作者 杨运桃 王英伟 《华中科技大学学报（自然科学版）》 EI CAS CSCD 北大核心 2015年第S1期448-451,共4页

为了提高集装箱的利用率,以空间利用率最大化为优化目标,建立集装箱船装载问题的数学模型,提出了一种新型混合遗传智能算法.算法中设计了一种包含货物装填顺序和放置状态的两段编码方式,构造适应集装箱船装载问题的部分映射交叉算子、... 为了提高集装箱的利用率,以空间利用率最大化为优化目标,建立集装箱船装载问题的数学模型,提出了一种新型混合遗传智能算法.算法中设计了一种包含货物装填顺序和放置状态的两段编码方式,构造适应集装箱船装载问题的部分映射交叉算子、两点交叉算子、顺序逆转变异算子和基本位变异算子,并对此算法进行了仿真验证.以Loh和Nee的两组经典测试数据为实例进行算法测试,空间利用率分别达到94.3%和91.4%,与相同类型装箱算法进行对比,空间利用率有明显提升,验证了混合遗传智能优化算法的有效性. 展开更多

关键词 集装箱船 三维装箱 遗传算法 启发式算法 遗传编码

原文传递

求解长方体Packing问题的捆绑穴度算法 被引量：3

15

作者 何琨 黄文奇 《软件学报》 EI CSCD 北大核心 2011年第5期843-851,共9页

在穴度方法的基础上结合捆绑策略,为三维欧氏空间中长方体Packing问题的求解提供了一种高效的启发式算法.试算了由Loh和Nee于1992年提出的15个经典算例,对其中的困难算例LN2,取得了98.2%的空间利用率,比目前的最好纪录高1.6个百分点;对... 在穴度方法的基础上结合捆绑策略,为三维欧氏空间中长方体Packing问题的求解提供了一种高效的启发式算法.试算了由Loh和Nee于1992年提出的15个经典算例,对其中的困难算例LN2,取得了98.2%的空间利用率,比目前的最好纪录高1.6个百分点;对另一个困难算例LN6,取得了96.2%的空间利用率,与目前的最好纪录持平;对其他13个较为容易的算例均取得了最优的布局,与目前的最好纪录持平.总体而言,15个算例的平均空间利用率为70.96%,在整体空间利用率上达到了较好的效果. 展开更多

关键词 三维布局 装箱 拟人 穴度 捆绑

下载PDF 职称材料

新型集装箱立体堆场及其规划设计 被引量：1

16

作者 温富荣 宋海涛 耿卫宁 《物流技术》 2022年第6期95-100,共6页

针对集装箱码头堆场能力紧张和作业效率提升困难等问题,分析传统集装箱堆场模式的不足,研究立体仓储技术与集装箱堆场应用结合的新型立体堆场,并针对新型集装箱立体堆场进行了规划设计。通过比较分析表明,新型立体堆场可以提高集装箱堆... 针对集装箱码头堆场能力紧张和作业效率提升困难等问题,分析传统集装箱堆场模式的不足,研究立体仓储技术与集装箱堆场应用结合的新型立体堆场,并针对新型集装箱立体堆场进行了规划设计。通过比较分析表明,新型立体堆场可以提高集装箱堆场利用率、降低翻箱率、提高作业效率、降低单箱能耗,有较高的应用价值和推广空间。 展开更多

关键词 集装箱 立体堆场 规划设计

下载PDF 职称材料

集装箱装箱辅助决策系统 被引量：2

17

作者 王朝霞 《上海海事大学学报》 北大核心 2011年第4期43-48,共6页

为提高集装箱空间利用率,根据集装箱装箱作业的实际操作要求,开发提供辅助性决策的集装箱装箱系统软件.该软件由参数设置、环境设置、计划制订、装载计算等4个模块组成,充分考虑集装箱装箱过程中的复杂约束,采用启发式算法对模型进行求... 为提高集装箱空间利用率,根据集装箱装箱作业的实际操作要求,开发提供辅助性决策的集装箱装箱系统软件.该软件由参数设置、环境设置、计划制订、装载计算等4个模块组成,充分考虑集装箱装箱过程中的复杂约束,采用启发式算法对模型进行求解.对2个实例的分析表明,由该软件提出的装箱方案可以为工作人员提供辅助性决策,提高集装箱空间的利用率. 展开更多

关键词 集装箱 三维装箱 启发式算法 空间划分与结合

下载PDF 职称材料

立体绿化集成技术配套产品开发利用研究进展 被引量：2

18

作者 杨红梅 叶少萍 +1 位作者 杨晓 阮桑 《湖南林业科技》 2020年第1期94-98,共5页

当前立体绿化在国内多个大中城市中得到了蓬勃发展,促进了相关配套产品的研发和推广应用,同时新型的配套产品又推动了立体绿化的快速发展。本文对华南地区立体绿化基质产品、蓄水种植容器、植被毯、绿墙、生态植被砖等相关配套产品的研... 当前立体绿化在国内多个大中城市中得到了蓬勃发展,促进了相关配套产品的研发和推广应用,同时新型的配套产品又推动了立体绿化的快速发展。本文对华南地区立体绿化基质产品、蓄水种植容器、植被毯、绿墙、生态植被砖等相关配套产品的研发及应用情况展开综述,旨在为今后能更有效地推广立体绿化集成技术及相关产品提供参考。 展开更多

关键词 立体绿化 配套产品 基质 蓄水种植容器 植被毯 生态植被砖 绿墙

下载PDF 职称材料

一种垂直横移式智能立体货柜的设计 被引量：1

19

作者 柏利春 游有鹏 罗福源 《机械与电子》 2017年第3期42-46,共5页

针对不同高度大中型货箱的存储需求,结合堆垛机和自动货柜的优点,设计研发了一种柔性存储智能立体货柜。其主体部分采用刚度较好、工艺要求较低的承重支架,传动部分采用链条提升和货叉横移的结构组合;控制系统采用DSP代替传统的PLC,实... 针对不同高度大中型货箱的存储需求,结合堆垛机和自动货柜的优点,设计研发了一种柔性存储智能立体货柜。其主体部分采用刚度较好、工艺要求较低的承重支架,传动部分采用链条提升和货叉横移的结构组合;控制系统采用DSP代替传统的PLC,实现货柜空间资源的柔性分配、执行机构的快速定位、多传感器的状态监测等功能。应用表明,本货柜系统能可靠地完成高位货箱的出入库和高效柔性存储。 展开更多

关键词 立体货柜 柔性存储 DSP 可靠性

下载PDF 职称材料

基于边缘计算的大地电磁法三维反演分布式计算实现 被引量：1

20

作者 梁萌 吴文鹂 +2 位作者 冯斌 陈实 刘艳丽 《物探化探计算技术》 CAS 2021年第1期70-76,共7页

随着大地电磁法三维勘探及处理技术的逐步推广,导致数据计算量成倍增长,需要具备高性能计算能力的系统才能满足计算需要。提出基于边缘计算的理念,采用容器技术构建具备大规模计算资源池的分布式计算环境,实现了大地电磁法三维反演的分... 随着大地电磁法三维勘探及处理技术的逐步推广,导致数据计算量成倍增长,需要具备高性能计算能力的系统才能满足计算需要。提出基于边缘计算的理念,采用容器技术构建具备大规模计算资源池的分布式计算环境,实现了大地电磁法三维反演的分布式并行计算。基于松耦合的软件架构设计研发了大地电磁法三维反演分布式计算软件,实现了人机交互操作和反演结果可视化。 展开更多

关键词 边缘计算 大地电磁法 三维反演 分布式计算 容器 Kubernetes

下载PDF 职称材料