基于ACO的智能終端旅游行程規(guī)劃系統(tǒng)設計

睢先先　宋夫華

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

?

基于ACO的智能終端旅游行程規(guī)劃系統(tǒng)設計

睢先先宋夫華

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

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

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

0　引　言

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

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

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

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

1　行程規(guī)劃系統(tǒng)設計

1.1系統(tǒng)體系架構設計

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

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

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

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

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

1.2數(shù)據(jù)庫設計

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

2　行程規(guī)劃功能詳細設計和算法實現(xiàn)

2.1系統(tǒng)體系架構設計

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

圖2　行程規(guī)劃數(shù)據(jù)流圖

2.2行程規(guī)劃模型分析

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

為了使用計算機或移動終端進行旅游行程規(guī)劃，有必要把行程規(guī)劃所涉及到的元素及元素之間的關系轉化成完全圖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)為景點關閉時間。

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

(4)

Tt≤Tmax

(5)

Tc≤Cmax

(6)

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

(7)

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

2.3行程規(guī)劃算法設計

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

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

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

(1) 行程路線的構建

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

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

(8)

其中，C是一個常數(shù)。

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

(9)

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

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

(10)

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

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

j=argmaxpk(i,j)

(12)

(2) 路徑信息素的更新

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

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

(13)

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

(14)

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

根據(jù)行程規(guī)劃算法設計，算法實現(xiàn)的流程如圖3所示。

圖3　行程規(guī)劃算法流程圖

3　智能終端行程規(guī)劃軟件實現(xiàn)

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

圖4　客戶端軟件結構

3.1需求交互功能模塊實現(xiàn)

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

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

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

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

3.2地圖展示功能模塊實現(xiàn)

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

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

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

圖7　行程規(guī)劃結果　　　圖8　公交路線信息

在該功能模塊實現(xiàn)時，根據(jù)需求對百度地圖功能做了以下改進：

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

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

4　結　語

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

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

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

[4] 劉振波, 方志剛, 徐潔. 改進的蟻群算法在智能導游系統(tǒng)路徑優(yōu)化中的應用[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服務平臺關鍵技術及旅游規(guī)劃引擎的研究[D]. 北京：北京郵電大學, 2007.

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

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

[13] 范懷寧. Android開發(fā)精要[M]. 北京: 機械工業(yè)出版社, 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)；國家科技部創(chuàng)新基金項目(10C26213304114)；浙江省科技廳國際合作專項(2012C24030)。睢先先，碩士生，主研領域：智能優(yōu)化，計算機應用等。宋夫華，副教授。

TP311

A

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