汪朋朋 施群 謝云斌 謝家駿 潘炳偉

摘要：高效自動排料算法中布料利用率的提升對于企業(yè)具有重要的經(jīng)濟價值。但排料問題屬于NP完全問題，難以在有限時間內(nèi)找到問題的最優(yōu)解。研究提出基于最小重力勢能原理的排料算法，并將遺傳算法應(yīng)用到排料優(yōu)化問題中，最終進行排料算法的對比驗證?；谧钚≈亓菽茉砑斑z傳算法的排料算法優(yōu)化減小了每次排料過程中的計算量，可在有限的時間內(nèi)得到近似最優(yōu)解。結(jié)果表明，所提出的自動排料算法在提高利用率方面具有較高的實用價值。

關(guān)鍵詞：排料算法；最小重力勢能原理；遺傳算法；不規(guī)則排料

中圖分類號：TS195.644文獻標志碼：A文章編號：1009-265X（2018）03-0053-09Garment Nesting Algorithm Based on Principle of Minimum

Gravity Potential Energy and Genetic Algorithm

WANG Pengpeng， SHI Qun， XIE Yunbin， XIE Jiajun， PAN Bingwei

（School of Mechatronic Engineering and Automation， Shanghai University， Shanghai 200072， China）Abstract：The improvement of material utilization in efficient automatic nesting algorithm has important economic benefits for Enterprises. However， nesting problem is a NPcomplete problem and it is hard to find out the optimal solution to the problem within the finite time. The nesting algorithm based on the principle of minimum gravity potential energy was proposed in this paper and genetic algorithm was also applied in nesting optimization problem. Finally， the comparison validation of the nesting algorithm was conducted. To a certain extent， this nesting algorithm based on the principle of minimum gravity potential energy and genetic algorithm reduce and optimize the computation load in each process， and the quasioptimal solution can be gained within the limited time. The experimental results show that this automatic nesting algorithm has a high practical value in improving the utilization rate.

Key words：nesting algorithm； principle of minimum gravity potential energy； genetic algorithm； irregular nesting

服裝排料屬于不規(guī)則圖形排料問題，部分研究者采用最小矩形包絡(luò)法將不規(guī)則圖形排料轉(zhuǎn)化為矩形排料[12]，這種方法排料效率較高，但存在材料利用率低的缺陷。排料優(yōu)化問題主要包括樣片最優(yōu)排放位置確定和樣片最優(yōu)排樣順序確定兩個問題。

樣片位置確定有多種研究策略，最常用的是Baker等[3]左下角（BottomLeft condition，BL）策略，BL策略的主要思想是在保證樣片不重疊的前提下，重復將樣片向左、向下移動，直到不能再移動為止，由于BL策略容易引起排料結(jié)果左側(cè)偏高，遺留較大塊的空白區(qū)域等問題，一些學者提出了相應(yīng)的改進算法，如Liu等[4]向左平移優(yōu)于向下的BLLF策略、Hopper等[5]左下角填充的BLF策略。采用BL策略進行排料的算法一般需要計算臨界多邊形（NFP），當樣片數(shù)量（N）和旋轉(zhuǎn)次數(shù)（RN）增大時，臨界多邊形的計算非常耗時；另一種常用的是最低重心排料策略，Dowsland等[6]指出如果將零件看作砂礫，母材看作玻璃瓶，通過不斷搖晃“玻璃瓶”可以使“砂礫”排列更加密實，Lee等[7]提出在母材上布置多個等距離散排樣點，將樣片平移到各個排樣點上并進行旋轉(zhuǎn)來確定其排放位置，劉虓[8]提出的Hape算法中給出了排料問題的物理意義：零件總是試圖通過平移和旋轉(zhuǎn)運動盡量降低零件的重心高度，從而得到更加緊密的排列。

樣片排放順序?qū)τ谂帕侠寐示哂兄匾绊懀潭樞虻呐帕系玫降慕Y(jié)果往往不能令人滿意。但由于N個樣片存在N！種順序，目前的計算能力下無法在可接受的時間內(nèi)找到最優(yōu)排料順序，因此一些學者將優(yōu)化搜索算法引入排料算法中，如Gomes等[9]使用模擬退火算法搜索排料解空間，在當前排樣圖的基礎(chǔ)上，挑選兩個零件互換位置，從而產(chǎn)生當前解的鄰域解。湯安平等[10]采用遺傳算法和排料約束條件相結(jié)合的方式來進行排料，對樣片順序和旋轉(zhuǎn)角度進行編碼，這種算法可能得到較好的排料結(jié)果，但進一步增大了算法的計算量。

