基于旅行商問題轉化和遺傳算法求解汽配件噴涂順序

，*

（1.西華師范大學數學與信息學院，四川南充 637009；2.西華師范大學計算方法及應用軟件研究所，四川南充 637009）

0 引言

汽車產業的飛速發展使得汽配件的生產呈現爆發性增長。外觀類汽配件通常需要進行顏色噴涂，這樣既能滿足顧客對汽車外觀的審美需求，也能確保汽車在自然環境條件下的耐用性需求。生產線上的汽配件噴涂顏色時，若前后相鄰兩個汽配件需要噴涂不同的面漆色，則稱為一次“換色”，此時需要更換噴槍的涂料顏色，換色次數的多少會影響生產成本。

上述情形可稱為汽配件顏色噴涂順序問題，本文選取比較常見的一種環形噴涂生產線，如圖1 所示，生產線上設置有一定數量的滑橇，有特定的換件處和噴涂處。汽配件被依次安裝在滑橇上，隨滑橇在軌道上移到噴涂處進行噴色，當移到換件處則將其取下。

圖1 汽配件噴涂生產線Fig.1 Spraying production line for auto parts

在實際生產過程中，某些類別的汽配件由于形狀等因素會導致不能相鄰排列、某些顏色的汽配件由于顏色原料的特定要求會導致不能相鄰排列，這些因素都會影響到顏色切換次數進而影響到生產成本，因此，研究和優化一批生產任務內的汽配件序列，可以理論指導生產實踐并幫助企業提高生產效率、降低生產成本。

上述問題實質上是一類產品加工順序問題，也可看作是一類柔性作業車間調度問題。通常遇到這類調度問題首先考慮到用經典的動態規劃方法來對問題進行求解，但動態規劃方法在求解大規模問題時效率低、速度慢，而在對原問題的分析中發現在汽配件噴涂生產線上，每一個滑橇上安裝的汽配件都要噴涂且只噴涂一次，這非常類似于旅行商問題（Travelling Salesman Problem，TSP）［1］，故本文采用借鑒TSP建模的方法對汽配件噴涂順序問題進行轉化建模。旅行商問題作為著名的NP-hard 問題，近年來許多專家學者對該問題的求解提供了許多的優化算法，如遺傳算法［2-3］和模擬退火算法［4］、蟻群優化（Ant Colony Optimization，ACO）算法［5］、粒子群優化（Particle Swarm Optimization，PSO）算法［6-7］、狼群算法［8］、煙花算法［9］，取得了比較豐富的研究成果。而遺傳算法自提出以來，在求解TSP 領域中取得了較好的成果。同傳統的PSO算法和ACO算法相比，遺傳算法的全局尋優能力強、具有潛在的并行性，可以進行多個個體的同時比較。盡管如此，遺傳算法的進化概念不能直接應用于求解汽配件噴涂順序問題，必須通過將原問題轉化為TSP，建立適應的TSP 轉化模型，再用遺傳算法對模型進行求解從而求解出汽配件噴涂的順序問題。為此，本文提出了一種基于TSP 轉化和遺傳算法的優化和求解方法，實驗結果表明該優化模型刻畫準確、求解算法高效實用。

1 TSP轉化與建模

1.1 定義TSP頂點及其距離

在汽配件噴涂生產線上，每一個滑橇上安裝的汽配件都要噴涂且只噴涂一次，這非常類似于TSP。設一條生產線共有N個滑橇，將待噴涂的N組汽配件看作是N個TSP 頂點，對它們以一定順序編號，即構成一個TSP 的頂點集，記為V={v1，v2，…，vN}。

與TSP不同，在汽配件噴涂順序問題中，任意兩組待噴涂的汽配件之間并沒有距離的概念。考慮到問題的目標是使噴涂生產線上換色次數盡量少，因此可以用任意兩組汽配件的顏色是否發生切換來定義頂點之間的距離。

設N組待噴涂汽配件的顏色共有L種，用自然數1，2，…，L來表示對應的顏色號，頂點vi對應的顏色號記為pi∈{1，2，…，L}，所有頂點顏色號記為P={p1，p2，…，pN}。定義任意兩個頂點是否需要換色（顏色是否相同）為其距離，若要換色則距離為1，否則為0，可表示為：

由dij構成的頂點距離矩陣記為D=(dij)N×N，由于dij是0-1變量，因此N個頂點構成的一條TSP路徑（一個噴涂序列）的距離之和剛好也能反映噴涂該序列的換色總次數。

1.2 構建TSP模型

