智慧旅游路線的TripPlan算法規劃

徐星辰，鄭世超

（1.中共懷寧縣委黨校安徽安慶246121；2.中國石油大學(華東)控制科學與工程學院，山東青島266580）

當今旅游的方式發生了翻天覆地的變化，景區特色游、鄉村游等眾多方式成為城鎮居民的體驗首選，而且旅游的發展符合國家產業發展的目標，其已經成為農民脫貧致富、精準扶貧及城鄉融合發展的重要方式[1].但是在發展的同時，也帶來了諸多方面的問題，如環境污染、旅游無秩序等，此時就迫切需要新的管理方式，而信息化就成為一種重要的促進力量.通過智慧旅游信息化系統的建設，能夠帶來多方面效益，包括經濟效益、社會效益等，有效地融合目前的物聯網、大數據、AR 等現代化的技術體驗，為用戶提供更為有趣的使用體驗[2].

在智慧旅游的發展之中，隨著游客訪問數據信息及整個系統運營數據信息的增多，系統可以采用大數據的分析方式來發揮這些存儲數據信息的價值[3].本文在大數據分析之中，選擇旅游線路的規劃問題進行分析與設計，整個算法的輸出主要包括游客的當前位置信息及游客瀏覽的時間限制兩個方面約束條件[4].Pei 在提出此旅游線路規劃問題時給出了最簡單的處理方法，這個算法簡稱為BFM 算法，是一個蠻力搜索算法，在一定數據范圍之內能夠獲得最優解，但是隨著景點數據的增加，使得整個算法處理的時間成倍的增加，很難有效地對整個數據信息進行快速分析[5].面對此計算復雜度高的問題，Lu等學者提出了新的解決方法TripMine 算法[6]，其最大的優勢在于能夠有效降低總體算法計算的復雜度，但這個算法主要的問題在于得到的算法結果未必是最優解，且實際運行過程中，其本身的計算效率也存在較低的問題.

數據挖掘是通過分析每個數據，從大量數據中尋找其規律的技術，主要有數據準備、規律尋找和規律表示三個步驟[7].數據準備是從相關的數據源中選取所需數據并整合成用于數據挖掘的數據集；規律尋找是用某種方法將數據集所含的規律找出來；規律表示是盡可能以用戶可理解的方式（如可視化）將找出的規律表示出來.數據挖掘的任務有關聯分析、聚類分析、分類分析、異常分析、特異群組分析和演變分析等[8].

具體數據挖掘方法如圖1所示.

圖1 數據挖掘分析模型

常見的聚類分析算法有以下五種.

（1）劃分法.依托于K-MEANS、K-MEDOIDS和CLARANS 等算法，其操作步驟是系統提供一個有限定的數據集，利用分裂法將其分為n 個代表聚類的小組，系統會通過算法直接先給一個初始分組，而后通過多次更迭分組，調換數據來盡量達到同一組中記錄更近、不同組中記錄更遠的最佳目標[6].

（2）層次法.相對于劃分法來說是一個由分散到聚集的過程，其算法可以通過BIRCH、CUR 等算法來實現.計算原理是將給定的數據看成一個個單獨的組，可以自上而下或者自下而上對數據集進行層層解析，然后合并有相似屬性的單個數據組，直至給定的數據集滿足所需要的條件.

（3）基于密度方法.只要一個區域的點的密度大于這一范圍內的臨界值，就將其分到與之最近的小組中.這一行為主要通過DBSCAN、OPTICS 等算法來實現.

（4）基于網格的方法.該法的優點就是效率高、耗時少、處理速度快.不以數據空間中單個的數據為處理對象，而是利用STING 等算法以數據空間分成的有限單元為處理對象，一次性處理數據多，方便快捷[9].

（5）基于模型的方法.利用統計和神經網絡的方式實現，計算方式是假設一個模型，該模型可以是數據的密度分布、概率分布、轉折分布等，然后根據已經假定的模型有針對性地尋找符合條件的數據集，并將相應數據統計歸納到模型里即可完成數據的聚類.

結合上述BFM、TripMine 算法以及實際旅游數據信息的相關具體問題，本文運用了更為高效的TripPlan 算法，并通過算法的分析結果證實算法能夠得到整個線路規劃的最優解，且在整個算法的計算過程中總體計算復雜度較低，從而為景區的游客提供便利性的服務.

1 算法優化策略

算法處理分為三個過程：第一，對景點的候選集合進行構造；第二，在景點的候選集合之中生成旅游線路；第三，在旅游線路的候選集合之中選出最優的旅游線路.

1.1 候選的景點集合數據信息處理過程

設景點集合S1={al1,al2,al3,…,alk} ，S2={am1,am2,am3,…,amk} 為兩個k 階的合法景點集合.若al1=am1，al2=am2，al3=am3,…,alk-1=amk-1且alk≠amk，則 由S1與S2生 成的k+1 階候選景點集合為S3={al1,al2,al3,…,alk,amk}或S3={am1,am2,am3,…,amk,alk}.

1.2 候選景點集合生成旅游線路信息處理過程

對于旅游線路而言，最主要的就是景點先后瀏覽順序的排列，因此若景點集成為S={al1,al2,al3,…,alk} ，則此景點對應生成的旅游線路就是這些景點集合中每一個景點的全排列，即al1、al2、…、alk的全排列，由此可以確定旅游線路規劃條數為k!.

