基于ACO的智能旅游景區(qū)路線規(guī)劃系統(tǒng)設(shè)計

郝 標(biāo)，譚云蘭，王偉年，賈金原

?

基于ACO的智能旅游景區(qū)路線規(guī)劃系統(tǒng)設(shè)計

郝 標(biāo)1，*譚云蘭2，王偉年3，賈金原1

（1.同濟(jì)大學(xué)軟件學(xué)院，上海 201804；2.井岡山大學(xué)電子與信息工程學(xué)院，江西，吉安 343009；3.井岡山大學(xué)商學(xué)院，江西，吉安 343009）

針對目前旅游景區(qū)路線系統(tǒng)因景點(diǎn)數(shù)量多、景點(diǎn)間差異度大而導(dǎo)致線路規(guī)劃不合理等問題，對路線規(guī)劃算法和實(shí)現(xiàn)方案進(jìn)行研究，并提出了交互式智能旅游路線規(guī)劃系統(tǒng)的解決方案。通過研究ACO蟻群優(yōu)化算法(Ant Colony Optimization)、百度地圖API接口、Bootsrap等技術(shù)，改進(jìn)ACO算法模型，引入流式柵格布局，架構(gòu)了基于B/S架構(gòu)的系統(tǒng)平臺。實(shí)驗(yàn)結(jié)果表明，基于改進(jìn)的ACO和百度地圖所架構(gòu)的路線規(guī)劃系統(tǒng)在國內(nèi)大規(guī)模景點(diǎn)規(guī)劃方面具有規(guī)劃速度快、規(guī)劃結(jié)果合理、信息顯示全面等優(yōu)點(diǎn)。

ACO算法；旅游路線規(guī)劃；交互式系統(tǒng)；百度地圖

隨著互聯(lián)網(wǎng)產(chǎn)業(yè)的蓬勃發(fā)展，旅游產(chǎn)業(yè)科技化含量也越來越高，基于web3d技術(shù)的虛擬旅游[1]已經(jīng)讓旅游突破了傳統(tǒng)的模式有了新的意義，而無論對于實(shí)體旅游還是虛擬旅游，合理的旅游規(guī)劃都顯得特別重要。針對目前旅游景區(qū)路線系統(tǒng)因景點(diǎn)數(shù)量多、景點(diǎn)間差異度大而導(dǎo)致線路規(guī)劃不合理等問題，本文通過對蟻群算法[2-3]的研究提出了綜合考慮多因素的、可以完成大規(guī)模景點(diǎn)規(guī)劃的交互式智能旅游規(guī)劃系統(tǒng)。系統(tǒng)采用了目前流行的B/S架構(gòu)，集成了php、html5、javascript、css、ajax等技術(shù)，并引入了Bootstrap框架和百度地圖API接口，并接入井岡山虛擬漫游平臺。井岡山虛擬漫游平臺是建立在現(xiàn)實(shí)旅游景觀基礎(chǔ)上的，通過模擬現(xiàn)實(shí)景觀而打造的一個集虛擬旅游、旅游信息展示、電子商務(wù)、虛擬社區(qū)、全景漫游管理、旅游信息管理系統(tǒng)、電子商務(wù)管理系統(tǒng)和虛擬社區(qū)管理系統(tǒng)于一體的綜合型虛擬旅游網(wǎng)站[4]。交互式智能旅游規(guī)劃系統(tǒng)作為井岡山虛擬漫游平臺的一個主干模塊，開發(fā)過程中充分考慮了與系統(tǒng)其它模塊之間的數(shù)據(jù)共享以及數(shù)據(jù)通信，為系統(tǒng)的其它模塊以及整個系統(tǒng)的高質(zhì)量開發(fā)打下堅(jiān)實(shí)基礎(chǔ)。

1 系統(tǒng)架構(gòu)

由于傳統(tǒng)的C/S架構(gòu)存在需要安裝客戶端、對系統(tǒng)硬件要求比較苛刻、安裝復(fù)雜等缺點(diǎn)，本系統(tǒng)采用當(dāng)前已被廣泛應(yīng)用的B/S架構(gòu)(瀏覽器和服務(wù)器結(jié)構(gòu))來實(shí)現(xiàn)，是WEB興起后的一種網(wǎng)絡(luò)結(jié)構(gòu)模式，由于WEB瀏覽器是客戶端最主要的應(yīng)用軟件，這種模式統(tǒng)一了客戶端，將系統(tǒng)功能實(shí)現(xiàn)的核心部分集中到了服務(wù)器上，簡化了客戶端電腦載荷，減輕了系統(tǒng)維護(hù)與升級的成本和工作量，降低了用戶的總體成本，而且可以滿足用戶隨時隨地使用本系統(tǒng)的需求。

