汪嵐， 陳海洋

( 黎明職業(yè)大學(xué) 智能制造工程學(xué)院，福建 泉州 362000 )

我國(guó)是皮革生產(chǎn)、消費(fèi)大國(guó).裁剪作為皮革加工中的關(guān)鍵工序，對(duì)整個(gè)皮革加工效率具有重要影響.目前，國(guó)內(nèi)企業(yè)使用的數(shù)控皮革裁剪機(jī)其生成的裁剪路徑基本都是通用型，這使得裁剪過(guò)程不僅運(yùn)動(dòng)軌跡復(fù)雜，而且裁刀在樣片之間移動(dòng)時(shí)會(huì)不可避免地生成大量的空行程，增加走刀時(shí)間.因此，面對(duì)數(shù)量眾多、輪廓各異的待裁樣片，如何規(guī)劃一條科學(xué)合理的裁剪路徑對(duì)提高生產(chǎn)效率和增強(qiáng)企業(yè)的市場(chǎng)競(jìng)爭(zhēng)力具有重要意義.通常，裁剪路徑優(yōu)化問(wèn)題被歸結(jié)為廣義旅行商問(wèn)題(GTSP)[1]，并且已有很多學(xué)者利用遺傳算法[2-4]、蟻群算法[5-6]、局部搜索算法[7]等對(duì)其進(jìn)行了優(yōu)化求解.但在實(shí)際應(yīng)用中發(fā)現(xiàn)：采用單一算法優(yōu)化裁剪路徑時(shí)，其優(yōu)化能力難以求解GTSP這一復(fù)雜問(wèn)題；采用局部搜索算法優(yōu)化裁剪路徑時(shí)，容易丟失最優(yōu)解空間；采用多種智能算法相結(jié)合的混合算法優(yōu)化裁剪路徑時(shí)，因復(fù)雜度較大而耗時(shí)過(guò)長(zhǎng).因此，本文提出一種分類優(yōu)化算法，在保留最優(yōu)裁剪路徑解空間的前提下，實(shí)現(xiàn)GTSP向TSP(旅行商問(wèn)題)的轉(zhuǎn)化，以此降低算法求解的復(fù)雜度，實(shí)現(xiàn)皮革裁剪最優(yōu)路徑的快速求解.

1 裁剪路徑優(yōu)化模型

1.1 裁剪路徑問(wèn)題的描述

數(shù)控皮革裁剪機(jī)的裁剪路徑為：裁刀由原點(diǎn)出發(fā)，行走一段空行程后達(dá)到第1塊待裁皮革樣片的裁剪起始點(diǎn)；入刀后按照設(shè)定方向沿樣片輪廓路徑進(jìn)行裁剪，裁剪完畢后回到該樣片的裁剪起始點(diǎn)出刀.以此類推，繼續(xù)行走一段空行程后移動(dòng)到第2塊待裁剪皮革樣片的裁剪起始點(diǎn)進(jìn)行裁剪加工.重復(fù)上述步驟，待完成所有樣片的裁剪加工后，裁刀回到原點(diǎn).故裁刀裁剪路徑的數(shù)學(xué)模型可表示為：

(1)

1.2 空行程路徑優(yōu)化模型

由于裁刀空行程路徑問(wèn)題可視為一個(gè)廣義旅行商問(wèn)題，因此根據(jù)圖論[8]可將其描述為：假設(shè)G=(V,A)是一個(gè)賦權(quán)有向圖，其中V={V1，V2,…,Vn}是G的n塊樣片的頂點(diǎn)集合，A={(vi,vj):i≠j,vi≠vj,vi,vj∈V}是G的邊集或弧集.各樣片的頂點(diǎn)集合分別為V1={v1,1,v1,2,…,v1,V(1)},V2={v2,1,v2,2,…,v2,V(2)},…,Vi={vi,1,vi,2,…,vi,V(i)},…,Vn={vn,1,vn,2,…,vn,V(n)}，其中V(i)為第i塊樣片的頂點(diǎn)數(shù)，V=V1∪V2∪…∪Vn，Vi∩Vj=? (i≠j).

