基于蟻群算法的5A景點旅游路線規劃問題研究

萬慧云 蔣艷

摘 要： 根據我國普通居民旅游情況，建立并求解乘坐公共交通工具、花費較少時間進行舒適度較高、花費較低的綜合效益最大化旅游體驗模型，以提升我國居民生活質量。收集我國5A景點的經緯度坐標、門票費用、最佳旅游時間、路況及食宿費用等相關數據，基于蟻群算法與Matlab2018a軟件進行編程求解，得出全國5A景區旅游路線規劃方案。最后根據研究結果得出結論，綜合時間、費用、路程和舒適度4個目標效益最大化的模型與已有單方面或只有2～3個目標函數的模型相比，其在進行旅游路線規劃時，不僅考慮因素更加全面，而且更加貼合我國大部分居民的實際需求。

關鍵詞：旅游路線規劃;蟻群算法;最短路徑

DOI：10. 11907/rjdk. 182281

中圖分類號：TP319文獻標識碼：A文章編號：1672-7800（2019）004-0141-04

0 引言

隨著社會的發展和人們生活水平的不斷提高，旅游經濟收入已成為很多城市的主要收入來源之一。由于私家車數量不斷增多，導致旅途交通擁擠、景區車輛停放等問題越來越突出。因此，如何選擇合適的交通工具、最佳游覽時間實現舒適度較高，而花費較低的旅游體驗，對于城市居民生活質量提升具有重要意義[1]。

1 研究現狀

旅游路線規劃問題是基于經典TSP問題演化而來的。TSP問題是一個典型的組合優化問題，目前國內外對于TSP問題研究較多，已提出基于經典算法改進的Dijkstra算法、動態規劃算法、分支定界法等[2]，以及基于啟發式優化算法改進的蟻群算法、遺傳算法、模擬退火算法、禁忌搜索算法、Hopfieltl神經網絡、粒子群優化算法、免疫算法等[3]。但截至目前，尚沒有一個解決TSP問題的完美方案。20世紀90年代，我國學者開始將TSP模型應用于實際的旅游路線規劃問題中，研究結果表明，旅游者類型具有多樣化特征，但其目標主要歸結為兩種，即自我耗費成本最小化與獲得收益最大化[4]。吳凱[5]將定量與定性方法相結合設計旅游路線，但未進行實證分析，僅停留在理論層面;吳小根[6]分析研究江蘇省省內旅游路線中城市節點、景區節點、臨時節點三大節點類型的節點配置特征;史春云[7]研究基于線路節點特性的旅游模式，探究長三角城市旅游經濟收益的空間差異[8];黃燕平[9]研究影響消費者旅游路線選擇的相關因素，并以湖南永州旅游路線為例進行實證分析;劉宇青[10]研究高鐵開通對消費者旅游路線選擇的顯著影響;黃騰[11]首先采用遺傳算法對河南省13個5A景點進行無約束條件下的旅游路線規劃，然后運用蟻群算法進行有費用約束條件下的旅游路線規劃。在以上研究基礎上，本文基于蟻群算法，并以時間最短、費用最少、路線最短、舒適度最高為目標，研究以全國任意城市為起點，乘坐公共交通工具游覽全國249個5A景區的旅游路線規劃設計，并以上海市作為出發城市進行實證分析，得出具體旅游時間、費用以及詳細行程安排。

2 蟻群算法

2.1 算法原理

蟻群算法（Ant Colony Algorithm）是由意大利學者Colorni等[12]于20世紀90年代初期通過模擬自然界中螞蟻集體尋徑行為而提出的一種基于種群的啟發式仿生進化算法[13]。該算法采用分布式并行計算機制，具有較強的魯棒性，但是具有搜索時間長、容易陷入局部最優解的缺點[14]。

2.2 蟻群算法流程

（1）參數初始化。在計算之前對相關系數進行初始化，如蟻群數量m、信息素重要程度因子[α]、啟發函數重要程度因子[β]、信息素揮發因子[ρ]、信息素釋放總量Q、最大迭代次數maxiter等。設迭代次數初值iter為1，然后將m個螞蟻放置于n個頂點上[17]。

3 模型建立

3.1 模型假設

假設旅游者出發點是隨機的，是綜合距離最近、交通方便、票價最低3個因素得出的一個出發點，本文假設旅游者從自己所在地到達其城市站點的相關影響因素不在路線規劃考慮之內，模型選取的出發點為旅游者所在城市公共交通工具的站點。旅游者只能選擇火車、飛機、長途汽車3種出行方式，因此將每個城市站點分為火車站、飛機場與長途客運站3類，其中火車站包含出行方式有高鐵、動車、普快。

