基于改進(jìn)遺傳算法的激光切割協(xié)同作業(yè)路徑規(guī)劃

周銳 馬漢武

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

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

中圖分類號(hào)：F273??? 文獻(xiàn)標(biāo)識(shí)碼：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? 引? 言

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

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

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

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

1? 問(wèn)題描述與建模

1.1? 問(wèn)題描述

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

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

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

特征點(diǎn)的集合V：

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

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

V開始對(duì)零件2進(jìn)行切割，再到V對(duì)零件1進(jìn)行切割，最后返回原點(diǎn);激光器2對(duì)零件3和零件4進(jìn)行切割，為防止含有子環(huán)的零件因?yàn)橹亓Φ袈?，從原點(diǎn)出發(fā)，抵達(dá)V對(duì)零件3進(jìn)行切割，再到V對(duì)零件4的子環(huán)進(jìn)行切割，然后到V對(duì)零件4的父環(huán)進(jìn)行切割，最后返回原點(diǎn)。

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

1.2? 數(shù)學(xué)建模

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

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

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個(gè)激光器從原點(diǎn)出發(fā)并且返回，式（7）和式（8）確保每個(gè)特征點(diǎn)只有一個(gè)激光器通過(guò)，式（9）是子閉跡消去約束[14]，用來(lái)防止沒有機(jī)床原點(diǎn)的情況下生成路徑，u表示任何一個(gè)激光器抵達(dá)一個(gè)特征點(diǎn)的數(shù)量。

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

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

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

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

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

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

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

步驟3：以問(wèn)題為導(dǎo)向，設(shè)計(jì)遺傳算子;

步驟4：初始化種群;

步驟5：計(jì)算適應(yīng)度函數(shù);

步驟6：通過(guò)選擇部分染色體作為父代進(jìn)行遺傳操作;

步驟7：對(duì)選擇出來(lái)的父代基因進(jìn)行交叉;

步驟8：對(duì)選擇出來(lái)的父代基因進(jìn)行變異;

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

步驟10：更新種群，重復(fù)步驟5到步驟9;

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

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

（1）種群初始化編碼

每條染色體由n+m-1個(gè)基因組成，前n-1個(gè)基因代表激光器抵達(dá)特征點(diǎn)的排列，剩下的m個(gè)基因表示每個(gè)激光器能夠到達(dá)的特征點(diǎn)的數(shù)量。因?yàn)樗屑す馄鞅囟◤臋C(jī)床原點(diǎn)出發(fā)和返回，所以這個(gè)特征點(diǎn)不包括在染色體中，以節(jié)省內(nèi)存。然后生成多個(gè)染色體，這些染色體組成初始種群。

（2）適應(yīng)度函數(shù)的設(shè)計(jì)

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

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

式（10）中，L為適應(yīng)度值，x，y為各點(diǎn)的坐標(biāo)。適應(yīng)度值與各組點(diǎn)的距離之和成反比。

（3）變異操作

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

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

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

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

（4）交叉操作

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

（5）局部算子操作

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

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

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

2.3? 算法流程

本文提出的帶有局部算子的遺傳算法，完整過(guò)程如圖5所示：對(duì)多個(gè)激光器和帶切割零件的特征點(diǎn)進(jìn)行編碼，成為染色體;計(jì)算整個(gè)流程的適應(yīng)度;優(yōu)先檢查目前的加工零件是不是最優(yōu)路徑，是的話直接輸出結(jié)果，否則，進(jìn)行下一步;對(duì)個(gè)體執(zhí)行選擇、變異和交叉操作;因?yàn)榧す馇懈畹奶厥庑裕瑸榱朔乐箍招谐探?jīng)過(guò)切割區(qū)域和“碰刀”現(xiàn)象，采用局部算子進(jìn)行優(yōu)化;根據(jù)終止的標(biāo)準(zhǔn)：達(dá)到一定的遺傳代數(shù)，或者得到的結(jié)果不再有顯著的改善;最后輸出最優(yōu)路徑。

3? 仿真實(shí)驗(yàn)與結(jié)果分析

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

Matlab2014b和I5-8400H。

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

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

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

4? 結(jié)? 論

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

參考文獻(xiàn)：

[1] 周濟(jì). 智能制造——“中國(guó)制造2025”的主攻方向[J]. 中國(guó)機(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] 張素云，楊勇生，梁承姬，等. 自動(dòng)化碼頭多AGV路徑?jīng)_突的優(yōu)化控制研究[J]. 交通運(yùn)輸系統(tǒng)工程與信息，2017，17（2）：83-89.

[4] 肖珂，高冠東，馬躍進(jìn). 基于Kinect視頻技術(shù)的葡萄園農(nóng)藥噴施路徑規(guī)劃算法[J]. 農(nóng)業(yè)工程學(xué)報(bào)，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] 劉會(huì)霞，王霄，周明，等. 共邊排樣件激光切割路徑的規(guī)劃[J]. 中國(guó)激光，2004（10）：1269-1274.

[7] 楊建軍，劉保業(yè)，鞠錄巖. 激光切割路徑優(yōu)化的雙重編碼改進(jìn)遺傳算法[J]. 解放軍理工大學(xué)學(xué)報(bào)（自然科學(xué)版），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]. 鍛壓技術(shù)，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] 羅志遠(yuǎn)，豐碩，劉小峰，等. 一種基于分步遺傳算法的多無(wú)人清潔車區(qū)域覆蓋路徑規(guī)劃方法[J]. 電子測(cè)量與儀器學(xué)報(bào)，2020，34（8）：43-50.

[13] Liang M A. Artificial Ant Algorithm for Constrained Optimization[J]. 系統(tǒng)科學(xué)與系統(tǒng)工程學(xué)報(bào)（英文版），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]? 胡志偉，郄培，趙新超，等. 一種新的混合遺傳算法求解旅行商問(wèn)題[J]. 計(jì)算機(jī)與現(xiàn)代化，2010（11）：12-15.