基于蟻群算法的旅游線路優化

劉訓星，胡 敏，黎 穎

(宣城職業技術學院， 安徽 宣城 242000)

基于蟻群算法的旅游線路優化

劉訓星，胡 敏，黎 穎

(宣城職業技術學院， 安徽 宣城 242000)

旅游成為當今休閑放松的重要方式，每位旅客受空間、時間和經濟能力限制具有不同需求，因此游客面臨的首要問題就是選擇適合的旅游線路。針對宣城市豐富的旅游資源，利用蟻群算法對13個特色景點進行線路規劃，然后建立帶約束線路規劃模型，并通過評價分析求得最優結果。實驗表明：該方法能為不同游客推薦不同需求的旅游線路。

蟻群算法; 線路規劃; 旅游; 線路優化

隨著老百姓生活水平的提高，旅游已成為最時尚的休閑活動，怎樣在假期有限、預算不增加的情況下游玩更多的景點是廣大旅游愛好者迫切需要解決的問題，所以景點路徑規劃十分必要，有助于游客尋找最佳旅游路線。

旅游路徑規劃從區域范圍可以分為3個部分：城市之間的旅游路徑規劃、 城市內各景區的旅游路徑規劃、 景區內各景點的旅游路徑規劃。 城市之間的旅游路徑規劃和景區內各景點的旅游路徑規劃都是從一點出發，經過其他點，且只經過一次，最后回到出發點的路線規劃，即TSP 回路問題。這是一個經典的NP難題，所以解決方法非常多。其中包括：蟻群算法、退火算法、遺傳算法、粒子群算法和禁忌搜索算法等。對景點路徑規劃的研究有助于解決很多類似路徑規劃問題，所以研究景點路徑規劃問題具有重要意義。

目前路徑規劃已經在工業、物流方面大規模應用，國內外學者開展了深入研究，提出許多算法[1]和方案，包括啟發式搜索、蟻群算法[2]、Dijkstra、神經網絡。宣城市是文房四寶之鄉，有著豐富的旅游文化資源，文中首次將蟻群算法應用到宣城市文房四寶文化旅游線路規劃，通過在宣城市旅游信息平臺的應用，得出了最佳的旅游路線。

1 旅游信息服務平臺技術設計分析

1.1 Andriod系統

Andriod系統主要用于平板、手機智能移動終端，具有性能卓越、開源、市場占有率高等特點。Andriod系統具有以下優勢：① 任意移動終端生產商能夠自由融入Andriod聯盟。② Andriod系統具有開源免費的特點，有利于第三方軟件開發。③ 用于開發第三方軟件，程序java語言也具有開源免費的特點。

Andriod系統提供多種存儲方式：文件存儲、內容提供器、網絡存儲[3]和Sqlite存儲，文房四寶文化旅游系統采用Sqlite存儲數據。

Sqlite具有操作方便、靈活高效、跨平臺等特點，能夠嵌入應用程序中關聯數據庫。Sqlite在同一進程空間服務器和客戶端同時運行，在應用程序運行時無需管理和網絡配置。Sqlite使用權限只與文件系統有關。Sqlite由于高效占用內容空間小，非常適合用戶移動終端，在使用過程中只需把Sqlite編譯到文房四寶文化旅游信息服務平臺中。

Sqlite數據庫架構由接口、編譯器、虛擬機、后端組成。① 接口：用于Sqlite與文件、程序交互的接口。② 編譯器：先對查詢語句檢查，然后轉化語法樹，接著生成匯編代碼，最后交由虛擬機運行。③ 虛擬機：用于解釋運行代碼，完成特定的操作。④后端：管理運行數據，搜索數據維系頁面關系。

1.2 Web Service

Web Service是一種跨平臺應用程序。移動終端及網絡終端都能夠同時使用Web Service方法。Web Service具有以下優勢：① 數據交換更加便利，適合異構系統間數據交換和通信。② 使用了XML技術對對數據進行封裝，使用者僅能看到功能列表。③ 用標準的方法把不同語言開發和不同平臺程序集成起來。文中將采用Web Service來獲取移動終端信息，管理數據庫和生成具有導航功能的地圖。

1.3 蟻群算法

蟻群算法由Marco Dorigo等[4]受螞蟻覓食啟發提出的一種隨機智能算法。螞蟻在沒有輔助的情況下找到巢穴至食物最短路徑，螞蟻選擇路徑的過程是一種正反饋機制。旅客在不同景點游玩與螞蟻覓食有驚人的相似處，所以蟻群算法適用于景點間路徑規劃。

螞蟻算法的優勢表現在以下幾個方面：① 螞蟻算法能夠用來解決至今沒有找到合適算法的問題。② 螞蟻算法采用啟發式思維算法框架。③ 螞蟻算法是近似算法，具有較大彈性，可以針對不同應用問題加以改進，運用到不同領域。

