皮革裁剪路徑優(yōu)化算法的研究

汪嵐， 陳海洋

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

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

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

1.1 裁剪路徑問題的描述

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

(1)

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

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

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

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

假設有n塊樣片，且有n個裁剪起始點，并令樣片編號與其裁剪起始點編號對應(編號0為原點).若第i塊樣片的裁剪起始點i與第j塊樣片的裁剪起始點j之間的空行程距離為di,j，則存在如下關系：

(2)

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

(3)

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

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

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

2.1 裁剪起始點的確定

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

(4)

以坐標中心點C為參考點，定義第i個樣片的第j個頂點與坐標中心點C之間的距離為di j c.di j c的計算公式為：

(5)

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

2.2 裁剪順序的確定

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

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

(6)

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

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

(7)

(8)

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

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

(9)

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

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

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

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

step 2 按照式(4)計算坐標中心點C的x值與y值.

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

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

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

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

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

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

3 實驗與分析

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

圖2 待裁樣片的布局圖

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

由圖4(a)可知，應用本文提出的算法優(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%的長度，且算法收斂性良好(見圖4(b)).

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

4 結論

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