吳曉軍 曾培耘 鄧 林

（1.內(nèi)江市特種設(shè)備檢驗(yàn)所 內(nèi)江 641000）

（2.四川省特種設(shè)備檢驗(yàn)研究院 成都 610199）

對(duì)于坐標(biāo)確定的初始點(diǎn)，求解在特定條件下的最優(yōu)路徑問(wèn)題被稱為旅行商問(wèn)題（Travelling Salesman Problem， 簡(jiǎn)稱TSP）。采用窮舉法解決TSP 問(wèn)題，其時(shí)間復(fù)雜度為O（n!)。例如：在初始點(diǎn)為11 個(gè)時(shí)，路徑遍歷的次數(shù)為362 880 次；初始點(diǎn)為50 個(gè)時(shí)，路徑遍歷的次數(shù)則快速增加到3.04×1064次。隨著初始點(diǎn)的增加，窮舉法在工程實(shí)踐中由于耗時(shí)巨大已不具備實(shí)際意義。為解決實(shí)踐中的TSP 問(wèn)題，常采用一種稱為蟻群算法（Ant Colony Optimization，簡(jiǎn)稱ACO）的啟發(fā)式算法。其原理如下：?jiǎn)沃晃浵佋谛袆?dòng)過(guò)程中會(huì)在移動(dòng)路徑上留下一種化學(xué)“信息素”，在相同路徑上經(jīng)過(guò)的螞蟻越多，信息素的濃度則越高。螞蟻會(huì)傾向于向信息素濃度更高的路徑移動(dòng)，隨著螞蟻數(shù)量的增加，就使得短路徑上的信息素濃度不斷升高，長(zhǎng)路徑上的信息素濃度則增加緩慢甚至不再增加。同時(shí)，信息素濃度最高的路線成了最佳路線。通過(guò)使用計(jì)算機(jī)模擬蟻群行為，利用信息素的正反饋原理，能更好地求解路徑規(guī)劃問(wèn)題。

崔瀛[1]等人研究了在物流配送中采用蟻群算法的一種數(shù)學(xué)模型；田勁松[2]使用蟻群算法設(shè)計(jì)了一種測(cè)量控制網(wǎng)TSP 問(wèn)題的求解方法并得出了計(jì)算結(jié)果；王玉富[3]提出了一種多配送中心的蟻群算法模型，并使用K均值聚類算法進(jìn)行了研究；陳世歡[4]等人通過(guò)蟻群算法對(duì)航班路徑規(guī)劃進(jìn)行了研究；李霄玉[5]等人提出了一種在NSGA-Ⅱ基礎(chǔ)上加入局部搜索策略的自適應(yīng)算法。

觀光車(chē)作為特種設(shè)備，常用于景區(qū)中運(yùn)輸游客。某景區(qū)通過(guò)觀光車(chē)運(yùn)送旅客至景區(qū)內(nèi)的各個(gè)景點(diǎn)，并根據(jù)實(shí)際需要停留一定時(shí)間。與傳統(tǒng)的TSP 問(wèn)題不同，其存在以下差異：

1）起始點(diǎn)是固定的，在蟻群初始化時(shí)均在起始點(diǎn)生成。

2）觀光車(chē)到達(dá)各節(jié)點(diǎn)時(shí)，存在停留時(shí)間。

3）求解的并非是最短路徑，而是遍歷整個(gè)節(jié)點(diǎn)所需的最短時(shí)間。

傳統(tǒng)的蟻群算法并未對(duì)節(jié)點(diǎn)的停留時(shí)間進(jìn)行考慮，在計(jì)算時(shí)是否考慮停留時(shí)間將對(duì)結(jié)果產(chǎn)生巨大影響。本文采用了一種基于時(shí)間因子的改進(jìn)蟻群算法，通過(guò)與傳統(tǒng)蟻群算法進(jìn)行比較，在考慮遍歷節(jié)點(diǎn)時(shí)存在停留時(shí)間的情況下，取得了較好的結(jié)果。

1 問(wèn)題背景

