矩形布局問(wèn)題吸引子法研究

王金敏， 齊 楊

（天津職業(yè)技術(shù)師范大學(xué)天津市高速切削與精密加工重點(diǎn)實(shí)驗(yàn)室，天津 300222）

矩形布局問(wèn)題吸引子法研究

王金敏， 齊 楊

（天津職業(yè)技術(shù)師范大學(xué)天津市高速切削與精密加工重點(diǎn)實(shí)驗(yàn)室，天津 300222）

吸引子法是布局定位函數(shù)中的一種，在解決布局問(wèn)題中取得了較好的效果。論文的研究，獲得了吸引子法的一些基本性質(zhì)：諸如定位函數(shù)的三維圖像為一個(gè)平面、定位函數(shù)值相等的點(diǎn)共線、吸引子法使矩形塊堆積在一個(gè)角上等。此外，通過(guò)研究布入點(diǎn)的幾何意義，提出了一種手動(dòng)快速布局方法。最后通過(guò)研究吸引子放置位置對(duì)布局的影響，還得出了隱性吸引子這一重要的性質(zhì)。

布局問(wèn)題；啟發(fā)式算法；定位函數(shù)；吸引子法

矩形布局問(wèn)題[1]廣泛地存在于工業(yè)生產(chǎn)實(shí)踐之中。長(zhǎng)期以來(lái)，人們?yōu)榻鉀Q該問(wèn)題提出各種理論和方法[2]，并取得了一定的效果。這些方法中最主要的有兩種[3]：優(yōu)化算法和啟發(fā)式算法。其中優(yōu)化算法只能找到局部最優(yōu)解，且所得解的質(zhì)量在很大程度上依賴于初始解的選擇[4]。于是人們將研究的重心轉(zhuǎn)向了啟發(fā)式算法[5],并提出了一系列求解算法，其中，構(gòu)造啟發(fā)算法是最常見的一種算法。構(gòu)造啟發(fā)算法主要由定序規(guī)則和定位規(guī)則確定[6]。常見的定序規(guī)則有按面積遞減、按最長(zhǎng)邊遞減和按可行域面積等順序確定布局塊的布局次序。常見的定位規(guī)則有占角順?lè)挪呗浴⒔鸾遣呗浴⑾屡_(tái)階法和定位函數(shù)法等。吸引子法[7]是定位函數(shù)法中的一種。吸引子法吸收了下臺(tái)階法、BL算法等許多定位規(guī)則的優(yōu)點(diǎn)，并且其可量化的特點(diǎn)使其更容易在計(jì)算機(jī)上得到實(shí)現(xiàn)。

在對(duì)吸引子法的文獻(xiàn)檢索中，發(fā)現(xiàn)文獻(xiàn)都只注重對(duì)于吸引子法的應(yīng)用，如朱艷華[8]利用吸引子法結(jié)合遺傳算法求解二維布局問(wèn)題；王保春[9]利用吸引子法與混合 SAGA算法結(jié)合求解矩形布局問(wèn)題；而對(duì)吸引子法自身性質(zhì)的研究卻未見論述。

本文對(duì)吸引子法的基本內(nèi)容進(jìn)行推理研究，得出吸引子法的一些基本性質(zhì)，這將有利于吸引子法在矩形布局問(wèn)題求解中得到更好地運(yùn)用。

1 吸引子法趨角性研究

吸引子法的數(shù)學(xué)描述如下：

在空間中設(shè)置m個(gè)吸引子，吸引子t的位置為 ),(00ttyx 。矩形塊i在 ),(iiyx 處的定位函數(shù)

其中， ),(iityxg 是關(guān)于吸引子 t的定位函數(shù)，n為待布矩形塊的個(gè)數(shù)，tα、tβ和tω為權(quán)重因子，且令矩形塊的布入點(diǎn) (xj,yj)是其可行域內(nèi)定位函數(shù)值最小的點(diǎn)，即 G (xj,yj)= minG(xi,yi)。因矩形塊要求完全布入空間內(nèi)，故定位函數(shù)的最大定義域?yàn)椴季挚臻g。

吸引子法在求解二維矩形布局問(wèn)題時(shí)，通常會(huì)采用4個(gè)吸引子，分別布在矩形布局空間的四角。 ω1、 ω2、 ω3和 ω4分別為布局空間的左下、右下、右上和左上四角吸引子的權(quán)重因子。

