一種多約束指標(biāo)改進(jìn)的動(dòng)態(tài)旅游路線規(guī)劃算法

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

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

0 引 言

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

1 興趣景點(diǎn)集與特征拐點(diǎn)集建模

1.1 興趣景點(diǎn)集與景點(diǎn)提取基底矩陣建模

1.1.1 興趣景點(diǎn)集建模

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

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

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

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

φj=Φi[φj].

(1)

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

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

(2)

1.1.2 景點(diǎn)提取基底矩陣建模

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

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

(3)

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

(4)

1.2 特征拐點(diǎn)集建模

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

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

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

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

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

R={Rt|0

(5)

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

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

(6)

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

圖 1 景點(diǎn)及其特征拐點(diǎn)Fig.1 Sight spot and feature spot

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

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

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

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

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

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

定義8 景點(diǎn)區(qū)間動(dòng)機(jī)迭代指標(biāo). 起始景點(diǎn)和終止景點(diǎn)間多個(gè)景點(diǎn)子區(qū)間的動(dòng)機(jī)迭代指標(biāo)和.

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

(7)

(8)

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

1) 將t個(gè)特征拐點(diǎn)R1,R2,…,Rt放入Open表；

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

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

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

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

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

3 算例分析

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

(9)

表 1 景點(diǎn)子集元素景點(diǎn)編碼

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

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

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

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

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

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

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

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

4 結(jié) 論

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