本文采用Lee等[7]的方法在母材上布置等距排樣點，根據(jù)最小勢能原理建立數(shù)學模型，移動、旋轉(zhuǎn)樣片至各排樣點使其重力勢能最小，以此來確定各樣片初始排放位置。由于等距排樣點之間存在間隔，又借鑒BL策略提出了樣片快速靠接算法來確定樣片的最終排放位置。進一步對排料圖中樣片的排放順序進行編碼，利用遺傳算法求解不同順序下的排料結(jié)果，給出一種基于最小重力勢能原理與遺傳算法的服裝排料算法。

1基于最小勢能原理的排料算法設(shè)計

1.1排料算法基本定義

1.1.1樣片

樣片包含參考點（RP）、旋轉(zhuǎn)角度（α）、序號、面積、形心、最小包圍盒和樣片多邊形坐標點等信息。如圖1所示，樣片參考點（RP）是樣片平移、旋轉(zhuǎn)的基點，可以任意選取，這里選擇樣片最小包圍盒左下角頂點為參考點；旋轉(zhuǎn)角度（α）由旋轉(zhuǎn)次數(shù)（RN）決定，α=2πj/RN（j=0，1，2…，RN-1），樣片旋轉(zhuǎn)次數(shù)（RN）是影響排料效率的一個關(guān)鍵因素。

1.1.2母材及排樣點

母材指未進行排樣前的原材料，在母材上沿水平、豎直兩個方向均勻布置的離散點稱為排樣點，排樣點是確定樣片位置的基礎(chǔ)。如圖2所示，排樣點之間的間距為PPD，該參數(shù)值也是影響排樣效率的一個關(guān)鍵參數(shù)。需要特別說明的是：實際排料時習慣從左至右依次排料，因此假設(shè)重力方向為從右向左方向。

1.1.3樣片的旋轉(zhuǎn)、平移操作

圖2所示為樣片旋轉(zhuǎn)、平移操作。圖2（a）中，待排樣片的初始位置在①處，樣片參考點與母材中的一個排樣點重合，繞參考點旋轉(zhuǎn)180°后到達位置②；如圖2（b）所示，樣片在位置②按箭頭方向平移后到達位置③。

1.1.4樣片的重疊檢測算法

排樣時需要保證樣片之間不能發(fā)生重疊，以下給出兩個樣片多邊形A、B快速重疊檢測算法的主要流程：

a）計算多邊形A與多邊形B的最小包圍盒；

b）快速判斷A、B最小包圍盒是否重疊，若不重疊則A與B不重疊，流程結(jié)束；若重疊執(zhí)行下一步；

c）判斷A各邊與B各邊是否存在交點，若存在交點則A與B發(fā)生重疊；若不存在交點則轉(zhuǎn)下一步；

d）為防止A、B存在包含關(guān)系，判斷A的各頂點是否在B中，若A的某一頂點位于B中，則兩個多邊形發(fā)生重疊，流程結(jié)束；若多邊形A的所有頂點均不在多邊形B中，執(zhí)行下一步；

e）同理，判斷多邊形B的各頂點是否在多邊形A中。圖2樣片旋轉(zhuǎn)、平移操作

1.1.5樣片快速靠接算法

如圖3所示，根據(jù)排樣點確定的樣片位置之間仍然可能存在間隙。為提高排料利用率，需要使用靠接算法消除樣片之間水平和豎直方向的間隙，靠接算法流程如圖4所示，假設(shè)樣片A最終位置已確定，B樣片向左平移至恰好滿足不重疊條件。

1.2最小重力勢能原理與樣片形心計算

