周銳 馬漢武

摘? 要：多激光切割機同時進行同一塊板材的加工作業(yè)，不僅能夠提高效率，還能夠應對大規(guī)模定制的要求。但是由于加工路徑規(guī)劃不恰當，會使激光頭受損，成本大幅增加，效率也并未提升，因此，研究激光切割協(xié)同作業(yè)的路徑規(guī)劃具有十分重要的意義。文章以總路徑最短作為規(guī)劃目標，考慮空行程切割和切割沖突兩種情況，建立激光切割協(xié)同作業(yè)路徑的多旅行商模型，提出了一種改進遺傳算法。結果表明，與傳統(tǒng)遺傳算法相比，引入局部算子的遺傳算法能夠在相應約束條件下求出最優(yōu)路徑，而且收斂更好，計算時間更快。

關鍵詞：路徑規(guī)劃;遺傳算法;激光切割;協(xié)同作業(yè)

中圖分類號：F273??? 文獻標識碼：A

Abstract： The use of multiple laser cutting machine at the same time for the same piece of plate processing operations， not only can improve efficiency， but also to deal with the requirements of mass customization. But the processing path planning is not appropriate， the laser head will be damaged， and the cost increased significantly， the efficiency has not been improved. Therefore， the study of laser cutting collaborative operation path planning has very important significance. In this paper， the planning objective is to minimize the total path， and considering the two situations of empty stroke cutting and cutting conflict. A multiple traveling salesman model is established to plan the collaborative work path of laser cutting， and an improved genetic algorithm is proposed. Compared with the traditional genetic algorithm， the genetic algorithm with local operators can find the minimize path under the corresponding constraints， and has better fitness and faster calculation time.

Key words： path planning; genetic algorithm; laser cutting; cooperative operation

0? 引? 言

近些年來，我國開始著力開發(fā)高質量、高精度和高創(chuàng)新的制造系統(tǒng)[1]。激光切割技術已經逐漸成為一種常見的切割加工方式，相較于目前企業(yè)運用較廣的幾種切割方法，激光切割具有加工范圍廣、速度快、精度高等優(yōu)勢[2]。隨著激光切割技術的民用化，激光切割車間應運而生，而多臺激光切割機的協(xié)同作業(yè)可以更快地完成板材零件的加工任務，便于企業(yè)應對顧客大規(guī)模定制的需求。多機作業(yè)時需要確保每一臺激光切割機的加工路徑最短，并且在作業(yè)過程中不會出現(xiàn)“碰刀”的情況[3-5]。如何規(guī)劃激光切割車間的切割機協(xié)同作業(yè)路徑，節(jié)省加工成本，減少加工時間，提高加工效率是需要解決的問題。

目前，對于激光切割路徑規(guī)劃的研究主要集中在單機作業(yè)和智能算法優(yōu)化兩個方面，取得了一定的成果。劉會霞等[4]在保證有效切割零件和切割零件質量的基礎上，提高激光切割的生產率，基于圖論學理論，建立了激光切割路徑規(guī)劃的數(shù)學模型，給出了最優(yōu)行程規(guī)劃。楊建軍[5]將激光切割路徑優(yōu)化歸納為TSP問題，并改進了遺傳算法。提高了算法的優(yōu)化性能，改進了交叉操作與變異操作，有效地對激光切割路徑進行了優(yōu)化。Hajad[6]提出了一種模擬退火算法與自適應大鄰域搜索（ALNS）相結合的方法，以優(yōu)化激光切割過程中的路徑。該優(yōu)化算法基于廣義旅行商問題（GTSP），可以較好地解決數(shù)據(jù)庫中的多個數(shù)據(jù)集問題，在路徑距離和計算時間之間取得最優(yōu)解。王娜[7]為了進一步優(yōu)化切割路徑，縮短切割時間，基于廣義旅行商問題（GTSP），采用雙向蟻群算法進行激光切割的路徑優(yōu)化，針對激光切割過程中，根據(jù)切割路徑的特殊性，設計了不同搜索方向的引導問題，從而避免了“碰刀”的情況發(fā)生，與原來的算法相比，行程變短，時間減少，具有優(yōu)勢。以上的研究均從智能算法的角度成功對激光切割路徑進行了優(yōu)化，減少了切割路徑，縮短了切割時間，提高了切割效率。但是，還存在著一些不足：只考慮了單機加工的問題，沒有考慮過多機協(xié)同加工模式下的路徑規(guī)劃問題。

