基于遗传算法的三维装箱问题优化研究

在工业化自动装卸货物场景下,考量稳定性、方向性和重量等约束条件,提出一种将三空间划分策略和遗传算法相结合的三维装箱优化算法。本文通过介绍三维装箱问题,分析比较常用算法,最终使用遗传算法实现装箱过程;在MATLAB中开发一个简单的装箱系统,并可视化装箱结果。试验证明:该算法不仅对求解三维装箱问题具有优异的空间特性,而且对空间利用率有所提升。

求解三维装箱问题的多层启发式搜索算法

文中提出了一个高效求解三维装箱问题的多层启发式搜索算法.该算法基于块装载的思想,按照块选择算法确定每个阶段采用的块,然后以一种固定的装载方式装载块,直到无法继续装载.文中的主要贡献在于发展了一个有效的复合块生成算法,特别的,提出了基于多层搜索的块选择算法,该算法用多层搜索来评价可行块,然后选择最合适的块进行装载.对1500个三维装箱问题测试数据的计算结果表明,提出的算法几乎在所有测试数据上的填充率都超过了目前已知的优秀算法.

同一尺寸货物三维装箱问题的一种启发式算法

给出了集装箱装载同一尺寸长方体货物问题的一种启发式算法.该算法解决了许多三维装箱算法计算量大、排列不规则等缺点,同时用计算机编程实现该算法,并与国内主要装箱软件作了对比,最后给出了该算法的可行性与优势.

多种物品三维装箱问题的一种启发式算法

针对多种物品单箱三维装箱的问题,设计了一种新的启发式算法.该算法基于"平面"和"块"的概念,采取树搜索策略,允许货物在任何可行方向上旋转,在保证箱空间利用率足够高的同时,满足货物摆放稳定性的要求.实验结果表明,该算法是解决此类问题的一种有效的方法.

基于多元优化算法的三维装箱问题的研究

用多元优化算法(Multi-variant optimization algorithm,MOA)实现三维装箱问题的求解.算法通过随机放置和局部调整从而逐步逼近最优解.随机放置是将随机选择的几个箱子装入容器中;局部调整是根据目标函数值对随机放置容器的箱子序列作局部调整优化;通过递推的随机放置和局部调整优化,目标函数值逐步逼近最优值,从而获得一个较为理想的三维装箱方案.算法通过对BR1～BR10共1 000组三维装箱问题测试实例的测试仿真,得到理想的装箱效果,说明用多元优化算法实现三维装箱问题的有效性和可行性.

高效求解三维装箱问题的剩余空间最优化算法

为实现三维装箱问题的高效求解,提出了一个三维的剩余空间最优化算法(Three-Dimensional Residual-Space-Optimized Algorithm,3D-RSO)。在满足3个著名约束的条件下,该算法将三维问题转化为带有高度约束的二维问题,通过对箱子放置后的剩余空间状态分析,提出了基于概率较优的空间分割方法和箱子布置规则。相比于传统算法,3D-RSO在求解过程中不需要任何的预处理和搜索操作,是一种最坏计算复杂度为O(2n2)的直接求解算法。针对强异构体的实验表明,该算法能够在极短的时间内对算例进行高效求解,适合应用在大规模或者需要被快速求解的三维装箱问题中。

基于重力装载的自适应随机算法求解多箱型三维装箱问题

为了针对电商订单货物进行快速经济选箱,在建立多箱型三维装箱问题(3D-MBSBPP)数学模型的基础上,对空间搜索策略进行创新,提出两种求解算法。自适应随机算法实现货物与空间的自适应;粒子群算法采用动态编码,并实施5种类型的分段变异。采用重力式空间搜索策略求解已有三维装箱算例,使空间利用率提高2.16%,证明了重力式空间搜索策略的有效性。通过求解以三维装箱标准算例为基础构造的8类3D-MBSBPP实例来对比两种算法,自适应随机算法在8类算例上的表现均更优,且平均gap值优于粒子群算法19.59%,证明了自适应随机算法的优越性和稳定性。

货物三维装箱问题建模及其乌鸦搜索算法优化