圖1 系統(tǒng)架構(gòu)圖

本系統(tǒng)完整架構(gòu)設(shè)計包括后端設(shè)計和前端設(shè)計，考慮到與井岡山虛擬旅游系統(tǒng)開發(fā)平臺WordPress的兼容性，后端設(shè)計采用PHP和MySQL數(shù)據(jù)庫進(jìn)行開發(fā)，主要實(shí)現(xiàn)的后臺功能包括前端基本設(shè)置、景點(diǎn)信息管理、景點(diǎn)網(wǎng)絡(luò)化管理、登錄用戶管理以及預(yù)開發(fā)功能社交系統(tǒng)評介管理、云端信息同步管理、基于XML的管理后臺定制等。前端設(shè)計主要負(fù)責(zé)實(shí)現(xiàn)與用戶的交互，通過百度地圖的API向用戶直觀地展現(xiàn)景點(diǎn)信息并對用戶的旅游偏好進(jìn)行采集，根據(jù)與用戶的交互結(jié)果以及后臺數(shù)據(jù)庫數(shù)據(jù)，通過蟻群算法智能推薦路線并友好的將結(jié)果展示給用戶。

2 智能規(guī)劃算法及數(shù)據(jù)模型設(shè)計

2.1 基于Floyd的智能規(guī)劃前置算法設(shè)計

Floyd算法又稱為插點(diǎn)法，是一種用于尋找給定的加權(quán)圖中多源點(diǎn)之間最短路徑的算法，其原理是動態(tài)規(guī)劃。為了給蟻群算法提供滿足算法條件的數(shù)據(jù)，采用如下算法描述對景點(diǎn)數(shù)據(jù)進(jìn)行預(yù)處理：

2.2 智能規(guī)劃算法設(shè)計

為了更好的完成路線智能規(guī)劃，系統(tǒng)采用仿生學(xué)算法蟻群算法[5]，即Ant Colony Optimization，ACO是一種用來在圖中尋找優(yōu)化路徑的仿生線性優(yōu)化算法，具有并行性、正反饋性和全局極小搜索能力強(qiáng)等特點(diǎn)。它由Marco Dorigo于1992年在他的博士論文“Ant system: optimization by a colony of cooperating agents”中提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。蟻群算法是一種模擬進(jìn)化算法，主要用來解決TSP問題，在現(xiàn)實(shí)的應(yīng)用中，對于解決調(diào)度問題、車輛路徑問題、分配問題、設(shè)置問題、數(shù)據(jù)聚類分析以及電信路由問題方面都有較好的表現(xiàn)。

蟻群算法是受自然界中真實(shí)螞蟻的行為啟發(fā)而提出的一種仿生學(xué)算法，其基本思想是對螞蟻尋找食物的過程進(jìn)行模擬，并加入一些制約因素。螞蟻個體之間是通過一種稱之為信息素的物質(zhì)進(jìn)行信息傳遞的，模擬若干螞蟻，每只螞蟻在解空間中獨(dú)立尋找解，并在其所尋找的解上留下信息素，解的性能越好，留下的信息素也就會越多，根據(jù)螞蟻路徑選擇模型，信息素越多的解被再次選擇的概率也就越大，通過正反饋，會有越來越多的螞蟻選擇該解，理想的情況下最后所有的螞蟻都會選擇該路徑，整個系統(tǒng)收斂到該解，即最優(yōu)解。

對蟻群算法的模擬過程如下，首先假設(shè)有只螞蟻，對于每個螞蟻，它會根據(jù)結(jié)點(diǎn)距離和連接邊上信息素的數(shù)量等為變量的概率函數(shù)選擇下一個結(jié)點(diǎn)，通過禁忌表阻止螞蟻訪問已訪問的結(jié)點(diǎn)，螞蟻周游一周后會在每條訪問的邊上留下信息素。初始時刻各條路徑上信息素都相等為常數(shù)。螞蟻在運(yùn)動過程中，根據(jù)各條路徑上的信息素量決定轉(zhuǎn)移方向，表示在時刻螞蟻由位置轉(zhuǎn)向位置的概率，

(2)

2.3 智能路線規(guī)劃數(shù)據(jù)模型設(shè)計

