周 嘯， 李勝輝， 高奎亮， 劉成龍， 王含巢， 胡家瑋

(1. 信息工程大學(xué) 基礎(chǔ)部， 河南 鄭州 450001； 2. 河南機電職業(yè)學(xué)院 信息工程學(xué)院， 河南 鄭州 451191； 3. 信息工程大學(xué) 數(shù)據(jù)與目標(biāo)工程學(xué)院， 河南 鄭州 450001)

0 引 言

旅游者到達某個陌生旅游城市游覽前， 需要掌握該旅游城市最具代表性或最感興趣的景點信息， 特別是旅游地理信息和周邊服務(wù)信息， 并提前規(guī)劃出行路線， 以便在最短時間內(nèi)花費最少旅行代價獲得最佳旅游動機利益滿足. 因此， 智能旅游路徑規(guī)劃是智慧旅游研究領(lǐng)域中的一項熱門課題[1-3]. 旅游者對景點信息的掌握程度不一， 特別是一些對該旅游城市并不了解的旅游者， 他們通常借助智能推介系統(tǒng)選取旅游路線， 或者以旅行社、 旅游網(wǎng)站、 旅游書籍等推薦的路線為參考， 被動地接受已經(jīng)規(guī)劃好的路線， 個性化程度較低， 容易造成推介景點及路線不能滿足旅游者個性化需求的狀況， 降低旅游者獲得動機利益的滿足程度. 其中， 智能推介系統(tǒng)規(guī)劃旅游路線時， 不能考慮旅游者對興趣景點的偏好， 且通常僅以距離最短為目標(biāo)， 綜合考慮其他旅游地理信息較少， 推薦的最優(yōu)路線可能并非旅游者認(rèn)定的最優(yōu). 根據(jù)目前旅游路線規(guī)劃現(xiàn)狀， 需要解決以下兩個問題， 一是推介景點應(yīng)當(dāng)不僅具有代表性， 還要最大程度地切合旅游者的興趣需求； 二是以推介景點為基礎(chǔ)規(guī)劃最優(yōu)旅游路線時， 要在距離最短的基礎(chǔ)上充分結(jié)合與旅游者出行直接相關(guān)的城市服務(wù)系統(tǒng)， 最大限度提高旅游者滿意度[4-5]. 本文構(gòu)建了一種多約束指標(biāo)改進的動態(tài)旅游路線規(guī)劃算法， 該算法以興趣景點和特征拐點集模型為基礎(chǔ)， 結(jié)合城市旅游地理信息服務(wù)動態(tài)規(guī)劃最優(yōu)旅游路線， 實現(xiàn)旅游者個性化需求、 路線最短和便捷地理信息服務(wù)的結(jié)合， 最大限度滿足旅游者動機利益.

1 興趣景點集與特征拐點集建模

1.1 興趣景點集與景點提取基底矩陣建模

1.1.1 興趣景點集建模

智能旅游的一項核心目標(biāo)是為旅游者制定動機利益最大化的個性化旅游路線， 以盡可能提高旅游者對制定旅游路線和方案的滿意度， 提升旅游城市形象[6-8]. 規(guī)劃個性化旅游路線以旅游者確定適合自身心理需求和旅行規(guī)劃的興趣景點為前提， 因此景點的分類和選取方法是關(guān)鍵. 為用戶提供便捷的可視化景點選取平臺， 是規(guī)劃智慧旅游方案的重要前提. 以市區(qū)內(nèi)景點為研究對象， 景點的分類準(zhǔn)則不同[9-10]. 根據(jù)旅游者具體需求和景點自身屬性， 此處給出景點分類準(zhǔn)則及相關(guān)定義.

定義1 城市特征景點集Φ. 定義旅游城市市區(qū)空間范圍內(nèi)所有以智能機隨機選取或旅游者主觀提取為目的存在于智能機中的景點構(gòu)成的集合為城市特征景點集， 以Φ表示.

