基于用戶需求的旅游路線推薦方法

李 旭，李景文,2+，俞 娜

(1.桂林理工大學 測繪地理信息學院，廣西 桂林 541006；2.桂林理工大學 廣西空間信息與測繪重點實驗室，廣西 桂林 541006)

0 引 言

隨著智能移動設備和信息技術的飛速發(fā)展，使得過去求量型旅游方式轉向為求質型旅游方式，在用戶游玩過程中越來越注重個性化旅行體驗。因此體現用戶需求的旅游路線推薦技術成為了研究熱點[1,2]。如何根據用戶需求智能設計個性化旅游路線，為用戶提供精準旅游信息服務，為旅游企業(yè)創(chuàng)造出更大的旅游經濟價值已成為智慧旅游建設的重點任務之一[3]。Han等[4]根據旅行者的歷史旅行軌跡，建立了地標推薦模型，以幫助旅行者制定旅行計劃。林青等[5]根據時間地理學理論，計算時空可達性好的景點組合，提出了一種考慮游客時間成本的旅游線路推薦算法，提升了用戶旅游的滿意度。劉艷秋等[6]根據用戶的評論和景點評分信息，提出了一種基于Word2vec和LDA的推薦模型，并將該模型用于旅游路線推薦中。Salas-Olmedo等[7]利用Foursquare(觀光)、Panoramio(消費)和Twitter(社交活動)數據，研究了游客的旅行軌跡，驗證了不同景點情境特征下游客的旅游活動存在差異。

雖然以上研究都取得了一定的進展，但研究角度單一，缺乏對用戶需求及其關聯因素的統一分析，不能最大程度體現個性化推薦結果?；诖?，本文提出一種基于用戶需求的旅游路線推薦方法，通過景點評分方法實現基于用戶需求的景點推薦，在此基礎上根據旅行時間、費用等約束條件建立旅游路線推薦模型，并利用嵌入混沌擾動和方差判定準則的模擬退火算法求解該模型，從而為用戶推薦科學合理的旅游路線，滿足其在不同情境下的旅游需求[8,9]。

1 理論基礎

1.1 問題分析

軌跡f由一系列具有時序的GPS點組成f=(p1,p2,…pn)。 其中，n表示GPS點數量，p=(lat,lng,t)，lat,lng為該點的緯度和經度，t為該點的時間戳。定義score(s) 為景點s的得分，景點及景點間軌跡片段構成有向景區(qū)圖G=(S,F)， 其中，S為景點集合，F為連接景點的軌跡集合。

(1)

基于以上分析，旅游路線定制問題可表述為在軌跡集合F中發(fā)現得分最高的旅游路線，其中，景點得分是基于景點流行度、用戶偏好和景點游玩時間等這些用戶個人需求的。因此，為了解決該問題，構建體現用戶偏好的景點評分方法與包含約束條件的旅游路線定制模型成為旅游路線定制的關鍵。

1.2 基于用戶需求的景點評分方法

基于用戶需求的景點評分方法主要包括3個方面的內容：一是基于景點流行度的評分;二是基于用戶游玩時間的評分;三是基于景點游玩時間的評分。從這3個方面對景點和用戶需求進行分析，既能給用戶推薦符合個人喜好且熱度較高的景點，又能將景點最合適的游玩時間推薦給用戶。

1.2.1 基于景點流行度的評分

用戶在某個地區(qū)旅游時，該地區(qū)的熱門景點是最先吸引用戶關注的(例如，桂林的漓江、象鼻山等)，因此，針對熱門景點對用戶的影響，本文提出景點流行度的概念。

(2)

1.2.2 基于用戶游玩時間的評分

不同的用戶都有自己偏好的景點類型，對于自己喜歡的景點，游玩的時間就會相對長一些，而用戶對于自己不感興趣的景點，游玩的時間就會相對短一些。因此，本文基于用戶游玩時間的評分來判斷用戶對該景點的喜好。

(3)

由景點平均游玩時間得到游客對于某類型景點的個人偏好，其公式為

(4)

1.2.3 基于景點游玩時間的評分

實際旅行過程中，大部分景點的游玩時間都有限制和規(guī)定，并且，每個景點的最佳游玩時間也不同。比如，桂林的獨秀峰王城景區(qū)的游玩時間為8∶00～18∶00，在這個時間段用戶能夠進入景區(qū)游玩，超出這個時間范圍則不能游玩該景區(qū)。因此，針對景點游玩時間的問題，本文提出了基于景點最佳游玩時間的評分。

(5)

式中：tmax表示景點關閉時間，tmin表示景點開始游玩的時間。

1.3 旅游路線推薦模型