最小重力勢能原理的引入主要用來確定樣片排放位置。假設(shè)排料過程中已確定所有樣片的排料順序，則排料問題可歸結(jié)為：如何確定各樣片的排放位置，使排料利用率最高。利用最低重心排樣策略，根據(jù)樣片在母材中的位置關(guān)系，可以求出樣片的重力勢能，從而很方便的建立起樣片排放位置問題的數(shù)學模型。再通過樣片的平移和旋轉(zhuǎn)操作，遍歷所有排樣點和樣片旋轉(zhuǎn)角度，可以求出各樣片在母材中不同位置的重力勢能，當各樣片處于最小勢能狀態(tài)下時，整個排版圖的總勢能最小，即可確定當前順序下的樣片排放位置和排料利用率。根據(jù)最小重力勢能原理建立的評價樣片排放位置優(yōu)劣的模型，是整個算法的基礎(chǔ)。

在排料的過程中，樣片零件的重力勢能為：

EG=Gyc（1）

式中：EG為零件的重力勢能；G為零件的重力；yc為零件的形心高度。

排料問題的最小重力勢能原理：零件在排料過程中總是盡可能地通過平移或旋轉(zhuǎn)使其形心高度降低。如圖5（a）所示，三角形在排料時位于矩形上方，其重力勢能為Gy0；經(jīng)平移后到達如圖5（b）中所示位置，其重力勢能為Gy1；再經(jīng)旋轉(zhuǎn)、平移后到達如圖5（c）中所示位置，其重力勢能達到最小值Gy2。服裝樣版中包含直線段、曲線段，為保證算法通用性，排版前將所有樣片均處理為多邊形。設(shè)多邊形含有n個頂點，其中任一頂點的坐標為（xk，yk）（k=1，2，3，…，n），多邊形面積和形心均可由格林公式（2）推導得到。

DQx-Pydxdy=∮LPdx+Qdy（2）

令式（2）中P=-y，Q=x，即得多邊形的面積：

S=Ddxdy=12∮L-ydx+xdy

=12∑nk=1（xkyk+1-xk+1yk）（3）圖5排料過程中的最小重力勢能原理

式中：當k=n時，k+1=1。已知多邊形的形心公式

yc=DydxdyDdxdy（4）

若令P=-12y2，Q=0，則可得多邊形形心坐標yc：

yc=-12∮Ly2dx12∮L-ydx+xdy

=16∑nk=1（y2k+ykyk+1+y2k+1）（xk-xk+1）12∑nk=1（xkyk+1-xk+1yk） （5）

1.3確定樣片位置的流程

采用一種固定順序（如樣片面積大小順序）每次取一個樣片，按照如圖6所示流程即可確定各樣片的排放位置。流程圖中：

a）排料間隔PPD越小，則排樣點個數(shù)PPN越多。若排樣點個數(shù)PPN越多，同時旋轉(zhuǎn)次數(shù)RN越多，則排料時間越長，由算法流程圖可知，單個樣片的排料時間由式PPN2×RN決定。由于排樣時存在大量無效排樣點，因此在排樣時避免訪問無效點可進一步提高排樣效率；

b）由于假設(shè)重力方向是從右向左方向，所以需要計算樣片x方向的形心xc，計算參考式（5）。圖6樣片位置確定流程

2排料順序優(yōu)化

如圖7所示，排料順序?qū)ε帕侠寐示哂兄匾绊懀樞蚬潭ǖ呐帕喜灰欢艿玫阶顑?yōu)的排料結(jié)果。但由于N個樣片存在N！種順序，無法在可接受的時間內(nèi)窮舉樣片順序進行排料。遺傳算法是基于自然選擇和自然遺傳機制的搜索算法，它是一種有效的解決最優(yōu)化問題的方法，因此排料時可引入遺傳算法，通過全局優(yōu)化概率搜索來產(chǎn)生最佳的排料順序。實現(xiàn)排料優(yōu)化問題需要經(jīng)過編碼，初始化，適應(yīng)度計算，選擇，交叉，變異等操作。

2.1編碼與初始化

遺傳算法中常用的編碼方式有實數(shù)編碼、二進制編碼、浮點數(shù)編碼和格雷碼編碼等。排料前每個樣片都有唯一的編號，根據(jù)樣片的編號采用實數(shù)編碼可以直觀得到樣片的排料順序。假設(shè)N個樣片的編號分別為p1、p2、p3…pN，從這N個樣片中依次任意選擇一個樣片pn（n=1，2，…，N）在母材中進行排料，則所選樣片的順序就構(gòu)成了個體的編碼。實際操作時，由隨機函數(shù)產(chǎn)生1N的一個全排列即個體。種群由指定數(shù)目的個體組成，在使用遺傳算法前需要對種群進行初始化，假設(shè)種群個體數(shù)量為M，初始化即產(chǎn)生M個1N的全排列Xm（m=1，2，3…M）。