蟻群算法應用領域很廣泛，劉利強等研究在水下三維空間路徑規劃；朱慶保研究機器人路徑規劃；張維澤等研究物流配送規劃；王慧等[5]研究旅游線路規劃。

2 旅游信息服務平臺功能設計分析

2.1 系統框架設計

文房四寶旅游文化信息服務系統中客戶端采用Android系統使用Sqlite數據庫，服務器采用linux系統使用mysql數據庫，實現了多媒體播放、電子地圖、天氣查詢、交友等功能。

圖1 旅游信息平臺框架

2.2平臺功能模[6]塊設計

1) 定位、顯示附近用戶

定位：① 首先使用MyLocation Overlay類創建對象，在列表中添加創建對象。② 定時將自己最新位置發送到服務器，以便其他用戶獲取。

顯示附近用戶：首先，向服務器申請獲取附近用戶位置；其次，服務器向用戶移動終端返回JSON的字符串，解析字符串封裝成對象加入到附近用戶列表；最后，修改Constant類，在用戶客戶端顯示附近用戶。

2) 地圖應用

百度地圖API[7]使用JavaScript實現程序接口。程序員通過接口使用百度地圖數據和服務，創建功能全變應用程序。① 下載API包，百度地圖API包含libBMapApiEngine.so 和baidumapspi.jar兩個文件。② 程序使用百度地圖API進行開發，需要使用百度地圖提供用于開發類庫，只有擁有API密鑰才能使用百度地圖提供的類，所以需要申請API Key。③ 先將上述兩個包拷貝到工程目錄下，然后將baidumapapi.jar導入應用工程，最后將mapapi.Mapview加入布局文件里。④ 使用蟻群算法規劃行程路線。⑤ 將規劃線程顯示在地圖上。

3) 旅游路線規劃

① 旅游景點信息

通過poilist類實現，首先讀取用戶信息；其次在客戶端通過listview將景點信息展現出來；最后根據游客操作記錄游客對景點的偏好。

② 線路規劃

景點路線規劃的結果通過兩種方式展示：第1種，通過旅客游玩先后順序顯示各個景點；第2種，直接在百度地圖上顯示。

圖2 景點線路規劃流程

4) 多媒體應用[8]

通過預覽景區圖片、播放景區視頻，能夠提供景區四季景色和景區歷史圖片。Android提供豐富的編碼格式，能夠方便地將音頻、圖片、視頻等集成到應用程序中。

① 音頻播放功能

通過audioframeactivity類創建景點音頻信息列表，再使用audioplayactivity類播放音頻列表中的音頻。

圖3 Audioplayactivity與audioframeactivity通信流程

② 圖片瀏覽功能

通過pictureviewactivity和pictureframeactivity展示游客選擇圖片。Pictureframeactivity繼承listactivity類，使用simpleadapter綁定顯示的數據。Pictureviewactivity主要使用gallery組件和imageswitcher組件。首先使用findviewbyid()方法引用switcher；其次使用setfactory()方法視圖切換；接著使用setoutanimation()方法和setinanimation()方法設置圖片切換動畫效果；最后使用setadpter()方法設置imageadapter。

③ 視頻點播功能

通過videoplayactivity類和videoframeactivity類實現。Videoframeactivity用于顯示景點風景的經典圖片、景點相關介紹和視頻大小。Videoplayactivity定義3個runnable對象，用于視頻播放開始計數、重置和暫停。視頻播放核心代碼如下：

Runnable rnable1,rnable2,rualbe3;

run(){

counts=counts+1

t.setText(ntime2(counts));

handler.postDelayer(this,2000);

}

handler.removeCallbacks(rnalbe2);

handler.removeCallbacks(rnalbe1,2000);

handler.removeCallbacks(rnalbe3);

5) 天氣查詢應用

系統借助景點的經緯度坐標使用Google Weather API查詢景點天氣，先輸入景點的經緯度，Google Weather API返回xml文件，然后解析xml文件，Android系統有SAX、DOM、XMLPull 3種方式解析xml文件,使用方便、占用資源少，本系統采用XMLPull方式解析xml文件。

6) 游記應用

游記應用模塊為旅游者提供發表旅游過程中心情、感悟的功能。包括文章題目、時間、圖片和文字。為了實現游記功能，首先實現游記信息發布功能(recordactivity類)；其次實現信息修改功能(recordeditactivity類)；最后實現sqlite數據庫操作功能(dbadapter類)。

recordactivity類實現游記信息發布，通過listview組件布局，使用renderlistview()顯示信息數據，使用onemenuitemselecter()方法建立(creatediary())、刪除(deleteDiary())游記信息，最后使用recordeditactivity類onactivityresult()方法使得界面與數據信息保持一致。

3 行程規劃算法

