基于ACO的智能終端旅游行程規劃系統設計

睢先先　宋夫華

(中國計量學院機電工程學院　浙江 杭州 310018)

?

基于ACO的智能終端旅游行程規劃系統設計

睢先先宋夫華

(中國計量學院機電工程學院浙江 杭州 310018)

旅游行程規劃對自助游客來說是一件非常繁瑣的事情。針對該問題，對行程規劃模型、行程規劃算法和實現方案進行研究，構建城市內的旅游行程規劃服務平臺。結合蟻群優化ACO(Ant Colony Optimization)算法、百度地圖API、Android開發、WebService和JSON等技術，改進ACO算法，實現了基于Android智能終端的城市內自助游行程規劃系統。實驗結果表明，實現的智能終端行程規劃系統在城市區域內的旅游行程規劃方面具有規劃效率高、規劃結果合理、信息展示直觀、使用方便等優點，具有一定的推廣價值。

旅游行程規劃ACO算法百度地圖Android平臺

0　引　言

合理的行程規劃對自助游客擁有輕松愉快的旅游體驗是必要的。進行行程規劃的一般過程包括在各種旅游網站上搜集大量的旅游信息，然后決定去游玩哪些景點、景點游玩順序、游玩時間和景點之間轉移的交通路線等，通常需要花費大量的時間和精力，最終得到的結果卻往往不盡如人意。因此，開發一種能夠幫助自助游客規劃合理行程路線的工具顯得非常重要。

互聯網和新一代通信技術的出現和迅速發展為在線動態規劃行程提供了可能，同時也促進很多學者對如何規劃合理的行程路線進行了大量研究，大致可分為兩類。一類是從數學理論角度進行分析，旅游行程規劃屬于NP難題，其解決方法有原始的精確求解法和新興的啟發式算法、智能優化算法等。如文獻[1]提出采用遺傳算法求解最短路問題，文獻[2]在此基礎上，對大城市內具有時間約束的行程規劃問題進行了分析，提出基于嵌套結構的行程規劃方法，主程序和子程序中都采用遺傳算法去尋找優化路線，最后根據游客需求和選擇的旅游景點自動生成一條相關的旅游行程路線；文獻[3,4]在蟻群算法基礎上分別結合2-opt算法和模擬退火算法優化旅游路線，從而為該問題的研究積累了十分豐富的經驗。

另一類研究從應用分析角度進行，這類研究著重于在優化算法的支撐下，實現一個旅游行程規劃系統，如文獻[5]利用數學模型和交互式多目標技術設計了個人旅游路線規劃系統，可以生成一條基于用戶選擇的行程路線；文獻[6]實現了一個基于網絡和手機端的個性化旅游路線推送系統，系統可根據用戶一天可以游玩的景點數量、景點游玩時間和開放時間等參數，采用改進的啟發式搜索方法推薦出一條近似優化的行程路線；文獻[7]從團隊定向問題角度對行程規劃進行分析，把搜索優化解的過程分成兩個階段，預處理階段采用MapReduce框架探索出多個一日游路線，下一階段從中選擇優秀的行程路線進行組合排序，推薦給自助游客；文獻[8]開發了一個為游客提供城市旅行規劃的系統。然而，這些研究大部分是通過理論實驗進行的，并沒有基于真實的數據進行實驗。在實際情況中，通常包括大量的景點和復雜的交通網絡，潛在解空間的搜索范圍廣而且復雜。

本文通過對旅游行程規劃和蟻群優化算法的研究，設計了城市區域內能滿足自助游客多方面需求、可以進行多景點路線規劃的Android智能終端旅游行程規劃系統。系統采用三層體系架構，集成了行程規劃模型、蟻群優化算法、WebService、JSON、Android平臺開發和百度地圖API等理論與技術。相對于傳統的旅游服務內容，該系統旨在為游客提供智能行程規劃服務，屬于智慧旅游[9]建設的智慧服務體系中不可缺少的一部分，能夠更好滿足游客個性化的旅游需求。

1　行程規劃系統設計

1.1系統體系架構設計

