装箱问题的一种新的近似算法

 研究了一维装箱问题(Bin Packing Problem),给出了一个新的近似算法:交叉装填算法(简称CF算法).证明了CF算法达到装箱问题的最好的近似值3/2;并且当这些物件的大小按非增性质预先排序后,CF算法的时间复杂度是线性的.     

在线A形装箱问题: 模型及算法研究

A形装箱问题是由生产实际引发的一个新的数学模型,它是经典一维装箱问题的一种变形--每样物品有高度和半径两个参数.把装箱问题的经典算法推广到在线A形装箱问题,并分别从最坏情形分析与数值模拟两方面对算法进行了比较,得到了不同而且有趣的结果. 证明了 First Fit算法的渐近竞争比为2, 而其它在线启发式算法如Next Fit, Worst Fit, Best Fit(BF), Almost Worst Fit, Harmonic的渐近竞争比皆为无界; 通过数值模拟,在平均意义下BF的性质最好.     

一维装箱问题的一个衍生问题——最小基数箱子覆盖问题

文章介绍一维装箱问题的一个衍生问题:最小基数箱子覆盖问题和它的一个启发式算法。     

染色装箱问题及其启发式算法

研究了装箱问题的一个新颖的衍生问题:染色装箱问题,即在装箱问题中,给每个物件指定一个颜色,要求每个箱子中所装的物件颜色各不相同,使得所需要的箱子数目尽可能少.该问题是通常装箱问题的一种推广.笔者给出了染色装箱问题的一个启发式算法,同时研究了只有两种颜色的染色装箱问题:即2-色装箱问题,并给出了一个最优算法.     

集装箱货箱装载模型和算法

对集装箱装载货箱的两类问题,基于分层思想建立多步决策模型,提出棱(面)判别矩阵法把三维装箱问题转化为二维乃至一维装箱问题而得到模型的求解算法.     

有色装箱问题的一种新的近似算法

作为经典装箱问题的推广,有色装箱问题在多处理器实时计算机系统的任务调度等实际问题中有着很强的应用背景.本文提出了有色装箱问题的一种新的近似算法--交叉装箱算法（简称JCBP）,该算法首先对物品按长度进行排列,再从两头交叉进行装箱.实验证明,该算法较其他算法有较好的装箱效果,并且很多情况下能达到最优解.     

装箱问题的概率近似算法

研究了一维装箱问题的在线近似算法,给出了一种新的半在线算法：随机适应算法（简称RF算法）,说明了RF算法的时间复杂度是O（n^2）,一般情况下的性能比〈1.75。     

关于染色装箱问题的一个近似算法

装箱问题是组合最优化中的一个著名的问题。本文给出了装箱问题的一类衍生问题——染色装箱问题的一个近似算法,并讨论了算法的近似比。     

带启动重量的脆度装箱问题

讨论如下定义的带启动重量的脆度装箱问题：设有许多等长的一维箱子,给定一个物品集,每个物品有2个参数（脆度和重量）,若箱子是首次装入物品,则需要添加额外的启动重量,在装箱的过程中要保证每个箱子的启动重量和所装物品重量之和不能超过该箱子内物品的最小脆度,问怎样安排物品使所用箱子数最小．该问题是一个新的组合优化问题,来源于CDMA蜂窝通信系统中的信道分配．本研究给出了一个求解该问题的线性脱线算法C-NFI,分析了其最坏情况渐进性能比为2,并给出了相应的试验结果．     

时间表理论中LPT算法在装箱问题中的应用

本文利用二分搜索法和时间表理论中LPT算法求解装箱问题的近似最优解;给出了一个直观性算法,并研究这个算法的最坏情形,最后说明此算法在某些方面优于著名的FFD算法。     

大型二维装箱问题及其禁忌算法研究

对大型二维装箱问题进行描述,提出求解该问题的禁忌算法.算法基于自然数编码,设计了货物的摆放规则和序列生成方式,采用二种邻域,根据邻域的不同,构造了两种禁忌表.算法采用惩罚函‘数处理空间利用率约束.介绍算法的原理,给出了具有代表性算例试验结果并且进行了分析.试验结果表明了提出的禁忌算法对优化大型二维装箱问题的有效性.     

