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

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

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

针对瓦楞纸板在装箱过程中遇到的多种实际约束,提出一种基于剩余空间最优和多种实际约束的快速求解算法.该算法先根据纸板的先进后出和组合装载约束,确定纸板的装箱序列,接着将三维装箱问题转换成带高度约束的二维装箱问题,再基于剩余空间最优策略,选择空间的分割方式和纸板的放置方式,并对剩下的空间进行合并和重新分割,从而求解得到纸板...     

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

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

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

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

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

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

基于装箱树算法求解集装箱装载问题的研究

研究了把同种货物装入一个集装箱内，使箱子内的空间利用率为最大的集装箱装载问题．首先，运用启发式算法,充分考虑了箱子和货物的方位、剩余空间等问题．然后，通过主空间装填、空间分层、剩余空间优化等建立一个装箱树．最后，用Java程序完成装箱树算法，并实现集装箱装载问题的求解．用实例验证了算法的可行性，能够投入实际应用．     

一种自适应优化松弛量的装箱算法

装箱问题是物流系统和生产系统中的一个经典而重要的数学优化问题。装箱指把一系列物品按照一定顺序放进具有固定容量的箱子中,并最小化所使用的箱子数量,以最大限度地获取装箱问题的近似最优解。然而,现有的装箱算法存在明显的缺陷。遗传算法计算量过大,甚至无法求出所需解,启发式算法无法处理极端值问题,而现有的改进算法即使在引入松弛量的情况下,也极易陷入局部最小值。文中提出的Adaptive-MBS算法采用自适应权重来改进原有方法,即允许方法有一定的松弛量,并具有捕捉物体样本空间随时间变化的直觉,以使用更好的松弛量策略来装箱。Adaptive-MBS算法首先以当前箱子为中心,使用Adaptive_Search搜索算法迭代找到适合箱子容量的集合中所有物体的子集,Adaptive_Search搜索算法不要求完全装满箱子,而是允许箱子具有一定的松弛量,在训练过程中根据当前状态的变化,实现自动地调整松弛量,在找到完全填满箱子的子集后迭代至下轮搜索直至遍历完成。该方法不易陷入局部最优,具有较强的发现全局最优解的能力。文中使用装箱问题中经典的BINDATA和SCH_WAE数据集进行实验,结果表明,数据集中多达991例问题可以通过Adaptive-MBS算法得到最优解。在没有求解出最优解的实例上,所提算法也在所有对比算法上具有最低的相对偏移量百分比。数值实验结果表明,相较于其他经典的装箱算法,Adaptive-MBS算法有更好的效果,其收敛速度也显著优于其他算法。     

一种带脆度的尺寸可变装箱问题

作为经典装箱问题的扩展,尺寸可变装箱问题在现实生活中有着极高的应用背景。分析了尺寸可变装箱问题在解决货物装载运输问题上的不足,由此提出了一种带脆度的尺寸可变装箱问题。除了经典装箱问题中物品体积和箱子容量这两个参数,还引入了物品类型和箱子脆度等参数,给出了相关的数学模型。在经典的FFD（First Fit Decreasing）算法的基础上进行了推广,提出了新的启发式算法NFFD,它对箱子的特性进行了预处理,再进行装箱。分析了该算法的复杂性。对NFD、FFD和NFFD算法进行了数值模拟实验,实验结果表明,在相关参数符合均匀分布的条件下,NFFD算法的效果是最好的。     

雷达装备维修器材集装技术研究

多约束条件下的雷达装备维修器材装箱问题是一个复杂的组合优化问题,属于NP完全问题,其求解相当困难.为了解决雷达装备维修器材集装效率低的问题,该文在考虑实际应用的约束条件下,分析并建立了雷达装备维修器材优化装箱问题的模型,采用中间包装,空间分割,空间合并,抽屉分装等策略,提出了一种基于启发式算法的雷达装备维修器材装箱问题的解决方案.仿真实例及实际工作验证了算法的有效性和实用性,较好地解决了雷达装备维修器材的优化装载问题.     

集装箱装载的一种启发式算法

多约束条件下的三维装箱问题是一个复杂的组合优化问题,属于NP-HARD问题，其求解是很 困难的．所以在实际应用中,往往采用一些启发式算法来求解．本文在考虑一些实际应用中 的约束条件下，提出了一种三维集装箱装载的启发式算法．此算法采用了三空间分割、平均 高度装载、货物合并、空间合并等策略，考虑了方向、重量、优先顺序、货物的配置位置等 约束条件．通过逐步淘汰差的装载方案，最后达到满意的装载．实例仿真说明了该算法的有 效性和实用性，能够直接用于实际应用中．     

