文献综述在圆和球体包装问题:模型和方法

文摘

上最相关文献综述高效的模型和方法对包装循环对象/物品到欧几里得平面区域/项目和区域的对象要么是两到三维。这些包装问题是NP困难的优化问题和各种各样的应用程序。他们一直使用各种approaches-based算法从计算机辅助解决最优证明,和程序,建设性的方法,对多头凸极小化,台球模拟、多相启发式,metaheuristics。

1。介绍

切割和包装问题是科学挑战性问题广泛的应用程序。他们是非常有趣的np难组合优化问题;即没有过程能够完全解决确定性多项式时间。他们遇到各种现实世界的应用程序包括生产和包装的纺织、服装、海军、汽车、航空航天、食品等行业。他们是瓶颈问题在计算机辅助设计,设计方案生成的工厂,电子模块,核能和电厂等等(1]。

切割和包装问题包括包装一组几何对象/项目的固定尺寸和形状区域预定的形状而设计和技术考虑的问题1]。包装标识安排和确定位置的几何对象包含的尺寸形状,达到一个特定的目标函数的极值1]。当几何对象对象,包装问题降低到一个数学模型的约束条件反映的条件安排对象在给定区域内,相互nonintersection条件对象,和任何技术的限制,不能简化为纯粹的几何约束(1)(作为矩形断头台削减包装)。一种方法来解决这个复杂的问题是安排对象根据一些规定的顺序和搜索的局部极值1]。然而,精确的局部极值的搜索是耗费时间没有任何的保证一个足够好的收敛到最优(1]。

本文关注的问题处理循环对象,被两到三维。这些问题有一个广泛的应用程序从自然科学,工程设计,每一天的生活。包括覆盖地理区域的细胞发射器,存储的圆柱形鼓到容器或储存成一个开放的区域,瓶子或罐子包装成最小的盒子,在一个给定的地区植树,以最大限度地利用森林密度和树之间的距离,等等(2]。

包装循环对象离散和计算几何来说是一个挑战2]。与大量的圆形物体,很难找到最优的解决方案。一个最优解可能会旋转,反射或圆形对象重新排序;因此,同等数量的最优解吹成圆形物体数量的增加(2- - - - - -4]。此外,一个或多个圆形的对象可能会略有移动而不影响最优解。实际上,存在一个连续最优解(2- - - - - -4]。最后,计算准确度和精密度的问题。

很明显,包装圆形物体产生优化的问题,但他们的分类为连续或离散的问题是模糊的。的确,圆形物体的位置是连续而最优的结构模式有一个离散的性质(5]。最近的趋势是设计方案技术解决(某种程度上)这两个方面同时进行。

许多变体圆形物体在平面上的包装被制定为非凸优化问题;希望这些配方解决了使用可用的解决非线性规划(NLP)产生高质量的近似解(6]。然而,大多数NLP解决全球最适条件无法识别。事实上,问题与圆形对象非常困难的优化问题。他们有大量的变量和局部最小值。因此,他们需要解决与启发式算法混合局部搜索过程以广泛探索搜索空间(7,8]。最近的趋势是采用近似方法(启发式),结合全球的方法(启发式)搜索和本地详尽(精确)的方法搜索的局部最小值或其近似(9]。

本文提供了一个广泛的调查最近的文献对包装圆形物体。文学可以分为两类:论文寻找最优解或展示的最优模式,和论文试图改善以前公布的结果(10]。独立的分类,这些论文寻找最好的解决方案,不管的改善幅度或计算费用10]。部分2认为该地区的情况是一个正多边形而部分3关注该地区的情况是圆形的。最后,部分4是一个总结。

2。多边形区域

在本节中,我们区分两——三维情况。

2.1。二维情况

包装在一个二维的几何形式,如一个单位正方形或unit-side三角形(11)是最好的已知类型的极值平面几何问题(12]。在此,该地区的情况是一个广场,一个矩形,多边形进行了讨论。

2.1.1。包装圈成一个正方形

的问题之一,吸引了最多的关注在于包装相同的单元内圈与最大化的目标之间的最小距离圆圈的中心;也就是说,确定最大半径的相同的圈子,融入一个正方形的边长是(即之一。、固定和已知)。是一个几何问题,可以被视为一个连续全局优化。它可以表示为决策变量的最优水平和因此在哪里表示圆心的坐标和是欧氏距离分离圈子的中心和

这个包装问题相当于散射的问题点在单位广场这样的最小距离任何一对点之间是最大化。这种散射问题可以表示为凸函数的不同项目(13)或作为一个二次优化问题14)或连续非线性不等式约束全局优化一个(15]。前两个配方是有趣的数学家,因为他们是困难的优化问题;然而,他们没有任何实用价值(16]。过去的配方,它使用几何方面的问题,是更有效的。它可以表示为在哪里表示的坐标点原问题的最优解相关的散射问题如下: Maranas et al。15]求解散射问题使用迈诺斯和gam建模语言。他们雇佣multistart策略提高寻找全球解决方案问题的概率高达30圈。

Nurmela和Oestergard17]介绍,圆包装成一个单位广场,一个不同的非线性规划制定基于一个能量函数在哪里代表之间的欧几里得距离圆圈的中心和是一个比例因子,是一个正整数。能量函数的最小化,广场内的产品配件,不重叠。问题是由一个适当的变化转化为一个无约束的变量,和解决使用multistart混合线搜索算法,使用渐变类型方向一开始和牛顿型方向附近的解决方案。当地的优化从至少50随机生成解决方案。然后使用解决方案通过优化算法作为起点来解决系统的非线性方程,目的是提高解决方案的准确性。的问题是解决。发现一些替代方案,改善的方法的结果。它认识到一些普通模式大概适合小但成为nonoptimal大的值例如,平方晶格的包装是最优的但不是格雷厄姆和Lubachevsky [18)扩展的模式(17)使用一个台球模拟,让他们确定阈值指标高于它成为nonoptimal保证标识的常规模式。

棉子et al。19提出一种两阶段方法。第一个阶段是一个近似一个动作每一个点的适当选择方向的步长运行指数下降。第二阶段是一个精炼,第一阶段的结果是一个台球模拟的起点。他们最著名的包装改进和

Casado et al。20.]细分单元广场subsquares,他们通过将构造一个初始解点随机的中心subsquares截然不同。然后他们随机扰乱每个点。他们甚至可以接受一个摄动点nonimproving时(即。期间,允许回溯搜索)。基于这些结果,萨博(21开发一些新的正则点的模式。

和Raber右路放倒10)提供一个上限的最大半径相同的圈子,可以放入一个单位正方形。他们的问题建模为一个二次优化问题,并引入两个属性,必须满足至少一个最佳的解决方案。他们开发一个聪明的和有效的算法,从一般的矩形和,并利用问题的特殊结构和性能的一些解决方案。他们证明了最优,在一个精确,在文学最著名的解决方案和他们改善现有包装并证明其在给定的公差和最优性但不证明其最优性。他们的算法提供了一个生动的例子,计算的指数增长的努力增加。例如,试图改善先前计算的解决方案需要小于0.5秒超过2分钟,超过30分钟为CPU计算时间超过27小时。