在多機協(xié)同作業(yè)的研究中，Senthilkumar[10]利用生成樹算法對機器人的協(xié)同探索作業(yè)進行了研究，但是得到的結果中，重復路徑過多。Seyyedhasani[11]通過禁忌算法對3臺拖拉機的協(xié)同作業(yè)路徑進行了優(yōu)化，提高了工作效率，但并未處理路徑沖突問題。羅志遠[12]利用分布遺傳算法解決了多無人清潔車的協(xié)同作業(yè)全局規(guī)劃，成功將這種路徑規(guī)劃問題轉化為多旅行商（MTSP）問題，但是對于路徑沖突問題依然沒有研究。

本文研究了激光切割協(xié)同作業(yè)的路徑規(guī)劃，充分考慮作業(yè)沖突問題，建立了激光切割協(xié)同作業(yè)的多旅行商問題（Multiple Traveling Salesman Problem， MTSP）數(shù)學模型，提出了帶有局部算子的遺傳算法，在滿足各種約束條件的前提下，縮短切割路徑并減少切割時間。

1? 問題描述與建模

1.1? 問題描述

激光切割鈑金零件，切割區(qū)域是由直線、曲線、圓和圓弧組成的閉合輪廓，如圖1所示，我們將這個閉合輪廓定義為閉環(huán)（Loop），如果這個閉環(huán)內還存在其他輪廓，則稱外部閉環(huán)為父環(huán)（FatherLoop），而內部閉環(huán)則稱為子環(huán)（SonLoop），構成這些閉環(huán)的線段為邊（E），這些邊的端點稱作頂點（V）。

圖2為一塊待加工鈑金，由四個待切割零件構成，其中有五個閉環(huán)，定義閉環(huán)集合L：

L=L，L，…，L， k=0，1，2，3，4，5????????????????????????????????????? （1）

特征點的集合V：

V=V， k=0，1，2，3，4，5， i=0，1，2，…，n????????????????????????????????? （2）

單機激光切割的過程是從機床原點出發(fā)，快速抵達第一個閉環(huán)的特征點，完成切割后，快速移動到下一個閉環(huán)的特征點，依次往復，直至切割完所有待切割零件，最后返回機床原點。激光切割協(xié)同作業(yè)的過程可以看作是多個激光頭同時對材料進行加工，如圖2所示，激光器1對零件1和零件2進行切割，為避免激光頭在移動過程中經過已切割區(qū)域，從原點出發(fā)，抵達

V開始對零件2進行切割，再到V對零件1進行切割，最后返回原點;激光器2對零件3和零件4進行切割，為防止含有子環(huán)的零件因為重力掉落，從原點出發(fā)，抵達V對零件3進行切割，再到V對零件4的子環(huán)進行切割，然后到V對零件4的父環(huán)進行切割，最后返回原點。

根據(jù)上文所述的激光切割過程，激光切割協(xié)同作業(yè)路徑規(guī)劃問題，就是在滿足約束條件的前提下，使總加工路徑和總加工時長最短。

1.2? 數(shù)學建模

將激光器看作多旅行商問題中的旅行商，待加工零件上的初始特征點為城市，一個零件上的所有特征點構成一個城市集合。求激光切割協(xié)同作業(yè)的路徑規(guī)劃問題就轉化為求解MTSP問題，定義如下：給定m個激光器，n個待加工零件，使所有激光器的總切割路徑最小，每個零件只會有一個激光器到達。所有的激光器從同一個原點出發(fā)，然后返回同一個原點（原點不記作城市）。每個切割器至少需要切割一個零件，最多P個零件。