為了完成兼顧所有因素的路線智能推介，需要對蟻群算法進(jìn)行改進(jìn)，將算法中的參數(shù)替換為自己的模型，按照設(shè)計需求，需要考慮的因素包括景點(diǎn)到景點(diǎn)之間的距離，參觀過景點(diǎn)的游客對景點(diǎn)的推薦度，景點(diǎn)的星級，景點(diǎn)是否適宜當(dāng)前季節(jié)旅行，景點(diǎn)參觀需要花費(fèi)的時間，景點(diǎn)的管理員調(diào)整參數(shù)，通過以上因素綜合考慮，可以推薦出最適合用戶的路線規(guī)劃結(jié)果。參數(shù)模型為：

圖2 數(shù)據(jù)處理流程圖

Fig.2 Data process flow chart

3 用戶交互界面構(gòu)建

3.1 交互前端構(gòu)建

考慮到目前市場上瀏覽器種類紛雜，如Chrome、Firefox、IE、Safari、360瀏覽器等，每種瀏覽器對W3C標(biāo)準(zhǔn)的遵循程度都不同，甚至同一瀏覽器的不同版本對js和css的解析也不同。為了盡可能的兼容更多的瀏覽器和不同分辨率的顯示器，同時也為了滿足系統(tǒng)本身景點(diǎn)較多，友好直觀展示出眾多景點(diǎn)關(guān)系有一定挑戰(zhàn)性的問題，系統(tǒng)開發(fā)過程中引入了Bootstrap框架[7]。Bootstrap是Twitter推出的一個開源的用于前端開發(fā)的工具包。它由Twitter的設(shè)計師Mark Otto和Jacob Thornton合作開發(fā)，是一個CSS/HTML框架。Bootstrap提供了優(yōu)雅的HTML和CSS規(guī)范，它是由動態(tài)CSS語言Less寫成，其一直是GitHub上的熱門開源項(xiàng)目。Bootstrap中包含了豐富的Web組件，包括下拉菜單、按鈕組、按鈕下拉菜單、導(dǎo)航、導(dǎo)航條、面包屑、分頁、排版、縮略圖、警告對話框、進(jìn)度條、媒體對象等，系統(tǒng)開發(fā)過程中采用了bootstrap的流式柵格布局，并引入了輕量級導(dǎo)航條、縮略圖、模態(tài)、模態(tài)對話框、按鈕組等組件。

圖3 流式柵格布局效果

3.2 路線規(guī)劃交互地圖構(gòu)建

交互地圖的構(gòu)建無論對于用戶交互選擇景點(diǎn)還是向用戶直觀清晰的展示景點(diǎn)網(wǎng)絡(luò)結(jié)構(gòu)、景點(diǎn)詳情都至關(guān)重要，交互地圖的構(gòu)建主要需要完成地圖創(chuàng)建、地圖配置、景點(diǎn)坐標(biāo)拾取、景點(diǎn)信息展示、景點(diǎn)拖拽選擇以及路徑規(guī)劃結(jié)果展示等幾大功能，需要使用百度地圖API、百度地圖坐標(biāo)拾取系統(tǒng)以及HTML5新的拖拽特性[8]等共同集成實(shí)現(xiàn)。

3.2.1 引入百度地圖Javascript API

百度地圖JavaScript API[9]是一套由JavaScript語言編寫的應(yīng)用程序接口，主要包括基本地圖功能、地圖控件展示功能、覆蓋物功能、工具類功能、定位功能、右鍵菜單功能、鼠標(biāo)交互功能、駕車導(dǎo)航功能等大的功能塊接口，系統(tǒng)開發(fā)過程中采用百度地圖1.5版本，開發(fā)過程中需要首先通過js腳本將API引入界面中，由于百度地圖自1.5之后版本需要申請秘鑰，所以需要首先在百度地圖官網(wǎng)申請秘鑰。引入百度地圖腳本如下：

3.2.2 提取景點(diǎn)坐標(biāo)

由于井岡山景區(qū)的景點(diǎn)大部分沒有在百度地圖上標(biāo)識，為了在路徑規(guī)劃時能夠智能動態(tài)顯示詳細(xì)的景點(diǎn)位置，我們使用經(jīng)緯度來定位井岡山景點(diǎn)位置。而通過GPS照相設(shè)備獲取的經(jīng)緯度屬于WGS84坐標(biāo)系，這是一個比較通用的坐標(biāo)體系，目前國內(nèi)不能直接使用WGS84坐標(biāo)，因此百度地圖API的經(jīng)緯度是經(jīng)過加密偏移的。一般百度地圖API默認(rèn)使用墨卡托投影(Mercator Projection)[10]，由于投影參數(shù)不同，同樣的墨卡托投影也會有所差別，所以為了在地圖中標(biāo)注所有景點(diǎn)的位置，并不直接通過GPS來獲取景點(diǎn)的實(shí)際坐標(biāo)，而是通過百度地圖提供的BMap.MercatorProjection類來實(shí)現(xiàn)坐標(biāo)轉(zhuǎn)換，方可在百度地圖中獲取正確的景點(diǎn)位置信息。本系統(tǒng)開發(fā)過程中使用了百度地圖拾取坐標(biāo)系統(tǒng)，通過拾取坐標(biāo)系統(tǒng)可以很方便的獲取所有景點(diǎn)在百度地圖中的平面坐標(biāo)，能在規(guī)劃界面上準(zhǔn)確地顯示所有景點(diǎn)的信息和路線規(guī)劃結(jié)果。