行程規劃系統基于一云多屏的智慧旅游公共服務平臺理念，采用結構清晰、明確的三層架構體系，如圖1所示。該架構可以降低系統各層之間的依懶，減輕系統后期的維護成本和維護時間，整體具有較強的擴展性、易用性和開放性。其中，表現層包括少部分的邏輯代碼，主要負責與用戶進行交互，接受用戶的請求及數據返回；業務邏輯層屬于系統架構的核心，是連接用戶端和數據庫的橋梁，主要負責按照業務邏輯對數據庫進行操作，并將數據結果傳給表現層；數據庫層主要負責解決大數據存儲、數據高并發訪問、數據分類、加工、封裝和數據服務問題。

圖1　系統架構圖

系統應用服務器采用Tomcat部署WebService服務，提供行程規劃和用戶信息管理等服務。應用邏輯被封裝到了應用服務器中，當應用邏輯發生變化時，僅需修改服務器中的程序，用戶端的應用程序不必更新。用戶端與數據庫服務器通過應用服務器進行連接，降低系統資源的開銷，進而提高系統的可靠性和安全性。

系統數據庫采用MySQL構建，存儲從云端獲取的興趣點基礎數據信息、興趣點間的交通數據和用戶數據信息，并提供數據備份和安全管理等功能。

該系統面向游客提供包括電腦、Android/iOS智能手機、PAD等多種形式的服務終端。用戶端通過訪問開放的應用程序接口，從興趣點數據庫獲取景點信息展示給用戶，并從云端或交通信息數據庫搜集用戶偏好的景點交通信息，采用蟻群優化算法智能生成旅游行程路線，最后在百度地圖上將規劃結果直觀、友好地展示給用戶，極大地提升了用戶體驗。

1.2數據庫設計

根據系統架構分析，建立了“TRPData”數據庫，主要包括景點信息、交通信息、用戶信息和城市信息等多個實體。下面僅對景點信息和交通信息中主要的表進行說明。景點信息表用于存儲景點的基本屬性信息，字段包括身份id、景點名稱name、地址address、電話tel、星級star、門票價格price、開放時間timeframe、經度lonx、緯度laty和最佳游玩時間playtime。交通信息表用于存儲景點之間的交通信息，字段包括起點from、目的點to、旅途時間traveltime和旅途費用travelcost。

2　行程規劃功能詳細設計和算法實現

2.1系統體系架構設計

業務邏輯層承載著系統主要功能模塊的實現，行程規劃模塊作為系統的核心功能，主要向用戶提供行程規劃服務，其詳細設計也是針對業務邏輯層展開。如圖2所示是行程規劃模塊的數據流圖，系統根據用戶輸入的基本信息和從交互平臺搜集的用戶偏好信息，采用行程規劃算法進行行程規劃，最后將規劃結果展示給用戶。

圖2　行程規劃數據流圖

2.2行程規劃模型分析

旅游行程規劃是指根據游客的旅游需求和個人偏好，搜索旅游綜合信息數據庫中滿足條件的相關信息要素，并對偏好景點進行規劃排序，生成一條合理的行程路線。

為了使用計算機或移動終端進行旅游行程規劃，有必要把行程規劃所涉及到的元素及元素之間的關系轉化成完全圖G={S,E}進行分析，其中S={si|i=1, 2,…，n}代表游客偏好的景點集合，E={eij|i,j∈S}代表兩個景點間的旅游交通路線構成的邊集合。對于任意頂點si，t(i)表示在景點i的游玩時間，c(i)表示對應的游覽費用；對于任意邊eij，t(eij)表示從景點i到景點j的旅途時間，c(eij)表示對應的旅途費用c(eij)。

用R={s1,s2,…，sn-1，sn}表示一條滿足要求的行程路線，行程所需的旅游花費C和旅游時間T分別如式(1)、式(2)所示：

(1)

(2)

其中d(i)表示提前到達目的地景點時產生的等待時間，如式(3)所示：

(3)

其中tp(i)為景點關閉時間。

以旅游時間最小化和旅游花費最小化的聯合來評價可選行程路線R的優劣，目標函數Φ(R)的表達式如下：

(4)

Tt≤Tmax

(5)

