劉訓(xùn)星，胡 敏，黎 穎

(宣城職業(yè)技術(shù)學(xué)院， 安徽 宣城 242000)

基于蟻群算法的旅游線路優(yōu)化

劉訓(xùn)星，胡 敏，黎 穎

(宣城職業(yè)技術(shù)學(xué)院， 安徽 宣城 242000)

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

蟻群算法; 線路規(guī)劃; 旅游; 線路優(yōu)化

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

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

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

1 旅游信息服務(wù)平臺技術(shù)設(shè)計分析

1.1 Andriod系統(tǒng)

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

Andriod系統(tǒng)提供多種存儲方式：文件存儲、內(nèi)容提供器、網(wǎng)絡(luò)存儲[3]和Sqlite存儲，文房四寶文化旅游系統(tǒng)采用Sqlite存儲數(shù)據(jù)。

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

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

1.2 Web Service

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

1.3 蟻群算法

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

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

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

2 旅游信息服務(wù)平臺功能設(shè)計分析

2.1 系統(tǒng)框架設(shè)計

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

圖1 旅游信息平臺框架

2.2平臺功能模[6]塊設(shè)計

1) 定位、顯示附近用戶

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

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

2) 地圖應(yīng)用

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

3) 旅游路線規(guī)劃

① 旅游景點信息

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

② 線路規(guī)劃

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

圖2 景點線路規(guī)劃流程

4) 多媒體應(yīng)用[8]

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

① 音頻播放功能

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

圖3 Audioplayactivity與audioframeactivity通信流程

② 圖片瀏覽功能

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

③ 視頻點播功能

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

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) 天氣查詢應(yīng)用

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

6) 游記應(yīng)用

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

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

3 行程規(guī)劃算法

3.1析規(guī)劃行程模型[9]

(1)

(2)

(3)

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

(4)

式中:ω0表示旅游時間與費用關(guān)系的權(quán)重參數(shù)，Tmax代表可支配最長時間，cmax代表可消費最大預(yù)算。

3.2 構(gòu)建行程路線

(5)

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

(6)

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

(7)

(8)

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

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)表示評價路線的目標(biāo)函數(shù)。

4蟻群算法在文房四寶旅游信息平臺應(yīng)用

4.1實驗數(shù)據(jù)

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

4.2蟻群算法[10]應(yīng)用

1) 經(jīng)緯度

查閱資料獲得上述景點的經(jīng)度與緯度。

只獲取經(jīng)緯度還不夠，還必須計算出景點間距離,τdp表示單個景點旅客游玩時間，時間是根據(jù)景點類型和景點景區(qū)大小粗略估計，游客一天游玩時間以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)表示經(jīng)度，Y(i)表示緯度，R表示地球半徑，distance(i,j)表示景點i與景點j的距離。

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

表1 景點與經(jīng)緯度

4.3 路線規(guī)劃

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

在使用螞蟻算法8次求解中，從表3能夠看出：① 得到高質(zhì)量的解。在所有解中最好的為91.85 km。② 計算結(jié)果比較穩(wěn)定，最差解比最好解多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。通過以上可以看出：使用螞蟻算法可以得到比較理想的結(jié)果。

圖4 景點分布

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

表3 實驗結(jié)果

4.4 評價路線

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

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

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

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

4) 景區(qū)影響力綜合指數(shù)是衡量景點對游客吸引力綜合評價指標(biāo)(f)。

(14)

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

考慮交通、景點影響力和花費等多方面影響，運用螞蟻算法得出理想旅游線路，重新評價分析得出以下結(jié)論：線路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 景點影響力指數(shù)

5 結(jié)束語

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

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

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

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

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

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

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

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

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

[7] 付林，閆強，李祥.基于百度地圖的小區(qū)域?qū)Ш綄崿F(xiàn)方案研究[J].計算機技術(shù)與發(fā)展.2014,24(5):223-226.

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

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

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

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

(責(zé)任編輯楊黎麗)

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

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

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

劉訓(xùn)星，胡敏，黎穎.基于蟻群算法的旅游線路優(yōu)化[J].重慶理工大學(xué)學(xué)報(自然科學(xué))，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