3.2.3 創(chuàng)建地圖框架

根據(jù)百度地圖API文檔首先通過創(chuàng)建地圖容器，然后通過以下腳本創(chuàng)建地圖實(shí)例。

之后所有的地圖控件和覆蓋物都需要添加在該容器中，系統(tǒng)根據(jù)需要添加了基于Control基類的縮略圖控件、比例尺控件和地圖類型控件。覆蓋物控件是景點(diǎn)顯示的重要窗口，首先根據(jù)用戶選擇的條件對符合條件景點(diǎn)在地圖中對應(yīng)的經(jīng)緯度位置渲染出默認(rèn)標(biāo)注紅氣球，同時在附近創(chuàng)建自定義的覆蓋物展示景點(diǎn)信息，浮動顯示景點(diǎn)圖片和景點(diǎn)介紹信息并完成拖拽選擇景點(diǎn)功能的實(shí)現(xiàn)。根據(jù)百度地圖API以及用戶的交互結(jié)果在地圖上展示出最佳的游覽線路，路線規(guī)劃結(jié)果支持衛(wèi)星展示和行政區(qū)域展示，用戶可以通過兩種不同的展示效果更好的識別地形和行政區(qū)域。如圖4所示, 圖4 (a) 是在百度三維地圖上進(jìn)行路線規(guī)劃的效果圖，圖4 (b)是在行政區(qū)域地圖上路線規(guī)劃的效果圖。

(a)Baidu三維地圖規(guī)劃效果

(b)行政區(qū)域地圖規(guī)劃結(jié)果

圖4 路線規(guī)劃結(jié)果展示

Fig.4 Result of route planning

3.2.4 百度地圖功能改進(jìn)

景點(diǎn)拖拽選擇實(shí)現(xiàn)：鑒于百度地圖不支持將景點(diǎn)拖動出地圖容器，為了實(shí)現(xiàn)景點(diǎn)拖拽功能，首先基于百度地圖API創(chuàng)建Maker對象，并在Maker對象上添加onMouseOver監(jiān)聽，實(shí)時獲取鼠標(biāo)位置，當(dāng)鼠標(biāo)浮動到自定義覆蓋物上時，以鼠標(biāo)位置為中心生成隱藏浮動框，當(dāng)鼠標(biāo)click事件被觸發(fā)時將隱藏的浮動窗口顯示出來，并調(diào)用HTML5的拖拽特性，從而實(shí)現(xiàn)景點(diǎn)的拖拽選擇特效。

多景點(diǎn)路線聯(lián)繪實(shí)現(xiàn)：鑒于百度地圖并不支持多點(diǎn)規(guī)劃路線，只支持兩點(diǎn)間路線的繪制，為了將多景點(diǎn)的路線規(guī)劃結(jié)果直觀的繪制在百度地圖上，首先記錄智能路線規(guī)劃算法計算出來的景點(diǎn)順序，然后將每兩點(diǎn)的路線記錄下來，再通過百度的Polyline 覆蓋物折線基類繪制接口將所有景點(diǎn)間路線按照順序渲染出來，從而完成對景點(diǎn)規(guī)劃結(jié)果的聯(lián)繪實(shí)現(xiàn)，折線基類構(gòu)造函數(shù)如下：

Polyline(points:Array[, opts:PolylineOptions])

4 結(jié)語與展望

