基于混合蟻群算法的“多日游”路線優化問題

楊麗馨

（唐山市第十二中學，河北 唐山 063000）

基于混合蟻群算法的“多日游”路線優化問題

楊麗馨

（唐山市第十二中學，河北 唐山 063000）

針對“多日游”路線優化問題，提出了一種新的混合蟻群算法，并建立了“多日游”旅游交通路線的數學模型。通過多次實驗和計算，證明將混合蟻群算法運用于“多日游”旅游交通線路，可以有效求得問題的最優解或近似最優解，并以秦皇島地區各旅游景點為例進行了分析。

“多日游”旅游交通路線；混合蟻群算法；路徑優化

“多日游”旅游交通路線優化問題的研究在旅游研究領域中具有十分重要的理論和現實意義。在旅游企業中，找到一組費用最小、旅游景點最多的旅游路徑，可有效降低成本、提高服務效益并增加總體經濟效益，因此，采取科學合理的方法確定旅游路線是一項非常重要的工作。蟻群算法是一種來自大自然的隨機搜索尋優方法，是生物界的群體啟發行為，現已應用于組合優化、人工智能等多個領域。蟻群算法的正反饋性和協同性使其可用于分布式系統，隱含的并行性使之具有極強的發展潛力。已有文獻[1,2]用蟻群算法對“多日游”路線優化問題進行了研究并取得較好的效果。本文在前人研究的基礎上，將混合蟻群算法用于多日游路線優化問題，以期為旅游企業的決策提供理論指導。

1 混合蟻群算法原理

本文蟻群算法是以TSP（旅行商問題）的蟻群算法為基礎，充分考慮VRP（車輛路徑問題）的具體要求，并在此基礎上對算法的選擇機制、更新機制以及協調機制做進一步改進，引入自適應的轉移策略和信息素更新策略，并融合大洪水算法、節約法等方法，以克服蟻群算法計算時間長、易出現停滯的缺陷[3-5]。

1.1 混合蟻群算法設計

1.1.1 算法基本規則[6-8]

1.1.1.1 轉移規則

借鑒Dorigo的Ant-Q算法思想，采用確定性選擇和隨機性選擇相結合的轉移策略。

1.1.1.2 信息素更新規則[9]

信息素更新采用局部更新和全局更新相結合的策略。

1）局部更新規則

定義1 設經過結點i的螞蟻數為R，經過有向邊(i, j)的螞蟻數為r，則稱r/R為邊(i, j)的螞蟻吸引力。

在進行信息素局部更新時，若每次施放的信息素量Q為常量，則(i, j)的螞蟻吸引力越大，經過邊(i, j)的螞蟻相對其它的邊來說數量越多，從而局部更新的次數就越多，久而久之，會導致邊之間的信息素量差距過大，限制算法搜索的全局性。Q值也會影響算法的搜索效率，Q值過大會使算法易收斂于局部極小值，過小又會影響算法的收斂速度。隨著算法搜索狀態的變化，Q值也應該不斷調整，調整的原則是，邊的吸引力越大，t時刻的信息素量Q(t)越小，不妨設Q(t) = Q(1-r/R)，t為時刻。

假設第k只螞蟻在第nc次迭代周期中的第f次轉移時經過邊(i, j)，在此之前共有Rk只螞蟻經過i點，其中有rk只螞蟻選擇了邊(i, j)，于是得到算法的局部更新規則如下：

2）全局更新規則

在所有螞蟻均構造完路徑后，對所有可行解以及迄今為止最優解的邊進行全局信息素更新。采取的規則如下

p2p當(i, j) ∈L*時，Δ=Q3D( L*)，否則Δτ*ij=0。其中，D( Ap)表示第p個可行解的路徑長度，D(L*)表示迄今為止最優解的路徑長度；ρ2表示更新后信息素的揮發度；Q2、Q3分別表示對應時刻的信息素量；Ap為第p個可行解。

3）負反饋機制

