一種關于駕游路線規劃的分布均勻度自適應蟻群算法

宋明杰，吳宇航

(1.華北理工大學 理學院，河北 唐山 063210；2.華北理工大學 教務處，河北 唐山 063210；3.河北省數據科學與應用重點實驗室，河北 唐山 063210)

0 引言

自駕游是當今熱門的出行方式，是以旅行人自行駕駛交通工具，有組織、有計劃的按照既定方案進行旅行[1]，其在旅游目的地的選擇、到達與停留時間以及食宿安排上都有很大的自主性，與傳統的參團方式相比更有獨特魅力。如何合理的規劃旅行路線，在旅行體驗和經濟開支上進行合理平衡，成為廣大自駕游愛好者需要考慮的重要因素[2]，因此如何規劃旅行路線成為了一個現實性的研究課題。

蟻群算法[3]是近年來出現的一種新型的模擬進化算法。它充分利用了蟻群搜索食物的過程與旅行商問題（TSP）[4]之間的相似性。蟻群算法在求解復雜優化問題方面具有很大的優越性，而引入分布均勻度后的自適應蟻群算法在加速收斂和防止早熟停滯現象之間取得很好的平衡，更適合于求解大規模的TSP問題。

蘇州歷史悠久，是國家首批 24個歷史文化名城之一，以其獨特的園林景觀被譽為“中國園林之城”，素有“人間天堂”、“東方威尼斯”、“東方水城”的美譽。蘇州園林是中國私家園的代表，被聯合國教科文組織列為世界文化遺產，是人們最好的旅游勝地之一。本文以蘇州21個景點為例設定自駕游旅游路線。

1 數據獲取及數據預處理

本文選取蘇州為旅游目的地，將 21個蘇州當地景點設為旅游結點。通過查閱相關數據可得到這21個景點的經緯度、票價和逗留時間等相關信息，如表1所示。

表1 蘇州21個當地景點相關信息表Tab.1 Information table of 21 local scenic spots in Suzhou

利用MATLAB軟件根據經緯度與距離之間的關系，求出21個景點兩兩之間的最短距離。考慮到蘇州作為交通發達的一線城市，蘇州內部各景點之間的距離矩陣為對稱矩陣。（給出前十個景點之間的最短距離矩陣）

并根據Google earth繪出21個景點的相應的分布圖，如圖1所示。

圖1 蘇州21個景點相對分布圖Fig.1 Relative distribution of 21 scenic spots in Suzhou

從圖1中可以明顯看出，景點2、3、4、5、6、7、8、9、10、11、12、13、15 比較集中，而景點1、14、16、17、18、19、20、21相對分散。這對自駕游路線的規劃有一定性的指導作用。

2 基于蟻群算法求解最少遍歷路程的模型

2.1 基本蟻群算法

蟻群算法是一種通過模擬自然界螞蟻尋徑的行為的進化算法。螞蟻在尋找路徑時會在路徑上釋放出一種特殊的信息素，當它們碰到一個還沒有走過的路口時，就隨機地挑選一條路徑前行，與此同時釋放出與路線長度有關的信息素，路徑越長，釋放的激素濃度越低，當后來的螞蟻再次碰到這個路口的時候，選擇激素濃度較高路徑概率就會相對較大，這樣形成了一個正反饋。最優路徑上的激素濃度越來越大，而其它的路徑上激素濃度卻會隨著時間的流逝而消減。螞蟻通過個體間的信息交流和相互協作找到最優路線。

2.2 聚度和信息權重

在基本蟻群算法中，加速收斂和防止早熟、停滯現象是一對矛盾。為了加速收斂，Ant-Q Sysetm[5]讓信息量最大的路徑對每次路徑的選擇和信息量的更新起主要的作用。由于強化了最優信息的反饋，會導致早熟、停滯現象。而MAX-MIN 蟻群系統[6]將各個路徑上的信息量的更新限定在固定的范圍內，雖然在一定程度上避免了早熟、停滯現象，但在解的分布較分散時收斂速度較慢。本文提出的基于分布均勻度的自適應蟻群算法根據螞蟻選路的分布均勻情況，動態地調整信息量更新策略和確定每次選擇路徑的概率，這樣，可以在加速收斂和防止早熟、停滯現象之間取得很好的平衡。為此，引入“聚度”的概念來衡量解的均勻程度，從而決定每次選擇路徑的概率以及信息量更新的策略。當所有路徑上螞蟻的分布相對比較分散時，聚度就較小，此時難以強化最優信息，可能導致搜索速度較慢。因此，要強化正反饋信息，應該讓較少的幾個較優的路徑有較大的概率被選取；在信息量更新時，應該僅讓較少的幾個較優的路徑上的信息量得到較大程度的增強。反之，在所有路徑上螞蟻的分布相對比較集中時，聚度就較大，此時易引起早熟、停滯現象。因此，要使解趨于多樣化，應該使較多的路徑有可能被選取，在信息量更新時，應該讓較多路徑上的信息量得以增強。通過這樣動態的自適應調節，可以在有效地改善螞蟻搜索速度的同時避免局部優化。為此，我們在基于分布均勻度的自適應蟻群算法的迭代過程中，根據各條可能的路徑上的聚度來確定下一次迭代中可供螞蟻選擇的路徑的信息權重，并以此來確定它們被選中的概率。