現(xiàn)研究在定位函數(shù)中參數(shù) αt， βt和 ωt確定時(shí)，定位函數(shù)值在布局空間內(nèi)的變化情況。設(shè)對(duì)于某個(gè)任意點(diǎn) (xi,yi)的定位函數(shù)值已知，則該點(diǎn)在X方向偏移 Δ x后所得點(diǎn) (xi+ Δx,yi)（依然在布局空間內(nèi)）的定位函數(shù)為

因點(diǎn) (xi,yi)與點(diǎn) (xi+ Δx,yi)都在矩形布局空間內(nèi)，故存在 x01= x04≤ xi≤ x02= x03和x01= x04≤ xi+ Δx≤ x02= x03，其中，

同理可得

由式（2）、（3）可得

若取 xi=0,yi=0,Δx =x,Δy=y，可得 G(x ,y)=

需要說(shuō)明的是，上式中 (xi,yi)所取的原點(diǎn)(0 ,0)一般選在布局空間左下角點(diǎn)，但根據(jù)情況也可選在其他點(diǎn)，該點(diǎn)的選取并不影響最終的布局結(jié)果。

由上式可知，當(dāng)吸引子的位置與參數(shù)值確定時(shí), ω1α1? ω2α2?ω3α3+ω4α4， ω1β1+ω2β2?ω3β3? ω4β4和 G (0,0)都為常數(shù)。若設(shè)

G (0 ,0)=C，則上式可簡(jiǎn)化為

由此方程可得出如下性質(zhì)：

性質(zhì)1 由各個(gè)點(diǎn)坐標(biāo) (xi,yi)與其定位函數(shù)值 G (xi,yi)所確定的三維點(diǎn)群 (xi,yi,G(xi,yi))在同一個(gè)平面內(nèi)，即在以布局空間所在平面為XOY平面、定位函數(shù)值為Z軸的三維空間內(nèi)，定位函數(shù)圖像為一個(gè)平面。

性質(zhì)2 在矩形布局空間內(nèi)，定位函數(shù)值相同的點(diǎn)在同一條直線上。

當(dāng)在這些點(diǎn)群中選出定位函數(shù)值 ),( yxG 最小的點(diǎn)作為矩形塊布入點(diǎn)時(shí)，此時(shí)問(wèn)題已經(jīng)轉(zhuǎn)化成為一個(gè)二維線性規(guī)劃問(wèn)題。該線性規(guī)劃問(wèn)題可描述為

其中，iI為第i塊布入矩形塊的可行域。

因此矩形塊布入點(diǎn)的確定有許多與線性規(guī)劃問(wèn)題相同的性質(zhì)和特點(diǎn)。

首先，由線性規(guī)劃的理論可知，線性規(guī)劃問(wèn)題可能存在無(wú)限解[10]。同樣，可行域內(nèi)也可能存在多個(gè)甚至是無(wú)限個(gè)備選點(diǎn)。在理論上，這些點(diǎn)都可以成為矩形塊的布入點(diǎn)。但實(shí)踐的經(jīng)驗(yàn)告訴我們，矩形塊布在中間位置往往得不到較好的布局結(jié)果，所以在定位原則中往往有“貼邊靠角”的特點(diǎn)。因此我們?cè)诖艘?guī)定：當(dāng)有多個(gè)點(diǎn)可做布入點(diǎn)時(shí)，選擇這些點(diǎn)中最靠左或最靠下的點(diǎn)作為布入點(diǎn)，靠下的原則要高于靠左的原則。需要說(shuō)明的是，這樣一個(gè)特別規(guī)定只是為了方便尋找布入點(diǎn)，而對(duì)吸引子法本身的性質(zhì)沒(méi)有任何影響，尤其是后面將提到的趨角性。事實(shí)上，矩形塊選擇備選點(diǎn)中的任何一點(diǎn)作為布入點(diǎn)都不影響其趨角性，趨角性是由后文所提到的隱形吸引子這個(gè)性質(zhì)所決定的。

其次，線性規(guī)劃最優(yōu)解的一個(gè)重要特征是最優(yōu)解總是發(fā)生在解空間的角點(diǎn)，且當(dāng)求目標(biāo)函數(shù)最小值時(shí)，最優(yōu)點(diǎn)出現(xiàn)于在等值線負(fù)梯度方向區(qū)域[10]。同樣，矩形塊的布入點(diǎn)也存在于其可行域的頂點(diǎn)之中。且當(dāng)A≥0，B≥0時(shí)，矩形塊的布入點(diǎn)存在于可行域的左下角區(qū)域；當(dāng) A≥0，B＜0時(shí)，矩形塊的布入點(diǎn)存在于可行域的左上角區(qū)域；當(dāng)A＜0，B＜0時(shí)，矩形塊的布入點(diǎn)存在于可行域的右上角區(qū)域；當(dāng)A＜0，B≥0時(shí)，矩形塊的布入點(diǎn)存在于可行域的右下角區(qū)域，如圖1所示。