蟻群算法的選擇機制就是使好的路徑以較大的概率選中，而正反饋機制又必然會促使這些路徑在以后的選擇中更具競爭優勢。當搜索陷入局部最優解時，算法無法從局部極小值點跳出來，為此引入負反饋機制，包括：（1）借鑒MIN-MAX的思想，將各個路徑上的信息量限定在某個固定的范圍內，以便在一定程度上減少路徑之間信息素濃度差距；（2）在全局更新時，加入負反饋信息量，即讓Q2Q3<0，以減少該局部解所對應路徑上的信息素量。

1.1.2 可行解問題

在VRP中，每只螞蟻所構造的回路僅是可行解的一個組成部分，各螞蟻所構造的回路可能組成一些可行解，但也可能一個可行解都得不到。如果得不到可行解，則該次迭代除施加了局部信息素影響外對最優解的搜索未有任何影響，若經常出現這種情況，則顯然會浪費大量的計算時間。因此如何有效避免無可行解現象是算法設計的一個關鍵問題。可以采取以下策略：（1）大螞蟻數策略。增加算法的螞蟻數量M，擴大組合范圍，從而增加可行解產生的可能性；（2）螞蟻初始分布均勻策略。在每次迭代前，將螞蟻隨機均勻分布于各個結點，從而增加發現可行解的機會；（3）多周期螞蟻組合策略。在螞蟻數較少情況下，可以將本次迭代中各螞蟻所產生的回路和往次未發現可行解的迭代（一次或多次）所產生的子回路進行組合；（4）近似解可行化策略。在找不到可行解的情況下，選擇一些和可行解接近的非可行解作為問題的近似解，再按照某些規則（如節約法等）將近似解轉變成可行解。當算法不存在可行解時，采取該策略顯然可以保證獲取至少一個可行解。

1.2 混和蟻群算法的步驟

混合蟻群算法求解VRP問題的步驟如下：

（1）初始化各參數，輸入系統基礎數據，設找到的最優解為L*，迭代計數器nc=0；

（2）將M個螞蟻隨機均勻地放到N個結點上，得到結點i的螞蟻集Si和螞蟻數bi，初始化螞蟻k的已走點集tabuk以及候選點集allowedk；l表示已旅游完一天的螞蟻數，l=0；初始點為0的螞蟻的過程變量Pro[k]=1，初始點為非0點的螞蟻的過程變量Pro[k]=2；

（3）在結點i取螞蟻k，判斷其初始結點。若為0點，按轉移規則確定結點j，更新tabuk、Si、bi。并且若Pro[k]=1，則Pro[k]=2，轉步驟3；而當Pro[k]=2時，若j點為初始結點，則l++，轉步驟3；否則轉步驟4。若為非0點，則按轉移規則確定轉移結點j，更新tabuk、Si、bi。并且當Pro[k]=1時，若j點為0，則Pro[k]=2，轉步驟3；當Pro[k]=2時，若j點為初始結點，則l = l+1，轉步驟3，否則轉步驟4；

（4）更新Si，重復步驟3-4直到該結點的螞蟻數量bi=0為止；

（5）重復步驟3-5，直到所有結點的bi=0；

（6）在所有螞蟻都移動一次后，按局部更新規則對所有路徑的信息素進行更新；

（7）更新所有結點的bi，若所有結點上螞蟻數量bi=0或l = M，轉下一步，否則轉步驟3；

（8）由各螞蟻的tabuk得到路徑集

在L中尋找可行解，得到可行解集

若未發現可行解，實施多周期螞蟻組合策略生成L-ch子回路集，再在L-ch中尋找可行解。若仍未發現可行解，則采取近似解可行化策略，轉下一步。

（9）采用大洪水算法對可行解集A中各個可行解進行局部優化，得到A′，計算本次搜索到的最優路徑L*(nc)，并得到迄今為止的最優路徑，

L*=min{L*(nc),L*}，nc為迭代計數；

（10）若算法陷入停滯，采用負反饋機制調整路徑上的信息素，并調大r0，否則按全局更新規則進行信息素的全局更新；

（11）判斷nc是否等于最大迭代次數ncmax，若是，則算法終止，輸出L*；否則，nc++，轉步驟2。

2 實驗及分析

2.1 實例仿真

設有20個旅游景點（JD）隨機分布于邊長為10 km的正方形區域內。休息地位于區域正中央，其坐標為(0, 0)。各旅游地游玩所需時間也由計算機隨機產生，每天的游玩時間為9 h。基礎數據如表1所示，其中tdp為單個景點游玩的時間（h）。