其中，特征點和切割路線可以用無向完全圖表示G=V，E，V表示所有特征點的集合，V表示機床原點，E表示特征點之間距離的集合。將整個鈑金看作一個坐標系，則每一個特征點V都可以用一個坐標x，y進行表示，E表示從特征點V到V的路徑，距離記作S。定義一個二進制變量X表示從特征點V到V的路徑狀態(tài)，如果E在選中的路徑中，則X=1，否則，X=0，因此，本文的問題可以建模為：

D=minCX??????????????????????????????????????????? （3）

條件約束為：

X∈0，1， E∈E??????????????????????????????????????????? （4）

X=m??????????????????????????????????????????????? （5）

X=m???????????????????????????????????????? ???????（6）

X=1??? j=1，2，…，n-1?????????????????????????????????????? （7）

X=1??? i=1，2，…，n-1?????????????????????????????????????? （8）

u-u+PX≤P-1， 1≤i≠j≤n-1????????????????????????????????????? （9）

式（5）和式（6）確保有m個激光器從原點出發(fā)并且返回，式（7）和式（8）確保每個特征點只有一個激光器通過，式（9）是子閉跡消去約束[14]，用來防止沒有機床原點的情況下生成路徑，u表示任何一個激光器抵達一個特征點的數(shù)量。

2? 帶有局部算子的遺傳算法

為了求解多旅行商問題，提出帶有局部算子的遺傳算法進行求解。設計兩個新的局部算子：分支定界算子和交叉消除算子，以加快搜索過程的收斂速度，提高解的質量。

2.1? 傳統(tǒng)遺傳算法

遺傳算法（Genetic Algorithm， GA）是基于達爾文進化論和遺傳學理論，根據(jù)大自然中生物體進化規(guī)律而設計提出的。是模擬自然選擇和生物進化過程的一種數(shù)理模型，是一種通過模擬演化自然進化過程來解決最優(yōu)解問題的方法。經過優(yōu)勝劣汰的自然選擇，適應環(huán)境能力比較強的個體或者基因，會被保留下來，而適應能力比較弱或者完全無法適應的個體或者基因就會被淘汰[15-16]。

遺傳算法通過一系列選擇、交叉和變異的過程，不斷重復這些流程，最終得到一個比較優(yōu)秀的解。具體步驟如下：

步驟1：確定個體編碼的方式，并且設定好遺傳參數(shù);

步驟2：寫出適應度函數(shù);

步驟3：以問題為導向，設計遺傳算子;

步驟4：初始化種群;

步驟5：計算適應度函數(shù);

步驟6：通過選擇部分染色體作為父代進行遺傳操作;

步驟7：對選擇出來的父代基因進行交叉;

步驟8：對選擇出來的父代基因進行變異;

步驟9：不斷進化，取一個合適的遺傳代數(shù)，記錄最優(yōu)個體;

步驟10：更新種群，重復步驟5到步驟9;

步驟11：進化終止，得到最優(yōu)解。

2.2? 帶有局部算子的遺傳算法

（1）種群初始化編碼

每條染色體由n+m-1個基因組成，前n-1個基因代表激光器抵達特征點的排列，剩下的m個基因表示每個激光器能夠到達的特征點的數(shù)量。因為所有激光器必定從機床原點出發(fā)和返回，所以這個特征點不包括在染色體中，以節(jié)省內存。然后生成多個染色體，這些染色體組成初始種群。

（2）適應度函數(shù)的設計

遺傳算法的適應度函數(shù)的設計，要考慮激光切割協(xié)同作業(yè)任務的均衡調度問題。這種問題相當于已經分組好的TSP問題，直接使每組的路徑最短即可：

L=1???????????????????????????????????? （10）

式（10）中，L為適應度值，x，y為各點的坐標。適應度值與各組點的距離之和成反比。

（3）變異操作

根據(jù)設計的染色體。染色體中第一部分中的特征點只能出現(xiàn)一次，第二部分的基因值之和必須等于特征點的總數(shù)。因為這些約束條件，所以采用優(yōu)化的遺傳算子改進進化機制。

染色體的第一部分，有兩種變異操作方法，分別是隨機交換和反向交換。隨機交換就是選擇兩個不同的隨機位置G和G，其中i≠j，這兩個基因進行交換。反向交換就是選擇兩個隨機的基因片段，片段內基因的位置顛倒。