最后，當(dāng)可行域不變時(shí)，目標(biāo)函數(shù)中價(jià)值系數(shù)的改變有可能導(dǎo)致解的變化[10]。同樣，矩形塊的可行域是固定的，而A和B卻可能隨吸引子參數(shù)變化而變化，故矩形塊的布入點(diǎn)在很大程度上取決于由吸引子決定的目標(biāo)函數(shù)中的價(jià)值系數(shù)A和B。

以上的性質(zhì)雖然是單個(gè)矩形塊布入點(diǎn)的特征，但是眾多矩形塊布入的積累效果使得吸引子法還存在以下性質(zhì)：

性質(zhì)3 吸引子法的布局結(jié)果會(huì)出現(xiàn)矩形塊堆積在一個(gè)角上的情況，而且根據(jù)A和B取值的不同，矩形塊堆積的角不同，堆積的狀態(tài)也不同。

可見在矩形塊布入順序確定的情況下，布局結(jié)果完全取決于A和B的取值，因此A和B是吸引子法的重要布局參數(shù)。

因?yàn)榫匦尾季謫?wèn)題的布局空間和矩形塊都是對(duì)稱的，所以任何一種布局情況，通過(guò)改變A和B的取值都可以出現(xiàn)于另外3個(gè)角上。故以下的分析中以左下角為主要研究對(duì)象，其他3個(gè)角的研究可參照該角。

圖1 價(jià)值系數(shù)確定矩形布入點(diǎn)所在區(qū)域

2 布入點(diǎn)的幾何意義

由研究可知，矩形塊堆積在布局空間的左下角區(qū)域時(shí)，A≥0，B≥0。

如圖2所示，設(shè)當(dāng)?shù)趇塊矩形塊布入時(shí)，可行域?yàn)?Ii（陰影部分），其中點(diǎn) P (xj,yj)為矩形塊的布入點(diǎn)。此時(shí)由定位函數(shù)所確定的等值線為Ax + By+C'=0，該直線與水平線的夾角

若將可行域沿逆時(shí)針旋轉(zhuǎn)角度θ，如圖3所示，等值線經(jīng)過(guò)旋轉(zhuǎn)后成為水平線，則此時(shí)經(jīng)過(guò)旋轉(zhuǎn)后的矩形塊布入點(diǎn) P'( x'j,y'j)為新可行域I'i內(nèi)的最低點(diǎn)，即 y'j= miny'i。

當(dāng)B=0時(shí)，等值線為 z = Ax+C'，等值線與水平線的夾角為 π /2。此時(shí)矩形塊布入點(diǎn)在可行域最左的邊界線段中，根據(jù)靠下的原則，矩形塊的布入點(diǎn)為該線段的下端點(diǎn)。若可行域沿逆時(shí)針旋轉(zhuǎn) π /2，可行域最左的邊界線段成為了新可行域中最下的邊界線段，新的矩形塊布入點(diǎn)依然為新可行域內(nèi)最低點(diǎn)。

同樣的性質(zhì)在其他3個(gè)角上也是成立的。但要注意的是，其他3個(gè)角需要旋轉(zhuǎn)的角度不一樣。右下角與左下角關(guān)于過(guò)布局空間中心點(diǎn)的垂直線對(duì)稱，故右下角要沿順時(shí)針旋轉(zhuǎn)角度θ，即沿逆時(shí)針旋轉(zhuǎn)角度2 π?θ ；而右上角與左下角關(guān)于布局空間中心點(diǎn)對(duì)稱，故右上角要沿逆時(shí)針旋轉(zhuǎn)角度π后再旋轉(zhuǎn)角度θ，即沿逆時(shí)針旋轉(zhuǎn)角度π+ θ；左上角與右下角關(guān)于布局空間中心點(diǎn)對(duì)稱，故左上角要演逆時(shí)針旋轉(zhuǎn)角度π后再沿順時(shí)針旋轉(zhuǎn)角度θ，即沿逆時(shí)針旋轉(zhuǎn)角度 π? θ。

