服裝矩形樣片組合優(yōu)化模型及其求解算法

王 姝，金福江

(華僑大學(xué)信息科學(xué)與工程學(xué)院，福建 廈門 361021)

面料利用率直接影響服裝企業(yè)的生產(chǎn)成本和生產(chǎn)效率，因此服裝排料技術(shù)是服裝生產(chǎn)的關(guān)鍵。從數(shù)學(xué)計(jì)算復(fù)雜性理論來看，優(yōu)化排料問題屬于具有最高計(jì)算復(fù)雜性的NPC類問題［1］，這類問題的求解時(shí)間與問題的規(guī)模呈指數(shù)級(jí)關(guān)系增長［2－3］，至今還沒有找到解決該問題的有效方法。目前，服裝企業(yè)中應(yīng)用較多的排料方法還是傳統(tǒng)的人工排料。即在反復(fù)多次擺放后，一般能達(dá)到較高的排料率，但通常排料周期較長，效率低，修改難度大。隨著計(jì)算機(jī)的廣泛應(yīng)用，服裝CAD排料系統(tǒng)被運(yùn)用于服裝排料中，雖然能使排料完全實(shí)現(xiàn)自動(dòng)化，但缺乏相應(yīng)的數(shù)學(xué)模型和優(yōu)化算法，達(dá)不到最優(yōu)排料的要求。

針對(duì)服裝排料問題，國內(nèi)外學(xué)者提出了很多算法。ALBANO在樹搜索的基礎(chǔ)上加入啟發(fā)式的搜索技術(shù)，把樣片的二維最優(yōu)布局問題轉(zhuǎn)化為在一個(gè)狀態(tài)空間尋找一條最優(yōu)路徑的問題，得到了一個(gè)近似優(yōu)化的排料方案［4］，啟發(fā)式算法提高了搜索效率，放寬了對(duì)計(jì)算結(jié)果與最優(yōu)解偏離程度的限制，求出的不一定是最優(yōu)解。ADAMOWICZ的算法是在矩形布局階段采用了矩形包絡(luò)法［5］，將不規(guī)則圖形簡化為矩形，簡化算法的復(fù)雜度。HAIMS的規(guī)劃方法適用于矩形排料，待排部件數(shù)量不受限制，在每一步都將矩形部件放在料板的一個(gè)角上［6］。GILMORE和GOMORY用線性規(guī)劃方法和背包算法研究了矩形圖形的二維排料問題［7］，但是不適用于不規(guī)則多邊形的直接排料。國內(nèi)的學(xué)者也做了大量的研究［8－12］，但在以往的研究中，把服裝排料問題的重點(diǎn)放在算法上，對(duì)實(shí)際排料的模型研究成果較少。筆者運(yùn)用矩形包絡(luò)法，先將服裝裁片通過組合優(yōu)化，得到相應(yīng)的矩形件，再研究服裝最優(yōu)排料的數(shù)學(xué)模型，彌補(bǔ)了服裝排料理論研究的不足。

1 矩形樣片服裝排料問題

筆者對(duì)服裝排料建模做如下假設(shè):

(1)在定寬定長的面料上，每批服裝的所有樣片均參與自動(dòng)排料。

(2)矩形樣片長寬一定，且數(shù)量不限。

(3)暫且不考慮實(shí)際排料中面料的色差、紋理等條件。

矩形樣片服裝排料問題的描述如下:

(1)一系列數(shù)量不限的矩形樣片為Pn，這里n為不同尺寸矩形的種類數(shù)，矩形樣片的長度為ai(i=1，2，…，n)，矩形樣片的寬度為 bi，矩形樣片沿寬度方向的矢量為di，矩形樣片的面積為si。

(2)設(shè)邏輯變量為γi，面料沿長度方向的矢量為d。γi=did，γi=0表示矩形Pn為橫排，即Pn的長度方向沿面料長度方向排列，γi=1表示Pn為豎排，即Pn的長度方向沿面料寬度方向排列。

(3)設(shè)面料利用率為η，在幅寬為W，長度為L的面料P上排放矩形樣片Pn，η=∑si/(WL)，因面料面積為WL不變，當(dāng)所有所排矩形面積∑si最大時(shí)，服裝面料利用率η最大。

對(duì)于排放任意矩形樣片Pn，為不超出面料范圍，則每一列排放的矩形樣片的長度或?qū)挾鹊目偤筒荒艹^面料的幅寬，每一行排放的矩形樣片的長度或?qū)挾鹊目偤筒荒艹^面料的長度。

2 矩形樣片混合排料的建模

當(dāng)所排的矩形樣片滿足γi=0或1，即所排矩形樣片中包含有既可橫排(γi=0)也可豎排(γi=1)的矩形樣片時(shí)，混合排料建模分析如下:

設(shè)Sj為第j列所有矩形件的面積和，Wj為第j列所有矩形件的寬度或長度和，Lj為第j列所有矩形件中長度或?qū)挾鹊淖畲笾担琸ij為邏輯變量，kij=1為第i種矩形件排列于第j列中，kij=0為第i種矩形件未排列于第j列中。

