王金敏， 朱麗蘋

（1. 天津市高速切削與精密加工重點實驗室，天津 300222；2. 天津職業(yè)技術師范大學機械工程學院，天津 300222）

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

王金敏1,2， 朱麗蘋2

（1. 天津市高速切削與精密加工重點實驗室，天津 300222；2. 天津職業(yè)技術師范大學機械工程學院，天津 300222）

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

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

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

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

1 三元序列模型

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

1.1 三元序列

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

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

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

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

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

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

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

1.2布局算法

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

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

一旦布局物體i被放置在布局空間中，它就加入到集合P中。文獻[12]給出一個布局算例，其布局物體長、寬、高尺寸如表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) 得到的布局結果（見表2），布局結果如圖1所示。

表1 布局物體的長寬高

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

圖1 文獻[12]給出的布局結果

1.3 分析

對文獻[12]進行分析可知：

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

(2) 文獻[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)得出的布局結果如圖2所示，圖1所示的三元序列應為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 實際的布局結果

2 三元序列結合可行域改進算法

文獻[12]的算法雖然能達到一定的布局效果，但是由算例結果來看，布局效果并不是非常理想。因此，本文在此算法的基礎上做出了改進，每一個待布局物體由三元序列確定了一個布局位置（一個點）之后，再把可行域內的其他點與三元序列確定的點進行比較，比較這些點與上一個已布入的布局物體的距離，選擇距離最小的點作為待布局物體的布局位置?？尚杏虻那蠓ㄒ娢墨I[14]。原算法和改進的布局算法基本流程圖分別如圖3和圖4所示。

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

圖4 改進布局算法的基本流程

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

2.1 編碼策略

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

2.2 適應度函數及初始種群的產生

本文中的初始候選解由計算機隨機產生，每個候選解就是一個個體，這些個體構成了初始種群。適應度函數f是評價各解優(yōu)劣的標準。本文適應度函數選為布局空間的體積利用率，即：

2.3 選擇算子

選擇操作就是從種群中選擇兩個候選解，以便進一步操作。本文使用蜜蜂進化選擇算子，其具體實現如下：

2.4 交叉算子

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

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

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

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

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

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

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

圖5 序列B單點交叉

圖6 序列A兩點交叉

2.5 變異算子

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

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

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

3 算例及分析

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

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

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

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

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

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

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

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

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

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

圖12 兩種算法對C類算例的計算結果

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

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

4 結 束 語

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

[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] 唐曉君, 査建中, 陸一平. 布局問題的復雜性和建模方法[J]. 北方交通大學學報, 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]. 華中理工大學學報, 1998, 26(10): 38-41.

[6] 晏 敏, 張昌期, 劉育騏. 平面布局的一個拓撲模型:方圖[J]. 小型微型計算機系統(tǒng), 1989, 10(2): 23-32.

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

[8] 王英林, 吳慧中, 田宜風. 求解布局模型的并行矩陣算法研究[J]. 計算機輔助設計與圖形學學報, 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è)技術師范大學學報, 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

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

王金敏(1963-)，男，河南舞陽人，教授，博士。主要研究方向為智能布局、計算機輔助設計及圖形學。E-mail：wang_jin_min@163.com