由上述可知，裁剪空行程路徑優(yōu)化問(wèn)題就是在賦權(quán)有向圖G中尋找一條由原點(diǎn)出發(fā)，裁刀依次遍游每塊樣片中的某一個(gè)頂點(diǎn)(該頂點(diǎn)為裁剪起始點(diǎn)，所在樣片的其他頂點(diǎn)無(wú)需再游歷)并返回原點(diǎn)，且在樣片間移動(dòng)軌跡無(wú)重復(fù)的最短路徑，如圖1所示的虛線路徑.

圖1 裁剪空行程路徑的GTSP模型

假設(shè)有n塊樣片，且有n個(gè)裁剪起始點(diǎn)，并令樣片編號(hào)與其裁剪起始點(diǎn)編號(hào)對(duì)應(yīng)(編號(hào)0為原點(diǎn)).若第i塊樣片的裁剪起始點(diǎn)i與第j塊樣片的裁剪起始點(diǎn)j之間的空行程距離為di,j，則存在如下關(guān)系：

(2)

裁剪空行程的優(yōu)化模型(目標(biāo)函數(shù))為：

(3)

根據(jù)實(shí)際裁剪工藝要求，約束條件主要考慮裁刀和樣片頂點(diǎn)集兩大約束，具體包括：裁刀的起始點(diǎn)和終止點(diǎn)都是裁床的原點(diǎn)；裁刀到達(dá)和離開(kāi)每塊樣片有且只有一次；裁刀在各樣片之間的移動(dòng)軌跡不重復(fù)(無(wú)子回路).定義樣片外輪廓上的各線段的起點(diǎn)和終點(diǎn)為頂點(diǎn)(如圖1中線段vi,1vi,2，對(duì)應(yīng)頂點(diǎn)為vi,1和vi,2)；定義樣片外輪廓上的各弧線的起點(diǎn)和終點(diǎn)為頂點(diǎn)(如vi,1和vi,V(i))，若弧線角度大于90°時(shí)可每隔90°定義一個(gè)頂點(diǎn).

2 裁剪路徑優(yōu)化算法

由圖1可知，裁刀空行程的路徑距離主要由樣片裁剪起始點(diǎn)和裁剪順序決定，因此可將其視為是一個(gè)NP優(yōu)化問(wèn)題.該優(yōu)化問(wèn)題的求解難度隨樣片數(shù)量的增加呈指數(shù)增大.為降低求解難度，本文采取分類優(yōu)化的思路，即：①引入坐標(biāo)中心點(diǎn)概念[9]，依據(jù)最近規(guī)則選取各樣片的裁剪起始點(diǎn)，即將GTSP問(wèn)題轉(zhuǎn)化為T(mén)SP問(wèn)題，以此降低問(wèn)題的求解難度；②利用改進(jìn)蟻群算法優(yōu)化樣片裁剪順序(即裁剪起始點(diǎn)游歷順序)，以此生成空行程的最短路徑.

2.1 裁剪起始點(diǎn)的確定

