殷浤益 何貞銘 張 穎 趙 暖

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

0 引言

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

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

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

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

1 顧及多因素的旅游路徑規(guī)劃算法實現(xiàn)

1.1 相關(guān)概念介紹

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

1.1.1景點、酒店

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

1.1.2經(jīng)濟型旅游

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

1.1.3舒適型旅游

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

1.1.4觀測狀態(tài)概率

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

1.1.5三類空間位置關(guān)系

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

1.1.6狀態(tài)轉(zhuǎn)移概率

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

1.1.7旅游時間

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

1.2 用格網(wǎng)模型表達點之間的空間位置關(guān)系

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

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

為使格網(wǎng)模型能夠恰當?shù)乇磉_點之間距離相近、適中、遠離的空間位置關(guān)系,單位格網(wǎng)需為邊長為α的正方形,那么根據(jù)景點、酒店最大范圍的經(jīng)緯度坐標,需要用如下公式計算格網(wǎng)的行數(shù)NR與列數(shù)NC:

(1)

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

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

圖1 用曼哈頓距離表示空間位置關(guān)系示意圖

1.3 狀態(tài)轉(zhuǎn)移概率與觀測狀態(tài)概率的計算

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

(2)

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

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

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

(3)

(4)

1.4 維特比算法實現(xiàn)旅游路徑規(guī)劃

在上文中已經(jīng)通過游客選擇旅游類型確定每個景點和酒店的觀測狀態(tài)概率,通過格網(wǎng)模型和高斯函數(shù)確定了兩個點之間狀態(tài)轉(zhuǎn)移概率?；诰S特比算法實現(xiàn)旅游路徑規(guī)劃的方法是,分步求解每一個狀態(tài)到下一個狀態(tài)的最優(yōu)路徑,從而得到整個最優(yōu)路徑,每個狀態(tài)的最優(yōu)路徑通過尋找觀測概率和轉(zhuǎn)移概率乘積的最大值來確定[10],循環(huán)計算每個狀態(tài),直到達到用戶設(shè)定的旅游時間,如圖2所示。

圖2 維特比算法示意圖

每個狀態(tài)的最優(yōu)解可以用以下公式計算:

(5)

s≥1,0≤i≤n-1

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

圖3 維特比旅游路徑規(guī)劃算法流程圖

2 實驗研究

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

2.1 實驗數(shù)據(jù)準備

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

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

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

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

2.2 實驗結(jié)果

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

表2 實驗詳情

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

表3 實驗結(jié)果展示

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

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

2.3 實驗結(jié)果與其他旅游路徑規(guī)劃結(jié)果對比

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

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

3 結(jié)束語

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

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