3.1析規劃行程模型[9]

(1)

(2)

(3)

式中:C表示旅游花費，T表示旅游時間，R={S1,S2,…,Sn-1,Sn}是一條符合旅游需求的路線。d(i)表示提前到達景點等待所花時間。t0(i)表示景點開門時間，ta(i)表示到達景點時間，tp(i)表示景點閉門時間。

(4)

式中:ω0表示旅游時間與費用關系的權重參數，Tmax代表可支配最長時間，cmax代表可消費最大預算。

3.2 構建行程路線

(5)

式中：C表示常數，w(u)表示景點營業時間約束段旅客吸引度。

(6)

式中:P(i,j)代表景點選擇概率；α代表信息濃度約束重要性；β代表啟發式信息約束重要性；υ代表開放時間約束重要性。

(7)

(8)

式中:γ1代表時間約束重要性；γ2代表花費約束重要性；η(i,j)代表路徑啟發式信息。

j=arg maxpk(i,j)

(9)

若q≤q0，下個景點j由式(9)確定；若q>q0，下個景點j由式(4)獲得選擇概率，然后使用輪盤賭方式確定。

3.3 更新行程信息素

τ(i,j)=(1-ρ)τ(i,j)+Δτ(i,j)

(10)

式中：ρ表示信息素減少度，取值范圍為0<ρ≤1。Δτ(i,j)代表形成路線信息素升高度。

(11)

式中Φ(R)表示評價路線的目標函數。

4蟻群算法在文房四寶旅游信息平臺應用

4.1實驗數據

宣城市是文房四寶之鄉，有著豐富的旅游資源，從中選擇有代表性的景點13處：① 中國鱷魚湖，② 恩龍世界木屋村，③ 皖南事變烈士陵園，④ 安徽宣硯文化有限公司，⑤ 中國宣紙文化園，⑥ 桃花潭風景區，⑦ 績溪龍川景區，⑧ 夏林風景區，⑨ 太極洞風景名勝區，⑩ 江村古建筑群，徽杭古道，敬亭山風景名勝區，寧國華東大裂谷。

4.2蟻群算法[10]應用

1) 經緯度

查閱資料獲得上述景點的經度與緯度。

只獲取經緯度還不夠，還必須計算出景點間距離,τdp表示單個景點旅客游玩時間，時間是根據景點類型和景點景區大小粗略估計，游客一天游玩時間以9h計算。

2) 景點間距離

C=sin(90-X(i))sin(90-X(j))·

cos(Y(i)-Y(j))+

sin(X(i))sin(X(j))

(12)

distance(i,j)=R·αcos(C)·π/180

(13)

式中:X(i)表示經度，Y(i)表示緯度，R表示地球半徑，distance(i,j)表示景點i與景點j的距離。

運用式(6)～(13)進行計算，結果見表1。

表1 景點與經緯度

4.3 路線規劃

假設：① 實驗運行參數值如表2所示。② 旅客一天游玩有效時間為8小時。③ 總共運行8次。

在使用螞蟻算法8次求解中，從表3能夠看出：① 得到高質量的解。在所有解中最好的為91.85 km。② 計算結果比較穩定，最差解比最好解多2.71%。③ 平均求解用時為2.17 s，求解效率較高。④ 線路1:0—1—12—9—0；線路2:0—5—3—6—0；線路3:0—10—4—7—11—0；線路4:0—2—13—8—0。通過以上可以看出：使用螞蟻算法可以得到比較理想的結果。

圖4 景點分布

名稱Mnτmaxτij游玩最大路程游玩最小路程αβγρ1ρ2Q1Q2Q3γ0值8040101505110.50.850.9510501001

表3 實驗結果

4.4 評價路線

通過使用螞蟻算法得到理想狀態下的4條路線，然而在實際旅游過程中還需要考慮游客對景點評價、交通狀況、景點門票和住宿等費用。

1) 景點等級(g)。依據國家旅游網景區等級劃分、宣傳宣城“文房四寶之鄉”的意義、景點人氣和景點開發時間并給予評定，分為4個等級，系數分別是1.1、1.2、1.3、1.4。

2) 交通狀況(t)。依據道路性質、旅游資源配套設施、“攜程旅行網”游客反饋意見和對我校導游專業學生調查問卷，通過匯總分析。分為5個等級，系數分別是0.6、0.7、0.8、0.9、1.0。

3) 費用水平(c)。依據景區門票價格、住宿花費、餐飲花費，分為3個等級，系數分別為0.9、1.0、1.1。

4) 景區影響力綜合指數是衡量景點對游客吸引力綜合評價指標(f)。

(14)

式中:fi為景區影響力綜合指數；ρ為花費超支懲罰系數；gi為景點等級指數；μ為景區人氣縮放系數；ti為交通狀況及配套設施綜合評價指數；ci為景區消費指數；γ為景區消費縮放系數。

