基於pda的旅遊智能行程導航系統的製作方法

2023-09-15 12:06:20

專利名稱：基於pda的旅遊智能行程導航系統的製作方法
技術領域：
本發明屬於旅遊信息化領域，具體涉及基於GPS的位置信息處理，實時信息查詢、 旅遊行程規劃、智能導航和應急救援等。
背景技術：
自助行程導航的關鍵技術就是GIS導航技術，目前國內外在GIS導航技術上已經 比較成熟。在地圖匹配技術中，可以建立以道路為約束條件的卡爾曼濾波模型，利用車輛行 駛的位置和方向信息把車輛匹配到正確的道路上。 在GPS方面，由於受GPS噪聲的影響，實際測量的位置往往帶有偏差。針對這個問 題，可以採用基於模糊邏輯理論的綜合地圖匹配算法，該算法充分考慮了道路幾何特性以 及GPS測量數據的偏差特性。在地圖匹配的實時性、魯棒性及匹配精度上，可以依據車輛運 動的連續性，引入道路網絡的分塊思想，並利用車輛行駛的位置、方向信息及實際道路網絡 的拓撲特性，可以提出一種時間複雜度為0(c)的快速地圖匹配算法。 基於GIS的最短路徑求解也是一個關鍵技術，在最短路徑求解中Dijkstra算法是 最經典的最短路徑算法之一，針對GIS特殊問題，基於面向對象的改進算法，可以大大降低 內存消耗，搜索效率也明顯提高。同時針對^算法，可以利用蟻群算法改進。基於人工智 能的A啟發式搜索算法藉助限制條件對預搜索節點進行評估，通過用二叉堆對包含評估值 的預搜索節點進行排序，該算法複雜度僅為O(n)。 在應急救援方面，針對終端的不同能力，可以接收文本，語音，圖像等方式的救援， 接收到求救者的救援信息後，採用機器學習的方法對救援信息進行分類存儲，並向相關部 門轉發。然後採用基於GIS地圖匹配的相關算法給出救援指導路線。 本發明集上述技術的優點於一體，提出了一種新的專門針對旅遊行業的基於PDA 的旅遊智能行程導航系統。

發明內容
本發明開發了一個基於PDA的智能導航系統，包括GPS的位置信息處理，實時信息 查詢、旅遊行程規劃、智能導航和應急救援等。系統由五部分構成，分別是數據搜索與查 詢、旅遊行程規劃、智能導航、應急救援與系統配置。 1.數據搜索是基於垂直搜索技術的信息查詢，可以提供與遊客旅遊相關的信息搜 索，例如餐飲、賓館住宿、景區信息、景區天氣等信息的查詢；
2.旅遊行程規劃部分提供規划行程和查看行程； 3.智能導航主要實現GPS數據獲取與處理、用戶位置跟蹤、用戶軌跡顯示、路線規 劃、地圖瀏覽和智能語音導航； 4.應急救援是指在突發事件發生的情況下，遊客通過本系統將準確的向相關部門 (120， 110等)求援，本系統將會在相關部門實施救援以前給需要救援的遊客A發送必要的 避險和自救知識。系統將搜索遊客信息庫，查找求救遊客A附近是否有醫生B或者救援知
3識比較豐富的遊客C，如果有，系統會將等待救援遊客A的位置和其情況發送給B和C，請他 們協助救援。


