基于格網模型的維特比旅游路徑規劃算法

殷浤益 何貞銘 張 穎 趙 暖

(長江大學 地球科學學院, 湖北 武漢 430100)

0 引言

隨著網絡技術的發展,當下人們出行旅游前多在各大旅游網站上搜集信息[1],但僅能獲得景點、酒店的靜態位置及屬性信息,依此信息設計滿足自身旅游需求的路徑規劃將耗費大量時間與精力。雖然少量旅游網站也提供類似路徑規劃功能,但選取該功能后多數出現旅行社旅游線路產品推薦而非區域內旅游路徑規劃。因此大眾迫切需要一種考慮景點、酒店等多方面因素的旅游路徑規劃方法,以滿足游客的個性化及實用需求。

近年來,許多學者對旅游路徑規劃算法進行了大量深入的研究[2-6]。樊守偉等[2]采用改進的Dijkstra算法實現了旅游路線規劃。牛悅誠將旅游路徑規劃問題轉化為旅行商問題,并使用改進的蟻群算法進行求解[3];盧昕[4]、徐峰等[5]對蟻群算法進行了改進;李孟則采用改進的A*算法求解旅行商問題[6]。

現有旅游路徑規劃研究成果相對較多,但仍存在不足之處:(1)限制因素比較固定,并未考慮多種實際因素的影響,如大多算法僅依據景區進行旅游線路規劃,而實際旅游過程中并未考慮重要因素“酒店”的影響,致使路徑規劃結果適用性下降;(2)大多算法中的數據基源于歷史數據,這些數據并未充分顧及游客的個性需求,并未根據游客喜好、消費水平的不同而生成個性化的旅游路線規劃方案。

維特比算法是一種在數字通信中經常使用的譯碼算法,于1976年由維特比(Viterbi)提出,是最優的動態規劃算法之一[7],本文將旅游路徑規劃問題抽象成多階段決策最優化問題,即將旅游路徑分解成若干個由景點和酒店交錯組成的鏈狀序列,其每個節點與前后都具有相關聯系,用維特比算法求解每個階段的最優解,最后得到整個最優路徑,同時引入了格網模型與景點、酒店的屬性信息來實現路徑規劃的個性化需求。

1 顧及多因素的旅游路徑規劃算法實現

1.1 相關概念介紹

為了方便介紹本文的研究內容,對本文算法中所涉及概念進行解釋。

1.1.1景點、酒店

本文中進行旅游線路規劃的兩個重要因素:景點是游客能夠游玩的一系列地點,酒店是能為游客提供住宿條件的地點,它們的屬性包括:坐標,名稱,用戶評價等級,消費等級。

1.1.2經濟型旅游

這是針對消費水平較低的游客選取的旅游方式,例如學生游客,此類群體在旅游時往往選擇性價比高的景點和酒店,性價比高代表用戶評價等級高且消費等級低。

1.1.3舒適型旅游

相對于經濟型旅游的概念,當游客為擁有較高穩定收入的人群時,其需求為最佳的旅游體驗,這就要求用戶評價等級與消費等級均高的景點和酒店。

1.1.4觀測狀態概率

維特比算法進行動態規劃的重要基礎之一,代表景點和酒店對游客的吸引程度。若無任何其他因素的影響,每個景點和酒店的觀測概率都是相同的,但是當用戶選擇舒適型旅游或者經濟型旅游時就會發生變化,由景點、酒店的用戶評價等級和消費等級決定。

1.1.5三類空間位置關系

在GIS中描述兩點之間的空間位置關系僅用重疊和不重疊表達,不能較好地表達景點與景點或者景點與酒店之間空間位置關系,因此定義如下三類點與點之間的空間位置關系,用h表達兩點間的距離,α,β為常量,單位均為km。①距離相近:當0≤h<α時,兩點之間是距離相近關系;②距離適中:當α≤h<β時,兩點距離適中;③遠離:當h≥β時,兩點距離較遠。α,β的數值需要根據不同城市的具體情況進行確定。