圖2 左下角可行域與矩形塊布入點(diǎn)

圖3 旋轉(zhuǎn)角度θ后的可行域

綜上所述，矩形塊的布入點(diǎn)存在以下性質(zhì)。

性質(zhì)4 當(dāng)A≥0，B≥0時(shí)，可行域沿逆時(shí)針旋轉(zhuǎn)角度θ，當(dāng)A≥0，B＜0時(shí)，可行域沿逆時(shí)針旋轉(zhuǎn)角度 θπ? ，當(dāng)A＜0，B＜0時(shí)，可行域沿逆時(shí)針旋轉(zhuǎn)角度 θπ+ ，當(dāng)A＜0，B≥0時(shí)，可行域沿逆時(shí)針旋轉(zhuǎn)角度2 θπ? ，其中矩形塊的布入點(diǎn)都存在于新可行域的最低點(diǎn)中。

由上述性質(zhì)可得吸引子法的布局幾何過(guò)程描述：首先根據(jù)確定的吸引子參數(shù)得出布局參數(shù)A和B，根據(jù)A和B的取值確定矩形塊的堆積的角，再根據(jù)A和B確定旋轉(zhuǎn)角度φ，布局空間沿逆時(shí)針旋轉(zhuǎn)角度φ后，將矩形塊（也沿逆時(shí)針旋轉(zhuǎn)角度φ）布入布局空間的可行域中的最低位置，直至無(wú)法布入矩形塊為止。

以上布局描述可以成為一種手動(dòng)快速布局方法。圖4為手動(dòng)快速布局方法的流程圖。

圖4 手動(dòng)快速布局流程圖

本文利用文獻(xiàn)[8]中的布局空間為2.5*2的算例進(jìn)行檢驗(yàn)。文獻(xiàn)[8]中吸引子參數(shù)為

根據(jù)A和B的取值可確定矩形塊堆積于布局空間的左上角。由于

所以， θ=0.797038856，因矩形塊堆積于布局空間的左上角，故需要旋轉(zhuǎn)的角度為? =π? θ= 2.344553797，即 134.3°。將布局空間沿逆時(shí)針旋轉(zhuǎn)134.3°，并將算例中的布入矩形按面積大小進(jìn)行排序后，矩形塊的布入順序?yàn)?4→29→2→23→20→0→28→10→9→24→8→30→1→25→33→35→31→4→32→36→27→19→18→16→39→7→13→22→11→17→12→3→38→21→5→26→6→15→37→34。將矩形塊依次布入布局空間中該矩形塊可行域的最低位置。布局結(jié)果如圖5所示，而圖6為文獻(xiàn)中算例的布局結(jié)果。兩圖比較可知兩種布局結(jié)果是一樣的。的 部 分 ， 當(dāng) xi＜ x0t時(shí) ，

圖5 手動(dòng)快速布局結(jié)果

圖6 文獻(xiàn)[8]中的布局結(jié)果

另外，傳統(tǒng)的定位規(guī)則BL算法也有趨角性，只不過(guò)其趨向的角僅為左下角。本文也利用 BL算法解決文獻(xiàn)[8]算例，再利用矩形的對(duì)稱性，將布局結(jié)果轉(zhuǎn)化為趨向左上角的情況，其結(jié)果如圖7所示。對(duì)比圖6與圖7的布局結(jié)果，我們可以發(fā)現(xiàn)，圖6的布局結(jié)果要優(yōu)于圖7，且圖6布局結(jié)果中間隙少而密，而圖7布局結(jié)果中間隙多而散。這是由于吸引子法的布局靈活，更容易保證矩形塊之間緊貼，不制造較大的間隙。

3 隱性吸引子研究

以上研究中，4個(gè)吸引子放置在布局空間的四個(gè)角上，這種放置是比較規(guī)則的。而理論上吸引子是可以任意放置的。以下研究吸引子的放置對(duì)布局問(wèn)題的影響。

圖7 BL法布局結(jié)果

首先明確，整體空間是無(wú)界的，吸引子可以放置在其中任意位置。而布局空間只是整體空間的一部分，矩形塊只能放置于布局空間內(nèi)。不妨假設(shè)在整體空間內(nèi)任意放置若干吸引子，且放置位置與布局空間無(wú)關(guān)。矩形塊對(duì)位于 (x0t,y0t)的 吸 引 子 t的 定 位 函 數(shù) 為gt(xi,yi) = αt|xi? x0t|+ βt| yi? y0t|。其中關(guān)于；當(dāng)ix ≥0tx 時(shí)，同理可得，當(dāng)tiyy0＜時(shí)，當(dāng)iy≥0ty 時(shí)，于是關(guān)于吸引子t的定位函數(shù)可寫成