在景點評分方法挖掘出符合用戶需求的景點的基礎上，充分考慮旅行時間和旅行費用等約束條件對旅行的影響，建立時間和旅行費用約束下的旅游路線定制模型[10]，使得推薦的旅游路線更加符合生活實際。

根據1.2節(jié)中的景點評分方法可以得到景點si的評分為

(6)

式中：ω取0.4，讓用戶偏好占更大比重，凸顯用戶需求。

因此，旅游路線得分為

(7)

根據以上分析，旅游路線定制模型及其約束條件如下

(8)

(9)

(10)

(11)

(12)

(13)

其中，式(7)是旅游路線定制模型的目標函數，定制的旅游路線為得分最高的旅游路線，xi,j是決策變量，當景點sj是景點si的下一個游玩景點，則xi,j=1， 否則為0。式(9)-式(10)保證定制的旅游路線的起點是s1，終點是sn。式(11)確保定制的旅游路線連貫且景點不重復。式(12) -式(13)表示定制旅游路線的旅行時間和花費必須在用戶允許的最大旅行時間和花費之內，ti和ei表示景點內游玩時間和門票費用，ti,j和ei,j表示景點si和sj之間的行駛時間和花費，對于兩個景點之間的距離，本文利用Haversine公式[11]來計算

(14)

式中:κi和κj表示景點si和sj的緯度， φi和φj表示景點si和sj的緯度。

2 改進SA的旅游路線定制算法

2.1 改進SA算法

模擬退火算法(simulated annealing，SA)[12]是旅游路線規(guī)劃中最常用的算法之一，但是極易受到降溫策略的影響，導致收斂速度下降，影響算法效率[13]。因此，為了提高SA算法的全局搜索能力，加快算法的收斂速度，本文將改進SA算法用于旅游路線定制模型中。本文對SA算法進行以下2個方面的改進：

(1)通過混沌擾動確定搜索范圍，防止算法陷入局部最優(yōu)。混沌具有初值敏感性、遍歷性及貌似隨機的規(guī)律性。在模擬退火算法中嵌入混沌擾動能動態(tài)調節(jié)搜索步長，更準確找出最優(yōu)解，從而定制出更準確合理的旅游路線。本文利用一維logistic映射產生混沌擾動對解空間進行搜索的公式如下

Dk+1=μDk(1-Dk) (k=0,1,2,…)

(15)

式中：Dk為當前最優(yōu)解，μ為混動調節(jié)參數，根據一維logistic映射產生的混沌狀態(tài)特點，當μ=4時，混沌產生的效果最佳。

(2)利用方差判定準則作為終止搜索條件，防止冗余迭代，提高SA算法的運行效率。方差判定公式如式(16)所示

(16)

式中：ε為方差判定因子，n為搜索向量數量，k為迭代次數，D(Li)為方差。

2.2 改進SA算法步驟

基于時間和旅行費用約束下的SA算法推薦旅游路線的具體步驟如下：

輸入：旅游景點數據、用戶需求以及時間和費用約束。

輸出：符合用戶需求的最優(yōu)旅游路線。

步驟1 設置模型參數。設置ε，k，Q0(初始溫度)，D0(混沌向量)。

步驟2 根據景點評分機制算出景點得分score(si)，并挑選出n個得分最高的旅游景點。

步驟3 計算景點之間的兩兩距離di,j， 根據選擇的景點初始化一條滿足模型約束條件的旅游路線trip1=Initial(si)。

步驟4 計算新的旅游路線tripnew。當用戶游玩路線的時間與消費滿足最大旅行時間與旅行消費限制時，按混沌擾動方式Dk+1=μDk(1-Dk) 在解空間進行最優(yōu)解搜索tripnew=NewAnswer(trip1)。

步驟5 接受新的旅游路線tripnew。當score(tripnew)>score(trip1) 時，接受新解tripnew，當score(tripnew)

步驟6 溫度更新。按指數下降公式Qk+1=λQk進行溫度更新，若滿足方差判定準則，循環(huán)終止，進行步驟7，否則，轉到步驟4。

步驟7 輸出最優(yōu)旅行路線tripbest和游玩時間Tbest與花費Ebest。

3 實驗結果與分析

3.1 實驗設置

本文實驗數據來自于去哪兒網攻略庫(桂林)，通過對數據集進行預處理：①刪除分享照片數量少于5張的用戶；②刪除重復多余的照片；③刪除用戶評論數少于2條的用戶。最終得到的數據集包含了338名用戶對156個景點分享的9275張圖片，景點的經緯度坐標、照片拍攝時間、人均費用、游玩時間、景點類型和帶有用戶情感的評論信息等。

除了從去哪兒網獲取到實驗數據外，本文設置改進SA算法中初始溫度Q0=200；方差判定因子ε=0.01，降溫速率λ=0.95，也對評分方法中涉及到的初始值進行了設定(見表1)，表中與時間有關的單位是min，與花費有關的單位是元。并且將用戶的初始位置設為桂林理工大學屏風校區(qū)，終止位置設為桂林理工大學雁山校區(qū)。