基于优先级的邮运调度算法的设计与实现

邮运调度是邮区中心局生产作业系统的重要环节,而调度算法的核心是装箱问题。针对邮运调度特点,设计一种基于优先级的装箱调度算法,并给出了算法的设计思路和流程。     

一种用遗传算法求解装箱问题的新编码方法

装箱问题在实际生产中应用非常广泛,然而在传统装箱问题中箱子的容量是固定的,并没有考虑多种容量箱子的问题;文章提出一种用遗传算法求解装箱问题的新编码方法,并用单亲遗传算法实现;这种算法和混合遗传算法相比,有编码简单、收敛快及实现容易等优点。     

求解装箱问题的一种混合分组遗传算法

通过设计一种适应度函数,利用分组遗传算法结合BF算法和FFD算法来对此适应度函数进行优化,从而求得一个优化的装箱结果。用C++实现该算法并对装箱实例进行仿真实验与比较,结果表明:在遗传算子的交叉操作过程中采用FFD+GGA的混合分组遗传算法是一种解决装箱问题的有效方法,在大部分情况下用很短的时间都可求得最优解。     

最小基数箱子覆盖问题

最小基数箱子覆盖问题,是在物件大小满足一定的条件下的装箱问题．给出了一个时间复杂度为O（n）的启发式算法．     

面向PI集装箱的组合适配装箱算法

针对PI(Physical Intemet)集装箱与货物的适配问题,考虑PI集装箱标准化、模块化、可扩展的特性以及货物装箱的体积、方向、完全支撑等约束,通过PI集装箱模块化重组,构建与货物适配的组合式PI集装箱,目标是PI集装箱的空间利用率最大化.结合PI集装箱组合适配装箱问题的特性,设计一种组合适配装箱算法,包含货物分类、货物装箱、箱体组合等三个步骤.在货物装箱步骤中,嵌套调用基于粒子群算法的改进模因算法求解货物装箱顺序和位置,该算法引入多种群变异策略以提高算法前期搜索质量,引入路径重连技术和扰动操作防止算法陷入局部最优.在多批量少货类和少批量多货类两种实验场景下进行求解,并通过算法对比验证了改进模因算法的有效性.     

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

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

装箱问题在物流领域的研究回顾与分析 ——基于美国科学情报研究所科研数据库(Web of Science,1989～2018)的科学计量分析

集装箱作为物流运输过程中的关键环节,研究如何通过装箱过程有效利用集装箱空间,降低物流成本,提高经济与社会效益具有重要的现实意义。为全面分析装箱问题在物流领域的研究发展状况,本文以Web of Science数据库中1989～2018年间的相关研究论文为数据来源,运用科学计量分析与复杂网络的方法从作者、关键词、地区及期刊4个维度进行研究。研究表明,启发式算法、模型等一直是物流领域装箱问题的研究热点,且研究规模和成熟度逐步上升;同时,物流领域装箱问题的研究有从逐步从侧重理论过渡到侧重实际应用的趋势。基于本文分析,针对特定运输形式的物流装箱研究及人工智能相关算法在求解装箱问题上的研究是未来可能的研究热点。     

染色的装箱问题及其近似算法

给出了染色装箱问题和染色覆盖问题的数学描述,得到了给定颜色限制的染色装箱问题和染色覆盖问题的两个近似算法.     

一种简化粒子群算法及在三维装箱问题中的应用

在简化粒子群算法中引入混合蛙跳算法的分组思想,使得粒子群算法在进化后期能够利用更丰富的信息,有效避免算法早熟收敛和收敛到局部最优点问题,且收敛速度更快。将改进后的简化粒子群算法用于解决集装箱装箱问题,数值试验表明这种集装箱装载方法能够达到较好的容积利用率。为了指导实际的装箱操作,设计出了集装箱装载软件。