與標準TSP 的約束一樣，汽配件噴涂順序問題的N個頂點要構成一條TSP 路徑，也要滿足任意頂點的出度為1、入度也為1，以及不構成子回路這三種基本約束條件。此外，比起標準的TSP來說汽配件噴涂順序問題還應當滿足噴涂生產的兩類限制條件：某些配件的顏色因調色等因素具有互斥性，對應的這些汽配件組將不能安裝在相鄰的滑橇上噴涂；某些配件的形狀容易導致相互之間碰撞和劃傷，對應的這些汽配件組將不能安排在相鄰的滑橇上噴涂，故將借鑒TSP經典模型，建立適合汽配件噴涂問題的TSP轉化數學模型。

類似于頂點距離的定義，可以對任意兩個頂點的顏色和類別是否允許相鄰進行定義，再用它對TSP 路徑的顏色和類別限制進行約束。為便于計算，首先對顏色或類別之間是否允許相鄰進行量化定義。設汽配件的類別共有K種，用自然數1，2，…，K來表示對應的類別號，則任意兩種顏色或類別是否允許相鄰可分別定義為：

由cij，tij構成的顏色和類別的相鄰性矩陣分別記為C=(cij)L×L，T=(tij)K×K，矩陣C、T不一定是對稱陣，因為有些顏色或類別之間的前后相鄰性并不完全相同。

設頂點vi的配件類別號為qi∈{1，2，…，K}，所有頂點的類別號記為Q={q1，q2，…，qN}，則任意兩個頂點的顏色和類別是否允許相鄰性可分別定義為：

由rij，sij構成的頂點顏色和類別相鄰性矩陣分別記為R=(rij)N×N，S=(sij)N×N。

仿照標準TSP的0-1規劃模型，設有如下0-1變量：

則可建立汽配件噴涂順序問題的0-1規劃模型如下：

在模型中，約束條件（1）和（2）使得對每一個頂點只能有一條邊進和一條邊出，約束條件（3）使得不會產生任何的子回路，約束條件（4）和（5）使得在TSP 路徑上的相鄰兩個頂點之間不會出現汽配件的顏色和類別不允許相鄰的情形。

2 遺傳算法設計

在實際生產中，汽配件噴涂順序問題的規模較大，現代智能啟發式算法［10］是求解這類問題的主要算法，遺傳算法［11］就是其中一種高效實用、魯棒性強的算法，它借鑒生物遺傳學原理，模擬自然界生物的遺傳進化過程，具有優異的自適應性、并行性和全局尋優能力。遺傳算法首先需要為可行解選擇恰當的基因編碼方案，并產生一定數量的初始種群，然后對種群進行一定次數的遺傳進化操作，包括適應度評估、選擇、交叉、變異操作，最終獲得問題的近似最優解。下面根據汽配件噴涂問題的特點，進行遺傳算法的設計。

2.1 編碼方案

遺傳算法不能直接處理問題空間的參數，需要將其編碼成為遺傳空間的染色體。遺傳算法的魯棒性強，對基因編碼方案要求并不苛刻，但是編碼方案對遺傳操作有很大的影響，特別是交叉和變異操作。在TSP 的0-1 規劃模型中，所有的0-1 型變量xij就是問題空間的參數，共有N2個，如果將這些參數編碼成為二進制形式的染色體，當N較大時，會導致染色體的編碼長度太長，在計算機存儲和遺傳操作的運算等方面都會難以處理。除此以外，xij還受到五類約束條件的限制，因此即使生成了編碼，也必然存在著大量的無效編碼，需要借助額外的算法進行檢測和剔除，再重新補充生成合法有效的染色體編碼，這必然又增加算法的復雜性。

考慮到汽配件噴涂順序問題也是TSP 的一類擴展應用，需要求得的最優解就是所有頂點（全部待噴涂的汽配件組）的某個特定的最優順序，因此可以將這些頂點編號作為問題空間的參數進行編碼：一方面滿足編碼方案的完備性、健全性和非冗余性；另一方面染色體的編碼長度從N2位下降到N位，這樣遺傳算法也容易實現，提高了算法的實用性。一般地，頂點編號以自然數表示，因此在本問題中，采用不重復的自然數對全部頂點進行染色體編碼［12］，于是每一個個體的染色體編碼可表示為：

設初始種群規模為m，則可表示為X=[X1；X2；…；Xm]。

2.2 適應度函數

適應度函數用于評估和區分種群個體的優劣，是進行遺傳選擇的依據。本問題中，由于有生產限制的約束條件，即使采用不重復的自然數編碼［13］方案，也仍然無法避免無效編碼的出現。此時有兩種解決方法：一是設計額外的檢測算法，剔除無效編碼，再補充生成有效編碼；二是將與無效編碼對應的約束條件以懲罰分量的形式添加到目標函數中，使得包含有無效編碼的個體在遺傳進化過程中具有更差的適應度。為降低算法的空間和時間復雜性，提高算法的實用性，本文采用第二種解決方法，并按以下方法構造適應度函數。