表1 評分方法參數初始化設置

3.2 基于用戶需求的景點評分方法評估

3.2.1 景點得分結果展示

表2 景點數據示例

表3 景點得分示例

圖1 桂林市景點得分值

3.2.2 景點評分方法合理性分析

為了驗證基于用戶需求的景點評分方法的合理性，將該方法與文獻[14]提出的TRR(three ratios ranking algorithm)算法推薦的景點進行對比。采取在360 min、480 min和600 min這3種不同旅行時間下推薦景點的準確率、召回率和它們的調和值F-Measure來判斷推薦效果的優(yōu)劣，見表4。

準確率的公式如下

(17)

召回率的計算公式為

(18)

F-Measure的計算公式為

(19)

其中，sr表示推薦的旅游景點集合，sv表示游客去過的旅游景點集合。

由表4可知，從推薦效果來看，本文提出的景點評分方法推薦景點的準確率、召回率和F-Measure值都比TRR算法的高，這是因為TRR算法根據景點熱度比(類似本文的景點流行度)推薦景點，并沒有考慮用戶偏好和景點的最佳游玩時間對用戶旅行的影響。而從整體情況來看，3種不同旅行時間下的F-Measure值都在0.6以上，這表明本文方法推薦的景點能準確地反映用戶對景點的喜好，推薦效果良好。

3.3 旅游路線推薦

3.3.1 旅游路線推薦界面展示

假若某用戶使用共享汽車(1.5元/公里)來游玩桂林市區(qū)的旅游景點，出發(fā)地點為桂林理工大學屏風校區(qū)，目的地為南溪山公園，旅行時間約束為480 min，旅行花費約束為500元，且在約束條件內盡可能游玩多的景點，其余旅行參數見表1。根據景點評分方法挖掘出的景點和旅游路線定制模型，分別用傳統SA和改進SA算法規(guī)劃旅游路線。傳統SA算法規(guī)劃旅游路線經過景點為：桂林理工大學屏風校區(qū)→七星景區(qū)→象山景區(qū)→兩江四湖→靖江王城→南溪山公園，改進SA算法規(guī)劃旅游路線經過景點為：桂林理工大學屏風校區(qū)→七星景區(qū)→靖江王城→兩江四湖→象山景區(qū)→南溪山公園。傳統SA和改進SA算法路線旅行時間和花費見表5，個性化展示界面如圖2所示。

表5 旅游路線定制參數

圖2 旅游路線個性化定制界面

從圖2和表5可知，傳統SA算法和改進SA算法定制的旅游路線都在時間和費用預算范圍內，但改進SA算法相比傳統SA算法定制的旅游路線節(jié)約了7 min，節(jié)省了9元。這表明改進SA算法定制的旅游路線更加科學準確，能為用戶推薦更符合生活實際的旅游路線。

3.3.2 改進SA算法性能分析

為了進一步檢驗嵌入混沌擾動和方差判定準則的模擬退火算法的優(yōu)化效果，本文利用3個經典測試函數[15](見表6)對嵌入混沌擾動和方差判定準則的模擬退火算法進行測試(測試結果如圖3所示)。

表6 測試函數

圖3 測試函數迭代曲線

通過圖3的Resenbrock函數優(yōu)化曲線可知，改進SA算法能夠能夠更快尋得最優(yōu)解，說明算法運算效率大大提升，能夠更快地定制出滿足用戶需求的景點；Griewank函數和Resenbrock函數的優(yōu)化曲線表明改進SA算法跳出局部最優(yōu)的能力大大增強，使得定制的旅游路線更加符合用戶需求。

4 結束語

本文針對旅游路線推薦中個性化程度不高的問題，從景點流行度、用戶偏好和景點游玩時間這3個角度出發(fā)，提出基于用戶需求的景點評分方法，在此基礎上考慮用戶時間與費用等約束條件建立了旅游路線推薦模型，并將嵌入混沌擾動和方差判定準則的模擬退火算法用于該模型求解符合用戶需求的旅游路線。最后，通過實例驗證本文提出的景點評分方法比TRR算法有著更高的準確率和召回率，改進SA算法比傳統SA算法無論是在最優(yōu)解的搜尋精度還是在收斂速度上都有明顯的提升。

用戶游玩過程中，城市交通路況復雜，需要用到各種各樣的交通出行方式，并且不同的交通方式對旅行體驗有著很大的影響。在接下來的工作中，如何量化用戶旅游出行方式，考慮用戶出行方式對旅游的影響，并運用到旅游路線推薦模型中，是我們需要去重點研究和解決的問題。