求解TSP問題的Flexsim仿真方法研究

（湖北汽車工業(yè)學(xué)院 經(jīng)濟管理學(xué)院，湖北 十堰 442002）

求解TSP問題的Flexsim仿真方法研究

張偉豐

（湖北汽車工業(yè)學(xué)院 經(jīng)濟管理學(xué)院，湖北 十堰 442002）

TSP問題是一類典型的組合優(yōu)化問題，一般智能優(yōu)化算法存在求解難度大、陷入局部解的問題。針對這些問題，提出了用Flexsim仿真軟件求解此問題的方法，以旅行路線總距離最短為優(yōu)化目標，建立了Flexsim仿真模型，并進行仿真運算，確定了最優(yōu)旅行方案。通過對仿真結(jié)果進行分析，證明了此方法的有效性，較好地解決了旅行路徑規(guī)劃問題。

TSP；路徑優(yōu)化；仿真；Flexsim

旅行商問題（Traveling Salesman Problem，TSP）是典型的NP難題：一個旅行者由起點出發(fā)，訪問n個城市，每個城市必須訪問且只能訪問一次，求解的目標是找出一條長度最短的路徑。TSP問題應(yīng)用廣泛，很多現(xiàn)實問題都可抽象為該問題的求解，如車輛調(diào)度、機器人控制、路由器布設(shè)等，因此探索其優(yōu)化方法具有重要的現(xiàn)實意義。目前很多群集智能優(yōu)化算法被應(yīng)用于TSP問題的求解，如模擬退火算法、遺傳算法、粒子群算法、蟻群算法等［1］，在一定程度上能找到最優(yōu)或接近最優(yōu)路徑，但仍然存在陷入局部最優(yōu)解和收斂速度慢的問題。在實際應(yīng)用中，這些方法的求解過程比較復(fù)雜，參數(shù)設(shè)置不當(dāng)時求解結(jié)果的可信度往往不高，限制了其在實際中的應(yīng)用。文中應(yīng)用Flexsim仿真軟件對TSP問題進行建模與仿真，并通過計算對比分析找出最優(yōu)的路徑組合。使用Flexsim仿真軟件能快速建模并仿真，得出各類統(tǒng)計數(shù)據(jù)，在解決此類問題上更加方便快捷，相比其他方法更具實用性。

1 TSP問題數(shù)學(xué)模型

TSP問題數(shù)學(xué)描述如下：令G=(V,E)為賦權(quán)圖，V={1,2,…,n}為頂點集，E為邊集，各頂點間距離為dij，且(dij＞0，i,j∈V)，設(shè)

則數(shù)學(xué)模型表述為

式中：K是V的全部非空子集；|K|為頂點個數(shù)；式（2）為目標函數(shù)；式（3）～（4）表示經(jīng)過每個頂點且只經(jīng)過一次；式（5）保證沒有子回路解的產(chǎn)生。

2 建立求解TSP問題仿真模型

2.1 構(gòu)建Flexsim仿真模型思路

Flexsim軟件是基于OpenGL技術(shù)開發(fā)的，有良好的三維效果，實現(xiàn)了建模仿真的可視化，數(shù)據(jù)信息可以方便地用軟件中的模型庫表示出來。求解TSP問題時，節(jié)點(城市)數(shù)量及距離等參數(shù)確定后，通過選擇合適的實體，設(shè)置合理的參數(shù)，可構(gòu)建符合需要的仿真模型，行走路線由隨機數(shù)控制，在不同參數(shù)條件下對仿真模型反復(fù)運行，并對仿真結(jié)果進行對比分析和計算，即得到近似最優(yōu)解與最短行走路徑方案。

在建立求解TSP問題仿真模型中，根據(jù)需要解決的問題和期望達到的要求，采用如下方式建模：用暫存區(qū)來模擬城市節(jié)點，每個暫存區(qū)表示一個城市；用作為臨時實體的任務(wù)執(zhí)行器來模擬旅行者，旅行者由一個發(fā)生器產(chǎn)生；用吸收器來吸收作為臨時實體的旅行者，進入吸收器后，代表旅行者走完了所有的城市和一個仿真過程的結(jié)束。在仿真模型中，通過設(shè)置臨時實體流的發(fā)送端口來控制旅行者的行走路線，由于每次仿真運行產(chǎn)生的隨機數(shù)不同，每次的行走路線也不同，在仿真中記錄每次的行走路線和距離，經(jīng)過若干次仿真后，對仿真結(jié)果進行對比分析，找出路徑最短的路線作為TSP問題的近似最優(yōu)解。