定義2 城市特征景點子集Φi. 定義旅游城市市區(qū)空間范圍內(nèi)以某一準(zhǔn)則R劃分的城市特征景點集的子集為城市特征景點子集， 每個子集代表一類景點， 以Φi表示， 其中i∈(0,p]∈Z+，p為在準(zhǔn)則R定義下城市特征景點的種類， 即城市特征景點子集數(shù)量， 其中p∈(0,maxp]∈Z+.

定義3 城市特征景點元素φj. 定義旅游城市市區(qū)空間范圍內(nèi)任意城市特征景點子集?Φi所包含的任意單個景點?Φj為城市特征景點元素， 以φj表示. 為區(qū)別不同城市特征景點子集Φi下的景點元素， 景點元素表示為

φj=Φi[φj].

(1)

定義4 景點分類準(zhǔn)則. 定義根據(jù)旅游者年齡結(jié)構(gòu)、 心理需求、 行程安排、 景點特征及其屬性等因素劃分景點的具體原則為景點分類準(zhǔn)則. 對城市特征景點集Φ，p的取值越大， 景點分類越多. 而對城市特征景點子集Φi， 特征景點元素φj的數(shù)量由城市容納的景點數(shù)量決定， 即對每一子集都有

Φi={φj|Φi[φj], 0

(2)

1.1.2 景點提取基底矩陣建模

以城市特征景點集Φ及其子集為數(shù)據(jù)源構(gòu)建景點提取基底矩陣A. 景點提取基底矩陣是智能機隨機選取景點的數(shù)據(jù)矩陣. 當(dāng)旅游者對城市景點情況不了解時， 向智能機提供希望游覽的興趣景點種類和數(shù)量， 智能機根據(jù)旅游者的年齡、 興趣、 行程等隨機選取特征景點后調(diào)用算法規(guī)劃路線. 以特征景點子集構(gòu)建景點提取基底向量A， 有

Ai=[Φi[φ1],Φi[φ2],…,Φi[φj]].

(3)

以p和景點提取基底向量構(gòu)建maxp×maxj維矩陣， 矩陣第i行元素為子集Φi元素Φi[φj]， maxj-j位取0， 則有景點提取基底矩陣A為

(4)

1.2 特征拐點集建模

旅游者從一個景點游覽擺渡到下一景點的過程中需經(jīng)過街區(qū)和路口， 智能機選取最優(yōu)街區(qū)和路口， 能給旅游者提供交通擺渡最佳體驗， 獲得動機利益滿足[11-12]. 此處定義指標(biāo)特征和特征拐點集.

定義5 特征指標(biāo)因子γ. 定義道路樞紐指數(shù)γ1、 公交換乘站點系數(shù)γ2、 地鐵換乘站點系數(shù)γ3和道路擁堵指標(biāo)γ4等影響旅游者擺渡的因子為特征指標(biāo)因子. 4項特征指標(biāo)因子對旅游者選擇擺渡路線、 獲得動機利益滿足有重要影響， 標(biāo)準(zhǔn)如下：

1) 道路樞紐指數(shù)γ1： 道路及道路節(jié)點在城市區(qū)域交通中的重要性系數(shù). 根據(jù)道路重要性和街區(qū)通行能力， 將城市道路分為主干道路Path1、 次要道路Path2和輔助道路Path3. 主干道路或兩條主干道路交點設(shè)γ1，1=0.20， 次要道路或主次道路交點設(shè)γ1,2=0.40， 輔助道路或兩條次要交點設(shè)γ1,3=0.60， 次輔道路交點設(shè)γ1,4=0.80， 兩條輔助道路交點設(shè)γ1,5=1.00.

4) 道路擁堵指標(biāo)γ4： 一天內(nèi)平均擁堵總時長n3(h)的倍數(shù)0.1n4.

