基于時間因子的蟻群算法在觀光車路徑規劃中的應用

吳曉軍 曾培耘 鄧 林

（1.內江市特種設備檢驗所 內江 641000）

（2.四川省特種設備檢驗研究院 成都 610199）

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

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

觀光車作為特種設備，常用于景區中運輸游客。某景區通過觀光車運送旅客至景區內的各個景點，并根據實際需要停留一定時間。與傳統的TSP 問題不同，其存在以下差異：

1）起始點是固定的，在蟻群初始化時均在起始點生成。

2）觀光車到達各節點時，存在停留時間。

3）求解的并非是最短路徑，而是遍歷整個節點所需的最短時間。

傳統的蟻群算法并未對節點的停留時間進行考慮，在計算時是否考慮停留時間將對結果產生巨大影響。本文采用了一種基于時間因子的改進蟻群算法，通過與傳統蟻群算法進行比較，在考慮遍歷節點時存在停留時間的情況下，取得了較好的結果。

1 問題背景

某景區采用觀光車運送旅客，N個景點之間路線為完全圖，觀光車從景區1 號景點出發，可自行選擇行駛至任意下一個景點，最終遍歷完景區內的每一個景點。根據景點的不同情況，觀光車在每個景點需停留不同的時間，問題為：求解觀光車的行進路線（路徑），使得在遍歷完整個景點的情況下所用的時間最短。

2 模型建立

設景區內景點的集合為N，在不考慮各節點的停留時間時，求解上述關于路徑距離的最小值，用式（1）表示：

其中，di，j表示第i個節點到第j個節點的距離，arrivedi，j表示i、j之間的距離，各節點之間的距離矩陣用式（2）表示：

顯然，當i=j時，di，j=0，則上述距離矩陣可轉化為式（3）：

進一步，在考慮觀光車在各節點的停留時間時，將各節點的停留時間表示為時間因子，見式（4）：

其中，ti表示各節點應停留時間。基于各節點的時間因子，對距離矩陣式（3）中元素采用式（5）進行處理：

其中，v代表車輛行駛速度，上述式（3）轉化為式（6）所示的形式：

根據式（3）～式（6），上述式（1）最終轉化為求解tmin的方程，見式（7）：

其中，tmin表示觀光車在遍歷完全部景點后所用的最短時間。

3 算法步驟與實現

3.1 算法步驟

1）對螞蟻種群進行初始化，使生成的螞蟻全部位于起始點（1 號節點），啟動遍歷程序。

2）生成已訪問節點表、待訪問節點表（allow），某時刻螞蟻向下一個節點轉移的期望用啟發函數ηi，j表示，路徑上的信息素濃度用τ表示，啟發函數用式（8）表示：

某時刻t，螞蟻從i節點轉移到j節點的轉移概率pi，j（t)用式（9）表示：

式中：

α，β——啟發因子系數；

τi，j（t)——t時刻位于節點i、節點j之間的路徑上信息素濃度；

τi，s（t)——t時刻位于節點i至目標點s的信息素濃度；

ηi，s（t)——螞蟻在t時刻位于節點i、目標點s之間的轉移期望程度；

ηi，j（t)——螞蟻在t時刻位于節點i、節點j之間的轉移期望程度。

3）采用輪盤賭方式，選擇轉移概率最大的節點作為下一個即將訪問的節點，隨即對已訪問節點表（allow）進行更新。

4）螞蟻遍歷完成所有節點后，取出路徑表，并在每次迭代完成后計算出最短時間及路徑表。

上述過程如圖1 所示。

3.2 算法實現

由于算法中大多采用矩陣記錄相關信息，針對該特點本算法采用Matlab 編程實現，關鍵步驟如下：

1）載入各節點間距離矩陣（distance）。

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

3）參數定義及賦值見表1。

表1 參數定義表

4）初始節點設置為1 號節點，將蟻群初始化后定位初始生成位置為該節點。將該位置放入節點路徑記錄表并建立節點索引。

5）逐個螞蟻、逐個節點進行以下循環：

記錄已訪問節點列表（禁忌表）→生成待訪問節點列表→用式（9）計算下一個節點的轉移概率→采用輪盤賭方法選擇下一個即將訪問的節點。

6）上述循環完成后，取出每個螞蟻的路徑并計算路徑用時與路徑平均用時，同時更新信息素，進行下一次迭代。

7）迭代完成后，取出各代最佳路徑用時與各代路徑平均用時，計算結束。

4 結果分析

以某景區實際問題為例，景區內停站景點（節點）為31 個，每個景點的停車時間見表2，各景點位置坐標化后如圖2 所示。

表2 節點時間因子賦值表

圖2 各景點位置坐標圖

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

表3 計算結果統計表

圖3 不同種群及迭代次數時平均用時與最短用時圖（續）

圖3 不同種群及迭代次數時平均用時與最短用時圖

圖4 不同種群及迭代次數時產生的最優路徑圖

由上述結果可見，采用隨機遍歷的方式通過所有節點，其平均用時約為4.6 ～4.7 h。采用基于時間因子的蟻群算法最短用時為3.5 ～4.0 h，最大程度節約時間達24.5%。同時，初始蟻群總量對結果的影響較大，但初始蟻群總量確定后，迭代次數較少即可達到收斂，體現了算法的優越性。

5 結束語

本文采用一種改進的蟻群算法對景區內觀光車運行路徑規劃問題進行了研究，通過引入一種特定的時間因子，改進了原始距離矩陣表。通過增加種群數量及迭代次數，計算結果改善較為明顯，改進的算法能更好地適應特定條件下增加的路徑規劃需求。