2.2 仿真模型建立步驟

1）構(gòu)建模型布局 根據(jù)旅行者所經(jīng)過的城市，以及城市間的距離，分析各種狀態(tài)變量與參數(shù)的邏輯關(guān)系，建立求解TSP問題仿真的模型布局。

2）定義模型運行流程 根據(jù)Flexsim對象實體間的邏輯層次關(guān)系，連接輸入輸出端口，定義運行流程，實現(xiàn)仿真的目的。

3）編輯實體參數(shù) 以所構(gòu)建模型想要達到的仿真模擬目標，對實體對象進行參數(shù)編輯，設(shè)定各實體的標簽值，以完成系統(tǒng)的仿真。

4）運行仿真 模型實體對象的連線完成后，編輯各實體模型運作參數(shù)，根據(jù)邏輯關(guān)系編寫程序，進行仿真運行，直觀的觀察模型的運行情況。

5）分析仿真結(jié)果 通過對仿真模型的運行，可以得到各類的圖表及統(tǒng)計數(shù)據(jù)，分析仿真運行結(jié)果，對仿真數(shù)據(jù)進行對比，確定最優(yōu)解。

3 應(yīng)用示例仿真與分析

3.1 模型案例

為考察仿真模型的有效性，以一個應(yīng)用示例進行了模擬，用Flexsim軟件建立仿真模型，確定一條行走路徑，在經(jīng)過所有城市且只經(jīng)過一次的情況下使得行走距離最短。模型案例采用一個典型的TSP問題，即10個城市問題。

3.2 仿真模型建立

首先構(gòu)建仿真模型的布局和連線，以暫存區(qū)表示節(jié)點城市，節(jié)點之間采用a連接，連接方式如下：發(fā)生器與10個城市(暫存區(qū))進行a連接，10個暫存區(qū)再與吸收器進行a連接，每個暫存區(qū)再與其他9個暫存區(qū)a連接，連接好之后，每個暫存區(qū)有10個輸入端口和10個輸出端口，模型布局和實體間連線如圖1所示。

模型需要達到的效果描述如下：首先由發(fā)生器產(chǎn)生一個臨時實體，代表旅行者，隨機到達某一個暫存區(qū)后，通過設(shè)置輸出端口，控制下一站到某個暫存區(qū)，具體到哪個暫存區(qū)由程序控制，要求下一站隨機選擇并且不與之前到過的暫存區(qū)重復(fù)，在此過程中記錄走過的暫存區(qū)并計算走過的距離，這些數(shù)據(jù)保存在全局表中，當(dāng)旅行者經(jīng)過最后一個節(jié)點后，進入吸收器被吸收，完成一次旅行過程的模擬。經(jīng)過若干次仿真運行后，在全局表中選擇一條路徑最短的行走路線，作為TSP問題近似最優(yōu)解。為了實現(xiàn)模型要達到的效果，需要進行各個實體對象的參數(shù)設(shè)置、標簽設(shè)置、程序設(shè)計和結(jié)果輸出等。

圖1 仿真模型布局圖

3.2.1 發(fā)生器、暫存區(qū)參數(shù)設(shè)置

發(fā)生器的主要作用是產(chǎn)生臨時實體，為了比較真實地模擬旅行者行走過程，臨時實體種類選擇“任務(wù)執(zhí)行類臨時實體”，到達方式選擇“到達時間間隔exponential（0，100，0）”，勾選“使用運輸工具”并選擇“任務(wù)執(zhí)行器作為臨時實體”，這樣仿真運行時能顯示臨時實體行走過程，10個暫存區(qū)的“臨時實體流”頁面設(shè)置同上。

3.2.2 實體對象標簽設(shè)置

為了完成仿真過程，很多變量需要借助標簽值來設(shè)定，在后面的程序設(shè)計中用來完成計數(shù)、標記、計算等功能，上述標簽均為數(shù)值型標簽，各實體對象主要設(shè)定的標簽以及所起的作用如表1所示。

表1 各實體對象標簽及其作用

3.2.3 全局表建立