假設(shè)有n塊樣片，第i塊樣片有v(i)個(gè)頂點(diǎn)，第i塊樣片的第j個(gè)頂點(diǎn)vi,j(1

(4)

以坐標(biāo)中心點(diǎn)C為參考點(diǎn)，定義第i個(gè)樣片的第j個(gè)頂點(diǎn)與坐標(biāo)中心點(diǎn)C之間的距離為di j c.di j c的計(jì)算公式為：

(5)

根據(jù)式(5)即可求出所有的樣片頂點(diǎn)與坐標(biāo)中心點(diǎn)C的距離.從每塊樣片的頂點(diǎn)集合中選取一個(gè)距離C點(diǎn)最近的頂點(diǎn)vi,j，令其為所在樣片的裁剪起始點(diǎn).以此類推，最終獲得所有樣片的裁剪起始點(diǎn)集合，由此即可完成由GTSP向TSP的轉(zhuǎn)化.

2.2 裁剪順序的確定

蟻群算法是一種求解TSP問(wèn)題的經(jīng)典算法[10]，但傳統(tǒng)蟻群算法自適應(yīng)性差，容易陷入局部最優(yōu)解和出現(xiàn)早熟現(xiàn)象，因此本文選用改進(jìn)最大最小蟻群算法對(duì)已獲得裁剪起始點(diǎn)的游歷順序進(jìn)行優(yōu)化排序.

1)路徑的選擇概率規(guī)則.假設(shè)有m只螞蟻，τi j(0)和τi j(t)分別為樣片i和樣片j之間路徑的信息素濃度初值和當(dāng)前值，τi j(0)=C(C為常數(shù)).t時(shí)刻時(shí)，螞蟻k根據(jù)路徑上的信息素濃度強(qiáng)弱選擇是否從樣片i移動(dòng)到樣片j，其選擇概率規(guī)則為：

(6)

式(6)中：ηi j(ηi j=1/di j)為樣片i和樣片j之間路徑的能見(jiàn)度，路徑距離越短，能見(jiàn)度越高，選中幾率越大；α為信息素因子，用以表征信息素濃度對(duì)螞蟻移動(dòng)的影響度;β為啟發(fā)因子，用以表征信息素濃度與路徑距離的相關(guān)性.

2)信息素自適應(yīng)更新規(guī)則.t時(shí)刻時(shí)，任一路徑上的信息素濃度都存在疊加或揮發(fā)現(xiàn)象，即信息素濃度是動(dòng)態(tài)變化的.本文在傳統(tǒng)蟻群算法的基礎(chǔ)上對(duì)優(yōu)質(zhì)路徑進(jìn)行更新，并加入自適應(yīng)更新功能.其具體方法為：每次迭代結(jié)束后，對(duì)所有螞蟻移動(dòng)的路徑距離進(jìn)行排序，并定義排序靠前的l只螞蟻為精英螞蟻；只對(duì)精英螞蟻行走過(guò)的優(yōu)質(zhì)路徑進(jìn)行信息素更新，其更新規(guī)則[11]為：

(7)

(8)

式(8)中，μ的范圍為[0.1～0.8].在該范圍內(nèi)信息素濃度可自適應(yīng)地進(jìn)行動(dòng)態(tài)調(diào)整，而超出該范圍則算法不更新或完全更新信息素濃度，以此避免算法出現(xiàn)早熟現(xiàn)象.

為了防止優(yōu)質(zhì)路徑上的信息素因疊加或揮發(fā)過(guò)快而造成局部最優(yōu)，需對(duì)路徑上的信息素濃度進(jìn)行限制.限制的方法為：①只允許優(yōu)質(zhì)路徑才能增加信息素；②設(shè)置信息素濃度上、下限值.當(dāng)更新后的信息素濃度在[τmin，τmax]范圍內(nèi)時(shí)，信息素濃度為更新值；當(dāng)信息素濃度超過(guò)上限值或下限值時(shí)，信息素濃度為τmax或τmin，以此確保信息素濃度不超出有效范圍.τmin和τmax的計(jì)算公式為：

(9)

式(9)中，n為裁剪起始點(diǎn)的個(gè)數(shù)，0.05為螞蟻構(gòu)造最佳路徑的可能性.

2.3 分類優(yōu)化算法的求解步驟

采用分類優(yōu)化算法求解皮革裁剪空行程路徑的具體步驟如下：

step 1 初始化參數(shù).

step 2 按照式(4)計(jì)算坐標(biāo)中心點(diǎn)C的x值與y值.