染色體的第二部分，即每個激光器能夠到達的特征點數(shù)，采用隨機分布變異法。隨機選擇兩個不同的位置i和j，其中i

≠j，G增加1，G減少1，然后確保G≥1且G≤P。P為特征點的最大數(shù)目。

（4）交叉操作

利用邊緣重組交叉算子[17]修改交叉染色體的第一部分。這種方法能夠有效地解決MTSP問題。這個算子的交叉思路是，如果一條編碼出現(xiàn)在雙親染色體上，它被認為是一個好的基因，并且有更高的機會出現(xiàn)在最優(yōu)解中。

（5）局部算子操作

局部算子是使用局部搜索技術，引入貪婪染色體片段，為了防止早熟收斂，只對特定的遺傳代數(shù)和種群中前五個個體進行操作。引入兩個局部算子：交叉消除算子通過對激光器到達特征點順序的重新排列，縮短總加工路徑;分支定界算子為了從一條加工路徑出發(fā)，為一部分特征點構成的集合選擇最優(yōu)路徑。

交叉消除算子會積極搜索加工路徑內部形成的交叉，并通過重新排列特征點順序來消除交叉。激光協(xié)同加工中的交叉一般可以分成兩個類型：單個激光器加工路徑交叉和多個激光器加工路徑交叉。為了得到最優(yōu)解，建立一個包含所有解的列表，按降序形成求解序列，如圖3（b）所示，交叉消除得到的結果可能會使路徑變短，也可能像圖3（c）一樣變長。所以，需要經過幾個周期（最多5個）的迭代或在沒有明顯改進時停止求解。

分支定界算子基于分支定界算法，用于求解離散組合優(yōu)化問題，通過狀態(tài)空間搜索，所有候選解形成一個集合，不斷對集合的子集進行比較，得到最優(yōu)解。利用分支定界法對所有特征點重新排序，將MTSP問題轉化為TSP問題，得到局部最優(yōu)路徑，如圖4所示。

2.3? 算法流程

本文提出的帶有局部算子的遺傳算法，完整過程如圖5所示：對多個激光器和帶切割零件的特征點進行編碼，成為染色體;計算整個流程的適應度;優(yōu)先檢查目前的加工零件是不是最優(yōu)路徑，是的話直接輸出結果，否則，進行下一步;對個體執(zhí)行選擇、變異和交叉操作;因為激光切割的特殊性，為了防止空行程經過切割區(qū)域和“碰刀”現(xiàn)象，采用局部算子進行優(yōu)化;根據(jù)終止的標準：達到一定的遺傳代數(shù)，或者得到的結果不再有顯著的改善;最后輸出最優(yōu)路徑。

3? 仿真實驗與結果分析

根據(jù)本文的算法，采用MATLAB編程對多機激光切割協(xié)同作業(yè)的路徑進行規(guī)劃，實驗對象為一塊待切割板材，按照表1參數(shù)對切割路徑進行規(guī)劃，在計算時間和路徑長度上，與現(xiàn)有的MTSP求解方法進行比較。電腦開發(fā)環(huán)境為：Win10、

Matlab2014b和I5-8400H。

在激光切割協(xié)同作業(yè)中，對于引入局部算子的優(yōu)化曲線仿真如圖6所示。其中x軸表示遺傳代數(shù)，y軸表示路徑總長度，正方形實線表示傳統(tǒng)遺傳算法的收斂，圓圈實線表示引入分支定界算子的收斂，正三角形實線表示引入交叉消除算子的收斂，倒三角形實線表示引入兩種算子的收斂，可以看出引入兩種算子的遺傳算法隨著解的規(guī)模越大，收斂越快。

5個激光頭使用兩種算法得到的路徑如圖7和圖8所示。從圖7中可以看出，得到的路徑規(guī)劃無法避免交叉點，即會出現(xiàn)“碰刀”或者是空行程經過已切割零件區(qū)域的情況，而圖8引入交叉消除算子和分支定界算子之后，避免了這種情況的發(fā)生，在約束下找到了路徑最優(yōu)解。