在模型建立和仿真運行中需要用到2個全局表，分別用來存儲城市距離的原始數(shù)據(jù)和仿真結(jié)果的數(shù)據(jù)。在Flexsim中建2張表，名稱分別為“gt1”和“gt2”?！癵t1”如圖2所示，根據(jù)城市編號組成的行和列即可讀取出兩城市間的距離；“gt2”用來存儲仿真中旅行者走過的路徑和走過的總距離，共11列，前10列存儲依次走過的城市編號，最后一列存儲總距離，表的行數(shù)由程序動態(tài)設(shè)定，即產(chǎn)生多少個臨時實體就設(shè)定多少行，每一行記錄的是每個臨時實體走過的路徑和距離。

圖2 存儲城市數(shù)據(jù)的全局表

3.2.4 程序設(shè)計

上述步驟完成后，通過編程來確定每個實體的發(fā)送端口、計算行走距離等。

發(fā)生器產(chǎn)生臨時實體后，需要確定發(fā)送端口。由于與10個城市相連，在“發(fā)送至端口”中，由隨機數(shù)確定一個發(fā)送端口：return duniform(1,10)；在發(fā)生器中還需要完成臨時實體的計數(shù)，并將計數(shù)值寫入臨時實體標簽值中，同時設(shè)定全局表“gt2”的行數(shù)，上述操作在“離開觸發(fā)”中進行；當(dāng)再次運行仿真模型時，需要重置，將臨時實體計數(shù)的標簽值清零，并且將全局表“gt2”的行數(shù)設(shè)定為0，以便重新開始仿真，完成上述操作在“重置觸發(fā)”中進行。

臨時實體進入暫存區(qū)后要完成行走距離的計算，記錄經(jīng)過的城市，確定臨時實體輸出端口。

1）計算當(dāng)前臨時實體行走距離、記錄行走路徑 這一步在暫存區(qū)的“進入觸發(fā)”里實現(xiàn)，首先獲取臨時實體各項標簽值，主要標簽變量見表3的臨時實體對象，初始值均為0，判斷城市計數(shù)標簽值，如果為0，代表臨時實體從發(fā)生器過來，為初次進入暫存區(qū)，不計算走過的距離，將城市計數(shù)加1并寫入臨時實體對應(yīng)標簽值中，在全局表中根據(jù)臨時實體計數(shù)標簽值和城市計數(shù)標簽值確定對應(yīng)的行和列，將獲取的當(dāng)前暫存區(qū)“city”值，即當(dāng)前走過的城市寫入全局表中，然后將暫存區(qū)“city”值寫入臨時實體標簽“pecity”中，用于在下一站判斷上一站所經(jīng)過的城市。如果城市計數(shù)標簽值大于0，則要計算走過的距離，其他操作同上，距離計算過程為：根據(jù)臨時實體標簽“pecity”和當(dāng)前暫存區(qū)標簽“city”，即根據(jù)上個城市和當(dāng)前城市組成的行和列查詢?nèi)直怼癵t1”，獲取2個城市間的距離，累加到臨時實體標簽“mydistan”中，并將計算后的值寫入標簽中用于下一站累加計算，當(dāng)走完所有城市后，即可得到走過的總距離。暫存區(qū)“進入觸發(fā)”算法流程描述如下：

2）確定臨時實體輸出端口 在暫存區(qū)的“臨時實體流”屬性頁面中設(shè)置“發(fā)送至端口”來實現(xiàn)，當(dāng)臨時實體經(jīng)過當(dāng)前暫存區(qū)后，要控制其進入下一個暫存區(qū)，在此過程中，要求臨時實體隨機選擇下一個暫存區(qū)，并且不與之前經(jīng)過的暫存區(qū)重復(fù)，具體過程為：首先獲取臨時實體的城市計數(shù)標簽“sumci?ty”的值并進行判斷，如果值為10，說明已經(jīng)走過了所有的城市，下一步直接進入吸收器，否則，隨機確定下一個輸出端口，將與當(dāng)前暫存區(qū)輸出端口連接的其他暫存區(qū)標簽值“city”與已經(jīng)存入全局表的城市標簽值比較，如果未存入全局表，則表示未經(jīng)過此城市，存入數(shù)組中，隨機產(chǎn)生數(shù)組長度內(nèi)的隨機數(shù)作為數(shù)組序號，讀取數(shù)組里對應(yīng)的值作為下一個要到達的城市，遍歷輸出端口對應(yīng)的城市標簽值，獲得輸出端口值并返回。暫存區(qū)“發(fā)送至端口”算法流程描述如下：