Markot和Csendes22和萨博等。23)提供了一个高效的算法来消除大的散射问题的次优解集。

Markot和Csendes24]利用区间算法的加速装置间隔和优化算法。证明他们的计算奠定了基础为解决前面打开包装实例28日29日和30圈。

Markot [25)提出了一种使用区间算术计算数值可靠的验证方法,它可以被视为一个“计算机辅助验证法”证明圆包装的结构属性问题。他证明了最著名的包装结构28日29日和30圈在最优结果,(除了对称和免费圈)的发生独特的包装。在所有三个案例猜最优结构独特的最优几何解决特定问题。

艾迪斯et al。26)再用形式表示的问题作为一个数学程序有效的本地搜索程序和确定可行的解决方案是相对容易;,与一个线性目标函数数学程序但反向凸二次约束。事实上,他们代替欧氏距离non-overlap约束的散射点配方的广场;也就是说, 作者推测,拥有一个漏斗景观问题,常见的一个功能分子构象问题。他们开发一种随机搜索算法,在以人群为基础的版本由单调盆地跳跃(MBH)。MBH迭代搜索一样,从一个局部最优转移到另一个没有太多破坏原来的局部最优的结构。它调查附近的局部最优通过检查如果邻国可能导致改善解决方案,并停止如果nonimproving邻居的数量超过一定阈值作为前缀。邻居通过扰动得到各界的位置和使用摄动解作为起点的一种局部搜索方法,将收敛于局部最优。的以人群为基础的版本MBH MBH适用于一套当地的最适条件(父母)的人口。每个局部最优(父)产生一套新的解决方案(人口的儿童)。随后,每个解决方案的新的人口(每个孩子)是compared-based不同措施,即每个元素上的人口父母寻找最接近的一个。如果孩子比最亲密的父母,它取代它。毕竟儿童与父母的人口和一套新的父母获得,重启的过程。 This procedure improves 32 best known solutions in the range事实上,一个关键的成功基于人口的MBH是保持人口的多样性的不同测量(因此保证解决方案的探索更广泛的部分空间)保持足够的不同差距在个人的人口(8]。不同的不同措施,主要是基于成对集群圈之间的距离,介绍了(8]。测试表明,虽然没有单一的不同测量占据其他的,可以识别的一组不同标准保证最佳性能(8]。

面包车大坝et al。27)考虑不同但密切相关的问题问题的包装相同圈成一个单位正方形。包装问题的一些解决方案有强烈的阴影效果;也就是说,如果预计的或轴,解决方案有许多不同的投影点,远低于总体数量的点。因此,作者认为解决方案和额外的约束,投影点是否很好地分开。作者提出一个和(返回修改后的问题的最优解)和启发式方法点。

2.1.2。包装圈成一个长方形

一个问题有一个广泛的工业应用程序是汽缸托盘化。它由识别相同的圆的最大数量(一个已知半径),可以装进一个矩形的固定尺寸在矩形框内的圆圈应该完全和不应重叠。这个问题被列为一个背包问题的类型学沃斯切尔一如既往et al。28]。

柯瑞亚et al。29日)引入一个新的最优的圈数上界装进一个矩形。事实上,现有的类似的问题范围不能适应循环包装情况。例如,绑定由矩形的面积比圆的面积效率低下是由于的存在不可避免的圈子中未使用的空间。其他边界利用矩形装进一个矩形的几何特征;因此,不适合这种情况。最后,使用的面积平方船体的圈子不产生一个最优值的上界,尽管它可以用作一个下界。发达绑定使用更好地估计可用区域的矩形。减去从整个区域矩形的外部区域对应于沿托盘未使用的空间边界和内部区域相应的圈子中未使用的空间,在圈子里有固定的安排。分析结果的五个不同方面的问题表明,发达绑定在现有的上界,并且它的差距从下界,得到应用模拟退火(30.圆筒包装问题,非常小。

Birgin et al。31日)解决这个问题通过求解一系列决策问题。包装每个问题研究的可行性相同的圆的半径成如果这样的包装是可行的,是增加了一个决策问题是解决了。算法停止决策问题时产生一个不可行的包装。决策问题是制定决策问题是可行的,如果目标函数的值为0,否则,不可行。事实上,如果任何一对圆圈重叠,之间的欧几里得距离中心将小于半径的总和: 相当于和暗示如果目标函数的值由(2。5)是零,那么每一个条款的总和等于零。因此,没有一个双圈重叠。

的问题(2。5)是一种非线性分段连续优化问题的目标函数连续一阶导数不连续二阶导数。即目标函数变化的分析定义之间的边界地区。这显然是一个缺点最小化算法基于二次模型,如牛顿法,享有良好的收敛性能。作者克服不连续问题通过一个连续的正规化黑森保证更稳定的迭代。他们使用GENCAN解决由此产生的问题,一个增广拉格朗日方法平滑函数的最小化与一般的约束。它使用,在面临方向选择的每一步,truncated-Newton方法,采用正规化黑森近似。这意味着搜索向量是一个近似的二阶近似函数的最小值在当前的脸。共轭梯度是用来发现这个方向。GENCAN正规化的黑森是更有效的比使用不连续黑森相同的方法。方法是重新启动50 000初始随机生成解决方案搜索全局最小值。