對(duì)于第j列，每類矩形件的個(gè)數(shù)分別為xij(0≤xij≤X且xij∈Z)，則矩形樣片面積和為:

矩形樣片寬度和為:

矩形樣片長度和為:

其中，kij為邏輯變量，kij=1為第i種矩形件排列于第j列，kij=0為第i種矩形件未排列于第j列，即則對(duì)于整塊面料，其總面積和為:

1≤m≤M，M=int(L/f)，且 m∈Z

f=min{［(1 －γ1)a1+γ1b1］，…，［(1 －γn)an+ γnbn］}

總寬度為:

總長度為:

其中

綜上所述，得混合排料方式(γi=0或1)下，服裝排料的組合優(yōu)化模型為:

其中，式(8)為面積約束;式(9)為面料寬度約束;式(10)為面料長度約束;矩形樣片排列的總列數(shù)m滿足1≤m≤M，M=int(L/f)，f=min{［(1 － γ1)a1+ γ1b1］，［(1 － γ2)a2+ γ2b2］，…，［(1 －γn)an+γnbn］}且 m∈Z，xij為第 j列第 i種矩形樣片的個(gè)數(shù)，0≤xij≤X，X=int(W/c)，c=min{［γ1a1+(1 － γ1)b1］，［γ2a2+(1 － γ2)b2］，…，［γnan+(1 － γn)bn］}且 xij∈Z，kij為邏輯變量，kij=1為第i種矩形件排列于第j列，kij=0為第i種矩形件未排列于第j列。

3 混合排料的組合優(yōu)化算法

n種矩形樣片的排料方式共有2n種。通過對(duì)2n種情況進(jìn)行分類建模討論，得出最佳排料方案。(γ1，γ2，…，γn)為矩形樣片的排列方式，γ =0為矩形樣片橫排，γ=1為矩形樣片豎排。計(jì)算步驟如下:

(1)將(γ1，γ2，…，γn)的某種情況代入 M=int(L/f)，f=min{［(1 －γ1)a1+γ1b1］，…，［(1 －γn)an+γnbn］}和 X=int(W/c)，c=min{［γ1a1+(1 － γ1)b1］，［γ2a2+(1 － γ2)b2］，…，［γnan+(1 －γn)bn］}中，求解出 M、f、X、c。

(2)將求解出的M、f、X、c代入服裝排料的組合優(yōu)化模型中，得到具體的模型。

(3)通過式(9)求解出滿足條件的xij和mi(xij為第j列第i種矩形樣片的個(gè)數(shù)，mi為矩形樣片排料的總個(gè)數(shù))。

(4)通過式(8)算出面料的使用面積，比較可得最大的面料利用率，以及面料利用率最大時(shí)的xij和mi。返回步驟(1)，直到討論完所有情況。

(5)通過比較各種情況的面料利用率，確定最佳排料方案，最后得到排料圖。

4 混合排料模型的驗(yàn)證

以4種類型的矩形樣片為例，來說明混合排列方式下的排料模型。設(shè)定面料的幅寬、長度以及矩形樣片的相關(guān)尺寸參數(shù)如表1所示。

表1 面料和4種矩形樣片的尺寸表

由于每種矩形樣片都有兩種排列方式，因此n種矩形樣片的排料方式共有2n種。當(dāng)n=4時(shí)矩形樣片的排料方式共有24=16種，即(γ1，γ2，γ3，γ4)為(1，1，1，1)、(1，1，1，0)、(1，1，0，1)、(1，1，0，0)、(1，0，1，1)、(1，0，1，0)、(1，0，0，1)、(1，0，0，0)、(0，1，1，1)、(0，1，1，0)、(0，1，0，1)、(0，1，0，0)、(0，0，1，1)、(0，0，1，0)、(0，0，0，1)、(0，0，0，0)。下面分別對(duì)這16種情況進(jìn)行分類建模討論。

對(duì)于第 1 種方式(γ1，γ2，γ3，γ4)=(1，1，1，1)，即4種矩形都豎排，則有:

c=min{［γ1a1+(1 － γ1)b1］，［γ2a2+(1 －γ2)b2］，［γ3a3+(1 － γ3)b3］，［γ4a4+(1 － γ4)·b4］}=min(a1，a2，a3，a4)=6

f=min{［(1 － γ1)a1+ γ1b1］，［(1 － γ2)a2+γ2b2］，［(1 － γ3)a3+ γ3b3］，［(1 －γ4)a4+γ4b4］}=min(b1，b2，b3，b4)=2

M=int(50/f)=15，X=int(20/c)=3，代入組合優(yōu)化模型得:

該模型分解為以下幾種情況:

(1)(x1j≠0)＆＆(x2j=0)＆＆(x3j=0)＆＆(x4j=0)，即全部是第1類矩形樣片時(shí)優(yōu)化模型為:

解得:x1j=2，m=7，面料利用率 η11=7×66．5 ×2/1 000=93．1%;

(2)(x1j=0)＆＆(x2j≠0)＆＆(x3j=0)＆＆(x4j=0)，即全部是第2類矩形樣片時(shí)，同理可得:x2j=3，m=10，面料利用率 η12=3×30×10/1 000=90．0%;