（1）假設旅游總時間為T，Tij表示以城市i為起點、城市j為終點乘坐公共交通工具的消耗時間，Tjda表示從j城市車站到景點a之間乘坐交通工具的消耗時間，Tdab表示從j城市景點a到景點b之間乘坐公共交通工具的消耗時間，Tijh1表示以城市i為起點、城市j為終點乘坐公共交通工具的換乘時間，Tijh2表示在同一城市之內不同地點之間的換乘時間，Tjda表示在城市j第k個景點的游玩時間。

（2）假設旅游總路程為R，Rij表示以城市i為起點、城市j為終點乘坐公共交通工具經過的路程，Rjda表示從j城市車站到景點a之間乘坐交通工具的路程，Tdab表示從j城市景點a到景點b之間乘坐公共交通工具的路程。

（3）假設旅游總費用為F，Fij表示以城市i為起點、城市j為終點乘坐公共交通工具的票價，Fjda表示從j城市車站到景點a之間乘坐交通工具的票價，Fdab表示從j城市景點a到景點b之間乘坐公共交通工具的票價，Fjdk表示j城市第k個景點門票價格，Fjdks表示在j城市第k個景點的食宿費用。

（4）假設旅游者總體舒適感為S，Sjdkt表示在j城市第k個景點旅游時間方面的舒適度，如是否為景點最佳旅游時間點;Sjdkv表示在j城市第k個景點旅游交通方面的舒適度，如旅游景點游客數量等。

（5）假設時間約束為：景區開放時間按照國家規定為8：00-18：00，共計10小時，因此在景區游玩時間0≤Tjda≤10;考慮到旅游舒適度影響因素，每天乘坐公共交通工具時間不能超過8小時，即0≤Tij+Tjda+Tdab≤8。

（6）假設選擇步驟約束為：旅游者通常首先選擇一個想要旅行的城市，再到該城市的5A景點游玩，只有在該城市5A景點全部游覽完之后再選擇下一城市，即目標選取是有層次的。因此，本文模型可簡化為先對全國249個5A景點涉及的城市作一個旅游路線規劃，再針對每個城市的5A景點作旅游路線規劃。

3.2 目標函數

旅行總時間最小化目標為：

最終針對不同人群進行路徑規劃，主要分為3種：①對時間重視程度大于對金錢的重視程度;②對金錢重視程度大于對時間的重視程度;③對時間與金錢重視程度相同。對于相應權重設置可以根據個人實際情況加以考慮。

3.3 約束條件

在不同城市之間乘坐公共交通工具的時間為Tij=到達目的地時間-出發時間[21]。

（2）每天乘車時間不超過8小時[22]。

（3）先選擇城市再確定景點，或者確定景點之后，在對應城市之內游玩所有5A景點，才能轉移到下一城市。

4 實證研究

4.1 數據處理

根據中國旅游局官網收集全國249個5A景區數據，每個景點所在城市站點總數為165個（共獲得景區所在市縣237個，但部分數據無法獲得，因此歸并到最近市縣區）。按照官網順序從1開始編號，每組數據包含每個節點的經緯度坐標、節點名稱、景區最少游玩時間、景點門票費用、景點地區最低食宿費用等，然后到12306官網收集景點所在城市之間高鐵、動車、普快的相關數據（發車時間、行車時間、票價等），共得到5 445組數據[23]。

4.2 模型求解

通過Matlab 2018a編程，第一步設計全國249個5A景點涉及165個城市之間的最優路線，第二步是獨立設置每個城市5A景點的最佳旅游路線。隨機選擇出發城市，將模型與相應數據結合，165個城市之間最佳路線如圖1所示。最后得出結果：旅游最少時間為615.5天，最低費用為159 653元，最短路程為725.84km，此時舒適度相對最高。部分城市5A景區最佳路線規劃如圖2、圖3所示。

4.3 算例結果分析

以上海作為出發城市為例，即旅游者乘坐公共交通工具從上海出發游玩國內249個5A景區。通過分析比較，綜合時間、費用、路程、舒適度4個因素，得到旅游者綜合效益最優的方案為：旅游總時間為587.5天，總費用為153 653元，總路程為722.435km。

5 結語