这个问题的一个变体是考虑不全同的圈子。乔治et al。32]提出一种非线性混合整数规划包装不恒等的圈子(已知半径)成一个长方形固定的尺寸。该模型认为连续变量和使用二进制变量信号的一个圆的包含/排除模式。模型可以表示为在哪里时获得的利润包括圆的半径在矩形这个模型包括二元决策变量,连续的决策变量功能约束强化这一事实是矩形,全封闭包装循环包装,没有一双圆重叠。这个模型是非常困难的解决使用任何现成的非线性混合整数数学规划求解。事实上,通常有许多不同的包装配置给相同的目标函数值。这些可行的解决方案只有在不同模式的圈子。此外,可行域是不连续的;即改善可行解发生只有当一个额外的整个循环可以放在矩形。此外,展览许多当地的最适条件的问题,在许多情况下是一个全局最优点是相对罕见的数量相比,第二个最好的解决方案。换句话说,目标函数由一个小数量的峰值大,相对平坦的表面。显然,这个模型不能解决甚至小型问题。因此,作者通过建设性的启发式方法解决了这个问题,产生不稳定或稳定构型。 A configuration is stable if every circle is adjacent to two sides of the containing rectangle, or to one side of the rectangle and to another larger circle, or to two circles, and is unstable otherwise. These heuristics apply a set of common sense rules: (a) first fit decreasing packing, (b) corner packing, (c) edge packing, (d) packing identical circles in a cluster, (e) generating stable configurations, (f) random positions, (g) spin-out, and (h) shake down. The heuristics are coupled with a genetic algorithm which chooses the position of every circle. The first fit rule (i.e., rule (a) is reinforced for all solutions; that is, the circles are sorted in a nonincreasing order of their diameters for all solutions. The authors show experimentally that the quasi-random rule (i.e., rule (f) coupled with the genetic algorithm yield the best solutions. Hifi et al. [33)问题的模拟退火适应这种变体。他们开始从superoptimal非可行解和恢复可行性通过移动某些圈子的地带。

另一个问题是找到感兴趣的矩形的尺寸可以包含的最小面积不重叠的一致相同的圈子(已知的固定半径),矩形的宽度比高度是可变的。事实上,当封闭矩形的长宽比是固定的,最密集的包装最小化两个矩形的面积和周长。然而,通过允许一个变量长宽比,两个最适条件相同数量的圈子可能有所不同

Lubachevsky和格雷厄姆(34使用计算技术,包括两个独立的算法:受限制的搜索和压实机模拟。限制搜索运营假设所需的最小实现一组配置远小于设置的所有可能的配置。一组被限制为只包括六角模式、方格网模式,他们的混合动力车,模式通过删除某些圈子里从这些模式。一个配置被定义为6参数:这个号码最长的圈子里行,安排在一个六角交替模式的行数,那些rows-among六角排列行圈,中堆放的行数方格网模式,那些由方格网的行中圈,和“monovacancies”或孔的数量。这六个整数受到一组约束诱导模式及其封闭矩形。限制搜索过程并不一定产生全球最佳。压实机模拟生成一个随机的从可行但稀疏的配置圈躺在一个矩形(大)。然后,仿真模拟压实机的每一方矩形圈紧迫,所以圈被迫向彼此,直到他们果酱。圆圆或circle-boundary冲突解决使用硬碰撞仿真,没有重叠或boundary-penetrating圈过程中发生。仿真是重复很多次,开始与不同的圈配置和包装导致最小的封闭矩形的周长是保留作为包装的最佳候选人。压实机仿真没有作出假设关于包装产生的模式;即圆圈可以自由选择任何最终配置,只要它是卡住了。然而,这将导致模拟需要大量的初始配置之前达成一个好的候选人包装(相同的质量,通过限制搜索)。例如,它可能需要几分之一秒找到最小周长15圈的包装限制搜索但与成千上万的天试图模拟产生相同的答案。使用这两种技术,作者推测的最小值

Lubachevsky和格雷厄姆(35)需要注意的是,在许多的确定最佳配置,圆圈形式通常定期方格网或六角模式或其混合动力车。然而,对于大多数的值例如,对于,他们证明最优不可能通过这种定期的安排。一般来说,常规的最佳包装模式的偏差是可预测的小局部修改常规模式。然而,一些确定的最佳配置显示意想不到的重大违规行为扩展。这些对应的范围的实例也就是说,对于和57。最小边界矩形包含的高宽比相等的圆1

感兴趣的另一个问题是包装固定长度的圈成一个矩形和最小宽度没有超过矩形的尺寸或有重叠的圆圈;即圆二维开放维度问题[28]。

斯托亚和Yaskov36)提出一个数学模型不恒等的圈子问题的变体作者讨论了特征的特点以及由此产生的多维multiextremal问题的可行域。然后解决它使用和和梯度下降法的结合。他们寻找全球线性目标函数的极值调查所有极端点,通过构造搜索树排序。每个极端点由独特的结束节点搜索树的节点对应一个二次系统方程。他们从一个极端到另一个更小的目标函数值通过计算步长。他们说明他们的方法的应用程序可以通过一组例子,表明他们找到全局最小然而,对于他们的方法可以获得,一般来说,只有一些近似的全球最低。

同样的问题和模型公式,斯托亚和Yaskov9]提供了一个原始的方法从一个局部最小值跳跃到另一个在寻找全球最低的一个近似。对于给定的局部最小值,方法选择,通过拉格朗日因子,两个不恒等的圆圈和交换他们的位置。也就是说,这两个圆圈的半径可以作为变量;因此,该方法不适合包装相同的圈子。方法增加的尺寸问题,但允许从一个局部最小值转换到另一个,这样的过渡减少目标函数值。事实上,解决问题的方法是基于同时增加维度和选择运动方向从一个局部最小值到另一个通过一个简化梯度法以及活跃的不平等和牛顿法的概念。因为一些系统的活跃的不平等可以不一致,克服不一致被认为是。最终的解决方案取决于第一个极端点的选择。因此,获得一个好的近似全球最低需要应用afore-described方法与不同的极端点开始。计算测试表明该方法,可以视为一个隧道的方法逃离当地minimizers-coupled与当地一个高效的解决者和multistart策略,是充分有效的35圈。事实上,它执行比和方法(36]。

同样的问题,音响,M 'Hallah [37]提出建设性的启发式遗传算法。两种算法寻找良好的块,使用一个适应当地最好的位置程序(BLPP) [38,39包装圈。适应BLPP (ABLPP)位置圈上左边的位置但利用循环的部分探索更有前途的职位。ABLPP更简单和更快的比BLPP自定位圈不能再翻译,和一圈可以定位在洞已经生成的包装的。

为了解决同样的问题,黄等。40)首先研究决策问题,检查包装的可能性圈成一个矩形的固定尺寸。他们解决问题的决定使用两种贪婪算法:B1.0 B1.5。算法B1.0选择下圆定位根据maximum-hole学位(磁流体动力)规则,这是启发人类活动的包装。事实上,磁流体动力,职位当前循环最大孔度角落位置在所有可行的位置,也就是说,没有重叠的任何已经拥挤的圈子。一个角落当前循环的位置是一个可行的位置如果当前圆相切两个已经装圈或切线已经满圆的周长算法B1.5改善B1.0 self-look-ahead搜索策略来决定,在每次迭代中,圆包装及其位置。作者解决原始问题的最小宽度的确定一个矩形固定长度和包含圈,通过应用二分搜索迅速获得一个足够好的上界的宽度。他们,然后,逐步减少这个上界,直到B1.0和B1.5发现一个成功的配置。最后然后作为上界最小宽度的矩形。

崔(41)制定同样的问题作为一个约束圆形切割问题的目标减少材料浪费,并提出一种启发式解决方案策略,生成t形切割模式。

卡斯蒂略et al。42)模式使用相同的问题线性约束,非线性约束条件(如[36),一组简单的边界。最小化的目标函数可以包含矩形的面积或它的一个维度。作者应用现成的通用的全局优化技术。进一步改善他们的结果,他们运用归纳的策略,算法初步安排,互换所有大小对相邻圆到不可能的改进是可能的。

同样的问题,Akeb和音响系统43)提出了三个启发式。第一个位置半径的圆下令nonincreasing顺序使用最好的本地位置规则。第二个应用启发式固定数量的次每次使用不同的圈子里的顺序。最后,第三个结合了定向搜索和二分搜索矩形的宽度。