Tc≤Cmax

(6)

to(i)≤t(i)≤tp(i)

(7)

其中ω0是衡量旅游時間與旅游費用之間關系的一個權重系數。Tmax代表游客可支配的旅游時間，Cmax代表根據游客需求所得的費用預算。式(5)是對旅游時間的約束；式(6)是對旅游花費的約束；式(7)是對每個景點游玩時間的約束，以確保為游客提供的行程安排落在景點開放時間的范圍之內。

2.3行程規劃算法設計

根據上述分析可知，行程規劃實質上是一類含有多個約束條件的組合優化問題，高效、科學、強壯的算法是解決問題的關鍵[10]。為生成合理的行程路線，本系統采用ACO算法進行路線尋優。

ACO算法是一種基于螞蟻群體覓食行為的啟發式優化算法[11,12]，通過模擬螞蟻群體使用信息素軌跡進行交流判斷，成功找到較短覓食路線的過程，對問題可能的解空間進行搜索優化。算法實現的過程主要包括：螞蟻群體構建問題解和路徑上的信息素更新兩個步驟。首先，螞蟻個體會根據路徑上的信息素濃度和啟發式信息，并結合相應的狀態轉移規則，判斷每一步的轉移方向。然后算法根據問題的目標函數對每個螞蟻形成的路線進行評價，更新路徑信息素。經過反復迭代搜索，算法最終收斂于最優的螞蟻個體，也就找到了問題的優化解。

使用螞蟻個體模擬游客進行旅游行程路線選擇的過程中，把游客通常關心的旅游時間、景點開放時間、費用預算等需求參數設計到算法模型中去，對ACO算法進行改進。

(1) 行程路線的構建

假設螞蟻k(k=1, 2,…,m)在當前節點i選擇下一個游覽景點j，所有可選的景點存放在集合Rk中。改進的算法模型中，螞蟻個體不僅感知路徑上的信息素強度τ(i,j)和路徑啟發式信息η(i,j)，而且還會判斷景點j開放時間段的約束ω(u)對其吸引度，ω(u)的表達式為如式(8)所示：

ω(u)=C/(tp(u)-to(u))

(8)

其中，C是一個常數。

螞蟻個體計算可選景點的選擇概率時采用改進的狀態轉移規則，如式(9)所示：

(9)

其中，參數α、β、ν分別表示信息素濃度、啟發式信息和開放時間約束的相對重要性。顯然，在相同條件下，景點開放時間較短的景點將會被優先選擇進行游覽。

同時，為了兼顧游客的多重需求，將路徑啟發式信息η(i,j)從時間和費用兩個方面重新設計，改進后的啟發式信息計算模型如式(10)、式(11)所示：

(10)

(11)式中參數γ1、γ2分別表示時間和花費的重要程度，管理員可以根據游客的需求對其取值進行調節。顯然，由于各景點的最佳游覽時間和旅游費用不同，路徑(i,j)和(j,i)上啟發式信息也相應不同。螞蟻群體在構建行程路線時交替使用兩種啟發式信息，旨在尋找到一條滿足時間和費用聯合最小化的行程線路。

目標節點j的確定方式采用偽隨機比例規則，首先根據式(9)求得各景點的選擇概率，然后產生一個[0,1]內均勻分布的隨機變量q，與控制參數q0(q0∈[0,1])進行比較。如果q≤q0，下一個目標景點j采用確定性方式進行選擇，由式(12)確定；如果q>q0，根據已有的選擇概率，采用輪盤賭的選擇方法確定下一個目的景點j。

j=argmaxpk(i,j)

(12)

(2) 路徑信息素的更新

螞蟻群體構建完成各自的行程路線后，進行路徑信息素的更新，用ρ(0<ρ≤1)表示路徑信息素衰減度，具體更新規則為：

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

(13)

式中Δτ(i,j)表示螞蟻個體構建的行程路線R上信息素增量，計算公式為：

(14)

式中Φ(R)為上一節行程規劃模型分析得出的評價路線R的目標函數。

根據行程規劃算法設計，算法實現的流程如圖3所示。

圖3　行程規劃算法流程圖

3　智能終端行程規劃軟件實現