表1 實驗基礎數據

采用的參數為M=60，最多迭代次數ncmax=50，τij=10，游玩最多公里數MAX=100，游玩最少公里數MIN=2，α=1，β=1，γ=0.5，ρ1=0.85，ρ2=0.95，Q1=10，Q2=50，Q3=100，r0=1。運行10次，結果如表2所示，其中為平均最小行走距離（km），T為（游玩）所用天數（d），ncf為首次搜索終解代數，tc為計算用時（s），為行走距離與最小行走距離差（km）。

表2 實驗計算結果

從表2可以看出，用蟻群算法的10次求解中，都得到了質量很高的解。其中最好解為41.86 km，路線1：0-18-0；路線2：0-1-17-14-8-0；路線3：0-12-6-7-4-3-19-0；路線4：0-2-10-11-16-13-5-15-9-0。蟻群算法的計算結果穩定，10次求解中最差解的游玩里程僅比最好解多5.8%。從計算效率看，10次求解的平均計算時間為2.14 s，計算效率較高，有效地解決了計算時間長的問題。從上述分析可見，對于VRP，利用蟻群算法可取得比較理想的結果，且計算結果穩定。

為了便于比較，分別用爬山法、遺傳算法、模擬退火算法對該實例求解了10次，解的搜索次數都為15 000次，4種算法的計算結果見表3，其中Ddev為解的標準差。

表3 爬山法、遺傳算法、模擬退火算法及蟻群算法比較

由表3不難看出，從尋優結果看，蟻群算法明顯優于其它3種算法；從計算效率看，蟻群算法低于爬山算法和模擬退火算法，但高于遺傳算法；從算法的穩健性看，蟻群算法計算結果的穩定性明顯優于其它3種算法。

2.2 運行參數和算法策略對蟻群算法性能的影響

2.2.1 運行參數對蟻群算法搜索性能的影響

蟻群算法的運行參數主要有螞蟻數M、基本信息素量τij、轉移規則各相對重要性參數（α、β、γ、λ）、信息素的持久度（ρ1、ρ2）以及施放量（Q1、Q2、Q3）等。本文僅以螞蟻數M為例討論運行參數對算法搜索性能的影響。

對上述實例，分別取M =30、40、50、60、70、80、90、100，τij=20， ncmax=50， MAX=80， MIN=2，α=2，β=1，γ=0.5，λ=0.2，ρ1=0.85，ρ2=0.95，Q1=5，Q2=50，Q3=100，r0=1，各運行50次，結果如表4所示，其中為平均迭代步數。

表4 螞蟻數M對蟻群算法性能的影響分析表

由表4可以看出，螞蟻數較大時，解的質量比較高，但隨著螞蟻數的不斷增加，解的質量的提高越來越不明顯，而計算時間卻大幅度增加。因此就本實例而言，采用60～80個螞蟻就可以了。

2.2.2 算法策略（SC）對蟻群算法搜索性能的影響

實驗中發現，若不采取任何可行解獲取策略，較大規模問題的蟻群算法基本發現不了可行解，因此對大螞蟻數策略、螞蟻初始分布均勻策略、多周期螞蟻組合策略以及近似解可行化策略等4個策略以及它們之間的組合進行實驗比較，具體分析6種算法：SC1，采取小螞蟻數（M =40）和初始螞蟻分布均勻策略；SC2，采取大螞蟻數（M =80）和初始螞蟻分布均勻策略；SC3，在SC1的基礎上，增加多周期螞蟻組合策略；SC4，在SC1的基礎上，增加近似解可行化策略；SC5，在SC2的基礎上，增加近似解可行化策略；SC6，在SC4的基礎上，添加多周期螞蟻組合策略。分別對前述實例求解，最大迭代次數為20，各運行20次，結果如表5所示，其中ncn為找不到解的迭代數，為平均無可行解數。

表5 算法策略對蟻群算法性能的影響分析表