Birgin和Sobral44)考虑的问题最小化一个对象,其中包含的维度不重叠的项目,对象可以是两个或三维矩形,三角形,方形,圆形或圆,和项目。他们开发两次可微非线性规划模型,减少了计算nonoverlap的强化成本约束。事实上,该模型要求每一个经典的约束圈完全嵌入含有圆,但取代了由单一约束不重叠的约束: 这个约束有两个主要优势。并不是所有的的左手边方程(即需要评估。,对造成的数量之和),识别导致的双项可以进行求和模型是解决,从几个随机生成的初始解决方案,使用本地解决基于增广拉格朗日方法平滑约束最小化。

2.1.3。包装圈在一个紧凑的多边形集合

斯托亚和Patsuk45)考虑覆盖一个紧凑的多边形的问题设置相同的圆的最小半径。他们建立一个数学模型问题基于泰森多边形法多边形和其特点进行调查。然后应用Zoutendijk可行方向法的修改版本搜索局部最小值,并设计一种特殊的方法选择的起点。他们的成功说明建议的方法与许多计算例子。

2.2。三维情况下

包装三维物体如球体出现在各种行业的分支(46]。例如,随机几何对象的包装已经被用来作为模型来表示液体和玻璃的结构材料;研究现象如导电性、流体流动、应力分布、和其他颗粒材料的力学性能;和调查过程如沉降、压实和烧结46,47]。此外,他们在医学应用radio-surgical治疗计划(48在粉末冶金),三维激光切割(49安排和装载集装箱运输),(31日),在切削不同的天然水晶,在布局的计算机,建筑,等等。在此,我们认为该地区的情况是一个多维数据集,一个平行六面体,汽缸和三维多面体。

Gensane [50)描述了一种适应的台球模拟寻找最大半径的相同的可以容纳的球体多维数据集。台球模拟是一个随机的方法,模拟了理想化的台球运动在一个领域,与球的初始中心及其随机方向是固定的。获取配置这些概率选择的结果。提高随机算法的收敛,他引入了系统的扰动。他认为四个不同版本的模拟。在算法,小球不沿直线但随机,并实现一个随机游走。在算法,随机波动的幅度逐渐降低,当越来越多的球体产生堵塞。算法介绍了同步扰动的所有领域。算法交替的三种类型的扰动。作者应用摄动台球算法和获得所有最优和最著名的模式32。他改善了以前最著名的解决方案除了和他证明显示配置的存在和通过显式地构建它们。他推测,球体的中心之间的最小距离是常数范围内的最优模式他表明,与二维情况下,早些时候,台球算法无法生产不使用扰动最优配置好的精度。

斯托亚和Yaskov51包装处理优化问题相同的球体的半径成一个平行六面体 最小的高度他们建立一个数学模型: 在哪里球体的坐标吗这个模型有一个线性目标函数,但线性和二次约束。可行域通常是断开连接的连接组件连接。它的边界是由线性和反向二次凸表面。基于这个multi-extremal的特殊性,np难度问题,作者提供了一个解决方案策略包括一个特殊的搜索树结构,修改的Zoutendijk可行方向法计算局部最小值,和一个修改递减附近寻找一个近似方法对全球最低。

斯托亚和Yaskov52使用类似的方法进行包装相同的球体的半径到一个正确的循环油缸已知的半径和最小高度他们使用的模型是类似于在51除了约束有关和一个球体的坐标取而代之的是分别。作者获得最好的结果的日期和500年。他们的方法是非常有效的和能处理实例在很短的计算时间。

斯托亚et al。53[]使用类似的技术考虑9)确定的包装不全同的球,每个半径成一个平行六面体固定长度的和宽度但变量高度最小化的目标模型很直观: 作者为数值结果提供多达60个球体。Yaskov et al。54解决的问题的数量最大化相同的可以装进一个球圆柱由域。他们建立一个数学模型基础上的概念函数(55),和设计解决方案算法基于优化方法的修改变量组。

王(48)制定数学自动radio-surgical治疗计划问题领域的包装成一个三维的地区包装密度大于给定的阈值水平。他证明了这个包装问题是np完备性,提出了一种近似算法来解决这个问题。

Sutou和戴56)吸收自动化radio-surgical治疗计划问题包装不恒等的球体的三维多面体体积之和最大化的目标球包装的多面体。他们制定这个问题作为一个非凸优化的二次约束和一个线性目标函数。的基础上与这个问题相关的特殊结构,他们提出了各种各样的算法,显著改善现有的分支和一般的非凸二次规划算法。他们将启发式算法合并到分支界限法,以加强其效率。计算研究表明该算法的效率有限大小的问题。

斯托亚和Chugay46考虑包装的问题气缸平行六面体形状为一个三维的地区这样的高度占领地区很小的一部分,每一对的物品之间的距离,每个包装项目之间的距离和边境地区的必须大于或等于给定的距离。问题的数学模型建立及其特性研究。方法快速建设的起点,寻找局部最小值,和一个特殊的简单搜索的局部最小值获得良好的近似全球最低。

3所示。圆形区域

当对象和该地区二维的圈子里,这个问题被称为圆(CPP)包装问题。CPP有许多重要的应用在制造业、物流、网络、设施布局、和材料科学42]。例如,在汽车行业,设计工程师必须估计的大小上钻洞的尸体的车,他们计划通过这束线,汽车传感器连接到显示板(57]。洞必须大到足以让所有电线,但尽可能小,以避免不必要地削弱身体(57]。CPP也遇到了摩托车行业的生产的链轮(58]。同样,感兴趣的是电信/电力/石油公司和炼油厂通过包不同类型的电缆,管道,保温管道通过圆柱形状很长的距离。气缸的直径越小,成本越便宜。最后,CPP出现在材料科学,它是用来解释拓扑关系分析正常晶粒生长时遇到的两个维度(59和模型特定吸收的分子模式60]。

本节区分圈是相同的,这样不恒等的圈子。

3.1。包装一样的圆圈

包装一样的圈成一个单位圆一直被视为一个通用的问题几乎没有工业的相关性。然而,解决仍然是具有挑战性的。Mladenovic et al。6]应用一般再形成下降问题的启发式(RD)识别的最大半径相同的圈子,可以装进一个单元包含循环。RD迭代从解决CPP笛卡尔坐标表达转向解决它用极坐标表示,反之亦然,直到没有进一步改善。笛卡尔坐标系中表示的模型而它的配方在极坐标下在哪里表示圆的极坐标事实上,的距离是从原点的极坐标系统(同时在此包含圆的中心),和由直线部门分隔的角度加入吗极坐标的起源和水平轴。也就是说,和RD允许使用一阶非线性规划解决信息逃离静止的点。实验结果与100相同的圆圈显示实例RD 100倍速度比二阶非线性规划方法,最著名的解在40的情况下,而在其他情况下,误差不超过1