3.3 仿真實驗結(jié)果及其分析

仿真實例選取自TSPlib測試庫，仿真實驗環(huán)境為Flexsim7.5中文版仿真軟件，模型建立完成以及參數(shù)設(shè)置好之后，對仿真模型運行以獲取仿真結(jié)果，臨時實體行走路線完全由暫存區(qū)的輸出端口確定，而輸出端口都由隨機數(shù)確定，產(chǎn)生的隨機數(shù)不同，則行走路線和行走的總距離就不一樣，仿真的目的就是要找出一條行走距離最短的路線，仿真模型運行時不斷地產(chǎn)生臨時實體，每個臨時實體走完全部城市進入吸收器后即完成一次旅行，記錄每次旅行的計算結(jié)果，通過對計算結(jié)果的比較來找出距離最短的行走路線以及走過的距離。

1）獲取行走路徑信息及最短路徑 建立全局表“gt3”，存儲路徑最短臨時實體經(jīng)過的城市以及總距離信息，1行11列，臨時實體經(jīng)過所有的暫存區(qū)后，進入吸收器，在吸收器“進入觸發(fā)”中完成如下操作，從臨時實體標簽值中獲取行走總距離信息寫入吸收器“mydistan”標簽，并寫入全局表對應(yīng)行的最后一列中。另外還需要記錄仿真過程中最短路徑，如果是第一個臨時實體進入吸收器，將當(dāng)前路徑總距離寫入“mindistan”，否則比較兩者大小，如果小于之前記錄的最短路徑，則將當(dāng)前路徑總距離寫入“mindistan”標簽，并將經(jīng)過的路徑和總距離寫入全局表“gt3”，算法流程描述如下：

2）圖表數(shù)據(jù)輸出 在仿真中需要以曲線圖實時顯示每個臨時實體走過總距離的情況，用Flex?sim自帶的繪圖功能實現(xiàn)，在屬性設(shè)置中，選擇統(tǒng)計的實體為吸收器，統(tǒng)計的變量為吸收器標簽“mydistan”，再設(shè)置曲線顏色，橫坐標縱坐標等參數(shù)，在仿真中即可顯示行走總距離的曲線，最短路徑搜索曲線，以查看最短路徑搜索情況。

3）運行仿真模型及獲取仿真結(jié)果 所有程序、參數(shù)調(diào)試完成后可仿真運行，為盡可能搜尋到最優(yōu)解，仿真終止時間設(shè)置為2 000 s，運行結(jié)果存儲在全局表中，顯示每次行走的路徑及總距離，曲線在仿真過程中實時顯示，仿真結(jié)果及圖像如圖3～4所示。從圖4中可以看出：此方法能對所有可行的行走路線進行搜索，只要運行次數(shù)足夠，就能找出最短行走距離。上述顯示的是所有可行的運輸方式，從中選擇總成本最小的一行，即得到TSP問題仿真優(yōu)化的結(jié)果，并解讀出對應(yīng)的行走路徑和最短距離。對于本仿真實例，經(jīng)過反復(fù)多次運行，確定的最短距離行走路徑如圖5所示，即總距離最小的行走方案為“深圳（4）-北京（1）-天津（2）-西安（8）-杭州（7）-南昌（10）-長沙（5）-武漢（3）-成都（6）-拉薩（9）”，最短距離為10 384 km。

圖3 總距離曲線

圖4 最短距離變化圖像

圖5 最短距離及路徑信息

為檢驗此方法求解復(fù)雜TSP問題的效果，從TSPLIB 測試庫中選取了 pr136、kroB100、pr144、kroB150、CHC144等規(guī)模比較大的幾個TSP問題進行了測試，按照上述過程用Flexsim仿真軟件進行建模，參數(shù)設(shè)置，運行并得到仿真結(jié)果，與文獻記錄的最優(yōu)解進行對比，測試結(jié)果如表2所示。從表2的對比結(jié)果可以看出：該仿真方法求解復(fù)雜TSP問題所求最短路徑基本在文獻記錄的最優(yōu)值附近，反映了文中方法求解TSP問題是有效的。