2.2個體適應(yīng)度函數(shù)

排料利用率為所有樣片的面積和與使用母材的面積之比：

fXm=EXm=∑Nn=1SnLW（6）

式中：fXm為個體Xm的適應(yīng)度函數(shù)（m=1，2，3…M），EXm為個體Xm的排料利用率，L為樣片占用母材的總長度，W為母材的寬度，Sn為樣片n的面積（n=1，2，3…N）。

排料利用率是評價排料結(jié)果的關(guān)鍵因素，因此可以將式（6）作為個體適應(yīng)度的評價函數(shù)。

2.3選擇操作

選擇操作是遺傳算法中的優(yōu)勝劣汰機制。選擇操作可以在迭代的過程中保留種群中的優(yōu)良個體。采用輪盤賭進行選擇，定義個體Xm被選中的概率為pm=fXm∑Mm=1fXm，進行選擇時，隨機生成一個[0，1）區(qū)間的隨機數(shù)p，如果∑mj=1pj2.4交叉操作

交叉操作是由父代個體產(chǎn)生子代個體的過程。采用順序交叉，假設(shè)Xi、Xj是進行交叉操作的一對父個體，其中Xi=[4 5 1 7 2 8 9 6 3]，Xj=[7 9 3 4 5 6 1 2 8]，具體交叉操作方式如下：

a）在父個體Xi中隨機選擇一個片段，如[1 7 2 8]；

b）將該片段復制到子個體Yi的對應(yīng)位置[0 0 1 7 2 8 0 0 0]；

c）刪除父個體Xj中子個體Yi已含有的元素，產(chǎn)生一個過度個體X′j=[9 3 4 5 6]；

d）將個體X′j元素依次插入子個體Yi的空缺位置上，即得到子個體Yi=[9 3 1 7 2 8 4 5 6]。

2.5變異操作

變異是種群進化的關(guān)鍵手段，變異操作可以防止種群早熟收斂，提高遺傳算法的局部搜索能力。變異操作如下：假設(shè)子個體Yi=[9 3 1 7 2 8 4 5 6]，隨機選擇兩個位置的元素交換即可得到變異后的子個體，如交換1、5的位置，得到變異后的個體Yi′=[9 3 5 7 2 8 4 1 6]。

3排料算法流程及實例

3.1排料算法流程

引入遺傳算法后整體的排料流程如圖8所示，其中確定樣片n的位置即按照圖6所示流程進行。

3.2算法實例

3.2.1算法驗證平臺和參數(shù)

本文所述的排料算法在Visual Studio 2015集成開發(fā)環(huán)境下采用MFC框架、VC++語言編程驗證，算法驗證所用的計算機基本配置為，CPU：Intel Core i32350M 2.30GHz；RAM：8.00GB；操作系統(tǒng)：Win10 64位。如圖9所示，樣片在母材中位置確定后，樣片內(nèi)的排樣點被刪除，排料利用率可直接顯示在狀態(tài)欄；如圖10所示，排樣時需要設(shè)置的主要參數(shù)有排樣間隔PPD，樣片旋轉(zhuǎn)次數(shù)RN，種群迭代次數(shù)Iteration和種群個體數(shù)Population，遺傳算法中的交叉操作概率取0.8，變異操作概率取0.1。圖8排料算法流程

3.2.2算法測試和分析

為了驗證算法的性能和有效性，有必要對其進行測試和分析。本文從歐洲排樣研究組織ESICUP（https：//paginas.fe.up.pt/～esicup/datasets）提供的基準問題中挑出11個分別進行排樣，排料結(jié)果如圖11所示。圖11本文算法排料結(jié)果

對于服裝生產(chǎn)企業(yè)來說，在加工高級服裝面料和大批量生產(chǎn)時，材料利用率的微小提升都意味著巨大的經(jīng)濟效益，即排料利用率是排料算法的關(guān)鍵評價因素，本文主要就排料利用率進行了測試和對比。

表1是本文算法與GEFHNA[11]算法、Nestlib商業(yè)軟件的排料利用率對比。GEFHNA[11]算法是一種基于重心臨界多邊形和邊適應(yīng)度的不規(guī)則件啟發(fā)式排樣算法，該算法在選擇樣片排放順序時采用了FFD策略（通過衡量樣片與待排區(qū)域的貼合程度選擇排料順序），文獻[11]給出了這11個基準問題的排料利用率；Nestlib是一款商業(yè)排料軟件（其排料算法未公開），但其排料結(jié)果具有較高的參考價值。如圖12為GEFHNA算法和Nestlib軟件對基準問題shirts的排料結(jié)果。

軟件對shirts的排料結(jié)果

通過測試和對比可得出如下結(jié)論：

a）基于最小勢能原理與遺傳算法的服裝排料算法對任意多邊形（凹、凸多邊形）樣片均適用。

b）與GEFHNA算法相比，本文提出的排料算法獲得了8/11個相對最優(yōu)的排料利用率。GEFHNA算法采用FFD策略進行啟發(fā)式搜索排料，該算法實際上只進行單次排樣，因此其排料的效率會比較高，但其排料利用率容易受樣片與待排區(qū)域的貼合度影響；而本文采用遺傳算法對排料順序進行優(yōu)化搜索，可在多次搜索迭代后獲得一個較優(yōu)的排料順序，從而提高排料利用率。

c）與Nestlib軟件的排料結(jié)果相比，本文提出的排料算法獲得了10/11個相對最優(yōu)的排料利用率。說明本文提出的排料算法在提高排料利用率方面具有較高的實用價值。

4結(jié)語

本文闡述了排料問題的基本定義，在確定樣片排放位置時，介紹了最小重力勢能原理及其作用，并給出了基于最小重力勢能原理確定樣片位置的流程?？紤]到固定順序排料得到的結(jié)果不一定是最優(yōu)解，因此在確定最優(yōu)排料順序時引入遺傳算法，從而可以得到近似最優(yōu)排料結(jié)果，再給出整個排料算法的流程。最后，給出了算法的驗證平臺和詳細參數(shù)，并與其他排料結(jié)果進行了對比。結(jié)果表明，本文所提出的排料算法提高了服裝生產(chǎn)中的材料利用率，具有較高的經(jīng)濟價值和實用價值。