定義6 特征拐點集R. 定義由智能機或人工選取的任意城市特征景點?φj與其鄰域內(nèi)下一待游覽特征景點φj+1之間具有特征指標(biāo)因子γ的樞紐道路節(jié)點構(gòu)成的集合為特征拐點集， 以R表示， 有

R={Rt|0

(5)

式中：Rt為特征拐點集元素， 代表某一具備特征指標(biāo)因子γ的樞紐路口. 如圖 1 所示， 景點φj和φj+1位于若干街區(qū)中， 滿足特征指標(biāo)因子γ的樞紐路口有maxt個， 數(shù)字代表t的取值. 按景點φj到特征拐點Rt之間的緩沖區(qū)半徑r(φj,Rt)對特征拐點集元素升序排列， 有

R={Rt|R1,R2,…,Rmaxt},

(6)

式中：r(φj,R1)≤r(φj,R2)≤…≤r(φj,Rmaxt).

圖 1 景點及其特征拐點Fig.1 Sight spot and feature spot

由圖 1 可知， 旅游者從景點φj擺渡到景點φj+1需經(jīng)過若干特征拐點， 每個特征拐點具備特征指標(biāo)因子. 兩景點間基于空間距離dis(x)迭代特征指標(biāo)因子獲得迭代值以確定最優(yōu)旅游路線.

2 動態(tài)規(guī)劃算法建模

設(shè)disw,v,k為w點擺渡至v點過程中以集合K={k|0

1) 最短路徑經(jīng)過集合K中一點k：disw,v,k=disw,k,k-1+disk,v,k-1;

2) 最短路徑不經(jīng)過集合K中一點k：disw,v,k=disw,v,k-1. 則有：disw,v,k=min(disw,v,k-1,disw,k,k-1+disk,v,k-1). 若僅考慮路徑長短， 不一定能滿足旅游者動機利益， 應(yīng)結(jié)合擺渡過程的實際地理信息服務(wù)需求. 此處定義動機迭代指標(biāo).

定義7 景點子區(qū)間動機迭代指標(biāo). 由任意景點?φj與下一景點φj+1間特征拐點擺渡距離disw,v(km)和特征指標(biāo)因子γ迭代輸出的影響旅游者動機利益的指標(biāo)值.

定義8 景點區(qū)間動機迭代指標(biāo). 起始景點和終止景點間多個景點子區(qū)間的動機迭代指標(biāo)和.

根據(jù)節(jié)點擺渡距離disw,v和特征指標(biāo)因子γ構(gòu)建景點子區(qū)間動機迭代指標(biāo)Wφj,φj+1和景點區(qū)間動機迭代指標(biāo)W， 分別為式(7)和式(8). 其中Wφj為景點φj處的景點動機迭代初始值.

(7)

(8)

設(shè)景點φj與景點φj+1間包含k個特征拐點， 構(gòu)建Open表和Closed表， Open表存放未擴展拐點， Closed表存放已擴展節(jié)點. 旅游者根據(jù)自身興趣從景點提取基底矩陣A中以基向量所在行為單位提取m個待游覽的特征景點. 當(dāng)旅游者對城市景點不熟悉時， 也可根據(jù)特征景點種類提供游覽景點數(shù)量， 由智能機隨機選取m個特征景點. 首先研究起始景點到第二個景點間最優(yōu)路線， 構(gòu)建搜索算法：

1) 將t個特征拐點R1,R2,…,Rt放入Open表；

2) 選取距離景點φj最近的特征拐點R1并將其放入Closed表， 并從Open表刪除. 搜索R1和R1后繼鄰近節(jié)點Ra1間距離dis1,a1， 以R1,Ra1及二者之間通路的特征指標(biāo)因子γ迭代計算W1,a1；

3) 返回步驟2)， 搜索R1另一后繼鄰近節(jié)點Ra2， 迭代計算W1,a2. 若W1,a2W1,a1， 將Ra1存入Closed表， 并將其從Open表中刪除. 轉(zhuǎn)第4)步；