通過分析可知，帶有局部算子的方法能夠在避免空行程切割和碰刀的約束條件下使激光協(xié)同作業(yè)的路徑最短，但是從表2還可以看出，雖然算法的收斂程度很快，解決問題時間很快，在約束條件下的路徑是最優(yōu)的，但是相比于沒有約束時遺傳算法求得的路徑長度，加入約束之后的路徑變長了。

4? 結? 論

將多機激光切割協(xié)同作業(yè)路徑規(guī)劃問題轉化為帶有約束條件的多旅行商問題，基于避免空行程經過已切割區(qū)域、碰刀現(xiàn)象等工藝約束條件，引入兩種算子優(yōu)化遺傳算法，能夠很好地解決加工路徑規(guī)劃的問題。算法的收斂程度優(yōu)秀，求解時間相對短，但是求得最優(yōu)路徑，相比無約束的切割路徑是變長的。下一步針對如何再度計算更短的切割路徑，研究通過引入其他算法，或者是提前對鈑金待加工零件進行排樣優(yōu)化，進一步去縮短多機激光切割協(xié)同作業(yè)的路徑。

參考文獻：

[1] 周濟. 智能制造——“中國制造2025”的主攻方向[J]. 中國機械工程，2015，26（17）：2273-2284.

[2] P A Hilton. The early days of laser cutting[C] // 11th Nordic Conference in Laser Processing of Materials， 2007：20-22.

[3] 張素云，楊勇生，梁承姬，等. 自動化碼頭多AGV路徑沖突的優(yōu)化控制研究[J]. 交通運輸系統(tǒng)工程與信息，2017，17（2）：83-89.

[4] 肖珂，高冠東，馬躍進. 基于Kinect視頻技術的葡萄園農藥噴施路徑規(guī)劃算法[J]. 農業(yè)工程學報，2017，33（24）：192-199.

[5]? Bochtis D D， S？覬rensen C G， Busato P. Advances in agricultural machinery management： A review[J]. Biosystems Engineering， 2014，126（39）：69-81.

[6] 劉會霞，王霄，周明，等. 共邊排樣件激光切割路徑的規(guī)劃[J]. 中國激光，2004（10）：1269-1274.

[7] 楊建軍，劉保業(yè)，鞠錄巖. 激光切割路徑優(yōu)化的雙重編碼改進遺傳算法[J]. 解放軍理工大學學報（自然科學版），2012，13（6）：684-687.

[8]? Hajad M， Tangwarodomnukun V， Jaturanonda C， et al. Laser cutting path optimization using simulated annealing with an adaptive large neighborhood search[J]. International Journal of Advanced Manufacturing Technology， 2019，103：781-792.

[9] 王娜，王海艷，姜云春. 激光切割工藝路徑的雙向蟻群算法優(yōu)化[J]. 鍛壓技術，2020，45（11）：30-35.

[10]? Senthilkumar K S， Bharadwaj K K. Multi-robot exploration and terrain coverage in an unknown environment[J]. Robotics and Autonomous Systems， 2012，60：123-132.

[11]? Seyyedhasani H， Dvorak J S. Reducing field work time using fleet routing optimization[J]. Biosystems Engineering， 2018，169：1-10.

[12] 羅志遠，豐碩，劉小峰，等. 一種基于分步遺傳算法的多無人清潔車區(qū)域覆蓋路徑規(guī)劃方法[J]. 電子測量與儀器學報，2020，34（8）：43-50.

[13] Liang M A. Artificial Ant Algorithm for Constrained Optimization[J]. 系統(tǒng)科學與系統(tǒng)工程學報（英文版），2001，10（1）：57-61.

[14]? C E Miller， A W Tucker， R A Zemlin. Integer Programming Formulation of Traveling Salesman Problems[J]. ACM， 1960，7（4）：326-329.

[15]? Prinetto P， Rebaudengo M， Reorda M S. Hybrid Genetic Algorithms for the Traveling Salesman Problem[M]. Artificial Neural Nets and Genetic Algorithms. Springer Vienna， 1993：559-566.

[16]? 胡志偉，郄培，趙新超，等. 一種新的混合遺傳算法求解旅行商問題[J]. 計算機與現(xiàn)代化，2010（11）：12-15.