參考文獻：

[1] 靳旭玲.二維不規(guī)則排樣問題的研究[D].青島：山東科技大學，2003.

[2] 胡加宰，史偉民，楊亮亮.二維不規(guī)則樣片自動排料算法的優(yōu)化研究[J].現(xiàn)代紡織技術(shù)，2014，22（5）：26-30.

[3] BAKER B S， COFFMAN E G J， RIVEST R L. Orthogonal packings in two dimensions[J]. Siam Journal on Computing， 1980， 9（4）：846-855.

[4] LIU D， TENG H. An improved BLalgorithm for genetic algorithm of the orthogonal packing of rectangles 1[J]. European Journal of Operational Research， 1999，112（2）：413-420.

[5] HOPPER E， TURTON B C H. An empirical investigation of metaheuristic and heuristic algorithms for a 2D packing problem[J]. European Journal of Operational Research， 2001，128（1）：34-57.

[6] DOWSLAND K A， DOWSLAND W B， BENNELL J A. Jostling for position： local improvement for irregular cutting patterns[J]. Journal of the Operational Research Society， 1998，49（6）：647-658.

[7] LEE W C， MA H， CHENG B W. A heuristic for nesting problems of irregular shapes[J]. ComputerAided Design， 2008，40（5）：625-633.

[8] 劉虓.基于HAPE的二維不規(guī)則零件排樣算法及其性能研究[D].廣州：華南理工大學，2011.

[9] GOMES A M， OLIVEIRA J F. Solving irregular strip packing problems by hybridising simulated annealing and linear programming[J]. European Journal of Operational Research， 2006，171（3）：811-829.

[10] 湯安平，楊恢先，譚正華.一種基于遺傳算法的優(yōu)化排料方法[J].計算機應(yīng)用與軟件，2009，26（1）：171-221.

[11] 湯德佑，周子琳.基于臨界多邊形的不規(guī)則件啟發(fā)式排樣算法[J].計算機應(yīng)用，2016，36（9）：2540-2544.