考慮交通、景點影響力和花費等多方面影響，運用螞蟻算法得出理想旅游線路，重新評價分析得出以下結論：線路1:0—1—12—9—0，路線景點影響力綜合評價1.17；線路2:0—5—3—6—0，路線景點影響力綜合評價0.96；線路3:0—10—4—7—11—0，路線景點影響力綜合評價0.95；線路4:0—2—13—8—0，路線景點影響力綜合評價0.99。通過綜合分析得出：線路1線路4線路2線路3，因此最佳旅游線路為線路1：0—1—12—9—0。

表4 景點影響力指數

5 結束語

本文提出了基于螞蟻算法的文房四寶旅游信息服務平臺的建設，能夠為旅游愛好者提供便捷、人性化的服務，有助于“山水詩鄉，多彩宣城”旅游產業又快又好的發展。

蟻群算法應用在宣城市文房四寶旅游平臺應用，體現出蟻群算法在景點數量較少時規劃路徑的優越性。文中介紹了蟻群算法路徑規劃的思想和算法，結合“山水詩山，多彩宣城”豐富的旅游資源和獨特的文化底蘊，為廣大旅客尋找到符合各自需求的最佳旅游線路。

平臺采用Android系統，具有功能實用、界面友好和操作方便等特點，同時還能將該應用開發推廣到其他領域，如城智能城市公共交通工具選擇、船舶導航和物流配送。該平臺還需進一步改進，如將該應用程序與微信、QQ平臺融合，有助于該應用程序的推廣和完善。完善應用程序可根據用戶的獨特需求與愛好實現智能路徑規劃推送功能[11]。

[1] 唐良,方廷鍵.基于改進蟻群算法的路徑規劃方法[J].中國科學技術大學學報,2009,39(9):980-984.

[2] 李旭,汪海妹，劉家堡,等.基于蟻群算法的旅游線路優化研究[J].重慶工商大學學報(自然科學版),2015,32(2):67-70.

[3] 舒賢華.基于Android平臺的收集Web地圖服務設計[D].大連海事大學,2009：128-211.

[4] 段海濱.蟻群算法原理及其應用[M].北京：科學出版社,2015,5-123.

[5] 劉利強,戴運桃，王麗華，等.基于蟻群算法的水下潛器全局路徑規劃技術研究[J].系統仿真學報,2007,19(18):4174-4177.

[6] 韓瑞東.基于Android的運程“智慧旅游”手機APP應用[J].計算機時代,2016(11):44-47.

[7] 付林，閆強，李祥.基于百度地圖的小區域導航實現方案研究[J].計算機技術與發展.2014,24(5):223-226.

[8] 包冬梅.基于Android平臺的旅游系統的設計[J].呼倫貝爾學員學報,2016,24(2):92-95.

[9] 睢先先，宋夫華.基ACO的智能旅游行程規劃系統設計[J].計算機應用與軟件,2016,33(9):231-234.

[10] 王慧,劉昌華，王育玲，等.蟻群算法在旅游路線規劃中的應用[J].軟件導刊,2016,15(4):44-46.

[11] 李霞,尹川東，袁云.旅游路線個性化推薦算法比較分析[J].計算機技術與發展,2016,26(9):73-77.

(責任編輯楊黎麗)

TheAntColonyAlgorithm-BasedResearchonCulturalTouristRouteOptimization

LIU Xunxing, HU Min, LI Ying

(Xuancheng Vocational and Technical college, Xuancheng 242000, China)

Nowadays, tourism has become an important way of recreation. Every tourist possesses different demands restricted by space, time and economic capability, thus, the first question facing tourists is how to choose a proper tourism route. The thesis, aiming at abundant tourism resources of Xuancheng city, conducts a route plan on 13 scenic spot in a way of ant algorithm, and establishes constrained route plan model and pursues the best results through making an analysis. The experiment shows that this way can provide various tourism route for different tourists.

ant colony algorithm; route planning; tourism; path optimization

2017-08-01

安徽省高等學校自然科學重點研究項目(KJ2016A784)

劉訓星(1981—)，男，安徽宣城人，碩士，講師，主要從事網絡并行分布計算、數據挖掘、教育信息化研究，E-mail: 826038115@qq.com。

劉訓星，胡敏，黎穎.基于蟻群算法的旅游線路優化[J].重慶理工大學學報(自然科學)，2017(10):158-164.

formatLIU Xunxing, HU Min, LI Ying.The Ant Colony Algorithm-Based Research on Cultural Tourist Route Optimization[J].Journal of Chongqing University of Technology(Natural Science)，2017(10):158-164.

10.3969/j.issn.1674-8425(z).2017.10.025

O211;TP319

A

1674-8425(2017)10-0158-07