圖1為系統整體結構； 圖2為系統詳細結構； 圖3為數據搜索框架； 圖4為旅遊行程規划算法； 圖5遊客位置跟蹤與軌跡顯示； 圖6減小路段的弧度數 圖7為兩點路線規劃； 圖8為多點間路線規劃； 圖9為景點範圍確定； 圖10為景點索引的建立； 圖11為智能語音導航算法； 圖12為應急救援框架。
具體實施例方式
系統分為PDA端和伺服器端兩部分，兩者通過網絡進行通信，PDA作為整個系統的 前臺，是系統與用戶交互的主界面，伺服器端完成信息的存儲與查詢以及對資料庫中信息 的管理，系統整體結構如圖1所示。PDA端功能模塊如圖2所示，該系統主要由五大部分構 成，分別是數據搜索與查詢、旅遊行程規劃、智能導航、應急救援與系統配置。
1.數據搜索 數據搜索是基於垂直搜索技術的信息查詢，可以提供與遊客旅遊相關的信息搜 索，例如餐飲、賓館住宿、景區信息、景區天氣等信息的查詢，其技術方案如圖3所示。下面
分別介紹各子模塊的功能。
1. 1餐飲美食模塊 該模塊是用於向用戶提供一個查詢各城市各地區餐飲美食的平臺。用戶根據個人 需要輸入要查詢的條件，給出要查詢的關鍵字、城市及地區、菜系的名字以及在某個地區範 圍以內，然後提交給伺服器，伺服器根據用戶的輸入條件查詢資料庫，將滿足用戶需求的餐 飲美食反饋給用戶客戶端，以列表的形式展示給用戶。用戶還可以查看查詢結果中各個餐 飲美食選項的具體信息，包括各餐廳的名稱、地址及電話等信息。遊客在主界面中輸入查詢 條件，經過後臺伺服器處理後將在PDA上顯示符合條件的數據，在遊客選擇一個餐廳後點 擊"詳細信息"按鈕會出現餐廳的詳細信息，其中包括餐廳的名稱、地址、電話、菜系、主要菜 單和圖片等相關信息。
1. 2賓館住宿模塊 該模塊是向用戶提供一個查詢各城市地區的賓館住宿情況的平臺。用戶根據個人 需要輸入各項要查詢的條件，給出關鍵字、城市地區的名字及所在的地址範圍，然後將這些 條件信息提交給伺服器端，伺服器根據這些條件查詢資料庫，將滿足用戶需求的賓館住宿情況反饋到用戶客戶端，以列表的形式展示給用戶。用戶可以查看各個賓館的具體信息，包 括賓館的名稱、地址、電話及等級等信息。
1.3景區搜索模塊 該模塊包含三個子模塊，分別為按區域搜索模塊、按距離搜索模塊和按名稱搜索 模塊。在各個子模塊，用戶可以分別輸入要搜索的條件(區域名稱、距離範圍、景區名稱)， 然後提交給伺服器端，伺服器端將滿足用戶需求的景區信息以列表的形式反饋到用戶客戶 端。用戶可以查看查詢結果中各個景區的具體信息(名稱、地址、最低價格、電話及景區的 詳細信息)。 1. 4天氣查詢模塊 該模塊負責向用戶提供目前所在景區近幾天的天氣情況。
1. 5景區信息查詢模塊 該模塊負責向用戶提供目前所在景區的詳細信息介紹。系統會藉助GPS準確定位
當前遊客所在位置，確定當前在哪個景區，然後系統會將該景區的近兩天的天氣情況及景
區的介紹反饋給遊客。 1. 6景區周邊信息搜索模塊 該模塊包括定位搜索和範圍搜索兩個子模塊。在定位搜索子模塊，用戶輸入一個 搜索關鍵字，然後系統會從資料庫中搜索到與該關鍵字相關的地點，然後用戶根據需要選 擇要去的目標地點，然後系統會在地圖上顯示出該目標地點。在範圍搜索模塊，用戶根據需 要提供一個範圍信息以及選擇要去的地點，然後系統會在地圖上顯示出該目標地點並反饋 給用戶。遊客輸入要搜索的關鍵字，然後提交給系統，系統會搜索到與該關鍵字相關的周邊 地點，搜索結果以列表的形式展示，接下來遊客選擇要去的目標地點，然後系統會在地圖上 標示出該地點的位置，然後反饋給用戶。在模塊範圍搜索中，遊客輸入一定的搜索範圍，並 選擇要去的目標地點，然後進行搜索。同樣，系統也會將在地圖上標示出該地點的位置，然 後反饋給用戶。 1. 7景區視頻搜索模塊 該模塊負責為用戶提供景區的視頻信息，用戶可以查看所有視頻的列表信息，包 括各個視頻的名稱和位置，對於列表中的每個視頻，用戶均可播放觀看。用戶也可查看每個 視頻的具體信息(名稱、位置、大小、詳情介紹)。系統會顯示出可以為用戶提供的視頻列 表，遊客可以選擇一視頻進行播放觀看，同時遊客還可以查看各個視頻的詳細信息，包括視 頻的名稱、位置、大小及詳情信息。
2.旅遊行程規劃 該部分設計包括規划行程和查看行程兩個模塊。用戶根據個人需要輸入條件信 息，然後提交給系統，系統會進行資料庫的相關操作，將滿足用戶輸入條件的景區集合以列 表的形式反饋給用戶，用戶根據個人需要還可對此列表添加和刪除景區。列表信息確認以 後，系統會為用戶制定一套具體的行程規劃方案，還會根據用戶的需求條件為用戶安排具 體的旅遊路線。具體算法如圖4所示。
2. 1規划行程模塊 該模塊負責根據用戶的個人需求條件為用戶規划具體的旅遊行程。用戶要提供的 條件信息包括計劃旅遊天數、計劃門票開銷、計劃旅遊人數、旅遊的開始時間、出行方式、景區級別區域以及距離限制。然後這些信息將會提交給系統，系統會操作資料庫將滿足用 戶需求的景區篩選出來，以列表的形式反饋給用戶。用戶根據個人需要可以對搜索得到的 景區列表增加和刪除景區，然後將滿意的列表提交給系統，系統根據此列表和用戶的一些 條件為用戶安排具體的行程規劃。同時，系統也根據用戶的需求為用戶安排好了具體的旅 遊行程路線，為用戶提供了很大的便利。如果用戶滿意可以保存行程。遊客給出行程規劃 的條件後，系統會將運算後結果顯示出來。如果遊客對系統給出的景區集合滿意，點擊"規 划行程"會得到每天的行程安排，以及計劃完成情況。
2. 2查看行程模塊 該模塊查看系統為用戶制定的行程規劃。根據用戶提供的條件信息，系統為用戶 制定了每天的旅遊行程安排，用戶可以操作查看每天的規劃，並且可以查看每一個景區的 具體旅行路線。
3.智能導航 智能導航主要包括GPS數據獲取與處理，用戶位置跟蹤，用戶軌跡顯示，路線規 劃，地圖瀏覽和智能語音導航。其中GPS數據獲取與處理是其他各子模塊的基礎。用戶位 置跟蹤，用戶軌跡顯示，路線規劃和智能語音導航都是基於遊客位置的導航。系統可以顯示 遊客的位置和軌跡，同時在上下導航欄上給出了目前所在景點，和系統規劃的下一個計劃 景點，值得注意的是，該系統同時提供語音導航的功能。
3. 1位置跟蹤與軌跡顯示 位置跟蹤與軌跡顯示是指在PDA終端上實時顯示遊客的位置和旅遊路線，該功能 將有利於遊客對自己的位置進行定位，查看已經遊玩過的景點。其具體算法流程如圖5所 示。遊客的位置信息與軌跡信息將隨著GPS數據的刷新同時刷新。
3. 2路線規劃 路線規劃主要包括兩點間路線規劃和多點間旅遊順序規劃兩個子模塊，其中兩點 間路線規劃是一個求解前Kth條最佳路線的規劃問題，多點間旅遊順序規劃是一個TSP問 題。景點之間的路線規劃有一個合理性的問題。從用戶角度考慮，合理性應該包括路線趨 於最短；規劃的路線中應儘可能少地包含用戶已經到過的景點；規劃的路線應儘量避開目 前人流量較大的景點。針對以上三個問題，對景區中景點的信息存儲採用如表1所示的格 式。 表1景點信息結構
景點ID相鄰ID遊玩次數目前人數
12，30300
21，51750
n2， n_3， n_l0456
6
在計算兩景點之間的距離時，除了考慮兩景點間的實際距離外，還要將"目前人 數"和"遊玩次數"兩個欄位的信息進行加權處理。 假設景點a對遊客的承載量為^(")，目前的旅遊人數為9 (a)，則
景點a可達
;a)S2x—a)景點a半可達 (1) S3xcT(a)景點a備選 e(a) S 4 x htO)景點a不可達
在路線規劃中，景點a按照公式(1)式來決定是否在路線中出現。
如果景點a與景點b之間的路線弧度過大，本文採取在路段的拐點處添加一個臨 時節點來減小路段的弧度數。如圖6所示，在添加臨時結點c'之前，景點a到景點b的路 線為圖6中的路線"l"，添加臨時結點c'後，規劃的路線為"2"和"3"，更接近於實際路線。
在兩點規劃中，由GPS為用戶定位當前所在的景區及景點作為出發景點(遊客也 可以另外重新選擇出發景點)，然後由遊客選擇要去的目標景點，並提交給系統。系統會反 饋給用戶幾條可供選擇的旅遊路線，然後遊客隨意選擇一條路線後，系統會將線路標示在 電子地圖上。兩點間路線規划算法如圖7所示。 多點間旅遊順序規劃是指遊客在到達某個景區i後，由系統按照蟻群算法對該景 區所有景點進行規劃，例如，景區i有{Tl， T2， T3， T4}四個景點，蟻群算法規劃後將給出一 個順序(T2，T4，Tl，T3h遊客可以對該順序進行調節。遊客滿意後保存規劃結果，其結果將 在智能語音導航中使用。該算法流程如圖8所示。 其中蟻群算法(Ant Colony Algorithm)是一種模擬進化算法，該算法由意大 利學者M. Dorigo、 V. Maniezzo、 A. Colorini等人首先提出，它是一種應用於組合優化 問題的啟發式搜索算法，該算法的基本思想是設有m個城市，n只螞蟻，採用dij表示 城市i到城市j之間的距離，在歐氏TSP中，dij為i到j之間的歐氏距離，即dij = [(xi-xj) 2+ (yi-yj) 2] 1/2，螞蟻選擇下一個城市的依據主要有兩點 t u (t)是在t時刻城市i到城市j之間的路徑上的殘餘信息強度，由算法本身提 供信息；nij(t)是由城市i轉移到城市j的啟發信息，在TSP問題中一般取Jlij(t) =1/ dij， Pi/a)表示在時刻t螞蟻k由城市i轉移到城市j的概率，其中
. 0 , 否則 其中Tablek表示螞蟻k下一步允許行進的城市集合，它隨螞蟻k的行進過程而動 態改變。
、j(t)隨時間的推移會逐步消逝，用P表示它的消逝程度。螞蟻選擇轉移到哪 個城市採用偽隨機概率選擇規則。按照這種規則，每當螞蟻要選擇轉移的城市時，就產生一 個在[O，l]範圍內的隨機數，根據該隨機數按下列公式確定螞蟻轉移的方向。
argmaxj[r(!',/)I;Xz',力l" }若q 一 ( 3 )
S 否則 其中，q為一個在區間
內的隨機數，q0為
內的一個參數。 這樣，經過m時刻，螞蟻走完所有的城市，即完成了一次循環。此時根據下式對各
路徑上的信息素進行更新 ti j ( t + 1 ) = ( 1 - p) ti j ( t ) + A
(4) 其中
(5)
△ T 表示螞蟻k在本次循環中在城市i和城市j之間的路徑上留下的信息素。
M. Dorigo介紹了三種不同的實現方法，分別稱為Ant Cycle,Ant Density禾PAnt Quantity,
具體表達式分別為
* f義,如果螞蟻k在時刻t和t + l之間經過ij y 0，否則
T"(O)
其中Q是常數，Lk表示第k只螞蟻在本次循環中所走路徑長度. =C。
在初始時刻
A:
fg，如果螞蟻k在時刻t和t + l之間經過ij I 0，否則
Ar
,如果螞蟻k在時刻t和t + l之間經過ij
0，否則
考慮到實際應用，本發明對基本蟻群算法做了一些改進，提出了 "偶遇算法"，其描
述如下 ^， ， h ，仏l h j w隊w鬥w p一」取w m裡。圓v w w z "，且丄Gki ' , '丄w O，且Tableki U Tablekj = T，則結束螞蟻i和螞蟻j的旅程，並記下這兩隻螞蟻的旅遊路 線。其中Tableki為第ki只螞蟻未搜索的城市表，Tablekj為第kj只螞蟻未搜索的城市
設城市Cm在t時刻被訪問的螞蟻的數量Sum (Ant) > 2，且Tableki n Table 在螞蟻進行多次週遊中，路徑最短的螞蟻才更新信息素。在一次週遊中，選擇一個 城市後，計算當前路徑長度，如果長度超過本次循環已得到的最小值，即結束此次週遊。這 樣可以進一步減短計算時間。加入偶遇算法後的蟻群算法描述如下 1)初始化變量C，NC_max， a ， p ，Q isEND。其中C是各點的坐標，NC_max是最大 循環次數，isEND標誌螞蟻是否結束週遊。
2)將m只螞蟻隨機放到n個城市上 3)For(int
2 ;i < = n ;i++)〃n個城市4) {
5) For(intj = 1 ;j < = m ;」++)〃111隻螞蟻
6) {
7) If ( ! isEND[j])
8) 按照公式(1)計算螞蟻j到城市i的概率。
9) }
10) If(偶遇算法(i))
11) isEnd = true ^
12) }
13) 計算最佳路線
14) 更新信息素
15) 輸出結果
可以看出，當兩隻螞蟻在某城市偶遇後就結束旅程，從而可以縮短算法的計算時