Birgin和Sobral44]解决他们的新模式,从最初几个解决方案,使用本地解决基于增广拉格朗日方法平滑约束最小化。与100相同的报告解决方案实例圈配合最好的已知的解决方案(规定的公差)。

品特[61年]讨论了李普希茨全球优化器(LGO)软件集成了全球和局部作用域搜索方法来处理一个非常通用的一类非线性优化模型。特别是,他评论的主要特点和基本用法LGO实现与通用代数建模系统(gam)。然后,他说明了其包装的应用程序相同的圈成一个单位圆的目的是确定的最大半径小的圆圈。

3.2。包装不恒等的圈子

CPP变体之一在于包装不恒等的圈子里没有包含圆重叠到最小其中每个圆特点是其半径。我们的目标是寻找最好的包装圈到最好的包装浪费最小化。CPP,根据沃斯切尔一如既往的类型学et al。28),是一个二维的开放维度问题,因为所有的小物品(圆形)必须包装和大对象的扩展(圆形)没有得到但必须最小化。CPP相当于找到坐标每一个圈半径和协调的这样没有一双圆和重叠。正式,问题可以表示为决策变量的最优水平和这是在哪里第一组约束加强每一个圈内的完全控制第二组强化了没有任何一对不同的圈子里的重叠约束。最后一个约束提供了一个积极的下界为包含圆的半径。它代替nonnegativity约束的模型使得CPP无界的消除。CPP有一个线性目标函数但非线性约束。尽管其组可行解决方案分段光滑表面边界,CPP是一个困难的问题解决(62年]。出于实用的目的,CPP可以通过设置来解决或任何其他的坐标

包装如圈成一个正方形或长方形,Birgin和Sobral44)用CPP的non-overlap约束使用的单约束(2.11)。

另外,这个问题可以在极坐标下制定: 在哪里表示圆的极坐标事实上,是中心的中心的距离的和由直线部门分隔的角度加入吗来水平轴。也就是说,和

CPP是一个困难的问题解决(62年]。它带来了一些挑战。它不能通过纯粹的分析方法能够有效的解决42]。它嵌入两个极其困难的问题:一个纯粹的连续优化问题,和一个组合63年]。此外,它有无限的选择最适条件(62年),一个指数的地方最适条件不是全局最优,和不可数的静止点(6(即。,solutions that satisfy the KKT conditions but which do not correspond to local optima [63年])。此外,CPP的解决方案是对初始解的选择(在非线性优化一样)6]。最后,条目的数量越大,大局部最小值和静止的点的数量;因此,简单multistart全局优化策略需要更多的本地最小化达到全局最小值(44]。

CPP被基于三种截然不同的方法:解决决策问题(获得新包装使用的最大孔度规则)加上一些边界的机制建设性的启发式和非线性规划。

的第一个方法修复一个半径的值包含圆的和solves-based最大孔度的概念或模拟弹性部队击毙,决定问题,检查是否一个可行的包装的圈是可能的。当这样的包装是可行的,半径是下降,重复这个过程,直到没有可行的包装。

使用这种方法,王et al。64年]形容quasi-physical quasi-human算法模拟的物理模型的光滑圆筒包装在一个容器中。quasi-human策略然后提出触发跳卡对象为了摆脱局部最小值。可吸收一种自适应的禁忌搜索算法。它随机生成一个初始模式,每个圈子都有其中心包含内部循环。它可以测量解决方案的不可行性,翻译一个圆,其立场是不可行的,两轴。翻译的距离是一个函数的自适应步长和当前的目标函数的梯度模式。自迭代过程收敛迅速在可行的地方最适条件,圈子可以跳进包含圈内寻找一个新的职位。

免漆和严65年)制定CPP的势能函数通过模拟系统弹性固体。他们位置随机各界内部含有圆。如果这个配置没有重叠的圆圈,一个可行的解决方案。否则,弹性重叠产生的排斥力量驱动重叠的圆圈来恢复他们的形状和大小。圈沿着直线移动,相互碰撞和包含循环,直到弹性力的构成下降到零。如果重叠的数量也下降到零,然后这个过程停止一个可行的解决方案。否则,重新启动的过程。作者给quasi-physical算法,达到全局最小势能函数的模拟运动的重叠的圆圈。他们改善quasi-physical算法通过使用两种策略:一个early-escape策略,帮助搜索逃离局部最小值,和一个好的前景策略生成好的初始搜索解决方案。

苏吉哈拉et al。57应用一个收缩和策略。他们含有各界构建一个足够大的圆,然后它的半径减少翻译圈使用收缩和迭代策略。他们进一步加速他们的策略使用圆Vonoroi图来确定任何突出的翻译距离内圈的时候保持各界包含循环。

张,邓66年王]采用的模型等。64年),并使用混合方法组成的模拟退火探索当前解决方案的社区,和禁忌搜索实现跳跃。当探索当前解决方案的社区,一个圆圈的位置是不可行的翻译并计算你的邻居的程度的不可行性。邻近的解决方案,减少程度的不可行性成为现任解决方案而nonimproving解决方案被接受与给定的概率,减少随着搜索变得更有选择性。这种方法常常很快收敛于当地最适条件不可行,采用禁忌搜索允许圈子导致不可能实行跳出他们的当前位置和随机获得一个新职位包含内循环。

黄等。67年)解决CPP使用两个启发式A1.0 A1.5,扩展的的方法68年]。他们用磁流体动力的概念的一个圆圈的位置是给一个固定的值和的位置已经拥挤的圈子。A1.0选择圆包装可行位置有孔度最高。它是运行次;每一次从两人的不同圆圈。A1.5 A1.0修改版本。它应用一个自我先行的寻找每一个可行的角落位置圆的包装。考虑到组装圈,A1.5包在每一个可行的角落位置和使用A1.0包所有剩下的东西。如果它成功地包所有项目,A1.5停止;别的,它选择可行的角落位置产生不可行解的密度和最高追求包装剩余的圈子。实验结果,在基准实例100圈,表明A1.5具有良好性能的解决方案对包装质量和计算时间不平等的圈子。

黄和陈69年王]提出算法的一个改进版本的et al。64年)与平衡约束求解CPP。一个有效的战略,加快搜索过程中引入梯度法。

陆和黄70年)合并的概念最大的洞穴学位角落占领行动改善烫。现有算法的比较表明,它比张低效率和邓小平66年)都有几个大型圆相同实例的所有的启发式基于最大洞的概念的学位,但获得新的下界几个基准实例不恒等的圆圈。