由第1 章可知，對任意一個噴涂序列τ={τ1，τ2，…，τN}（τi∈V且互不相同），它的路徑長度（換色總次數）、出現配件顏色不允許相鄰的總次數、出現配件類別不允許相鄰的總次數，可分別用以下公式計算：

其中：f2，f3即是對模型中約束條件（4）和（5）的轉化，將其作為懲罰分量，添加到適應度函數中，當其值趨于0 時，噴涂序列中相鄰頂點的顏色和類別必定是符合生產要求的。

設三個分量的權重分別為λ1，λ2，λ3∈[0，1]，(λ1+λ2+λ3=1)，則適應度函數為：

可以看到，當適應度函數達到最小時，若分量f2，f3趨于0，則分量f1恰好能近似等于噴涂序列的最少換色次數。

2.3 遺傳進化策略

遺傳算法的遺傳進化策略包括選擇、交叉和變異［14］，選擇策略可以將種群中適應度高的個體選擇出來，交叉和變異策略可以在已選擇個體基礎上產生新個體，以提高種群的多樣性，提高收斂速度。一些研究表明，錦標賽選擇策略通用于最大化和最小化問題，在求解精度和收斂速度方面性能優異［15］。本文選擇錦標賽選擇策略，以此為基礎來設計遺傳進化策略。

體育運動的錦標賽最早是指單項運動的冠軍賽，運動員首先通過分組比賽，才能進入決賽獲得冠軍。錦標賽選擇策略正是借鑒這種賽制規則和賽程安排原理，基本思想是分組和優選，主要操作方法是預先確定一個分組規模，將整個種群隨機地分成若干個種群小組，每個小組內只選擇組內最優的個體作為遺傳的新個體，并將其復制若干份，以保持新個體的規模不變。為提高運算速度，在復制新個體時，可以同步加入個體的交叉和變異策略。由于編碼方案是不重復的自然數編碼，個體之間進行基因交叉，很容易導致兩個個體的基因都出現重復的數字，變成非法編碼，因此本文不采用交叉策略，著重設計了三種變異策略，分別用于不同的新個體，以提高新個體的多樣性。

第一種變異策略是兩點基因交換（Swap），即隨機產生兩個基因點，將個體中這兩個基因點的值進行交換。第二種變異策略是基因片段翻轉（Flip），即隨機產生兩個基因點，將介于這兩個基因點內的基因片段進行翻轉。第三種變異策略是基因片段滑動（Slide），即循環移位，具體做法是隨機產生兩個基因點，將介于這兩個基因點之內的基因片段作循環移位一次，可以向左移位，也可以向右移位。根據上述遺傳進化策略去具體求解汽配件最優噴涂順序的操作示例如圖2所示。

圖2 遺傳進化策略的操作示例Fig.2 Operation example of genetic evolution strategy

2.4 算法流程

根據遺傳算法的基本流程，結合上述算法設計，汽配件顏色噴涂順序問題的遺傳算法求解流程如圖3所示。

其中，汽配件初始數據主要包括：待噴涂汽配件的類別K、顏色L、組數M，配件之間顏色不允許相鄰的情況C、類別不允許相鄰的情況T，以及由上述數據計算得到待噴涂序列的頂點集V、顏色號P、類別號Q、任意兩個頂點的換色距離矩陣D、顏色相鄰性矩陣R和類別相鄰性矩陣S。

圖3 遺傳算法的流程Fig.3 Flowchart of genetic algorithm

3 仿真實驗與結果分析

3.1 實驗數據準備

為檢驗算法的有效性和實用性，參考一些企業的實驗生產數據，本文將待噴涂的汽配件個數最大設置為293 個，作為一條生產線的一個工作日的生產任務，這些汽配件包括31 個類別，需要噴涂的顏色有10 種，不同類別的汽配件、不同顏色的汽配件分為83組，全部初始實驗數據如表1。

表1 待噴涂汽配件的初始數據Tab.1 Initial data of auto parts to be sprayed

汽配件的顏色約束為：顏色號｛1，2，3，6｝中的任意顏色之后不能接4 或10 號顏色；4 號顏色后面不能接7 或9 號顏色；10 號顏色前面只能是4 號顏色。汽配件的類別約束為：22 號配件不能與｛11，21，23，24，26-31｝中任意一種配件相鄰；23號配件不能與｛11，21，22，24，26-31｝中任意一種配件相鄰。