(3)(x1j=0)＆＆(x2j=0)＆＆(x3j≠0)＆＆(x4j=0)，即全部是第3類矩形樣片時(shí)，同理可得:x3j=1，m=25，面料利用率 η13=1×22×25/1 000=55．0%;

(4)(x1j=0)＆＆(x2j=0)＆＆(x3j=0)＆＆(x4j≠0)，即全部是第4類矩形樣片時(shí)，同理可得:x4j=1，m=16，面料利用率 η14=1×36×16/1 000=57．6%;

(5)(x1j≠0)‖(x2j≠0)‖(x3j≠0)‖(x4j≠0)，即4種矩形樣片不全部為0時(shí)，由于0≤xij≤3∩xij∈Z，而3種矩形樣片單獨(dú)排放時(shí)，在使面料利用率最高的情況下 x1j=2，x2j=3，x3j=1，x4j=1，故優(yōu)化模型轉(zhuǎn)化為:

當(dāng)上式取等號(hào)時(shí)，求解出(m1，m2，m3，m4)可能的取值。當(dāng) m1=5，m2=2，m3=1，m4=1 時(shí)，總面積=2×5×s1+3×2×s2+1×1×s3+1×1×s4=903。綜上可知第 1 種方式(γ1，γ2，γ3，γ4)=(1，1，1，1)時(shí)，當(dāng) x1j=2，x2j=3，x3j=1，x4j=1，m1=5，m2=2，m3=1，m4=1 時(shí)，面料利用率最高為 η1=90．3%。

同理對(duì)于其他12種排料方式，可以分別得到面料利用率最高時(shí)，各參數(shù)的值，如表2所示。

對(duì)于(γ1，γ2，γ3，γ4)為(0，1，0，0)，(0，0，1，0)，(0，0，0，0)的這 3 種情況，沒有滿足條件的解。綜上所述，可知當(dāng)(γ1，γ2，γ3，γ4)=(1，0，0，1)，x1j=2，x2j=4，x3j=10，x4j=1，(m1，m2，m3，m4)=(1，3，2，1)時(shí)，能使面料的利用率最大為 η =96．9%。由此可以得到4種矩形的排料圖如圖1所示。

表2 剩余12種排料方式，面料利用率最高時(shí)各參數(shù)的數(shù)值表

圖1 4種矩形的排料圖

5 結(jié)論

筆者建立了混合組合方式下的服裝排料數(shù)學(xué)模型并設(shè)計(jì)了組合優(yōu)化算法，通過優(yōu)化算法得到了矩形樣片的最佳排料方案。最后，利用4種類型的矩形樣片的排料問題驗(yàn)證了該模型的有效性。該服裝排料的數(shù)學(xué)模型和組合優(yōu)化算法能縮短排料時(shí)間，有效地提高面料的利用率，降低生產(chǎn)成本，為提高服裝企業(yè)信息化水平發(fā)揮一定的作用。

［1］ 康立山，謝云，尤矢勇．非數(shù)值并行算法:模擬退火算法［M］．北京:科學(xué)出版社，2005:20－39．

［2］ 盧開澄．組合數(shù)學(xué)算法與分析［M］．北京:清華大學(xué)出版社，1983:41 －98．

［3］ PAPADIMITRIOU C H，STEGLITZ K．組合優(yōu)化算法和復(fù)雜性［M］．劉振宏，蔡茂誠，譯．北京:清華大學(xué)出版社，1988:50 －121．

［4］ ALBANO O．A heuristic solution of the rectangular cutting stock problem［J］．Operation Research，1977，25(l):70－81．

［5］ ADAMOWICZ A．A two stage solution of the cuttingstock problem［J］．Information Processing，1972(17):1086－1091．

［6］ HAIMS F．A multistage solution of the template layout problem［J］．IEEE Trans on Sys Sc．＆ Xyber，1970(2):302－310．

［7］ GILMORE P C，GOMORY R E．Multistage cutting stock problem of two and more dimensions［J］．Operation Research，1965，25(1):96 －120．

［8］ 周泓一，金廷贊．二維不規(guī)則形狀的最優(yōu)布局問題:計(jì)算機(jī)輔助服裝裁片自動(dòng)排料系統(tǒng)［J］．浙江大學(xué)學(xué)報(bào):工學(xué)版，1988(3):92－99．

［9］ 徐彥欣，彭文．二維矩形板材排料的產(chǎn)生式規(guī)則方法［J］．機(jī)械設(shè)計(jì)，1997(6):35－37．

［10］ 劉德全，滕弘飛．矩形件排樣問題的遺傳算法求解［J］．小型微型計(jì)算機(jī)系統(tǒng)，1998(12):20 －25．

［11］ 趙宗金，陳秋娜．計(jì)算機(jī)優(yōu)化排料［J］．電子工業(yè)技術(shù)，1996(4):166－172．

［12］ 李旭，嚴(yán)寒冰．服裝CAD中衣片和排料模塊技術(shù)的研究［J］．浙江工程學(xué)院學(xué)報(bào)，2000，17(3):166 －172．