由表5可見，SC3相對SC1而言，雖然計算時間稍長，但其求解質量有較大提高，而相對SC2而言，其計算結果和平均無可行解次數均比較接近，而計算時間卻有較大幅度的節省。后3種算法由于引進了近似解可行化策略，因此不存在無可行解的問題。SC4的計算結果質量較前3者有很大提高。在各種算法中，計算結果最好的為SC5，其平均計算結果為43.13 km，離問題最好解41.86 km相當接近，其原因在于它既采用了大螞蟻策略，又采用了近似解可行化策略，但計算時間也最長。

3 實例分析——秦皇島地區“多日游”交通路線模型

3.1 模型建立

表6 實驗基礎數據

秦皇島旅游區域內現有12個旅游景點，其基礎數據如表6所示，休息地位于區域正中央的天下第一關，各景點游玩所需時間tdp（h）由實際估計得到。

3.2 模型求解

假設：（1）采用的運行參數為M=60，ncmax=50，τij=10，MAX=100，MIN=2，α=1，β=1，γ=0.5，ρ1=0.85，ρ2=0.95，Q1=10，Q2=50，Q3=100，r0=1；（2）每天的游玩時間為9 h；（3）運行10次。按上述混合蟻群算法計算，結果如表7所示。

表7 實驗計算結果

從表7中可以看出，用蟻群算法的10次求解中，都得到了質量很高的解，其中最好解為83.72 km，路線1的行走路徑為0-1-3-0；路線2為0-2-7-0；路線3的為0-8-6-0；路線4的為0-11-10-12-0；路線5的為0-9-5-4-0。蟻群算法的計算結果也較穩定，10次求解中，最差解的游玩里程僅比最好解多5.8%。從計算效率看，10次求解的平均計算時間為2.14 s，計算效率較高。可見，對于VRP，利用蟻群算法可取得比較理想的結果，且計算結果也較穩定。

4 結論

將蟻群算法引入到VRP中來，通過分析VRP與TSP的區別，構造了適于求解VRP的蟻群算法。為減少計算時間，避免算法停滯，對算法的選擇機制、更新機制以及協調機制作了進一步研究，并融合了大洪水算法以及節約法等方法。在此基礎上，本文所設計的自適應混合蟻群算法不但具有很強的發現較好解的能力，還具有較高的計算效率，計算結果相當穩定。

[1] 王大志,汪定偉,閆楊.一類多旅行商問題的計算及仿真分析[J].系統仿真學報,2009,21(20)∶6378-6381.

[2] 李偉,趙瑜.基于蟻群算法的“多日游”線路優化問題[J].

中國物流與采購,2009(10)∶76-77.

[3] 姜啟源,謝金星,葉俊.數學模型[M].北京∶高等教育出版社,2003∶111-120.

[4] 李士勇.蟻群算法及其應用[M].哈爾濱工業大學出版社, 2004∶10-98.

[5] 馬良,朱剛,寧愛兵.蟻群優化算法[M].科學出版社,2008∶35-112.

[6] 邢文訓,謝金星.現代優化計算方法[M].清華大學出版社, 1999∶102-135.

[7] 高尚,楊靜宇.群智能算法及其應用[M].水利水電出版社, 2006∶9-157.

[8] 雷德明,嚴新平.多目標智能優化算法及其應用[M].科學出版社,2009∶22-38.

[9] 劉任任.算法設計與分析[M].武漢理工大學出版社, 2003∶40-47.

（責任編輯、校對：趙光峰）

Optimization Problem about the Choice of “Multi-Day” Tourism Route Based on Hybrid Ant Colony Algorithm

YANG Li-xin

(Tangshan No.12 Middle School, Tangshan 063000, China)

For the “multi-day” line optimization, a new hybrid ant colony algorithm is proposed and a “multi-day” tourist traffic route model is established. Through experiments and calculations, it shows that the optimal solution or near optimal solution can be effectively obtained when the hybrid ant swarm algorithm is applied to the “multi-day” tourist traffic lines.

“multi-day” tourism route; hybrid ant colony algorithm; path optimization

F59

A

1009-9115(2013)05-0037-04

10.3969/j.issn.1009-9115.2013.05.011

2013-05-09

楊麗馨（1968-），女，唐山人，碩士，高級教師，研究方向為最優化。