4) 搜索Ra1的后繼鄰近節(jié)點Ra3和Ra2的后繼鄰近節(jié)點Ra4， 后繼節(jié)點由城市道路分布和緩沖區(qū)半徑r(φj,Rt)決定. 迭代計算Wa1,a3和Wa2,a4；

5) 由步驟4)迭代計算W1,a3和W1,a4. 若W1,a3W1,a4， 將Ra2的后繼鄰近節(jié)點Ra4存入Closed表中， 并將其從Open表刪除；

6) 返回第2)步， 繼續(xù)搜索， 直到搜索到與目標(biāo)景點φj+1鄰近的特征拐點Rt為止， 輸出動機迭代值W1,t最小的一條路線的maxW1,t. 算法各步驟， 滿足ao∈(0,maxt]∈Z+,ao為R的序列腳標(biāo).

3 算例分析

考慮旅游者年齡構(gòu)成和景點特征， 取maxp=3， 則有maxi=3， 城市特征景點集Φ滿足Φ={Φi|0

(9)

表 1 景點子集元素景點編碼

由表 1，p1=7，p2=6，p3=7， 則maxp=7. 構(gòu)建景點提取基向量A1=[Φ1[φj1]]，A2=[Φ1[φj2]]，A3=[Φ1[φj3]]， 其中j1∈(0,7]∈Z+,j2∈(0,6]∈Z+,j3∈(0,7]∈Z+. 對景點提取基底矩陣補零后得式(9)景點提取基底矩陣A3×7.

圖 2 景點Φ2[φ3]和Φ1[φ2]間通路與特征拐點集Fig.2 Path of sight spot Φ2[φ3] and Φ1[φ2] and feature spot set

圖 3 景點Φ1[φ2]和Φ3[φ3]間通路與特征拐點集Fig.3 Path of sight spot Φ1[φ2] and Φ3[φ3] and feature spot set

表 2 景點Φ2[φ3]和Φ1[φ2]特征拐點擺渡距離disw,v(km)

表 3 景點Φ1[φ2]和Φ3[φ3]特征拐點擺渡距離disw,v(km)

表 4 特征拐點特征指標(biāo)因子

由算法步驟1)～6)迭代計算Φ2[φ3]和Φ1[φ2]景點子區(qū)間動機迭代指標(biāo)， 如表 5 所示. 由表可知， 從景點Φ2[φ3]到Φ1[φ2]輸出動機迭代最小值為W1,8， 即經(jīng)過拐點R1，R3，R4和R8. 同理， 動態(tài)遞推景點Φ1[φ2]和Φ3[φ3]間動機迭代最小值為經(jīng)過拐點R3，R4，R8和R9的W3,9. 綜合表 5 遞推結(jié)果， 從景點Φ2[φ3]游覽至Φ1[φ2]最后到Φ3[φ3]， 分別經(jīng)過區(qū)間一的R1，R3，R4，R8和區(qū)間二的R3，R4，R8，R9能夠輸出最小動機迭代值， 由景點即所屬區(qū)間拐點構(gòu)成的路線為最優(yōu)路線.

表 5 Closed表和Open表動態(tài)遞推動機迭代值最小路線

4 結(jié) 論

本文在最優(yōu)路線規(guī)劃的基礎(chǔ)上提出了一種多約束指標(biāo)改進的動態(tài)旅游路線規(guī)劃算法， 綜合考慮區(qū)間距離最短、 道路樞紐指數(shù)、 公交站點換乘系數(shù)、 地鐵站點換乘系數(shù)和道路擁堵指標(biāo)等約束條件， 動態(tài)遞推規(guī)劃動機迭代值最小的路線為最優(yōu)旅游路線. 算例證明， 該算法能夠輸出距離最短同時符合旅行擺渡過程一般規(guī)律的路線， 滿足旅游者個性化需求， 使旅游者獲得最佳動機利益滿足.