基于序列模型的三維矩形布局算法

王金敏， 朱麗蘋

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

基于序列模型的三維矩形布局算法

王金敏1,2， 朱麗蘋2

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

針對三維矩形布局問題進(jìn)行了研究。在三元序列的基礎(chǔ)上，結(jié)合布局物體的幾何可行域，提出了三元序列結(jié)合幾何可行域的布局算法。并且利用遺傳算法對布局算法進(jìn)行優(yōu)化，得到了三元序列結(jié)合可行域布局遺傳算法。分析和實(shí)例證明，三元序列結(jié)合幾何可行域的改進(jìn)算法有效地提高了布局效率。

布局問題；三元序列；可行域；遺傳算法

布局問題(packing problem)[1-2]是指給定一個(gè)布局空間和若干待布物體，將待布物體合理地?cái)[放在空間中滿足必要的約束，并達(dá)到某種最優(yōu)指標(biāo)。布局問題的求解非常困難，唐曉君等[3]詳細(xì)闡述了布局問題的復(fù)雜性。即使是最簡單的一維布局問題也被證明是 NP完全問題(non-deterministic polynomial, NP)。因此，布局問題吸引了大批的學(xué)者對其進(jìn)行研究。Hashimshony和 Roth[4]介紹了ALG模型，該模型在給定的約束條件下，利用圖論來產(chǎn)生可行的布局方案。袁苗龍等[5]利用圖法則分析了三維布局模型生成方法對車身內(nèi)進(jìn)行了布置，但文章并沒有過多地對布局結(jié)果進(jìn)行分析。晏敏等[6]給出了用于表達(dá)矩形物體平面布局空間關(guān)系的方圖模型，并提出了方圖矩陣及其運(yùn)算規(guī)則。該模型側(cè)重平面布局問題的求解，對空間布局問題的求解有一定的困難。吳慧中等[7-8]利用空間布局的約束圖方法對房間布局進(jìn)行了初步試驗(yàn)，證明約束圖在處理布局問題時(shí)比其他模型更簡便、高效，文章只是停留在試驗(yàn)階段，對該方法解決問題的能力有待進(jìn)一步闡述。

此外，許多學(xué)者利用啟發(fā)式優(yōu)化算法求解布局問題，取得了不錯(cuò)的結(jié)果。Lai和Chan[9-10]利用模擬退火算法和遺傳算法對布局問題進(jìn)行求解。解空間是待布物體的排列，一個(gè)解表示一個(gè)布局。但是文章只給出了有限的幾個(gè)解。Beasley[11]在遺傳算法的基礎(chǔ)上提出了一個(gè)能有效解決4000塊待布物體的啟發(fā)式算法。但是對已知最優(yōu)解的小算例該算法卻不能取得最優(yōu)解。Egeblad和Pisinger[12]提出了一個(gè)整數(shù)規(guī)劃方程式，并在此基礎(chǔ)上仿照Murata等[13]提出解決二維布局問題序列的方法，給出了一個(gè)由三元序列表示三維裝箱問題的布局算法，并用模擬退火算法優(yōu)化三元序列。但是文章沒有對由三元序列表示的布局結(jié)果進(jìn)行進(jìn)一步改善處理。本文在三元序列的基礎(chǔ)上，結(jié)合可行域，對原布局算法進(jìn)行了改善，之后再用遺傳算法對此布局算法進(jìn)行優(yōu)化。

1 三元序列模型

文獻(xiàn)[12]介紹了利用三元序列模型求解布局問題，此模型屬于圖論模型的范疇。大部分的布局可以用這個(gè)方法表示，其中具有代表性的是“機(jī)器人碼垛”，根據(jù)“機(jī)器人碼垛”的定義，總會(huì)有一個(gè)布局物體被放置在布局空間的最左、最下和最后的角點(diǎn)?！皺C(jī)器人碼垛”是從空間的左下后角點(diǎn)開始，依次布入布局物體，這樣，每布入一個(gè)布局物體都會(huì)在前一個(gè)已步入的布局物體的右面、上面、前面。

1.1 三元序列

lij(left)、rij(right)、uij(under)、oij(over)、bij(behind)和fij(front)分別表示布局物體i在j(i＜ j)的左面、右面、下面、上面、后面和前面。為了確保布局物體i和j不發(fā)生干涉，應(yīng)滿足如下不等式：

當(dāng) si= sj=1, lij, rij, uij, oij, bij, fij要滿足如下的不等式：

對于三維布局問題，可用一個(gè)三元序列A，B和C來表示，每一個(gè)序列都是n個(gè)布局物體的排列。對于每一個(gè)序列X，Xij表示：在序列X里，布局物體i在j之前。

為了方便起見，令 - Xij? Xji。

也就是說 Aij表示布局物體i在布局物體j的左面、上面或前面。

也就是說 Bij表示布局物體i在布局物體j的左面、下面或后面。

也就是說 Cij表示布局物體i在布局物體j的右面、下面或前面。

1.2布局算法

三元序列到布局，要建立3個(gè)約束圖。第一幅圖中，i到j(luò)的邊表示布局物體i在j的左邊，即第二幅圖中，i到j(luò)的邊表示布局物體i在j的下邊，即第三幅圖中，i到j(luò)的邊表示布局物體i在布局物體j的后邊，即

在每一幅約束圖當(dāng)中，Bij都是i在j之前的必要條件。因此，可以按照序列 B的順序布局。序列B中的第一塊待布物體放置在(0,0,0)，依次按照B序列中的排序布局。為了便于記錄，在布局過程中建立一個(gè)集合P，令P包含所有已布入的布局物體。子集 Px? P， Px中的布局物體滿足約束子集中的布局物體滿足；子集中的布局物體滿足若對布局物體 i進(jìn)行布局，為了確定i的布局位置，要把i依次和P中布局物體比較。布局物體i的坐標(biāo)(xi, yi,zi)可由如下方程求解：

一旦布局物體i被放置在布局空間中，它就加入到集合P中。文獻(xiàn)[12]給出一個(gè)布局算例，其布局物體長、寬、高尺寸如表1所示。

由三元序列A = (9, 4, 8, 5, 1, 6, 2, 7, 3)，B = (7, 8, 6, 9, 1, 3, 5, 2, 4)，C = (2, 3, 6, 7, 1, 4, 5, 9, 8) 得到的布局結(jié)果（見表2），布局結(jié)果如圖1所示。

表1 布局物體的長寬高

表2 布局物體的長寬高及布置位置

圖1 文獻(xiàn)[12]給出的布局結(jié)果

1.3 分析

對文獻(xiàn)[12]進(jìn)行分析可知：

(1) 文獻(xiàn)[12]指出lij+ rij+ uij+ oij+ bij+ fij= 1，但根據(jù)實(shí)際的布局情況，如果布局物體i既在布局物體j的前面，同時(shí)又在j的左面和上面，則有l(wèi)ij+rij+uij+oij+bij+fij= 3。本文將其改為：

(2) 文獻(xiàn)[12]指出 + + x xl y yh z

i ji i ji i≤ ˇ≤ ˇ≤zh ?B

j i ij +，本文將其改為：

(3) 由三元序列A = (9, 4, 8, 5, 1, 6, 2, 7, 3)， B = (7, 8, 6, 9, 1, 3, 5, 2, 4)，C = (2, 3, 6, 7, 1, 4, 5, 9, 8)得出的布局結(jié)果如圖2所示，圖1所示的三元序列應(yīng)為A = (9, 4, 8, 5, 1, 6, 2, 7, 3)，B = (7, 6, 8, 9, 1, 3, 2, 5, 4)，C = (2, 3, 6, 7, 1, 4, 5, 9, 8)。

圖2 實(shí)際的布局結(jié)果

2 三元序列結(jié)合可行域改進(jìn)算法

文獻(xiàn)[12]的算法雖然能達(dá)到一定的布局效果，但是由算例結(jié)果來看，布局效果并不是非常理想。因此，本文在此算法的基礎(chǔ)上做出了改進(jìn)，每一個(gè)待布局物體由三元序列確定了一個(gè)布局位置（一個(gè)點(diǎn)）之后，再把可行域內(nèi)的其他點(diǎn)與三元序列確定的點(diǎn)進(jìn)行比較，比較這些點(diǎn)與上一個(gè)已布入的布局物體的距離，選擇距離最小的點(diǎn)作為待布局物體的布局位置。可行域的求法見文獻(xiàn)[14]。原算法和改進(jìn)的布局算法基本流程圖分別如圖3和圖4所示。

圖3 原布局算法的基本流程

圖4 改進(jìn)布局算法的基本流程

本文利用遺傳算法對三元序列進(jìn)行優(yōu)化。

2.1 編碼策略

本文直接對優(yōu)化變量采用實(shí)數(shù)編碼。每個(gè)染色體由A、B、C 三個(gè)序列構(gòu)成，基因0～n-1（包括0和n-1）表示序列A，基因n～2n-1（包括n和2n-1）表示序列B，基因2n～3n-1（包括2n和3n-1）表示序列C。因此每個(gè)染色體都有3n個(gè)基因，基因的個(gè)數(shù)隨著待布局物體的個(gè)數(shù)變化而變化。

2.2 適應(yīng)度函數(shù)及初始種群的產(chǎn)生

本文中的初始候選解由計(jì)算機(jī)隨機(jī)產(chǎn)生，每個(gè)候選解就是一個(gè)個(gè)體，這些個(gè)體構(gòu)成了初始種群。適應(yīng)度函數(shù)f是評價(jià)各解優(yōu)劣的標(biāo)準(zhǔn)。本文適應(yīng)度函數(shù)選為布局空間的體積利用率，即：

2.3 選擇算子

選擇操作就是從種群中選擇兩個(gè)候選解，以便進(jìn)一步操作。本文使用蜜蜂進(jìn)化選擇算子，其具體實(shí)現(xiàn)如下：

2.4 交叉算子

(1) 將父代染色體的序列 B的基因（基因n+1～2n）全部交換。

將父染色體A和C序列的基因直接復(fù)制到子代解1的A和C序列部分，子代解1的B序列由母染色體的B序列填充；

將母染色體A和C序列的基因直接復(fù)制到子代解2的A和C序列部分，子代解2的B序列由父染色體的B序列填充。

(2) 將父代染色體的序列B的基因部分交換，進(jìn)行單點(diǎn)交叉。

隨機(jī)產(chǎn)生一個(gè)n+1～2n的交叉點(diǎn)，父染色體B序列在交叉點(diǎn)左側(cè)的代碼直接復(fù)制到子代解 1的左側(cè)，子代解 1交叉點(diǎn)右側(cè)的代碼依次從母染色體選擇未在子代解 1中使用的代碼。父染色體 A序列和C序列直接復(fù)制到子代解1的A序列和C序列。交叉過程如圖5所示。

(3) 將父代染色體的序列A的基因部分交換，進(jìn)行兩點(diǎn)交叉。

隨機(jī)產(chǎn)生兩個(gè)1～n的交叉點(diǎn)p1和p2，父染色體A序列在交叉點(diǎn)p1左側(cè)的代碼和p2右側(cè)的代碼直接復(fù)制到子代解 1的左側(cè)和右側(cè)，子代解 1的兩交叉點(diǎn)中間的代碼依次從母染色體中選擇未在子代解1中使用的代碼。父染色體B序列和C序列直接復(fù)制到子代解1的B序列和C序列。交叉過程如圖6所示。

圖5 序列B單點(diǎn)交叉

圖6 序列A兩點(diǎn)交叉

2.5 變異算子

(1) 隨機(jī)交換染色體A序列和B序列中兩個(gè)代碼的位置。

隨機(jī)產(chǎn)生一個(gè)[1, n]的數(shù)k1，一個(gè)[n+1, 2n]的數(shù)k2，交換k1和k2所對應(yīng)的代碼。將A序列中與交換后的代碼相同的基因位處，用 A序列未使用過的代碼替換；如果k1和k2所對的代碼相同，則重新產(chǎn)生隨機(jī)數(shù)直到k1和k2所對應(yīng)的代碼不相同為止。變異過程如圖7所示。

(2) 隨機(jī)交換染色體B序列和C序列中兩個(gè)代碼的位置。方法同(1)。

3 算例及分析

算例1.采用文獻(xiàn)[12]中的三維算例ep-3d。此類算例共包括60個(gè)三維裝箱問題。布局物體的個(gè)數(shù)分別為20，40，60。表3將文獻(xiàn)[12]算法和本文算法求出的布局結(jié)果進(jìn)行了比較。

圖7 序列A和序列B之間的變異

表3 文獻(xiàn)[12]算法與本文算法布局結(jié)果比較(%)

由表3可以看出，本文算法較文獻(xiàn)[12]算法有了很大地提高，利用率平均提高了10.24%。最差的結(jié)果也保持與文獻(xiàn)[12]算法的結(jié)果相等，而對于提升幅度最高的算例60lc90利用率則提高了27.2%。對于算例60lc90兩種算法的布局效果如圖8所示。圖 8中文獻(xiàn)[12]算法中布局物體之間的空隙比較大。這是由三元序列本身原因造成的，所以本文對由三元序列布局的結(jié)果進(jìn)行處理，即與布局物體幾何可行域結(jié)合，尋找待布局物體最優(yōu)的布局位置。算例20lc90、40ur50、60uc50的布局結(jié)果與Jens的布局結(jié)果比較如圖9～11所示?？梢钥闯霰疚乃惴ㄓ行У靥岣吡瞬季挚臻g的利用率。

算例2.此算例由二維C類算例改進(jìn)而來，在原有的算例基礎(chǔ)上，對布局空間和布局物體都增加了同樣的高。C1～C7算例中布局物體數(shù)量逐漸增多。C11～C13算例當(dāng)中總共有16塊布局物體，C71～C73當(dāng)中總共有196塊布局物體。表4將本文算法求出的布局結(jié)果和文獻(xiàn)[12]算法求解的結(jié)果進(jìn)行了比較。兩種算法對 C類算例的計(jì)算結(jié)果的對比如圖12。

圖8 文獻(xiàn)[12]算法(左)與本文算法(右)的布局結(jié)果

圖9 算例20lc90本文算法(左)與文獻(xiàn)[12]算法(右)的布局結(jié)果

圖10 算例40ur50本文算法(左)與文獻(xiàn)[12]算法(右)的布局結(jié)果

圖11 算例60uc50本文算法(左)與文獻(xiàn)[12]算法(右)的布局結(jié)果

表4 文獻(xiàn)[12]算法與本文算法對C類算例布局結(jié)果比較(%)

圖12 兩種算法對C類算例的計(jì)算結(jié)果

由表4的數(shù)據(jù)可以看出，對于C11算例布局空間利用率提高了 20.25%，C71算例提高了64.88%，所有算例平均提高了40.47%。

由圖12可以看出，隨著布局物體數(shù)量的增多，本文算法的利用率有所下降，文獻(xiàn)[12]算法的利用率則呈現(xiàn)顯著下降的趨勢。這是因?yàn)殡S著布局物體的增多，布局物體之間的空隙也就越來越多，從而造成布局空間體積的浪費(fèi)。這說明，文獻(xiàn)[12]算法只適用于布局物體數(shù)量較少的算例，而本文算法在布局物體數(shù)量較多的算例中同樣能表現(xiàn)出較好的性能。