轨道交通杂散电流腐蚀的监测及防护研究

南京港华燃气公司发现马群区域天然气高压管道上有强烈干扰的杂散电流存在,大大超过了行业规范《SY/T0017-2006埋地钢质管道直流排流保护技术标准》规定,该规定中提出当管道任意点的管地电位正向偏移均值大于100mV时,必须采取排流保护或其他防护措施,结合常规技术杂散电流防护存在的不足,提出了新型的监测及防护方法。本研究设计的方案采用了杂散电流补偿的方法,避免杂散电流对天然气高压管道的杂波干扰,通过设计出一套监测与防护系统,在系统中加入与地铁供电电流大小相等、方向相反的补偿电流,进而减小或抵消在特定区间内产生的杂散电流。试验结果表明,本文设计的方法大大减少了杂散电流,符合燃气管道相关标准,大大提高了轨道交通的安全性。     

Selfish bin covering

In this paper, we address the selfish bin covering problem, which is greatly related both to the bin covering problem, and to the weighted majority game. What we are mainly concerned with is how much the lack of central coordination harms social welfare. Besides the standard PoA and PoS, which are based on Nash equilibrium, we also take into account the strong Nash equilibrium, and several new equilibrium concepts. For each equilibrium concept, the corresponding PoA and PoS are given, and the problems of computing an arbitrary equilibrium, as well as approximating the best one, are also considered.     

Besk-k-Fit bin packing

The bin packing problem is to pack a list of reals in (0, 1] into unit-capacity bins using the minimum number of bins. LetR ^∞[A] be the limiting worst value for the ratioA(L)/OPT(L) asOPT(L) goes to ∞, whereA(L) denotes the number of bins used when the approximation algorithmA is applied to the listL, andOPT(L) denotes the minimum number of bins needed to packL. For Best-k-Fit (BkF for short,k≥1), we prove in this paper thatR ^∞[BkF]=1.7+3/10k.     

Bounded-space online bin cover

In this paper, we look at the online bounded-space bin cover problem and show how we can use the language of Markov chains to model and analyze the problem. We will use the insights given by the Markov chains to design an algorithm for the online bounded-space bin cover problem. The algorithm is a heuristic that we create by simplifying the Markov chain. We also show how we can use simple methods to improve the efficiency of the algorithm. Finally, we will analyze our algorithm and compare it to a well known online bin cover algorithm.     

Batched bin packing revisited

We revisit the batched bin packing problem. In this model, items come in K consecutive batches, and the items of the earlier batches must be packed without any knowledge of later batches. We give the first approximation algorithm for the case \(K=2\), with tight asymptotic approximation ratio of 1.5833, while the known lower bound of the model is 1.378. With the application of this result, we are also able to provide an improved algorithm for the recently defined graph-bin packing problem in a special case, where we improve the upper bound from 3 to 2.5833.     

Parameterized on-line open-end bin packing

This note deals with a new variant of bin packing, the so-called open-end bin packing problem in which a bin can be filled to a level exceeding its capacity by its last item if it is not full immediately before the last is packed. We investigate the on-line version of this problem and give best possible algorithms for parametric cases. This work is supported by the Foundation under State Education Committee of China.     

Matched filters for bin picking

Currently, a major difficulty for the widespread use of robots in assembly and material handling comes from the necessity of feeding accurately positioned workpieces to robots. ``Bin picking' techniques help reduce this constraint. This paper presents the application of matched filters for enabling robots with vision to acquire workpieces randomly stored in bins. This approach complements heuristic methods already reported. The concept of matched filter is an old one. Here, however, it is redefined to take into account robot end-effector features, in terms of geometry and mechanics. In particular, the proposed filters match local workpiece structures where the robot end-effector is likely to grasp successfully and hold workpieces. The local nature of the holdsites is very important as computation costs are shown to vary with the fifth power of structure size. In addition, the proposed filters tend to have a narrow angular bandwidth. An example, which features a parallel-jaw hand is developed in detail, using both statistical and Fourier models. Both approaches concur in requiring a very small number of filters (typically four), even if a good orientation accuracy is expected (two degrees). Success rates of about 90 percent in three or fewer attempts have been experimentally obtained on a system which includes a small minicomputer, a 128 × 128 pixel solidstate camera, a prototype Cartesian robot, and a ``universal' parallel-jaw hand.