設從城市i共有r條路徑到達另外r個城市i1,i2,…,ir，另設上一次迭代中，經過這r條路徑上的螞蟻數分別為 a1,a2,…,ar，如圖2所示。記：

圖2 源自城市i的各條路徑上螞蟻的分布情況Fig.2 Ant distribution on each path from city i

為城市i的聚度[7]。

在改善螞蟻搜索速度的同時避免局部優化，根據城市i的聚度sta(i)來確定螞蟻在該城市時下一步可供選擇的路徑的條數w，這里取：

設定信息權重[8]來限制信息量和期望程度對螞蟻選擇路徑概率的影響，從而調整各個路徑被選中的概率。按照信息量的大小對以城市 i為起點的路徑進行排序，將序號存于數組rank中，即數組元素rank[ j]的值為路徑(i,j)的序號。由（2）式計算得到的下一步可供選擇的路徑條數為w，取q=w/ r，記：

則ijξ為路徑(i,j)的信息權重。故螞蟻在城市i按選擇城市j的概率為：

利用信息量的均勻度自適應[9][13]地進行信息量的更新，動態地調整各路徑上的信息量的分布，其更新規律為：

Ll(t)為本次迭代中第l只螞蟻遍歷的路徑全長。ψl為第l只螞蟻所對應的解對該路徑上的信息量更新的影響程度。ψl的計算方法如下：設經過路徑(i,j)的螞蟻總數為 k，對它們在本次迭代中遍歷的路徑全長由小到大進行排序，所得序號存放于數組rank1中，即rank1[ l]表示第l只螞蟻對應的序號，則：

3 基于蟻群算法求解最少遍歷路程的模型求解

3.1 蟻群算法操作流程

在本文中，蟻群算法的具體實現步驟為：

Step1：參數初始化

令t=0，設置最大循環次數Ncmax，循環次數 Nc=0 ；

將m只螞蟻置于n個節點上，在每個節點i放置bi(t)只螞蟻；

Step2：迭代過程

①對n個城市進行循環

計算城市 i(1≤i≤n)的聚度，并求出選擇路徑數量w。

②對m只螞蟻進行循環

當下一步城市j可選擇城市數量小于w時，設定閾值0.4r，當w＜0.4r時，取q0=0.8；當w≥0.4r時，取q0=0.2

當下一步城市j可選擇城市數量不小于w時，可根據：

選擇城市j；

若選擇該路徑的螞蟻數量大于螞蟻數量的1/3，終止遍歷。并根據公式：

局部更新路徑(i,j)上的信息量；

終止螞蟻迭代的遍歷后，按照式（5）對所有城市的各條路徑整體更新其信息量。具體算法流程如圖3所示。

圖3 算法流程圖Fig.3 Algorithm flow chart

3.2 模型求解結果及分析

利用MATLAB軟件進行編程，得到模型求解的結果，如圖4所示。

圖4 模型求解結果Fig.4 Model solution results

由上圖可知最短路線為：

20→18→21→19→17→16→14→10→13→15→11→12→8→9→7→6→5→3→4→2→1

全程路線長度為250.9475km，油價費用約為169.3895625元。

查詢相關法律法規[10]可知，蘇州市區限速60 km/h，高速公路限速110 km/h，該路線各相鄰景點之間所需駕車時間均不大于一個小時，暫不計入時程安排。

游歷蘇州上述21個景點大概需要21天，門票價格合計為1107元，油價費用約為169.3895625元，食宿另算。實際上，一次性旅行上述21個景點并不實際，這里只是舉例介紹，自駕游的人們可根據自己喜好和實際假期時間合理規劃自己的行程。

4 結論

本文以蘇州為例，建立基于均勻度的自適應蟻群算法的自駕游設計路線模型，以最短路線為標準，相對應的時間和路程費用最小，食宿根據個人喜好以及經濟能力自行設定。熱衷于自駕游的年輕人可以利用此模型自行設計自己與好友的小長假旅游路線，平時工作忙碌的家庭可在長假時帶著妻子與孩子駕車去放松心情，釋放壓力