某景區(qū)采用觀光車(chē)運(yùn)送旅客，N個(gè)景點(diǎn)之間路線為完全圖，觀光車(chē)從景區(qū)1 號(hào)景點(diǎn)出發(fā)，可自行選擇行駛至任意下一個(gè)景點(diǎn)，最終遍歷完景區(qū)內(nèi)的每一個(gè)景點(diǎn)。根據(jù)景點(diǎn)的不同情況，觀光車(chē)在每個(gè)景點(diǎn)需停留不同的時(shí)間，問(wèn)題為：求解觀光車(chē)的行進(jìn)路線（路徑），使得在遍歷完整個(gè)景點(diǎn)的情況下所用的時(shí)間最短。

2 模型建立

設(shè)景區(qū)內(nèi)景點(diǎn)的集合為N，在不考慮各節(jié)點(diǎn)的停留時(shí)間時(shí)，求解上述關(guān)于路徑距離的最小值，用式（1）表示：

其中，di，j表示第i個(gè)節(jié)點(diǎn)到第j個(gè)節(jié)點(diǎn)的距離，arrivedi，j表示i、j之間的距離，各節(jié)點(diǎn)之間的距離矩陣用式（2）表示：

顯然，當(dāng)i=j時(shí)，di，j=0，則上述距離矩陣可轉(zhuǎn)化為式（3）：

進(jìn)一步，在考慮觀光車(chē)在各節(jié)點(diǎn)的停留時(shí)間時(shí)，將各節(jié)點(diǎn)的停留時(shí)間表示為時(shí)間因子，見(jiàn)式（4）：

其中，ti表示各節(jié)點(diǎn)應(yīng)停留時(shí)間?；诟鞴?jié)點(diǎn)的時(shí)間因子，對(duì)距離矩陣式（3）中元素采用式（5）進(jìn)行處理：

其中，v代表車(chē)輛行駛速度，上述式（3）轉(zhuǎn)化為式（6）所示的形式：

根據(jù)式（3）～式（6），上述式（1）最終轉(zhuǎn)化為求解tmin的方程，見(jiàn)式（7）：

其中，tmin表示觀光車(chē)在遍歷完全部景點(diǎn)后所用的最短時(shí)間。

3 算法步驟與實(shí)現(xiàn)

3.1 算法步驟

1）對(duì)螞蟻種群進(jìn)行初始化，使生成的螞蟻全部位于起始點(diǎn)（1 號(hào)節(jié)點(diǎn)），啟動(dòng)遍歷程序。

2）生成已訪問(wèn)節(jié)點(diǎn)表、待訪問(wèn)節(jié)點(diǎn)表（allow），某時(shí)刻螞蟻向下一個(gè)節(jié)點(diǎn)轉(zhuǎn)移的期望用啟發(fā)函數(shù)ηi，j表示，路徑上的信息素濃度用τ表示，啟發(fā)函數(shù)用式（8）表示：

某時(shí)刻t，螞蟻從i節(jié)點(diǎn)轉(zhuǎn)移到j(luò)節(jié)點(diǎn)的轉(zhuǎn)移概率pi，j（t)用式（9）表示：

式中：

α，β——啟發(fā)因子系數(shù)；

τi，j（t)——t時(shí)刻位于節(jié)點(diǎn)i、節(jié)點(diǎn)j之間的路徑上信息素濃度；

τi，s（t)——t時(shí)刻位于節(jié)點(diǎn)i至目標(biāo)點(diǎn)s的信息素濃度；

ηi，s（t)——螞蟻在t時(shí)刻位于節(jié)點(diǎn)i、目標(biāo)點(diǎn)s之間的轉(zhuǎn)移期望程度；

ηi，j（t)——螞蟻在t時(shí)刻位于節(jié)點(diǎn)i、節(jié)點(diǎn)j之間的轉(zhuǎn)移期望程度。

3）采用輪盤(pán)賭方式，選擇轉(zhuǎn)移概率最大的節(jié)點(diǎn)作為下一個(gè)即將訪問(wèn)的節(jié)點(diǎn)，隨即對(duì)已訪問(wèn)節(jié)點(diǎn)表（allow）進(jìn)行更新。

4）螞蟻遍歷完成所有節(jié)點(diǎn)后，取出路徑表，并在每次迭代完成后計(jì)算出最短時(shí)間及路徑表。

上述過(guò)程如圖1 所示。

3.2 算法實(shí)現(xiàn)

