An Improved Heuristic Recursive Strategy Based on Genetic Algorithm for the Strip Rectangular Packing Problem

与基因算法结合的改进启发式的递归的策略在这份报纸被介绍。第一，这个方法寻找一些矩形，它有一样的长度或宽度，到没有浪费空间，形成一些层，然后，计算留下包装顺序的高度使用启发式的递归的策略并且使用基因算法的进化能力减少高度。基准问题的几个班上的计算结果证明了介绍算法能与已知的进化启发规则竞争。它特别为大测试问题更好表现。

求解2D条带矩形Packing问题的迭代启发式算法

为求解二维矩形条带装箱问题,提出了一种新颖而有效的启发式算法.算法主要包括矩形装载适应度的计算规则和树型迭代搜索规则,通过选择最高适应度的矩形来装载空间.对大量国际上公认的Benchmark问题实例的计算结果表明,相对于当前的很多著名算法,提出的算法更加有效.

二维矩形条带装箱问题的底部左齐择优匹配算法

针对二维矩形条带装箱问题提出了一种启发式布局算法,即底部左齐择优匹配算法(lowest-level left a lignbest fit,简称LLABF).LLABF算法遵循最佳匹配优先原则,该原则综合考虑完全匹配优先、宽度匹配优先、高度匹配优先、组合宽度匹配优先及可装入优先等启发式规则.与BL(bottom-left),IBL(improved-bottom-left)与BLF(bottom-left-fill)等启发算法不同的是,LLABF能够在矩形装入过程中自动选择与可装区域匹配的下一个待装矩形.计算结果表明,LLABF结合遗传算法(genetic algorithm,简称GA)解决二维条带装箱问题更加有效.

二维一刀切装箱问题的两阶段启发式算法

对用于二维带排样问题的Heuristic Recursive算法进行了调整,给出同一层中两个相邻浪费区域在满足一刀切约束下是否可合并的判定定理。构造了二维带排样问题的多递归层算法,并将它与一维装箱问题的最优匹配递减算法相结合,提出适应二维一刀切非旋转装箱问题的两阶段算法。在500组标准测试案例的基础上,与多种算法进行了比较。实验结果表明,所提算法在绝大多数测试案例上能够获得更好的排样布局。

求解矩形条带装箱问题的动态匹配启发式算法

矩形条带装箱问题(RSPP)是指将一组矩形装入在一个宽度固定高度不限的矩形容器中,以期获得最小装箱高度.RSPP理论上属于NP难问题,在新闻组版、布料下料以及金属切割等工业领域中有着广泛的应用.为解决该问题,采用了一种混合算法,即将一种新的启发式算法——动态匹配算法——与遗传算法结合起来.混合算法中,动态匹配算法能根据4类启发式规则动态选择与装填区域相匹配的下一个待装矩形,同时将装箱后所需容器高度用遗传算法的进化策略进行优化.对2组标准测试问题的计算结果表明,相对于文献中的已有算法,提出的算法更加有效.

面向订单的铜板带生产组批及优化

如何有效地解决计划中的组批问题是铜板带加工首要考虑的问题。在深入研究铜板带生产中订单组批规律的基础上,建立了综合考虑铸锭化学成分、工艺路线以及经济性的多目标组批优化模型,采用一种基于基因段思想的遗传算法,设计了基于基因段的编码、解码、交叉和变异规则,并通过加权因子综合了铸锭个数和工艺路线重合度,将多目标问题转化为单目标进行求解。生产数据试验表明,采用的方法能够减少需要的铸锭数量和中间工序分卷次数,有效地解决了生产中的组批优化问题。

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

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

求解复杂集装箱装载问题的新方法

提出了一种求解复杂集装箱装载问题的新方法 ,该方法将求解复杂装箱问题分成两步 :首先 ,根据一定的启发式规则将集装箱进行体积最大化装载 ,并在深度方向根据货物将空间分层 ;然后 ,用遗传算法将各层进行重心位置最优化调整 ,使装载方案更加符合实际运输需要。实际应用结果表明 ,该方法在空间利用率、重心位置以及计算效率等方面都优于其他同类方法。

矩形件优化排样的混合启发式方法

提出一种启发式递归与遗传算法相结合的混合启发式算法求解矩形件优化排样问题。首先给出一种启发式递归算法,利用该算法逐个从待排矩形件中生成局部利用率高的条料,直到所有待排矩形件均生成条料;利用遗传算法全局搜索能力强的特点,对这些条料序进行搜索重组,使其所用的板材数最少;最后再次利用遗传算法,对条料生成之前的矩形件种类序进行全局最优搜索,使总的板材利用率达到了最大。对两个典型实际算例进行计算,并与相关文献比较,结果表明了该算法的有效性。

矩形件三阶段带排样问题的遗传算法