其中，當(dāng) xi＜ x0t時(shí)， λt=?1，否則 λt=1；當(dāng)yi＜ y0t時(shí)，ηt=?1，否則ηt=1。于是矩形塊的定位函數(shù)可寫成

所 以 當(dāng) 點(diǎn) (xi,yi)經(jīng) 過(guò) 微 小 移 動(dòng) 至(xi+Δx,yi+Δy )，且 λt與ηt不發(fā)生改變時(shí)，

由式（6）可知，對(duì)于吸引子任意放置的情況，布局參數(shù)為

需要注意的是，此時(shí)A和B已不再是常數(shù)。當(dāng)點(diǎn)(xj, yj)移動(dòng)經(jīng)過(guò)吸引子所在的垂直線（或水平線）時(shí)，λt（或ηt）便發(fā)生改變，隨之A（或B）也發(fā)生改變。因此可視參數(shù)A（或B）為關(guān)于矩形塊中心點(diǎn)坐標(biāo)xi（或yi）的階梯函數(shù)A(x)（或B(y)），且該階梯函數(shù)的間斷點(diǎn)的坐標(biāo)為各個(gè)吸引子坐標(biāo)x0t（或y0t）。

如圖8所示，若在布局空間內(nèi)任意放置3個(gè)吸引子，并畫出所有經(jīng)過(guò)吸引子點(diǎn)的水平線和垂直線，此時(shí)布局空間X方向被分為4個(gè)部分，分別命名為a、b、c和d，Y方向也被分為4個(gè)部分，分別命名為Ⅰ、Ⅱ、Ⅲ和Ⅳ，這樣布局空間就被分割為 4×4個(gè)小區(qū)域。在各個(gè)小區(qū)域中，參數(shù)A和B是根據(jù)其所在X和Y方向的部分所確定的。比如若矩形塊在X方向的a部分，

圖8 3個(gè)吸引子劃分的布局空間

若矩形塊在X方向的b部分，

若矩形塊在X方向的c部分，

若矩形塊在X方向的d部分，

若矩形塊在Y方向的Ⅰ部分，

若矩形塊在Y方向的Ⅱ部分，

若矩形塊在Y方向的Ⅲ部分，

若矩形塊在Y方向的Ⅳ部分，

圖中點(diǎn)C所在區(qū)域?yàn)閄方向的b部分和Y方向的Ⅲ部分，因此其定位函數(shù)中

因吸引子參數(shù) αt,βt,ωt∈[0,1]，當(dāng)矩形塊中心點(diǎn)坐標(biāo)xi從 ? ∞到 + ∞時(shí)，布局參數(shù)A隨著一直增加且由負(fù)到正。故存在且只存在一個(gè)間斷點(diǎn)x0，當(dāng) xi＜ x0時(shí)，A＜0；當(dāng) xi＞ x0時(shí)，A≥0。易知

同理可知，存在且只存在一個(gè)間斷點(diǎn)y0，使得