Akeb et al。71年)解决CPP使用一种自适应波束搜索算法结合了定向搜索和本地位置距离和二分搜索的概念。它使用一个宽度第一束搜索开发树的每个节点的决策是基于最大孔度,使用当地的最小距离。它逃脱局部最小值采用多元化策略。

Akeb et al。72年)解决CPP使用二进制搜索来确定和一束搜索检查包装的可行性圈到当半径是一个节点的水平定向搜索树的对应部分的包装圈到树的每个节点的潜力评估通过超前战略,从当前节点的分包装,分配每个打开圆其最大孔度的位置。定向搜索停止当超前战略确定了一个可行的包装或当它所有节点能了解的。

的第二个方法是一种建设性的方法,先后包项目和搜索包含最小半径的圆。例如,音响,M 'Hallah [3)提出一个动态的、自适应的局部搜索算法遍历动态耦合的两个互补的步骤在寻找最小的圆。在每个迭代中,该算法识别潜在的集合最好的地方一个圆圈的位置鉴于先前包装圆圈的位置,并确定每个职位包含圆的坐标和半径最小的。最好的本地位置最小化当前包含圆的半径。就是每一次额外的循环,中心和包含圆的半径是动态更新,和最小的圆。nonincreasing顺序过程考虑了圆圈的半径。

音响,M 'Hallah [62年)提出一个三相近似算法。在第一阶段,该算法先后包圈的有序集合。它搜索每个圆的“最好”的地位已经拥挤的圆圈的位置在最好的位置最小化当前包含圆的半径。在第二阶段,该算法试图减少应用包含圆的半径(i)对减少强化搜索搜索间隔和(2)一个多样化的搜索应用程序的布局方法。在第三和最后阶段,该算法引入了一个重启程序,探讨了社区目前的在寻找一个更好的解决方案排序的圆圈。

的第三方法解决了CPP使用随机multistart全局优化运行现有货架优化。例如,品特和康帕73年使用LGO]目前的数值结果。卡斯蒂略et al。42应用各种现成的通用的全局优化技术,并比较它们的性能。他们进一步提高结果的通用解决方案实施后验战略,给定一个算法初步安排,互换所有大小对相邻圆到不可能的改进是可能的。

艾迪斯et al。63年)混合标准局部优化程序与当地移动之间的最小值,同时强化不同但减少解决方案空间的解决方案。由此产生的方法获得最著名的50圈和解决的问题

音响,M 'Hallah [4)表明,该组合结构和CPP的连续优化方面不应该分别对待,但同时必须考虑。他们的建议是基于两种新设计的算法的性能比较:BS1 BS2。BS1是一种两阶段方法。第一阶段使用一束搜索(连同包装启发式的3)和非线性优化)来确定最佳订购。第二阶段考虑到圆圈标识的顺序在阶段1中,并使用一束搜索找到每个圆的最佳位置。BS2嵌入搜索到一个搜索树,在树的每一层都有两个子层:一个圆的包装,一个圆的包装位置。拟议的BS1和BS2在本质上是建设性的,但使用全局优化技术。他们寻找最好的排序的圆和圆的最佳位置给那些已经包装,减少当前包含圆的半径。他们进一步提高每个当地的部分解决方案通过应用全局优化技术。他们大部分的地图搜索空间,引导搜索进入最有前途的社区,允许逃离局部最小值,并加强解决方案不同。

Al-Modahka et al。74年]提出一种自适应混合算法,解决了组合CPP结构通过一个禁忌搜索(TS),及其持续优化方面通过嵌套分区(NP)和非线性优化。混合TS / NP算法利用TS的优点进行本地搜索旨在识别一个好的排列的圆圈而NP进行全局搜索来确定各自的最佳位置。提供的结果进一步修改/改进使用一些多元化策略。数值例子表明,该自适应混合算法是有效的和鲁棒性。

4所示。结论

综述了最近文献的NP困难的优化问题包装循环物品/对象到欧几里得区域的平面。这具有挑战性和难度的问题有很多实际应用,收到了很多的关注。它已经被建设性解决方法再加上meta-heuristics或局部搜索方法,通过仿真模拟一些物理或分子现象,通过分支和bound-type方法,和非凸优化。任何一种方法解决问题的连续和离散结构使用标准良好的局部优化的例程,当地局部最小值之间移动,和执行局部最小值之间的不同。这些方法的成功是由于计算机科学与技术的进步;随后,许多解决非线性处理能力的大型实例。

确认

作者感谢两位匿名裁判的有用的评论。这项研究部分由科威特大学研究格兰特SS02/06。第二作者感谢他们的支持。

引用