1.1.6狀態轉移概率

維特比算法進行動態規劃的另外一個重要基礎,在本文中表示游客從一個景點到下一個景點或者酒店的概率,基于1.1.5節的空間位置關系定義,本文用距離作為自變量的高斯函數計算狀態轉移概率。

1.1.7旅游時間

為了讓游客有充足的時間來旅游,本文中旅游時間計算以天為單位,且為游客提供個性化的旅游時間選擇方式。在總結國內旅游網站的旅游線路推薦和實際調研基礎上,認為單日旅游兩個景點相對適中,因此單日旅游時間代表兩個景點和一個酒店,兩日及以上的旅游時間依此類推。

1.2 用格網模型表達點之間的空間位置關系

在旅游路徑規劃中,可以近似將景點和酒店作為點來處理,在九交模型中,重疊與不重疊2種點/點關系[7]不足以充分描述旅游景點或酒店間的位置關系,于是本文提出了1.1.5節中的三種空間關系,其實質是以距離為梯度對點進行聚類處理,而格網模型是實現聚類的一種基礎且重要的方法。本文用起點與下一點之間的曼哈頓距離代替兩點之間的實際距離,依據1.1.5節的定義對格網距離進行梯度劃分,得到三類空間位置關系,此方法不僅能簡化坐標計算,并且劃分的結果充分契合高斯函數的特性。

曼哈頓距離是兩點在南北方向上的距離加上東西方向上的距離[9]。相比于歐氏距離,曼哈頓距離更適用于城市街道中的距離表達,也具有更高的計算效率;相比于實際距離,在城市中選擇不同的交通工具,其實際距離往往具有很大的區別,很難進行統一的量化處理。綜合考慮,本文采用了曼哈頓距離來近似表達兩點間的距離。

為使格網模型能夠恰當地表達點之間距離相近、適中、遠離的空間位置關系,單位格網需為邊長為α的正方形,那么根據景點、酒店最大范圍的經緯度坐標,需要用如下公式計算格網的行數NR與列數NC:

(1)

式中,μ代表1緯度的實際距離;θ、φ分別代表經度和緯度。

建立上述格網,選擇任意點為起點,與起點在同一格網內的其他點就與起點的關系是相近的,因為它們之間的距離小于α;以起點為中心,計算離起點的曼哈頓距離在β內的點,則這些點到起點的關系是適中的;與起點的曼哈頓距離大于β的點與起點的關系是遠離的,如圖1所示,圖中取β=2,則橫線格網內的點與起點的距離相近,陰影格網內的點與起點的距離適中,白色格網內的點與起點是遠離關系。

圖1 用曼哈頓距離表示空間位置關系示意圖

1.3 狀態轉移概率與觀測狀態概率的計算

從日常人們的出行經驗來看,若無其他因素影響,人們在旅游時前往下一個目標的概率與當前位置到下一目標的距離近似成高斯分布,即距離越遠,游客愿意到達這個目標的概率越小,因此本文采用高斯函數來表達曼哈頓距離與狀態轉移概率之間的關系,其數學表達式如下:

(2)

式中,μ、σ分別代表期望和均方差;x代表曼哈頓距離;P(x)為起點到下一個點的狀態轉移概率。當兩個點在同一格網里時有x=0,此時兩點間的距離小于α,對應兩點距離相近的空間位置關系,表示游客到達另一個點的可能性最大,因此P(x)在x=0時應取最大值,所以有μ=0;由高斯函數在x>μ上單調遞減的性質可知,?β>α,σ=f(β)使得P(β)≈10-8,那么當x>β時,可以認為游客到達該點的概率幾乎為0。為提高算法效率,本文只計算距離起點β內的點的狀態轉移概率。使用高斯函數來表達距離與狀態轉移概率之間的關系,既充分考慮了高斯函數的特性也符合實際。

