郝 標，譚云蘭，王偉年，賈金原

?

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

郝 標1，*譚云蘭2，王偉年3，賈金原1

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

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

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

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

1 系統(tǒng)架構

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

圖1 系統(tǒng)架構圖

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

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

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

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

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

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

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

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

(2)

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

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

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

Fig.2 Data process flow chart

3 用戶交互界面構建

3.1 交互前端構建

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

圖3 流式柵格布局效果

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

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

3.2.1 引入百度地圖Javascript API

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

3.2.2 提取景點坐標

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

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

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

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

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

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

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

Fig.4 Result of route planning

3.2.4 百度地圖功能改進

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

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

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

4 結(jié)語與展望

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

參考文獻：

[1] 譚云蘭,賈金原,彭碩,等.基于Web3D的虛擬旅游關鍵技術研究進展[J].系統(tǒng)仿真學報,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)架構設計[J]. 井岡山大學學報:自然科學版, 2012, 33(6): 46-50.

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

[6] 高尚. 解旅行商問題的混沌蟻群算法[J]. 系統(tǒng)工程理論與實踐, 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

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

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

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

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

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