為了分析整個景點候選集及此候選旅游線路的生成過程，可通過圖2來表示詳細的處理過程.若景點的候選集合數量為1，則其對應的旅游線路數量為1，從中可以看出，在景點候選集合中，由1個景點構成的旅游線路也是符合要求的線路，稱為合法線路，而此1 項集可以稱為合法項集.若景點集合為{a1}、{a2}、{a3}、{a4}，對應可以生成的2 項集經過對比分析之后可以確定包括{a1,a2}、{a1,a3}、{a1,a4}、{a2,a3}、{a2,a4}、{a3,a4}，每一個2項集之中的旅游線路條數經過計算可以得到2！，結果為2條，從中能夠確定旅游線路具體的數量為2.從圖2的處理過程還可以發現，若候選集數量變為3，此時任意的一個候選3項集對其合法線路數量分析結果均為0，因此可以認定所有的候選3 項集都為非法項集，同時不能通過3 項集的候選構成完成4 項候選集的分析處理，此時算法的分析過程停止.

圖2 候選項集及其對應線路的生成過程

1.3 最優線路選擇的處理過程

通過前面旅游線路生成的處理過程，能夠確定的是，若景點集合的數量為n，則其景點線路最大數量為n!，系統主要的工作目標是結合總體旅游時間的約束來完成之中最優旅游線路的確定，此時需要對確定的所有合法線路進行掃面處理，若當前最優線路為空，此時將其設置為最優的旅游線路，后續對其他旅游線路逐步進行分析處理，若新的旅游線路得分大于原先確定的最先線路，則將此新的線路設置為最優線路.

對于圖2中項集數量為1的合法線路，得分最高的為＜a4＞，因此可以將＜a4＞此線路設置為目前的最優旅游線路.通過項集1 為生成對應的項集為2 的候選項集，對比不同的線路得分能夠發現，最高的分數為＜a1,a4＞，因此＜a1,a4＞線路就代替＜a4＞成為最優線路，同時可以確定包括{a3,a4}和{a2,a4}這些集合的線路為非法線路，可以將這部分的數據信息進行剪枝操作，通過類似的處理方法，使用合法旅游線路的2項集能夠完成3項集的候選與處理工作，確定候選3 項集構成的線路都是非法的線路，這些數據都是非法的，不能在3 項集的基礎上去生成對應的四項集，整個算法分析處理過程結束.

2 算法框架

根據上述算法優化策略，若某景點當前旅游線路的得分小于最優旅游線路，則不需要對該景點對應的旅游線路重新構造，但該景點集合可能為合法景點集合（可生成合法線路），因此該景點集合不能刪除，將這一類景點集合存儲在集合UnKnownSet中，用于構造下一階的候選景點集合.具體的Trip?Plan算法框架如下（其中CAS表示候選景點集合）：

在算法1 中，attractionset 表示當前k 階候選景點集合景點列表；lasttriplist 表示k+1 階合法線路；t.insert(i,a)表示將對象a插入到列表t中位置i處，具體的景點集合生成旅游線路算法過程如下：

3 數據測試及分析

由于BFM 算法的處理時間過長，效率過低，經過對比分析，采用的是優化處理的BFM 算法.通過對TripMine 算法與TripPlan 算法進行分析對比，若能證明后者算法的性能優于前者，而TripMine 算法又是BFM 算法改進而來，則必然能夠證明TripPlan算法的性能也好于BFM 算法.三個算法對應的優化策略如表1所示.

表1 BFM算法、TripMine算法與TripPlan算法對比分析

從表1 可以看出，BFM 算法基本上沒有優化策略，僅在全排列的基礎之上進行最優旅游線路的分析構造，TripPlan 算法相比TripMine 算法而言，其線路構造優化等處理能夠更有效解決景點數量多且旅游時間約束等條件下的線路分析與推薦處理.

為了充分驗證整個算法處理的效率，本文選取某區域的21 個景點作為分析處理的實驗數據集，當約束時間相同時，對這三個算法運行的時間性能進行對比分析，由于在不同情況下處理時間可能不同，對每一個情況都進行了5次處理，之后取5次處理的平均值來完成整個數據信息的顯示，具體的算法分析結果如表2所示.

從表2 可以看出，21 個景點作為實驗數據集的分析處理結果顯示，當時間約束相同的條件下，不同算法的性能是不同的.這些算法性能對應的曲線如圖3所示.

表2 時間限制相同時候的不同運行效率對比

圖3 算法處理性能對比分析圖

從圖3 結合前面的計算結果能夠看出，在處理景點數為21、時間約束相同的狀況下，TripPlan 算法與TripMine 算法的運行時間相比BFM 算法而言有著顯著的下降.若時間約束TC ≤16 時，TripPlan 算法與TripMine 算法在運行處理時間上面是基本相同的，若時間約束TC ≥17 時，TripPlan 算法在處理時間之中有著明顯的優勢，且隨著時間約束的越來越大，這種優勢越來越明顯.當旅游景點數目確定的時，旅游規劃的時間越長，采用TripPlan 算法進行處理的效率越高.

4 結語

本文將TripPlan 算法應用于智慧旅游路線規劃當中，通過測試分析對比發現，在時間相同的情況下TripPlan 算法比傳統的BFM 算法具有顯著優勢，而當時間約束大于17 h 時TripPlan 算法更優于Trip?Mine 算法，且該優勢隨著時間的增長越發明顯，大大提高了旅游線路優化的效率.因此，TripPlan 算法可以作為智慧旅游管理系統的一種有效設計方法.