Android操作系統[13]是一個開放的平臺，近年來得到了快速發展，在市場份額中占有很大比重。因此，本文以Android開發平臺為例，實現杭州市內旅游行程規劃系統的用戶端，設計出一款界面布局合理、簡潔大方、功能完整、符合用戶體驗的軟件，方便用戶隨時隨地規劃行程。軟件的結構如圖4所示，主要包括需求交互功能和地圖展示功能兩個模塊。

圖4　客戶端軟件結構

3.1需求交互功能模塊實現

需求交互功能包括輸入基本需求、景點信息展示兩個界面，主要由界面組件Activity、列表組件ListView和通信組件Intent及相關技術開發實現。界面展示信息通過Android客戶端軟件訪問遠程景點數據庫獲取。由于平臺本身沒有提供直接調用WebService服務的庫，開發時采用第三方的類庫Ksoap2實現調用WebServie服務，服務器以JSON對象形式返回數據結果給客戶端。JSON對象具有數據量小、可讀性強等特點，客戶端解析時也不必用額外的類進行處理。

此外，服務器端處理數據時通過在內存中分頁來提高運行效率，將結果快速展示到用戶界面，并采用緩存技術來提高用戶的使用體驗。

基本需求確定界面運行效果如圖5所示，用戶輸入基本需求后，點擊“選擇景點”按鈕，提交需求信息，系統跳轉至景點信息展示交互界面，運行效果如圖6所示，界面上的“選擇”和“已選”按鈕用來記錄用戶的偏好選擇。點擊界面右上角的“查看線路”按鈕，客戶端向系統服務端發送行程規劃的請求，服務器根據請求內容，從系統數據庫搜集行程規劃所需的偏好景點游玩時間、開放時間、經緯度位置、景點間旅途時間和旅途費用等信息，并調用行程規劃算法模塊進行路線規劃，在地圖上顯示返回的行程路線結果。

圖5　輸入基本需求　　　圖6　景點信息展示

3.2地圖展示功能模塊實現

地圖展示功能模塊主要用于展示行程規劃結果和提供景點間交通線路搜索功能。該模塊的實現需要調用百度地圖Android SDK，它是一套開放給開發者的應用程序接口，用于Android系統移動設備的地圖應用開發，可提供基礎地圖、地圖覆蓋物、POI檢索、線路規劃等功能。地圖控件的引入及所有相關操作均在DituActivity類中實現。

其中，為景點添加圖形覆蓋物是顯示行程路線詳情的重點，首先根據用戶與系統的交互結果獲取行程規劃的路線信息，然后依次對各個景點添加自定義的覆蓋物圖標，最后根據添加順序在地圖上實現多點劃線。重寫自定義圖標的點擊事件onMarkerClick，當用戶點擊時，可以獲取對應景點的信息，運行效果如圖7所示。

景點間線路搜索功能采用地圖搜索模塊RoutePlanSearch開發實現，將線路搜索的城市區域設置為杭州市，并分別提供了公交、駕車和步行線路搜索功能，運行效果如圖8所示。

圖7　行程規劃結果　　　圖8　公交路線信息

在該功能模塊實現時，根據需求對百度地圖功能做了以下改進：

(1) 行程路線繪制：由于百度地圖SDK提供的多邊形覆蓋物是一個封閉的幾何圖形，在使用多邊形覆蓋物選項類PolygonOptions繪制行程線路時，改進該類方法對多邊形閉合邊框的設置，按照行程規劃結果，將起點到終點的景點線路繪制出來。

(2) 更改地圖中心位置：由于百度地圖在移動設備屏幕中心顯示的默認位置是北京市，而本文是以杭州市的行程規劃為例。為了調用地圖模塊時可以直觀地看到杭州市內的行程路線結果，首先獲取行程規劃結果起點的經緯度坐標值，然后使用MapStatusUpdate將地圖中心狀態位置設置為行程路線起點。

4　結　語

目前市場上的一些旅游網站可以提供基本行程規劃功能，但類似于本系統綜合考慮游客出游時間、費用和景點開放時間等多種需求的行程規劃模型還不多見。另外，本系統采用蟻群智能優化算法規劃行程路線，可以承受問題規模不斷擴大帶來的計算壓力，這也是其他優化算法不具備的優勢。