4 結(jié) 束 語

本文對文獻(xiàn)[12]提出的三元序列進(jìn)行了分析，提出了一種以三元序列為基礎(chǔ)，結(jié)合幾何可行域的改進(jìn)布局算法，并用遺傳算法來優(yōu)化布局物體的布局順序。最后分別用文獻(xiàn)[12]算法和本文布局算法對兩組算例進(jìn)行了計(jì)算、比較，實(shí)例證明，三元序列結(jié)合幾何可行域的改進(jìn)算法有效地提高了布局效率。

[1] Sweeny P E, Paternoster E R. Cutting and packing problems: a categorized, application-orientated research [J]. Journal of Operation Research Society, 1992, 43(7): 691-706.

[2] Dowsland K A, Dowsland W B. Packing problems [J]. European Journal of Operational Research, 1992, 56(1): 2-14.

[3] 唐曉君, 査建中, 陸一平. 布局問題的復(fù)雜性和建模方法[J]. 北方交通大學(xué)學(xué)報(bào), 2003, 27(1): 12-15.

[4] Hashimshony R, Roth J. ALG: a model for generating alternative layout graphs under architectural constraints [J]. Computer Aided Design, 1986, 18(8): 431-436.

[5] 袁苗龍, 胡于進(jìn), 付莉紅. 基于圖法則分析的三維布局模型生成方法[J]. 華中理工大學(xué)學(xué)報(bào), 1998, 26(10): 38-41.