step 3 按照式(5)計(jì)算各樣片與坐標(biāo)中心點(diǎn)的最近頂點(diǎn)，并令其為所在樣片的裁剪起始點(diǎn)，從而獲得所有樣片的裁剪起始點(diǎn)集合.

step 4 初始化蟻群算法的基本參數(shù)，讓m只螞蟻由原點(diǎn)出發(fā)，并令τi j(0)=τmax.

step 6 判斷螞蟻k是否已遍游所有樣片，若未完成則跳轉(zhuǎn)至step 5，若完成則向下執(zhí)行.

step 7 判斷所有螞蟻是否都已構(gòu)建完路徑.若未完成則令k=k+1，并跳轉(zhuǎn)step 5；若完成，則向下執(zhí)行.

step 8 按照式(7)、式(8)和式(9)更新優(yōu)質(zhì)路徑信息素濃度.

step 9 判斷算法迭代次數(shù)是否達(dá)到上限Ncmax，若未達(dá)到，則清空禁忌表，同時(shí)令Nc=Nc+1，并跳轉(zhuǎn)至步驟step 5；否則結(jié)束算法，輸出裁刀空行程的最優(yōu)路徑.

3 實(shí)驗(yàn)與分析

選取一塊面積為1 100 mm×1 100 mm的皮革為例進(jìn)行實(shí)驗(yàn).該皮革共包含62塊待裁樣片，樣片編號(hào)如圖2所示.將圖2中的V25,1為第25塊樣片的第1個(gè)頂點(diǎn)，其余頂點(diǎn)按順時(shí)針排序.形狀相同的樣片其頂點(diǎn)定義方法相同.按照數(shù)控裁剪機(jī)自帶的裁剪算法獲得的空行程裁剪路徑如圖3所示，其裁刀空行程路徑的距離為15 776.4 mm.利用本文給出的算法獲得的空行程裁剪路徑如圖4(a)所示，其空行程路徑的距離為10 338.9 mm.

圖2 待裁樣片的布局圖

圖3 優(yōu)化前的空行程路徑

由圖4(a)可知，應(yīng)用本文提出的算法優(yōu)化后的裁刀空行程路徑為：V0,0→V19,1→V38,4→V54,2→V56,3→V60,4→V48,5→V30,3→V51,1→V33,4→V34,3→V14,1→V15,4→V35,3→V36,5→V37,4→V55,2→V39,3→V40,3→V22,2→V41,4→V58,4→V57,3→V59,3→V61,2→V62,1→V53,2→V52,2→V50,1→V49,6→V32,4→V31,4→V10,4→V11,4→V12,4→V13,4→V9,4→V47,5→V29,4→V8,4→V6,3→V7,4→V5,3→V28,4→V46,5→V4,3→V3,3→V26,3→V44,4→V45,4→V43,4→V42,4→V23,2→V24,2→V1,3→V2,3→V25,3→V27,4→V16,1→V17,1→V21,2→V20,2→V18,1→V0,0.該路徑距離比優(yōu)化前的空行程路徑距離減少了5 437.5 mm，即縮短了34.5%的長(zhǎng)度，且算法收斂性良好(見(jiàn)圖4(b)).

圖4 優(yōu)化后的空行程路徑效果

4 結(jié)論

本文針對(duì)皮革裁剪過(guò)程中存在大量無(wú)效空行程的問(wèn)題，運(yùn)用分類優(yōu)化算法對(duì)裁剪空行程路徑模型進(jìn)行了求解，結(jié)果表明優(yōu)化后的空行程路徑距離比優(yōu)化前的空行程距離縮短了34.5%，實(shí)現(xiàn)了提高數(shù)控裁床加工效率的目的.本文在研究中未使用排料軟件進(jìn)行智能排料，故在原料的使用上存在一定的浪費(fèi)；今后我們將進(jìn)一步研究智能排料在本文算法中的應(yīng)用，以此提高本文算法的適用性.