采用混合遗传算法求解矩形件带排样问题,采用三阶段排样方式以满足特定的约束或简化切割工艺。改进遗传算子,在变异操作之后使用调整操作,以进一步简化得到的排样方案。在初始种群构造时,根据矩形件的特性采用一些简单有效的方法,使结果更好更快地收敛。实验结果表明方法对解决这类问题是有效的。

条形装箱问题的基于后缀表达式的混合遗传算法

装箱问题作为一种常见的运筹问题,在很多领域有着重要的应用,装箱问题可以分为一维、二维和三维装箱.主要讨论了二维装箱中条形装箱问题的遗传算法的求解,其中采用后缀表达式的形式对装箱方案进行编码,并详细提出了解码的算法和有关的证明,最后通过实例证明了该算法是可行的.

二维离线非旋转装箱问题的一个混合算法

针对二维离线非旋转装箱问题,在凹角和适应值的思想的基础上,提出了一个改进型的Best-Fit启发式算法,并结合基于自然数编码的遗传算法构建了混合算法。同时在遗传迭代过程中,引入二维装箱问题的下界思想作为迭代的终止条件之一,减少了遗传算法无效迭代次数,另外根据问题自身特点,有效地降低了染色体长度,提高了整体的计算速度。在36个标准测试案例的测试基础上与一些经典的算法进行了比较,实验结果表明该算法在工业生产可接受的时间内与其他经典的算法相比能够获得更为满意的结果。

启发式遗传算法在分段舾装分道作业计划中的应用研究

以分段舾装分道作业线的作业计划问题为研究对象,对分道作业线合理作业计划形式进行了研究。在分析分段舾装分道作业特点的基础上,建立了问题的数学模型,并结合启发式遗传算法进行了问题模型的求解,最后以一个算例证实了研究方法的可行性和有效性。

求解矩形装箱问题的一种近似算法

提出了利用近似算法求解二维矩形装箱问题的最小高度的一种方法。该方法基于启发式递归策略和遗传算法。利用启发式递归策略把所有大小各异的矩形都装入宽度固定的矩形容器中,并计算装完后所需容器的高度,用遗传算法的进化能力优化高度,使得所需容器的高度尽可能小。计算数据证明这种方法能够得到很好的结果,特别是对数据量大的测试问题,效果更好。

用于求解二维圆形排样问题的自适应混合算法

针对二维圆形版面不等圆排样问题,在最小局部距离定位布局策略的基础上,引入紧凑度和适应度,提出基于拟矩形排样的自适应启发式算法,并与以自然数编码的遗传算法相结合构建混合算法。该混合算法发挥两者的全局搜索能力与局部寻优能力。在标准测试算例上,与一些经典算法进行比较,结果表明,该算法能够在更短的时间内获得更为满意的结果。

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

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

一刀切约束下的二维装箱问题高效求解算法

目的为实现大规模物料的快速剪裁切割,对考虑一刀切约束的二维装箱问题进行研究,并构建相应的改进优先度算法IPH(Improved Priority Algorithm,IPH)。方法IPH能够在不需要任何迭代搜索下,直接进行剩余空间分割与填充。为此,发展PH算法中的优先度放置规则,并以最大化生成大空间面积和最小化生成小空间面积为基础,设计改进砌砖式空间分割策略。结果针对标准数据集的对比实验表明,IPH能够在较短时间内完成大规模算例的高效求解,并首次获得了多个算例的最优填装效果。结论基于概率较优的启发式求解方法,能够实现无迭代优选下的一刀切二维装箱问题直接求解,且运算效果令人满意。

基于强化学习的装箱问题研究

论文提出了一种基于改进规则和强化学习的混合启发式算法来求解二维带装箱问题(2D Strip Packing Problem,2DSPP)。首先,对基于skyline算法的评分规则进行了改进。其次使用Deep Q-Network(DQN)来获得初始的矩形物品序列,它可以提高空间利用率,防止算法陷入局部最优。将改进的评分规则与DQN相结合,提出了基于简单随机算法(SRA)的启发式算法,称为基于强化学习的简单随机算法(RSRA)。用五种算法对8个数据集进行了实验比较。结果表明,RSRA在8个数据集(C,N,CX,NT,2sp,NP,ZDF,BWMV)上的性能最好,Ave.Gap%分别比GRASP、SRA、IA、ISH算法分别提高45.86%、45.16%、30.89%和20.56%。

基于聚类和网格覆盖的三维装箱算法

三维装箱问题是一类常见的组合优化问题,现有的研究工作集中于提升算法的装载效率,较少考虑算法决策时间的影响,而时间效率是决定算法能否应用于工业实践的重要标准之一。本文提出了一种改进的三维最优适配算法用于解决装箱问题,通过结合遗传算法和聚类算法,在降低搜索空间维度、提高算法收敛速度、减少算法运行时间的同时,寻找更优的解。在华为数据集上的实验结果表明,本文提出的算法在兼顾时间效率和装载效率的基础上,能够获得较好的结果。