文中介紹了景點和酒店觀測狀態概率由景點和酒店的消費等級和用戶評價等級確定,這里用Lc和Lq(Lc、Lq∈[1,2,3,4,5])來分別表示消費等級和用戶評價等級,0與1分別代表經濟型和舒適型,T代表旅游類型,λ為常數,xi表示起點附近的第i個點,最后景點、酒店的觀測狀態概率為E(xi),其計算公式為:

E(xi)=Ec(xi)×Eq(xi)

(3)

(4)

1.4 維特比算法實現旅游路徑規劃

在上文中已經通過游客選擇旅游類型確定每個景點和酒店的觀測狀態概率,通過格網模型和高斯函數確定了兩個點之間狀態轉移概率。基于維特比算法實現旅游路徑規劃的方法是,分步求解每一個狀態到下一個狀態的最優路徑,從而得到整個最優路徑,每個狀態的最優路徑通過尋找觀測概率和轉移概率乘積的最大值來確定[10],循環計算每個狀態,直到達到用戶設定的旅游時間,如圖2所示。

圖2 維特比算法示意圖

每個狀態的最優解可以用以下公式計算:

(5)

s≥1,0≤i≤n-1

其具體的流程如圖 3所示。首先,游客需要確定旅游的起始點,預計旅游的時間以及旅游類型。接著,以游客確定的景點為起點,計算剩余每個景點到起點的曼哈頓距離,剔除遠離起點的景點和酒店以減少計算量,將與起點距離相近或適中的點的距離代入(2)式得到狀態轉移概率,然后使用(3)、(4)式得到范圍內景區、酒店的觀測狀態概率。用(5)式得到每個狀態的最優解,即為當前狀態中最有可能到達的點[11],將該點放入一個結果集合中,再以該點作為新的起點,在進行距離計算時剔除結果集合中的點,防止計算結果回溯,然后一直循環下去,直到滿足用戶需要的旅游時間。最后,算法結束,將結果集合中的點顯示在主界面上。

圖3 維特比旅游路徑規劃算法流程圖

2 實驗研究

為了展示研究成果,本文利用ArcGIS Engine平臺與ArcGIS Engine開發了基于維特比算法的旅游路徑規劃系統的桌面應用程序,實現了讓用戶選擇旅游起點、旅游天數、旅游類型后,自動計算出最符合要求的旅游路徑。

2.1 實驗數據準備

本文以武漢市為例,選取了武漢市具有代表性的15個景點,例如:黃鶴樓、戶部巷、武漢歡樂谷等;32個酒店,包括一般連鎖酒店與高檔酒店。底圖和坐標數據均來自湖北省天地圖。為了能確定1.1.5中α,β的值,統計了常見各類出行方式的平均速度,以武漢市市區為例,如表1所示。

表1 常見各類出行方式平均速度

表1統計的平均速度包含紅綠燈、武漢市的路況信息,公共交通的停站等待時間等,可以看出在武漢市市中心的出行速度較為緩慢,結合武漢市市區的實際出行情況,本文取α=1,β=15,此時根據計算取σ=β/2時,P(β)≈10-8。

計算得到參數后需要對數據進行處理。首先,將數據導入ArcMap中,給每個景點和酒店賦屬性值,其中用戶評價等級和消費等級的數據來源于網絡。本文中所有景點和酒店范圍的經度最大值為114.42°,最小值為114.21°,緯度最大值為30.68°,最小值為30.50°,將以上所有數據都代入式(1)得到NR≈20.006,NC≈19.998。然后,打開ArcMap中的Fishnet功能,輸入上述數據生成20×20的格網。最后,再將生成的格網分別與景區和酒店做疊加分析生成Intersect_Fishnet_Sceinc和Intersect_Fishnet_Hotel圖層,此時已經可以在新圖層的屬性表獲取到景點、酒店的格網坐標、等級、名稱、用戶評價等級和消費等級等所有信息。

2.2 實驗結果

本文假設了四種不同的情景,如表2所示,每個情景的條件都互不相同,對應了不同游客的需求,同時也可以對比不同條件下旅游路徑規劃結果,從整體來看,旅游路徑規劃結果滿足不同游客對旅游類型和旅游時間的需求。