為更好地說明其有效性，將此方法和一些智能計算方法的求解過程和結(jié)果進行了比較。由于在Flexsim中可以任意調(diào)整仿真模型運行速度，不能以運行時間作為比較依據(jù)，為客觀地比較幾種算法的性能，選取平均迭代次數(shù)、求解到最優(yōu)值的最少迭代次數(shù)和求解平均值進行性能比較。與模擬退火算法（SA）以及文獻提出的SFCPGA［2］、SECPSO［4］、GFOA［5］算法對比結(jié)果如表3所示。從表3可以看出：在迭代次數(shù)較少的情況下，F(xiàn)lexsim仿真算法的性能優(yōu)于或接近所列出的對比算法，從而進一步驗證了算法的有效性。

表2 文中方法對復(fù)雜TSP問題的求解結(jié)果

表3 文中方法和智能算法的比較

4 結(jié)束語

在分析了TSP問題求解特點的基礎(chǔ)上，用Flexsim軟件進行了建模，解決了參數(shù)設(shè)置、仿真模擬、結(jié)果輸出等環(huán)節(jié)中的問題，通過仿真尋找到了滿足距離最短的路徑，證明了文中方法的可行性和有效性。與其他基于智能計算的優(yōu)化方法相比，此方法建模快速，運行結(jié)果可靠，不會產(chǎn)生如進化計算中交叉變異后的不可行解，避免了復(fù)雜的編程計算以及陷入局部解的問題，實現(xiàn)了優(yōu)化過程的可視化，對典型TSP問題仿真實驗表明了此方法的實用性。文中只針對求解最短路徑及最短距離進行了建模，仿真中路徑隨機產(chǎn)生，基本類似窮舉法，沒有考慮采用啟發(fā)式算子來引導(dǎo)搜索以便更快地找到最優(yōu)解。如何進一步改進該模型，使其用于更復(fù)雜的TSP問題求解，將是下一步工作的研究重點。

［1］殷旅江，何波，楊立君.多類指派約束下汽車總裝裝配線平衡優(yōu)化［J］.制造業(yè)自動化，2014，36（24）：41-44.

［2］許智宏，趙嘉偉，董永峰，等.基于Spark的并行遺傳算法在旅行商問題中的應(yīng)用［J］.計算機應(yīng)用研究，2016，33（8）：45-48.

［3］牟銜臣等.基于遺傳算法航路規(guī)劃TSP問題的研究［J］.系統(tǒng)仿真學(xué)報，2013，25（8）：86-89.

［4］程畢蕓，魯海燕，黃洋，等.求解TSP的自適應(yīng)優(yōu)秀系數(shù)粒子群優(yōu)化算法［J］.計算機應(yīng)用，2017，37（3）：750-754+781.

［5］段艷明，肖輝輝.求解TSP問題的改進果蠅優(yōu)化算法［J］.計算機工程與應(yīng)用，2016，52（6）：144-149.

［6］Yin L,Li X,Gao L,et al.A New Improved Fruit Fly Opti?mization Algorithm for Traveling Salesman Problem［C］//Eighth International Conference on Advanced Computa?tional Intelligence.IEEE,2016:21-28.

［7］孟巧鳳，張林鍹，董杰濤，等.基于Flexsim仿真的裝配線平衡方法研究［J］.計算機仿真，2016，33（6）：176-179.

［8］王聰，張宏立.文化基因算法求解TSP問題的研究［J］.計算機仿真，2015，32（2）：284-287+358.

Research on Flexsim Simulation Method for Solving TSP Problem

Zhang Weifeng
（School of Economics and Management,Hubei University of Automotive Technology,Shiyan 442002,China）

TSP problem is a typical combinatorial optimization problem,the general intelligent optimiza?tion algorithm has the difficulty of solving the problem and it is easy to fall into the local solution.A method with Flexsim simulation software was proposed.Taking the shortest distance as the optimization objective,the Flexsim simulation model was established,and the optimal travel scheme was determined by simulation.The simulation results show that this method is effective and can solve the travel path planning problem better.

TSP;route optimization;simulation;Flexsim

TP301.6

A

1008-5483（2017）04-0075-06

10.3969/j.issn.1008-5483.2017.04.017

2017-05-24

張偉豐（1978-），男，湖北天門人，碩士，從事數(shù)據(jù)挖掘與智能計算方面的研究。E-mail：zhangweifeng7708@163.com