y . g .斯托亚“数学几何设计方法,”先进的CAD / CAM: PROLAMAT82学报》,列宁格勒,苏联,1982年5月,页67 - 86,北荷兰,阿姆斯特丹,荷兰,2003年。视图:谷歌学术搜索
p·g·萨博,m . c . Markot t . Csendes e . Specht l . g . Casado。加西亚,新方法圆包装在一个方形:与程序代码》第六卷施普林格优化及其应用施普林格,纽约,纽约,美国,2007年。视图:Zentralblatt数学|MathSciNet
M .音响,r M 'Hallah,“动态自适应局部搜索算法的循环包装问题,“欧洲运筹学杂志》上,卷183,不。3、1280 - 1294年,2007页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
M .音响,r M 'Hallah,“梁搜索和非线性规划工具的圆形包装问题,“国际期刊《运筹学的数学,1卷,不。4、2009。视图:谷歌学术搜索
p . r . j . Ostergard“书评”,电脑与行动研究36卷,第278 - 276页,2008年。视图:谷歌学术搜索
n . Mladenovic f . Plastria, d . Urosevic”再形成下降应用于圆包装问题,“电脑与行动研究,32卷,不。9日,第2434 - 2419页,2005年。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
m和f·舍恩右路放倒“高效大规模全局优化算法:Lennard-Jones集群,”计算优化和应用程序,26卷,不。2、173 - 190年,2003页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
a . Cassioli m,右路放倒和f·舍恩“以人群为基础的全局优化算法,不同措施”中出现计算优化和应用程序。视图:出版商的网站|谷歌学术搜索
余。斯托亚和g .丫'kov”的数学模型和解决问题的方法,将various-sized圈成一片,“欧洲运筹学杂志》上,卷156,不。3、590 - 600年,2004页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
m和美国Raber右路放倒,“包装相等的圆广场:确定性全局优化的方法,”离散应用数学,卷122,不。1 - 3、139 - 166年,2002页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
r·l·格雷厄姆和b . d . Lubachevsky”密集的包装相同的磁盘在一个等边三角形 $22$ 来 $34$ ,“电子杂志的组合,卷2,第一条,1-39,1995页。视图:谷歌学术搜索|Zentralblatt数学|MathSciNet
c .奥迪特·汉森和f . Messine,“为凸多边形,极值问题”杂志的全局优化,38卷,不。2、163 - 179年,2007页。视图:出版商的网站|谷歌学术搜索|MathSciNet
r·霍斯特和n v Thoai直流编程:概述”,优化理论与应用》杂志上,卷103,不。1页1 - 1999。视图:出版商的网站|谷歌学术搜索|MathSciNet
美国Raber,非凸二次全局优化问题:解决方案方法,应用程序和相关的话题特里尔大学,博士论文,特里尔,德国,1999年。
c·d·Maranas c . a . Floudas和p . m . Pardalos”新结果在相等的圆的包装在一个广场,“离散数学,卷142,不。1 - 3、287 - 293年,1995页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
r . b . Kearfott严格的全球搜索:连续问题13卷非凸优化及其应用Kluwer学术出版商,多德雷赫特,荷兰,1996年。视图:Zentralblatt数学|MathSciNet
k . j . Nurmela和p . r . j . Ostergard”包装50相等的圆广场,“离散与计算几何,18卷,不。1,第120 - 111页,1997。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
r·l·格雷厄姆和b d Lubachevsky”,重复的模式密集的包装相同的磁盘在广场”电子杂志的组合,3卷,不。1、R16 1卷,1996页。视图:谷歌学术搜索|Zentralblatt数学|MathSciNet
d . w·鲍尔,j·多诺万,r·l·格雷厄姆和b . d . Lubachevsky”提高密集的包装相同的磁盘在广场,“电子杂志的组合,7卷,不。1、R46 1 - 9, 2000页。视图:谷歌学术搜索|Zentralblatt数学|MathSciNet
l . g . Casado加西亚,p·g·萨博和t . Csendes相等的圆包装在广场。二世。新结果100圈使用TAMSASS-PECS算法,”优化理论:从Matrahaza最近的进展f . Giannessi, p . m . Pardalos和t . Rapcsak, Eds。59岁的卷应用优化,页207 - 224,Kluwer学术出版商,多德雷赫特,荷兰,2001年。视图:谷歌学术搜索|MathSciNet
p·g·萨博”,一些新结构的“平等圈包装在一个方形“问题”,中部欧洲运筹学杂志》上,8卷,不。1,第91 - 79页,2000。视图:谷歌学术搜索|Zentralblatt数学|MathSciNet
m . c . Markot和t . Csendes”,一个新的验证优化技术”包装圈在一个单位广场”的问题,“暹罗杂志上优化,16卷,不。1,第219 - 193页,2005。视图:出版商的网站|谷歌学术搜索|MathSciNet
p·g·萨博,m . c . Markot和t . Csendes”geometry-circle包装进入广场,全局优化”在全球优化论文和调查,奥迪特、p·汉森和g . Savard Eds。第七卷种族传说25周年系列施普林格,页233 - 265年,纽约,纽约,美国,2005年。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
m . c . Markot和t . Csendes”,一个可靠的圆面积缩小技术解决包装问题,“计算,卷77,不。2、147 - 162年,2006页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
m . c . Markot”间隔方法验证结构最优循环包装配置在单位广场”计算和应用数学杂志》上,卷199,不。2、353 - 357年,2007页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
b·阿迪斯m,右路放倒和f·舍恩“磁盘包装在一个方形:一个新的全局优化方法,”通知杂志上计算,20卷,不。4、516 - 524年,2008页。视图:出版商的网站|谷歌学术搜索|MathSciNet
e . r . van大坝,b . Husslage d .窝Hertog和h . Melissen极大极小拉丁超立方设计在二维空间中,“运筹学,55卷,不。1,第169 - 158页,2007。视图:出版商的网站|谷歌学术搜索|MathSciNet
g·沃斯切尔一如既往,h . Haussner和h·舒曼”一种改进的类型学的切割和包装问题,“欧洲运筹学杂志》上,卷183,不。3、1109 - 1130年,2007页。视图:出版商的网站|谷歌学术搜索
m·h·科雷亚,j·f·奥利维拉和j·s·费雷拉,“一个新的上界的圆筒包装问题,“在运筹学国际交易,8卷,不。5,571 - 583年,2001页。视图:出版商的网站|谷歌学术搜索
m·h·科雷亚,j·f·奥利维拉和j·s·费雷拉,“缸包装通过模拟退火,”尽管Operacional,20卷,不。2、269 - 284年,2000页。视图:出版商的网站|谷歌学术搜索
e . g . Birgin j·m·马丁内斯,d . p . Ronconi”优化圆筒包装成一个矩形容器:非线性的方法,”欧洲运筹学杂志》上,卷160,不。1,19-33,2005页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
j·a·乔治j·m·乔治,和b . w .拉马尔,“包装不同大小的圈成一个矩形容器,”欧洲运筹学杂志》上,卷84,不。3、693 - 712年,1995页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
m . Hifi诉Th。Paschos诉Zissimopoulos,“模拟退火方法的圆形切割的问题,“欧洲运筹学杂志》上,卷159,不。2、430 - 448年,2004页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
b d Lubachevsky r·l·格雷厄姆,“密度相等的圆的包装在矩形变量比例,”离散与计算几何:Goodman-Pollack纪念文集b . Aronov s·巴苏,j . Pach和m . Sharir, Eds。25卷算法和组合施普林格,页633 - 650年,柏林,德国,2003年。视图:谷歌学术搜索|Zentralblatt数学|MathSciNet
b . d . Lubachevsky r·l·格雷厄姆,“最小边界矩形封闭全等重叠圆圈,“离散数学,卷309,不。8,1947 - 1962年,2009页。视图:出版商的网站|谷歌学术搜索
y . g .斯托亚和g . n . Yaskov”优化问题的数学模型和解决方案方法放置矩形和圆考虑特殊限制,”在运筹学国际交易,5卷,不。1,45-57,1998页。视图:谷歌学术搜索|Zentralblatt数学
M .音响,r M 'Hallah“约束圆形切割问题的近似算法,”电脑与行动研究没有,卷。31日。5,675 - 694年,2004页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
M .音响,r M 'Hallah”,最好的本地位置的启发式方式的二维布局问题,“皆Informatica Universalis。国际期刊信息,卷2,33-56,2002页。视图:谷歌学术搜索
M .音响,r M 'Hallah”混合算法的二维布局问题:规则动词和不规则形状的情况下,“在运筹学国际交易,10卷,不。3、195 - 216年,2003页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
李y, w .问:黄,h . Akeb和c·m·李,“贪心算法对包装不平等圈成一个矩形容器,”运筹学学会》杂志上卷,56号5,539 - 548年,2005页。视图:出版商的网站|谷歌学术搜索
崔y”,生成最优循环空白t形切割模式”,电脑与行动研究,32卷,不。1,第152 - 143页,2005。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
卡斯蒂略,f·j·康帕,j·d·品特“全局优化解决圆包装问题:数值结果和工业应用,”欧洲运筹学杂志》上,卷191,不。3、786 - 802年,2008页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
h . Akeb和m . Hifi”算法循环二维开放维度问题,”在运筹学国际交易,15卷,不。6,685 - 704年,2008页。视图:出版商的网站|谷歌学术搜索|MathSciNet
e . g . Birgin和f·n·c·Sobral最小化对象维球面圆和包装问题,“电脑与行动研究,35卷,不。7,2357 - 2375年,2008页。视图:出版商的网站|谷歌学术搜索
y . g .斯托亚和v . m . Patsuk”相同的圆覆盖一个紧凑的多边形,”出现计算优化和应用程序。视图:出版商的网站|谷歌学术搜索
y . g .斯托亚和a . Chugay气瓶和矩形平行六面体包装成一个给定的区域之间的距离,“欧洲运筹学杂志》上,卷197,不。2、446 - 455年,2008页。视图:出版商的网站|谷歌学术搜索
s·r·威廉姆斯和a . p . Philipse“随机包装领域和sphero-cylinders模拟机械收缩,“物理检查EID 051301条,卷。67年,9页,2003。视图:出版商的网站|谷歌学术搜索
j .王”包装的不平等的球体和自动放射外科治疗计划,”杂志的组合优化,3卷,不。4、453 - 463年,1999页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
甘m, n . Gopinathan x,和r·a·威廉姆斯,“预测任意形状的填料粒子的特征。”背风面22卷,第93 - 82页,2004年。视图:谷歌学术搜索
Th。Gensane”,密集的包装等领域在一个立方体,”电子杂志的组合,11卷,不。1、R33 1卷,2004页。视图:谷歌学术搜索|Zentralblatt数学|MathSciNet
y . g .斯托亚和g . Yaskov“包装相同的球体成一个长方体,”智能决策支持。目前的挑战和方法,Betrieb-Swirtschaftlicher Verlar Th博士。加布勒a . Bortfeldt, j . Homberger h·科夫g . Pankratz说道,r . Strangmeier Eds。,页47 - 67,GWV Fachverlage GMbH,威斯巴登,德国,2008年。视图:谷歌学术搜索
y . g .斯托亚和g . n . Yaskov”包装相同的球体直圆柱,”《第五ESICUP会议2008年4月,意大利拉奎拉。视图:谷歌学术搜索
y . g .斯托亚、g . n . Yaskov和g . Scheithauer”包装不同半径的实心球体paralleliped,”中部欧洲运筹学杂志》上,11卷,不。4、389 - 407年,2003页。视图:谷歌学术搜索|MathSciNet
g . Yaskov y斯托亚,a . Chugay“包装相同的球体成圆柱形域,”美国削减股票问题研讨会(WSCSP Miercurea-Ciuc 9月5日,罗马尼亚),页75 - 82,Alutus Miercurea-Ciuc,罗马尼亚,2006。视图:谷歌学术搜索
y . g .斯托亚j . Terno g . Scheithauer, t . Romanova。” $Φ$ 功能主要2 d对象。”皆Informatica Universalis。国际期刊信息,卷2,学会年会,2002页。视图:谷歌学术搜索
a . Sutou和y戴”,全局优化方法不平等的全局优化方法不平等在3 d球体包装问题,“优化理论与应用》杂志上,卷114,不。3、671 - 694年,2002页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
杉原k、m . Sawai h·佐野D.-S。金,d .金“磁盘包装线包的大小的估计,”日本工业与应用数学杂志》上,21卷,不。3、259 - 278年,2004页。视图:谷歌学术搜索|Zentralblatt数学|MathSciNet
k . A . Dowsland m·吉尔伯特·g·肯德尔,”一个圆的局部搜索方法减少问题出现在摩托车行业,“运筹学学会》杂志上,卷。58岁的没有。4、429 - 438年,2007页。视图:出版商的网站|谷歌学术搜索
m . w . Nordbakke: Ryum, o . Hunderi”曲线多边形、圆包装有限和正常的晶粒生长,”材料科学与工程,卷385,不。1 - 2、229 - 234年,2004页。视图:出版商的网站|谷歌学术搜索
w·伦道夫·f·Harary, p . g . Mezey”最大的研究单位圆的形状研究caterpillars-tools吸附模式,”离散应用数学,卷67,不。1 - 3、127 - 135年,1996页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
j·d·品特“与gam / LGO非线性优化”,杂志的全局优化,38卷,不。1,第101 - 79页,2007。视图:出版商的网站|谷歌学术搜索|MathSciNet
M .音响,r M 'Hallah“适应性和重新启动techniques-based算法循环包装问题,“计算优化和应用程序,39卷,不。1,17-35,2008页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
b·阿迪斯m,右路放倒和f·舍恩”有效地包装不平等的盘成一个圈,“行动研究快报,36卷,不。1,37-42,2008页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
w·h . Wang黄问:张先生,d .徐”包装的改进算法包含圆圈圈在一个更大的不平等,”欧洲运筹学杂志》上,卷141,不。2、440 - 453年,2002页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
h .麒和k燕”,一个简短的报告在一个简单的启发式搜索diskspacking问题,“《运筹学,卷131,不。1 - 4、101 - 108年,2004页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
D.-F。张,其子a.s.。邓,”问题的一种有效的混合算法包装包含圈,圈成一个更大的“电脑与行动研究,32卷,不。8,1941 - 1951年,2005页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
c . m . w .问:黄,y Li Li和r·c·徐”新启发式包装不平等圈成一个圆形容器,”电脑与行动研究,33卷,不。8,2125 - 2142年,2006页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
李y, w .问:黄,h . Akeb和c·m·李,“贪心算法对包装不平等圈成一个矩形容器,”运筹学学会》杂志上卷,56号5,539 - 548年,2005页。视图:出版商的网站|谷歌学术搜索
w·黄和m .陈”,注意:包装的改进算法包含圆圈圈在一个更大的不平等,”计算机和工业工程,50卷,不。3、338 - 344年,2006页。视图:出版商的网站|谷歌学术搜索
陆z和w·黄”圆烫解决包装问题,”电脑与行动研究,35卷,不。5,1742 - 1755年,2008页。视图:出版商的网站|谷歌学术搜索
h . Akeb M .高保真,r M 'Hallah,“一束搜索算法的循环包装问题,“电脑与行动研究,36卷,不。5,1513 - 1528年,2009页。视图:出版商的网站|谷歌学术搜索
h . Akeb M .高保真,r·M 'Hallah”的自适应波束搜索有预见性的算法循环包装问题,“修订在运筹学国际交易。视图:谷歌学术搜索
j·d·品特f·j·康帕,“非线性优化mathematica与math-optimizer专业。”数学教育和研究卷,10队,2006页。视图:谷歌学术搜索
i Al-Modahka、M .音响和r M 'Hallah,“包装圈在最小的循环:一种自适应混合算法,“修订运筹学学会》杂志上。视图:谷歌学术搜索

行动研究进展

文摘