[6] 晏 敏, 張昌期, 劉育騏. 平面布局的一個(gè)拓?fù)淠Ｐ?方圖[J]. 小型微型計(jì)算機(jī)系統(tǒng), 1989, 10(2): 23-32.

[7] 吳慧中, 王英林. 一種立體空間布局模型及布局算法[J]. 計(jì)算機(jī)學(xué)報(bào), 1994, 17(11): 835-840.

[8] 王英林, 吳慧中, 田宜風(fēng). 求解布局模型的并行矩陣算法研究[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 1998, 10(4): 341-348.

[9] Lai K K, Chan J W M. Developing a simulated annealing algorithm for the cutting stock problem [J]. Computers and Industrial Engineering, 1997, 32(1): 115-127.

[10] Lai K K, Chan J W M. A evolutionary algorithm for the rectangular cutting stock problem [J]. International Journal on Industrial Engineering, 1997, 4(1): 130-139.

[11] Beasley J E. A population heuristic for constrained two-dimensional non-guillotine cutting [J]. European Journal of Operational Research, 2004, 156(3): 601-627.

[12] Egeblad J, Pisinger D. Heuristic approaches for the two and three dimensional knapsack packing problem [J]. Computers & Operations Research, 2009, 36(4): 1026-1049.

[13] Murata H, Fujiyoshi K, Nakatake S, Kajitani Y. VLSI module packing based on rectangle-packing by the sequence pair [J]. IEEE Transaction on Computer Aided Design of Integrated Circuits and Systems, 1996, 15(12): 1518-1524.

[14] 朱麗蘋, 王金敏. 基于空間分割的求解布局幾何可行域的算法[J]. 天津職業(yè)技術(shù)師范大學(xué)學(xué)報(bào), 2012, 22(2): 30-33.

An Improved Algorithm for 3D Rectangular Packing Sequence Model

Wang Jinmin1,2, Zhu Liping2
(1. Tianjin Key Laboratory of High Speed Cutting & Precision Machining, Tianjin 300222, China; 2. School of Mechanical Engineering, Tianjin University of Technology and Education, Tianjin 300222, China)

This paper studies the three dimensional rectangular packing problem. On the basis of sequence triple, combined with geometry feasible region of packing items, the sequence triple and feasible region packing algorithm is proposed. Then the packing algorithm is optimized by genetic algorithm, the sequence triple and feasible region packing genetic algorithm is formed. Analysis and examples prove that the improved sequence triple and feasible region packing algorithm can effectively increase packing efficiency.

packing problem; sequence triple; feasible region; genetic algorithm

TP 391

A

2095-302X(2014)06-0821-07

2013-04-19；定稿日期：2013-05-29

國家自然科學(xué)基金資助項(xiàng)目(60975046)；天津職業(yè)技術(shù)師范大學(xué)科研發(fā)展基金資助項(xiàng)目(KJ14-64)

王金敏(1963-)，男，河南舞陽人，教授，博士。主要研究方向?yàn)橹悄懿季?、?jì)算機(jī)輔助設(shè)計(jì)及圖形學(xué)。E-mail：wang_jin_min@163.com