针对货物三维装箱问题建立三维装箱模型.在模型中,为避免货物在运输过程中转弯时由于偏心导致翻车现象的发生,加入了考虑转弯时重心约束,得到重心区域投影为等腰三角形或者等腰梯形.货物放置规则中扩大了剩余空间区域,增加了解的多样性.在算法中,为了提高迭代收敛速度,增强其全局寻优的能力,采用改进的乌鸦搜索算法对模型进行求解与优化.在改进算法中,提出并引入了多概率随机游走策略和解修复策略.解修复策略使得算法适用于模型求解,尽可能增加解的多样性.多概率随机游走策略是种群迭代后继续以多种不同的概率进行随机游走,使得算法全局寻优能力更强.仿真实例与基准函数测试结果表明,改进后的算法优化效果明显.

求解三维装箱问题的混合遗传模拟退火算法

集装箱装载是货物运输过程中重要的一步,其属于NP-hard 问题。为了提高效率,降低成本,提出了以集装箱体积利用率最大化为目标建立三维装载模型,同时考虑体积约束、重量约束、重心约束、方向约束。利用混合遗传、模拟退火与三空间分割启发式装载算法求解模型,算法中融入局部最优解保存策略来避免局部较好解在后续的算法过程中出现适应度降低的情况。通过强异类算例与弱异类算例对算法进行性能测试,并结合具体的货物装载数据,得出三维装载图与目标函数值。结果表明,该算法应用于集装箱装载有着较好的效果。

三维装箱问题的启发式算法

三维装箱问题是一类典型的NP-hard组合优化问题。在一维、二维装箱问题基础上,设计了一种启发式算法,借以克服一般启发式算法依赖"经验"的不足,该算法结构简单,实验表明算法收敛速度快。

面向梯形箱子的三维装箱问题算法研究

针对梯形箱子的三维装箱问题,提出了一种基于空间分割的构造性启发式算法,根据梯形箱子三维装箱问题的特点,设计了相应的空间分割策略、空间合并策略与空间重组策略,在此基础上加入遗传算法,提高算法局部与全局搜索能力。实验结果表明,该算法能有效处理梯形箱子三维装箱问题。

圆柱形货物三维装箱问题简便解法

一种圆柱形货物摆放问题存在现有二维解法相对复杂、繁琐、优化程度不理想,三维立体装箱缺少有效解法等问题。为了解决这些问题,提出新的简便解法。新解法把货垛重新划分为对齐层、单数层和双数层,容易建立数学模型求解。求解时,把圆柱形货物看作是长为直径、宽为圆柱高的条块货物,进行平面和三维立体优化,得出三维优化结果。实证分析证明,新解法相对简单、易于掌握、优化程度高。

多种货物三维装箱问题研究

集装箱装载是货物运输、加工调度过程中的重要前提,其属于NP-hard问题,本文采用启发式三空间分割搜索算法,解决三维装箱问题。问题背景源于2019年美国数学建模竞赛B题“无人机发送:开发空中救灾响应系统”,本文分别对两种、三种、四种货物往固定尺寸的ISO集装进行装箱,使集装箱的空间利用率最大,且要保证货物之间数量的比例要求,最后,为了推广模型的应用,设计了GUI界面,输入四种货物的尺寸,就能输出各种货物的数量以及空间利用率。

多约束三维装箱问题的启发式优化算法

针对多约束三维装箱问题,传统的启发式算法往往很难满足所有约束条件,无法提高集装箱的装载率。为此,提出结合块装载算法的启发式优化算法,在满足多约束条件下采用块装载算法得到简单块,通过剩余空间的分割和合并确定块装载的目标空间,采用装载序列优化每个装载阶段的块选择,得到最优装载方案。基于BR经典算例结合正态分布法生成多约束BRw算例对该算法进行测试,实验结果表明,基于块装载算法的启发式优化算法平均装载率达到83.7%,比传统启发式算法提高了4%。基于块装载算法的启发式优化算法不仅能有效应对装载过程中的多种约束条件,而且能增加每次集装箱装载时的箱子体积,减少装载时间,同时也能提高集装箱的装载率。

面向纸板三维装箱问题的剩余空间最优算法