經過實驗，系統運行正常，并且已成功應用到杭州旅委的智慧旅游手機app中，提升了軟件的計算效率和導航精度，能夠滿足游客規劃行程的需要。系統可以通過Web服務器集群技術和數據庫分庫分表進一步增強性能，并與知名旅游網站結合，實現數據共享，進而規劃出更加科學和人性化的行程路線。

[1] Abbaspour R A, Samadzadgan F. A solution for Time-Dependent Multimodal Shortest Path Problem[J]. Journal of Applied Sciences, 2009, 9(21): 3804-3812.

[2] Rahim A Abbaspour, Farhad Samadzadegan. Time-dependent personal tour planning and scheduling in metropolises[J]. Expert Systems with Applications, 2011, 38(10): 12439-12452.

[3] 胡國軍, 祁亨年, 董峰，等. 一種改進蟻群算法的研究和旅游景區路徑規劃問題的求解[J]. 計算機應用研究, 2011, 28(5): 1647-1650.

[4] 劉振波, 方志剛, 徐潔. 改進的蟻群算法在智能導游系統路徑優化中的應用[J]. 江南大學學報:自然科學版,2008,7(5):561-563.

[5] Beatriz Rodriguez, Julian Molina, Fatima Perez, et al. Interactive design of personalized tourism routes[J]. Tourism Management, 2012, 33(4): 926-940.

[6] Gavalas, D, Kenteris M, Konstantopoulos C, et al. Web application for recommending personalized mobile tourist routes[J]. IET Software, 2012, 6(4): 313-322.

[7] Chen G, Wu S, Zhou J, et al. Automatic Itinerary Planning for Traveling Services[J]. IEEE Transcations on Knowledge and Data Engineering, 2014, 26(3): 514-527.

[8] Pieter V, Wouter S, Greet V B, et al. The City Trip Planner: An expert system for tourists[J]. Expert Systems with Applications, 2011, 38(6): 6540-6546.

[9] 張凌云, 黎巎, 劉敏. 智慧旅游的基本概念與理論體系[J]. 旅游學刊, 2012, 27(5): 66-73.

[10] 劉傳昌. Web服務平臺關鍵技術及旅游規劃引擎的研究[D]. 北京：北京郵電大學, 2007.

[11] Dorigo M, Stutzle. 蟻群優化[M]. 張軍,胡曉敏,羅旭耀,等譯. 北京: 清華大學出版社, 2007.

[12] Cook W J. 迷茫的旅行商：一個無處不在的計算機算法問題[M]. 北京: 人民郵電出版社, 2013.

[13] 范懷寧. Android開發精要[M]. 北京: 機械工業出版社, 2012.

DESIGNING ACO-BASED TRAVEL ITINERARY PLANNING SYSTEM WITH SMART TERMINAL

Sui XianxianSong Fuhua

(College of Mechanical and Electrical Engineering, China Jiliang University, Hangzhou 310018, Zhejiang ,China)

Travel itinerary planning is a very complicated issue for self-service travellers. In light of this problem, we studied the itinerary planning model, itinerary planning algorithm and implementation schemes, and constructed a service platform for urban travel itinerary planning. In combination with a variety of technologies such as ant colony optimisation (ACO), Baidu map API, Android development, WebService and JSON, etc., we improved the AOC and realised the Android smart terminal-based urban self-service travel itinerary planning system. Experimental results showed that the implemented itinerary planning system with smart terminal has the advantages of high planning efficiency, reasonable planning results, intuitive information display and easy in use for travel itinerary planning within city region. It has certain popularisation value.

Travel itinerary planningAnt colony optimisationBaidu mapAndroid platform

2015-04-21。國家自然科學基金項目(61272315)；國家科技部創新基金項目(10C26213304114)；浙江省科技廳國際合作專項(2012C24030)。睢先先，碩士生，主研領域：智能優化，計算機應用等。宋夫華，副教授。

TP311

A

10.3969/j.issn.1000-386x.2016.09.055