綜合時間、費用、路程和舒適度4個目標效益最大化的模型與已有單方面或只有2～3個目標函數的模型相比，一方面對各影響因素考慮更加全面，另一方面更加貼合我國大部分居民實際需求，在一定程度上也為我國相關部門制定旅游景點路線規劃提供了參考意見。本方法主要存在的不足是在模型假設中還有一些實際影響因素未考慮進去，另外本文僅采用蟻群算法進行求解，由于蟻群算法本身存在缺陷，容易導致結果可能不是最優解，而是相對最優解。如果能結合其它算法進行混合算法編程求解，可能會達到更好的效果。

參考文獻：

[1] 楊云鵬，袁光輝，金陽，等. 全國5A級景區旅游路線規劃問題研究[J]. 數學的實踐與認識，2016（15）：74-80.

[2] 徐清泉，趙夏，尚慶生. 冷鏈配送中的優化算法分析及應用[J]. 數字技術與應用，2016（8）：143-145.

[3] 于瑩瑩，陳燕，李桃迎. 改進的遺傳算法求解旅行商問題[J]. 控制與決策，2014（8）： 1483-1488.

[4] 楊萍. 區域旅游者行為模式及影響研究[J]. 經濟問題探索，2003（6）：114-117.

[5] 吳凱. 旅游線路設計與優化中的運籌學問題[J]. 旅游科學，2004（1）：41-44，62.

[6] 吳小根，李海鴿，馮英杰. 江蘇省國內旅游線路節點配置研究[J]. 地域研究與開發，2011（5）：118-122.

[7] 史春云. 旅行模式對目的地旅游經濟影響的空間差異[J]. 旅游學刊，2013（6）：102-110.

[8] 鄧志剛. 旅游目的地研究文章述評分析——以旅游學刊2013- 2014年為樣本[J]. 旅游縱覽，2015（8）：66-70.

[9] 黃燕平，程啟清，王建生.? 基于蟻群算法的孔群加工路徑優化研究[J]. 機械研究與應用，2016（5）：37-40.

[10] 劉宇青，楊惠，類延輝，等. 蟻群算法解決CTSP問題的參數設置研究[J].? 計算機與數字工程，2011（3）：34-39.

[11] 黃騰. 基于遺傳蟻群算法的5A景點旅游路線規劃問題研究[D]. 武漢：華中師范大學，2017.

[12] 張雨，李芳，周濤. 云計算環境下基于遺傳蟻群算法的任務調度研究[J]. 計算機工程與應用，2014（6）： 51-55.

[13] 郭文昌，張惠珍. 應用混合算法求解冷鏈配送中心選址問題[J]. 改革與開放，2017（8）： 82-84.

[14] 佟靜翠. 基于混合算法的生產調度系統在鋼構企業的研究與應用[D]. 天津：河北工業大學，2015.

[15] 秦傳東. 基于遺傳算法選擇參數的蟻群算法求解TSP問題研究[J]. 信息與電腦：理論版，2014（11）：180-185.

[16] 畢碩本，董學士，馬燕. 遺傳算法和蟻群算法優化TSP的設計與分析[J]. 武漢理工大學學報，2010，32（16）：89-92.

[17] 封燕，高建瓴，粱志福. 城市物流中心選址問題研究[J]. 貴州大學學報：自然科學版，2010，27（5）：76-80.

[18] WU B，SHI Z Z. A solvable continuous time dynamic principal-agent model[J]. Chinese Journal of Computers-Chinese，2001（12）： 1328-1333.

[19] 楊再甫，黃友銳，曲立國，等.? TSP的改進蟻群算法求解及其仿真研究[J]. 合肥工業大學：自然科學版，2014（8）：928-932.

[20] 張家善.? 基于改進蟻群算法的物流配送車輛路徑優化研究[D]. 阜新：遼寧工程技術大學，2014.

[21] DORIGO M. An ant colony algorithm based partition algorithm for TSP[J].? Machine Learning， 2010（5）：582-597.

[22] 張天赫，彭紹雄，羅亞民，等. 基于蟻群算法的艦載機避障路線分析[J]. 兵工自動化，2017，36（10）：71-74.

[23] 米永強. 蟻群算法及其在求解旅行商問題中的應用[J]. 電腦知識與技術：學術交流，2014（3）：1505-1507.

[24] 王松濤. 基于優化的遺傳算子改進蟻群算法AGV路徑規劃[J]. 自動化應用，2017（3）：47-49.

（責任編輯：黃 ?。?/p>