表2 實驗詳情

在實驗1中,游客選擇以“武漢大學”作為起點,規劃的路線如表3實驗結果所示,“武漢大學”的下一個景點是“湖北省博物館”,該景點門票免費,且藏品豐富,參觀價值極高,是武漢市性價比較高的景點之一,距離“武漢大學”約4 km,距離適中。搜索的酒店是“漢庭酒店(東湖店)”,該店在“攜程”等旅游網站中評分較高,該酒店地理位置優越,近地鐵四號線,價格親民,距離“湖北省博物館”約1 km,因此規劃的路線整體符合用戶要求。

表3 實驗結果展示

實驗2、3、4均是實驗1的對比實驗。在實驗2中僅改變旅游類型,檢索的下一個景點就變為“楚河漢街”,該景點屬于購物娛樂類型,周圍是3個大型商圈,因此人均消費較高,距離“武漢大學”約5 km,在距離適中的范圍內,檢索的酒店是武漢市的五星級酒店,距離“楚河漢街”約為0.2 km,規劃結果十分符合舒適型旅游的要求。在實驗3中改變了旅游時間,發現實驗1與實驗3第1日的旅游路徑相同,可以看出維特比算法從局部最優到整體最優的特性;實驗3第2日以“東湖海洋世界”作為起點開始檢索,距離該景點15 km內的景點有多個,但距離相對較近的只有“楚河漢街”與“武漢歡樂谷”,這兩個景點對規劃結果的影響較大,“武漢歡樂谷”到起點的距離雖然更近,但是由于消費等級的存在,最后計算結果是“楚河漢街”優于“武漢歡樂谷”,為該狀態下的最優解,說明了本文算法中觀測狀態概率與狀態轉移概率相互影響。最后實驗4中只改變了起始點,但是從計算結果來看,與實驗1并無本質區別。

從以上的實驗中可以得出,基于維特比算法的旅游路徑規劃充分運用了維特比算法的動態規劃方法,既考慮了游客與景點、酒店之間的距離因素,也結合了游客自身的旅游需求。引用的高斯函數能較好地表達距離與狀態轉移概率之間的關系;旅游類型的設定讓游客的選擇多樣化。

2.3 實驗結果與其他旅游路徑規劃結果對比

文獻[2]中使用改進的Dijkstra算法也實現了旅游路徑規劃,本文將維特比算法與其進行比較(表4)。在時間復雜度上兩個算法相差不大。實用性上維特比算法得出的旅游路徑更符合游客的要求,實用性較高。但不能否認Dijkstra算法適應性強和實現簡單的優點。

表4 維特比算法與文獻[2]中算法對比

3 結束語

本文對維特比算法和格網模型在旅游路徑規劃問題上進行了探索,創新性地提出了將酒店加入旅游路徑規劃之中,增加了旅游路徑規劃的實用性;用格網表達景點、酒店的空間位置關系;運用高斯函數表達觀測狀態概率;利用景點和酒店的屬性來表達狀態轉移概率;最后,成功把維特比算法與上述方法結合在一起,實現了維特比旅游路徑規劃算法,并用實驗進行了驗證,結果表明該算法是合理的,并且在一定程度上滿足了用戶多因素的路徑規劃需求。但是,該算法也存在不足之處,比如本文以格網模型下的曼哈頓距離代替實際距離會不可避免地產生誤差,在未來的研究中可以探索其他的聚類方法,盡可能減小誤差,使規劃結果更準確。

當今我國信息化產業發展迅猛,旅游業與GIS相結合使其信息化水平逐步提高[12],但仍然還有很大的發展空間。未來應用中,可建立全國最優旅游路徑網站或旅游線路查詢決策系統,旅游路徑規劃可以擴展到具體的道路規劃。旅游路徑的開發水平、完善程度,起到把控旅游流量、流向的作用,同時可以緩解旅游高峰期的擁堵情況,可有效地提高游客整體的旅游質量,對我國旅游業的發展具有重要意義。