為更好地檢驗上述TSP 模型及對應遺傳算法對不同規模數據的求解性能，現將上述初始數據進一步分組為較小規模、中等規模和較大規模的三組數據，具體數據如表2。

表2 三種規模的實驗數據Tab.2 Experimental data of three scales

對上述三種規模數據，汽配件個數分別為64、93、293，對應于TSP，即是分別有64、93、293個路徑頂點。由于本文討論的汽配件顏色噴涂問題的目標是使換色次數盡量少，而上述三種規模數據中汽配件的顏色數分別為5、7、10，因此它們的理論最優解分別為5、7、10。

3.2 結果分析

本次實驗硬件環境為AMD A8-45000M CPU/8GB/Win 7系統，編程環境為Matlab R 2018a。對表2 的三種規模數據，按流程圖3編程，在不同算法參數下求解結果如表3。

表3 三種規模數據在不同算法參數下的求解結果Tab.3 Results of solving data with three scales under different algorithm parameters

從表3 中對中等規模和較小規模的求解結果中可以看出，在迭代次數和種群規模適中的情況下最優適應度f分別為7 和5，其中3 個分量都值為f1=10，f2=0，f3=0，即這兩種規模汽配件數的最優噴涂序列換色次數都為顏色總數，違背顏色約束的次數都為0，違背配件類別約束的次數都為0。

同樣的，在迭代次數和種群規模適中的情況下，對較大規模的汽配件初始數據用本文設計的模型和算法進行計算時求解結果得到的最優適應度為f=10，其中3 個分量值為f1=10，f2=0，f3=0，即上述最優噴涂序列的最少換色次數為10次，違背顏色約束的次數為0，違背配件類別約束的次數為0。

從以上結果可以看出，不管數據規模的大小通過本算法的求解都可以得到最優解，充分證明本文的基于TSP 轉化和遺傳算法求解汽配件最優噴涂順序的優化方法是有效的。隨著迭代次數和種群規模的增加，還可以進一步提高算法優化能力，限于篇幅這里不再一一列舉。

圖4 是不同規模實驗數據下選擇第三行數據所做的適應度值隨運行次數的變化曲線。從圖4 中可以看出隨著迭代次數的增加，適應度的值逐漸接近于理論最優解。

圖4 不同規模數據的適應度進化曲線Fig.4 Fitness evolution curve of data with different scales

3.3 算法求解性能分析

表4是3.2節中不同規模數據求解結果的效率對比，其中當較小規模數據設置為表3 的第3 行參數時取得最優解5 的百分比為60%；參數為中等規模第3 行數據時，取得最優解7的百分比為76%；當參數設置為較大規模第3 行數據時取得理論最優解10的百分比為42%。

表4 本文算法對三種規模數據在100次運行下的求解性能Tab.4 Solution performance of the proposed algorithm on data with three scales under 100 runs

從表4 中可以看出，在迭代次數和種群規模適中的情況下，不管大小規模的初始數據在本文設計的優化方法的計算下都可以多次得到理論最優解，并且得到最優解的規模的平均值都已經非常接近最優解，標準差也非常小，表明本文設計的遺傳算法，在種群規模適中的情形下，可以得到非常優質的遺傳進化效果。

圖5 是對應于圖4 的100 次運行的適應度波動曲線，由此圖5 可以看出適應度一直在最優適應度附近波動，表明本算法有較高的概率可以求得精確最優解或非常接近最優解的值。所以，本文所建立的數學模型及設計的遺傳算法是穩定和實用的，對汽配件噴涂順序問題的優化效果顯著。

圖5 100次運行適應度波動曲線Fig.5 Fitness fluctuation curve of 100 runs

本文的數學模型及遺傳算法對更大規模的汽配件噴涂順序問題仍然是有效和實用的，限于篇幅，這里不再論述。

4 結語

本文借鑒TSP 的建模和求解思路，建立了汽配件噴涂順序問題的數學模型，設計了針對性和實用性強的遺傳算法來求解，通過實驗數據的驗證，求解結果完全能滿足實際的生產要求，對企業減少生產成本、提高生產效率具有很好的指導意義。

本文的數學模型及遺傳算法仍然適用于數據規模更大的汽配件噴涂問題，還可以推廣應用于其他企業生產作業調度［16］等問題。但是由于實際生產實踐中汽配件噴涂問題的復雜性，本文的方法還有不足之處，有待今后繼續進行研究完善。如果綜合考慮到大規模汽配件噴涂時放置汽配件的支架數目對汽配件噴涂順序的影響，如果動態調度配件種類顏色以及汽配件數目，建立的模型將更加有實際意義。