目前旅游行業(yè)已經(jīng)擁有各種類型的旅游規(guī)劃系統(tǒng)，可以完成基礎(chǔ)的旅游路線規(guī)劃功能，但是類似于本系統(tǒng)的綜合考慮各個因素的全方位智能旅游規(guī)劃的并不多見。另外本系統(tǒng)采用蟻群算法進(jìn)行規(guī)劃可以實(shí)現(xiàn)大規(guī)模景點(diǎn)無重疊規(guī)劃，這也是其它規(guī)劃算法所不具有的優(yōu)勢和競爭力。系統(tǒng)在未來的完善過程可以通過云端并行計算進(jìn)一步是提高規(guī)劃性能，也可以通過數(shù)據(jù)挖掘技術(shù)將社交系統(tǒng)、旅游網(wǎng)站等相關(guān)平臺的用戶數(shù)據(jù)匯總分析使得旅游規(guī)劃更加科學(xué)，更加可靠。

參考文獻(xiàn)：

[1] 譚云蘭,賈金原,彭碩,等.基于Web3D的虛擬旅游關(guān)鍵技術(shù)研究進(jìn)展[J].系統(tǒng)仿真學(xué)報,2014,26(7): 1541-1549.

[2] Gambardella M, Martinoli M B A, Stützle R P T. Ant Colony Optimization and Swarm Intelligence[C]//5th International Workshop. 2006.

[3] Zheng X, Luo J, Song A. Ant Colony System Based Algorithm for QoS-Aware Web Service Selection[C]// GSEM. 2007: 39-50.

[4] 譚云蘭,賈金原,康永平,等.基于 WebVR 的井岡山虛擬旅游系統(tǒng)架構(gòu)設(shè)計[J]. 井岡山大學(xué)學(xué)報:自然科學(xué)版, 2012, 33(6): 46-50.

[5] 段海濱,王道波,朱家強(qiáng),等. 蟻群算法理論及應(yīng)用研究的進(jìn)展[J]. 控制與決策,2004,19(12): 1321-1326.

[6] 高尚. 解旅行商問題的混沌蟻群算法[J]. 系統(tǒng)工程理論與實(shí)踐, 2005, 25(9): 100-104.

[7] Bootstrap中文網(wǎng),Bootstrap2文檔[EB/OL]. [2014]. http://v2.bootcss.com/getting-started.html.

[8] Lubbers P, Albers B, Salim F, et al. Pro HTML5 programming[M]. New York, NY, USA:: Apress, 2011.

[9] 百度地圖,Baidu Map JS API[EB/OL].[2014].http:// developer.Baidu.com/map/index.php?title=Jspopular.

[10] 360百科. 墨卡托投影 [EB/OL]. 2014.http:// baike. baidu.com/view/301981.htm?fr=aladdin.

INTELLIGENT TOURISM ROUTE PLANNING SYSTEM BASED ON ANT COLONY OPTIMIZATION

HAO Biao1,*TAN Yun-lan2, WANG Wei-nian3, JIA Jin-yuan1

(1.School of Software Engineering, Tongji University, Shanghai 201804,China;2.School of Electronic Information and Engineering，Jinggangshan University, Ji’an, Jiangxi 343009, China; 3.School of Business，Jinggangshan University, Ji’an, Jiangxi 343009, China)

The tourism route planning systems are often unreasonable because of a large number of scenic spots and large differences among them. Base on the research about route planning algorithms and their implementation schemes, we proposed a solution of interactive intelligent tourism route planning system. Furthermore, we construct a platform of tourism route planning system on Browser/Server architecture, which is blended several technologies, such as Ant Colony Optimization algorithm, Baidu map API interface and Bootsrap. In addition, we also improved AC Optimization algorithm model and introduced flow grid layout. The experiment and analysis show that the system makes the route planning more reasonable and scientific because Baidu map can provide wider coverage areas, more comprehensive information and higher speed of loading.

Ant Colony Optimization algorithm; tourism route planning; interactive system; Baidu map

1674-8085(2015)01-0008-06

TP391

A

10.3969/j.issn.1674-8085.2015.01.002

2014-09-21；修改日期：2014-12-28

國家十二五計劃重大科技支撐項(xiàng)目(2012BAC11B01-04)

郝 標(biāo)(1989-)，男，河南平頂山人，碩士生，主要從事WEB相關(guān)技術(shù)研究(E-mail:Brian.Hao211@gmail.com);

*譚云蘭(1972-)，女，江西新干人，副教授，博士生，主要從事虛擬現(xiàn)實(shí),圖像處理等研究(E-mail: tanyunlan@163.com);

王偉年(1970-)，女，江西吉安人，教授，博士，主要從事旅游規(guī)劃方面的研究(E-mail: wwnian@126.com);

賈金原(1963-)，男，山東樂陵人，教授，博導(dǎo)，主要從事圖形學(xué)，分布式虛擬現(xiàn)實(shí)，Web3D，游戲引擎等研究(E-mail: jyjia@#edu.cn).