针对瓦楞纸板在装箱过程中遇到的多种实际约束,提出一种基于剩余空间最优和多种实际约束的快速求解算法。该算法先根据纸板的先进后出和组合装载约束,确定纸板的装箱序列,接着将三维装箱问题转换成带高度约束的二维装箱问题,再基于剩余空间最优策略,选择空间的分割方式和纸板的放置方式,并对剩下的空间进行合并和重新分割,从而求解得到纸板装载放置的结果,实现容器空间利用率最高和使用数目最小的目标。通过计算随机算例和实际算例,以及对结果的三维可视化显示,验证该算法能实现多种约束,空间利用率高,运算效率高并具有有效性和实用性。

三维装箱问题研究现状与展望

装箱问题自1830年被提出以来就是学术界研究的重要领域,三维装箱问题是装箱问题中最复杂的一种。结合前人研究成果,将三维装箱问题按照多层次进行了详细的分类解读。系统地整理了三维装箱问题建模的三大要素:前提假设、目标函数、约束条件。同时提出了求解三维装箱问题的5类方法。统计了近年来几十篇文献,结合这些文献,对上述的问题分类、建模要素、求解方法等做出统计。最后针对目前三维装箱研究存在的问题和短板,为使三维装箱问题的研究可以更好地与实际工程问题相结合,提出了三点展望。

粒子群自进化算法求解物流装箱问题

为了解决当今物流行业中装载货物类型为强异构的情况,提高装载填充率和效率,提出了一种求解三维装箱问题的元启发式算法——粒子群自进化算法。算法包含两部分:极限点构造启发式算法和粒子群自进化规则。极限点构造启发式算法引入了极限点的概念,利用新的极值点思想推导出了三维装箱问题的启发式算法。粒子群自进化规则提出了在货物装载序列中表示粒子的方法,推导了粒子间交叉、变异算子,在极限点构造启发式算法的基础上不断迭代进化完成货物的装载。通过不同结果的比对,证明该算法显著提高了物流装载的空间利用率,强异构货物的平均装载率达到了85%,验证了算法在强异构货物下的有效性与优越性,并给出了货物装载的三维模型。由于实际测试集的缺少,分别为机腹仓装载类和集装板类模型提出了实例生成器,通过生成器的测试集验证了算法在实际应用中的紧凑性、实用性和快捷性。

基于混合遗传算法的可变尺寸货物装箱问题研究

目的针对冷链运输中的生鲜打包及装载优化问题,提出一种允许货物以体积恒定为前提进行尺寸变化的包装装载方案,以最大化集装箱的空间利用率。方法基于上述问题,构建非线性混合整数规划模型,为了方便CPLEX或LINGO等求解器对该非线性混合整数规划模型进行求解,采用一种分段线性化方法,将该非线性模型进行线性化处理。由于所研究问题具有NP-hard属性,无论是CPLEX还是LINGO都无法有效求解大规模算例,因此设计一种有效结合遗传算法与深度、底部、左部方向优先装载(Deepest bottom left with fill,DBLF)的算法。结果大小规模算例实验验证结果表明,混合遗传算法能够在合理时间内获得最优解或近似最优解。结论所提出的可变尺寸包装方案有效提高了装载率,有益于客户和物流公司。

三维货物装箱问题的研究进展

基于问题的复杂度、优化模型的现实度以及求解算法的适合度3方面,对三维装箱问题的研究现状进行分析,着重对货物与箱体的规模与异构性、优化目标与约束条件的实用性和求解方法的优缺点进行归纳;其次,总结三维装箱问题在以上3方面存在的不足;最后,从整体问题复杂化、优化目标多样化和约束条件现实化、假设条件最小化、求解方法实用化等5方面对三维装箱问题的研究进行展望。

三维装箱问题的模型与改进遗传算法

三维装箱问题是一类NP-hard的组合优化问题,构建一个适当的数学模型并设计高效快速的算法具有重要的理论和现实意义.该文将箱子空间划分为立方体单元,依此构建三维装箱问题的混合整数规划模型,并通过改进遗传算法求解,剔除大量不可行解提高了收敛速度.实验结果表明此算法运算过程及结果稳定,具有较强的实际应用价值,能有效解决复杂的三维装箱问题.