間。 在旅遊順序規劃模塊中，由GPS為用戶定位當前所在的景區，然後由遊客選擇要 去的目標景點集合，並提交給系統，系統會反饋給用戶一個景點旅遊的最佳順序，同時遊客 還可以將該旅遊路線保存下來，以方便用戶查看。
3. 3智能語音導航 基於語音的智能導航的主要功能包括景點的語音介紹、旅遊順序推薦等功能，將 極大地方便遊客出遊。語音導航是指在遊客到達某景點A後系統自動介紹該景點的景點信 息以及該景點前後左右的景點信息。 由於需要確定遊客所在的景點，所以一個景點至少應存儲三個信息中心點坐標 (x，y)、邊界點l(xl，yl)邊界點2(x2，y2)，如圖9所示。景點T有兩個邊界Rl和R2，其中
醜1 =如-x)2 + (}l-力2 i 2 1
(jc2-x)2 + (j;2 —力2 當遊客的位置Bi與景點中心T的距離D滿足D《R2時，判斷遊客進入景點T的 範圍。考慮到邊界效應，即遊客可能在景點T的邊界徘徊。此時並不播放景區介紹的語音， 只是做播放的準備工作。當D《Rl時，判斷遊客開始參觀景點T，系統播放景點T的介紹語 當遊客離開景點T時，需要計算出遊客在XY平面的方向角e (0《e《359.9° )。
根據方向角9向遊客預告與景點T相鄰景點的方位和信息。其中
0《6><90判定遊客進入區域l
90^6<180判斷遊客進入區域2
180《S<270判定遊客進入區域3
270《S<360判定遊客進入區域4
為了提高系統的反應速度，需要對景區的景點建立索引，如圖IO所示。本文將景 區劃分成若干區域A00，A10，. . . ，A皿。假設景點T的R2範圍在Aij內，則判斷景點T屬於Aij。例如在圖10的All區域內有T2， T3和T4三個景點。 對景區進行區域劃分後可以得到X坐標的區間序列(x0， xl)， (xl， x2)，...，
(xn-l， xn)和Y坐標的區間序列(y0， yl) ， (yl， y2) ， . . . ， (yn-l， yn)。按照二叉排序樹的
思想分別對X坐標的區間序列和Y坐標的區間序列建立二叉排序樹。建立二叉排序樹後，
系統只需要在第一次進入景區時查找二叉排序樹，確定遊客的區域Aij，隨後可以通過與區
間(xi，xi+l)和區間(yj，yj+l)的比較來確定遊客下一個到達的區域。本發明提出的語音導航算法如圖11所示。數據處理後首先利用二叉排序樹確定
遊客所在的區域Aij，然後通過計算遊客的位置與景點中心點的距離來判斷遊客所在的景
點。它包括兩個線程數據處理線程和語音播放線程。數據處理線程計算遊客與景點的距
離，判斷遊客所在的景點。語音播放線程在確定遊客所在景點後，向遊客播放景點相關語音介紹。 4.應急救援系統 應急救援是指在突發事件發生的情況下，遊客通過本系統將準確的向相關部門 (120， 110等)求援，同時本系統也將會在相關部門實施救援以前給需要救援的遊客A發送 必要的避險和自救知識。同時系統將搜索遊客信息庫，查找求救遊客A附近是否有醫生B 或者救援知識比較豐富的遊客C，如果有，系統會將等待救援遊客A的位置和他的情況發送 給B和C，請他們協助救援。該系統目的是建立一套救援協調與協助互救的救援指導系統。 其數據處理流程如圖12所示。
應急救援模塊的具體工作流程如下 當遊客發生突發事件時，通過本系統編輯簡訊或打電話獲取相應的應急救援指導
信息。系統會將用戶發送的SMS信息或語音信息通過電信網絡或網際網路發送到伺服器端。 伺服器端接收到信息以後，會對文本信息或語音信息進行一番處理，然後生成一
張救援信息表單，並將該求救信息進行備份到求救信息庫，以方便將來查詢使用。 備份好以後，伺服器會將求救信息分類，確定突發事件是屬於一般、緊急還是危機
中的哪一種級別，再看一下事件屬於醫療、刑事、保險還是其他中的哪種類型，然後根據不
同的級別與所屬類型將消息分發到120或110等不同的部門。 伺服器會根據救援知識庫、遊客信息庫、地理信息庫以及120或110反饋給的應急 信息進行消息的處理，從而生成救援指導信息，然後通過電信網絡或網際網路以簡訊或語音 的形式發送到用戶客戶端。 伺服器端提供與PDA的交互功能、通過WEB對資料庫中信息的查詢管理功能以及 WEB端的搜索導航功能。與PDA的交互功能通過在後臺運行Webservice服務來完成，主要 實現PDA信息的接收、處理和存儲，以及對PDA信息的回覆，這個過程需要資料庫系統的支 持。另外，系統還包括一個簡訊收發模塊，該模塊主要針對系統的求救和救援功能，它依託 PDA或手機的簡訊功能，通過簡訊的形式與帶有應用程式的PDA或普通的手機用戶交互，接 收和回復用戶發送的求援信息，同樣的該部分也需要資料庫系統的支持。基於WEB的數據 庫信息查詢管理功能使管理者可以通過瀏覽器查詢管理資料庫中的信息，資料庫中的信息 主要分為景區和遊客信息兩部分，該部分功能只對伺服器的管理人員開放。WEB端的搜索導 航功能是對普通用戶開放的，提供位置搜索和路徑推薦功能。
權利要求
基於PDA的旅遊智能行程導航系統，其特徵在於，該系統包括數據搜索與查詢；旅遊行程規劃；智能導航；應急救援與系統配置。
2. 根據權利要求1所述的方法，其特徵在於，數據搜索是基於垂直搜索技術的信息查 詢，可以提供與遊客旅遊相關的信息搜索，如餐飲、賓館住宿、景區信息、景區天氣等信息的 查詢。
3. 根據權利要求1所述的方法，其特徵在於，旅遊行程規劃部分包括規划行程和查看 行程兩個模塊。
4. 根據權利要求1所述的方法，其特徵在於，智能導航主要包括GPS數據獲取與處理， 用戶位置跟蹤，用戶軌跡顯示，路線規劃，地圖瀏覽和智能語音導航。
5. 根據權利要求1所述的方法，其特徵在於，應急救援是指在突發事件發生的情況下， 遊客通過本系統將準確地向相關部門(120， 110等)求援，同時本系統也將會在相關部門實 施救援以前給需要救援的遊客A發送必要的避險和自救知識。同時系統將搜索遊客信息 庫，查找求救遊客A附件是否有醫生B或者救援知識比較豐富的遊客C，如果有，系統會將等 待救援遊客A的位置和他的情況發送給B和C，請他們協助救援。目的是建立一套救援協調 與協助互救的救援指導系統。
全文摘要
本發明開發了一個基於PDA的旅遊智能行程導航系統，該系統包括數據搜索與查詢、旅遊行程規劃、智能導航、應急救援與系統配置。數據搜索與查詢可以提供與遊客旅遊位置相關的實時信息搜索和查詢；旅遊行程規劃包括規划行程和查看行程；智能導航包括GPS數據獲取與處理、用戶位置跟蹤、用戶軌跡顯示、路線規劃、地圖瀏覽和智能語音導航；在突發事件發生的情況下，遊客通過應急救援模塊可向相關部門求援。該系統實時性強，具有很高的應用價值。
文檔編號G06Q50/00GK101739617SQ20091024254
公開日2010年6月16日 申請日期2009年12月18日 優先權日2009年12月18日
發明者徐鋒, 杜軍平, 梁美玉, 顏志偉 申請人:北京郵電大學