由上述結(jié)論可知在整體空間內(nèi)存在一點(diǎn) ),(00yx ，使得

而且空間內(nèi)其他點(diǎn)距該點(diǎn)越遠(yuǎn)，定位函數(shù)值越大。可見該點(diǎn)已成為整體空間內(nèi)的一個(gè)隱性吸引子。而這個(gè)現(xiàn)象就得出了吸引子法的一個(gè)重要性質(zhì)。

性質(zhì)5 無(wú)論使用多少個(gè)吸引子，吸引子如何布置，參數(shù)大小如何，其達(dá)到的效果都相當(dāng)于在整體空間內(nèi)設(shè)置了一個(gè)隱性吸引子的效果。

若該隱性吸引子在布局空間內(nèi)（包括布局空間邊界），矩形塊將環(huán)繞該隱性吸引子布局，如圖9所示；若該隱性吸引子在布局空間外，矩形塊會(huì)因受該隱性吸引子吸引而堆積在一個(gè)角上，如圖10所示。

圖9 隱性吸引子在空間中心的布局

當(dāng)4個(gè)吸引子布置在布局空間四角時(shí)，由于吸引子這種特殊的布置，無(wú)論吸引子參數(shù)如何，隱性吸引子都只存在于4個(gè)角點(diǎn)之中。矩形塊因受到存在于角上吸引子的吸引，而導(dǎo)致布局結(jié)果會(huì)出現(xiàn)眾矩形塊堆積在一個(gè)角上的效果。這也很好地解釋了用吸引子法解決二維矩形布局時(shí)為什么會(huì)出現(xiàn)趨角性，也進(jìn)一步說(shuō)明，前面針對(duì)眾備選點(diǎn)所設(shè)定的特別規(guī)定并不影響吸引子法的趨角性。

4 結(jié) 論

以上推導(dǎo)出的性質(zhì)，都是由定位函數(shù)中的gt(xi,yi)=αt|xi?xot|+βt|yi?y0t|所決定的。這些性質(zhì)很好地保證了矩形塊貼邊占角的布局要求。這在一定程度上提高了布局空間的利用率。但矩形塊只堆積在一個(gè)角上的這個(gè)性質(zhì)，卻很容易將布局產(chǎn)生的間隙分散到其他3個(gè)角上，這樣有可能會(huì)降低布局空間的利用率。而這個(gè)問(wèn)題的解決還有賴于定位函數(shù)中函數(shù) gt(xi,yi)的改進(jìn)。因此改進(jìn)原有的函數(shù) gt(xi,yi)或提出新的函數(shù)應(yīng)成為下一步的研究目標(biāo)。

[1] Imahori S, Yagiura M, Ibaraki T. Local search algorithms for the rectangle packing problem with general spatial costs [J]. Mathematical Programming, 2003, 97(3): 543-569.

[2] Lodi A, Martello S, Monaci M. Two-dimensional packing problems: a survey [J]. European Journal of Operational Research, 2002, 141: 241-252.

[3] Hopper E, Turton B C H. A review of the application of meta-heuristic algorithms to 2D strip packing problems [J]. Artificial Intelligence Review, 2001, 16: 257-300.

[4] 查建中, 唐曉君, 陸一平. 布局及布置設(shè)計(jì)問(wèn)題求解自動(dòng)化的理論與方法綜述[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2002, 14(8): 1-8.

[5] Burke E K, Hyde M, Kendall G, et al. A genetic programming hyper-heuristic approach for evolving 2-D strip packing heuristics [J]. IEEE Transaction on Evolutionary Computation, 2010, 14(6): 1-17.

[6] 王愛(ài)虎, 鄂明成, 查建中. 基于空間分解的二維布局問(wèn)題的啟發(fā)式算法[J]. 天津大學(xué)學(xué)報(bào), 1996, 29(6): 840-846.

[7] 王金敏, 楊維嘉. 動(dòng)態(tài)吸引子在布局求解中的應(yīng)用[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2005, 17(8): 1725-1729.

[8] 朱艷華. 布局問(wèn)題遺傳算法的研究[D]. 天津: 天津工程師范學(xué)院機(jī)械工程學(xué)院, 2009.

[9] 王金敏, 王保春, 朱艷華. 求解矩形布局問(wèn)題的一種混合 SAGA算法[J]. 天津工程師范學(xué)院學(xué)報(bào), 2010, 20(2): 5-9.

[10] 束金龍, 聞人凱. 線性規(guī)劃理論與模型應(yīng)用[M].北京: 科學(xué)出版社, 2003: 14-62.

Research on attractive factor approach in rectangular packing problem

Wang Jinmin, Qi Yang
( Tianjin Key Laboratory of High Speed Cutting & Precision Machining, TUTE, Tianjin 300222, China )

The attractive factor approach, which is one of the location function approach, has gotproduces better results in the packing problems. This paper researches the attractive factor approach and gets some basic properties of it as follows: Such as the 3D image of the location function is a plane, the points with equal values of the location function are on the same straight line, the rectangular items are piled in a corner by the attractive factor approach, and so on. In addition, a manual rapid-packing method is given by studying the geometry significance of the pack-in point. In the end, the property which is about the of being an invisible attractive factor is obtained by studying the effect of the position of the attractive factors.

packing problem; heuristic algorithms; location function; attractive factor approach

TP 391.72

A

2095-302X (2012)06-0038-07

2011-05-30；定稿日期：2011-07-19

國(guó)家自然科學(xué)基金資助項(xiàng)目（60975046）

王金敏（1963-），男，河南舞陽(yáng)人，教授，博士，主要研究方向?yàn)橹悄懿季帧⒂?jì)算機(jī)圖形學(xué)。E-mail：wang_jin_min@163.com