由于算法中大多采用矩陣記錄相關(guān)信息，針對(duì)該特點(diǎn)本算法采用Matlab 編程實(shí)現(xiàn)，關(guān)鍵步驟如下：

1）載入各節(jié)點(diǎn)間距離矩陣（distance）。

2）根據(jù)時(shí)間因子矩陣：times=（t1t2···tN)及式（5）生成距離矩陣（Distance）。

3）參數(shù)定義及賦值見(jiàn)表1。

表1 參數(shù)定義表

4）初始節(jié)點(diǎn)設(shè)置為1 號(hào)節(jié)點(diǎn)，將蟻群初始化后定位初始生成位置為該節(jié)點(diǎn)。將該位置放入節(jié)點(diǎn)路徑記錄表并建立節(jié)點(diǎn)索引。

5）逐個(gè)螞蟻、逐個(gè)節(jié)點(diǎn)進(jìn)行以下循環(huán)：

記錄已訪問(wèn)節(jié)點(diǎn)列表（禁忌表）→生成待訪問(wèn)節(jié)點(diǎn)列表→用式（9）計(jì)算下一個(gè)節(jié)點(diǎn)的轉(zhuǎn)移概率→采用輪盤(pán)賭方法選擇下一個(gè)即將訪問(wèn)的節(jié)點(diǎn)。

6）上述循環(huán)完成后，取出每個(gè)螞蟻的路徑并計(jì)算路徑用時(shí)與路徑平均用時(shí)，同時(shí)更新信息素，進(jìn)行下一次迭代。

7）迭代完成后，取出各代最佳路徑用時(shí)與各代路徑平均用時(shí)，計(jì)算結(jié)束。

4 結(jié)果分析

以某景區(qū)實(shí)際問(wèn)題為例，景區(qū)內(nèi)停站景點(diǎn)（節(jié)點(diǎn)）為31 個(gè)，每個(gè)景點(diǎn)的停車(chē)時(shí)間見(jiàn)表2，各景點(diǎn)位置坐標(biāo)化后如圖2 所示。

表2 節(jié)點(diǎn)時(shí)間因子賦值表

圖2 各景點(diǎn)位置坐標(biāo)圖

種群初始化時(shí)，對(duì)蟻群的數(shù)量依次賦值為50、500、5 000 個(gè)，并分別迭代10、100、1 000 次，通過(guò)引入時(shí)間因子參與計(jì)算，求得最短遍歷時(shí)間及路徑，見(jiàn)表3。迭代至最短路徑（時(shí)間）時(shí)，迭代次數(shù)與用時(shí)（最短用時(shí)、平均用時(shí)）關(guān)系如圖3 所示。迭代至最短路徑（時(shí)間）時(shí)，路徑表如圖4 所示。

表3 計(jì)算結(jié)果統(tǒng)計(jì)表

圖3 不同種群及迭代次數(shù)時(shí)平均用時(shí)與最短用時(shí)圖（續(xù)）

圖3 不同種群及迭代次數(shù)時(shí)平均用時(shí)與最短用時(shí)圖

圖4 不同種群及迭代次數(shù)時(shí)產(chǎn)生的最優(yōu)路徑圖

由上述結(jié)果可見(jiàn)，采用隨機(jī)遍歷的方式通過(guò)所有節(jié)點(diǎn)，其平均用時(shí)約為4.6 ～4.7 h。采用基于時(shí)間因子的蟻群算法最短用時(shí)為3.5 ～4.0 h，最大程度節(jié)約時(shí)間達(dá)24.5%。同時(shí)，初始蟻群總量對(duì)結(jié)果的影響較大，但初始蟻群總量確定后，迭代次數(shù)較少即可達(dá)到收斂，體現(xiàn)了算法的優(yōu)越性。

5 結(jié)束語(yǔ)

本文采用一種改進(jìn)的蟻群算法對(duì)景區(qū)內(nèi)觀光車(chē)運(yùn)行路徑規(guī)劃問(wèn)題進(jìn)行了研究，通過(guò)引入一種特定的時(shí)間因子，改進(jìn)了原始距離矩陣表。通過(guò)增加種群數(shù)量及迭代次數(shù)，計(jì)算結(jié)果改善較為明顯，改進(jìn)的算法能更好地適應(yīng)特定條件下增加的路徑規(guī)劃需求。