一種單向動機(jī)迭代改進(jìn)旅游路線規(guī)劃算法*

周 嘯，袁云飛，楊 佳，楊明雷，崔財財

(1. 信息工程大學(xué) 指揮軍官基礎(chǔ)教育學(xué)院，河南 鄭州 450001； 2. 陸軍邊海防學(xué)院，陜西 西安 710100)

旅游者到一個陌生城市旅游前往往需要以城市景點(diǎn)數(shù)量、屬性、布局及其周邊服務(wù)等信息為基礎(chǔ)規(guī)劃最佳旅游路線以盡可能獲得最大動機(jī)利益滿足. 目前旅游路線規(guī)劃方法主要有兩類，一是基于旅游者主觀意識和對旅游城市的初步認(rèn)知，以海量數(shù)據(jù)為依托抽取離散興趣信息，對興趣信息自我加工后決定最適合自身風(fēng)格愛好的旅游路線； 二是市場上大批量旅行社設(shè)計規(guī)劃多種既定旅游路線供旅游者選擇[1-3]. 以旅游者主觀意識與認(rèn)知為背景規(guī)劃旅游路線時，旅游者往往對陌生城市海量地理信息和旅游服務(wù)信息的認(rèn)知不足，具有隨主流、教科書式的行程規(guī)劃趨向，表淺的規(guī)劃策略和較強(qiáng)主觀性對客觀條件不充分等缺陷導(dǎo)致最終規(guī)劃的旅游路線難以達(dá)到最大動機(jī)利益； 旅行社提供既定路線以盈利為目的，考慮旅游者個體興趣愛好較少，旅游者跟隨旅行社出游后真正充分獲得動機(jī)利益滿足的不多[4-6]. 目前，自駕游、自助游等個性化旅游出行方式占據(jù)旅游市場很大份額，是未來旅游市場的熱點(diǎn)和發(fā)展趨勢. 個性化出游要求旅游路線以追求旅游者動機(jī)利益為目的，使旅游者獲得最佳旅行體驗，特別是城市旅游中，不同景點(diǎn)對旅游者的吸引力不同，最大限度地遵循個性需求，規(guī)劃適合單一個體或群體的興趣旅游路線是智慧旅游中智能規(guī)劃旅游路線的重要研究內(nèi)容. 從路線規(guī)劃算法上看，Dijkstra算法、Floyd算法、人工蟻群算法和A*算法等以距離最短為目標(biāo)，采用不同模式規(guī)劃最佳路線，并未融入旅游者對旅游路線的個性需求和對旅游路線動機(jī)利益的最大化追求，僅從算法本身研究路徑規(guī)劃不能充分考慮旅游者主觀意志. 因此，將旅游者出行規(guī)劃和旅游過程中關(guān)心的因素量化為路徑規(guī)劃算法參數(shù)指標(biāo)，構(gòu)建符合旅游者主觀個性需求的路徑規(guī)劃算法，是實(shí)現(xiàn)旅游動機(jī)利益最大化的有效方法[7-9]. 本文在景點(diǎn)路徑規(guī)劃算法的基礎(chǔ)上構(gòu)建了一種單向動機(jī)迭代的改進(jìn)算法，以輸出動機(jī)迭代作用值為規(guī)劃最佳旅游路線的重要依據(jù)，通過仿真算例分析給出可行旅游路線規(guī)劃方案.

1 景點(diǎn)特征編碼集建模

旅游城市的市內(nèi)典型景點(diǎn)數(shù)量和分類一定，首先構(gòu)建景點(diǎn)特征編碼集模型，在此基礎(chǔ)上構(gòu)建子集. 景點(diǎn)特征編碼集是旅游者智能隨機(jī)選取個性化需求景點(diǎn)的數(shù)據(jù)集，通過調(diào)用隨機(jī)函數(shù)選取景點(diǎn)特征編碼子集和景點(diǎn)特征編碼元素對應(yīng)興趣景點(diǎn)，可實(shí)現(xiàn)智能選取或人工選取以充分滿足旅游者動機(jī)[10-12].

Def.1 景點(diǎn)特征編碼集. 由旅游城市包含的全部典型景點(diǎn)及其特征編碼構(gòu)成的父集為景點(diǎn)特征編碼集. 存儲不同種類特征景點(diǎn)，其子集為景點(diǎn)特征編碼子集.

Def.2 景點(diǎn)特征編碼子集. 由旅游城市包含的一類典型景點(diǎn)及其特征編碼構(gòu)成的子集為景點(diǎn)特征編碼子集. 存儲同類特征景點(diǎn)，其包含的元素為景點(diǎn)特征編碼元素.

Def.3 景點(diǎn)特征編碼元素. 景點(diǎn)特征子集包含的一個特征景點(diǎn)對應(yīng)的編碼為景點(diǎn)特征編碼元素.

令旅游城市景點(diǎn)為u類，景點(diǎn)特征編碼集為U，則U={Ut|t∈(0,u)?Z+}，Ut為景點(diǎn)特征編碼子集. 景點(diǎn)特征編碼子集包含et個景點(diǎn)特征編碼元素，則t∈(0,u]?Z+. 令?Ut元素為UtVr且r∈(0,et]?Z+. 取1維景點(diǎn)特征編碼基向量a=(UtV1,UtV2,…,UtVet)，由u維景點(diǎn)特征編碼基向量構(gòu)成景點(diǎn)特征編碼矩陣A=[UtVr]，包含u行maxet列u×maxet個特征景點(diǎn)編碼，第t行由景點(diǎn)特征基向量和maxet-et個0元素構(gòu)成，如式(1)所示. 景點(diǎn)特征編碼矩陣是提取特征景點(diǎn)元素對應(yīng)景點(diǎn)的源矩陣.

(1)

設(shè)連續(xù)型隨機(jī)變量X的分布函數(shù)為

(2)

則稱隨機(jī)變量X服從[a,b]區(qū)間上的均勻分布，記為X～F(a,b). 一次調(diào)用閉合區(qū)間上均勻分布函數(shù)可生成不超過區(qū)間內(nèi)單調(diào)最大值的指定有限元素個數(shù)，且元素具有較強(qiáng)隨機(jī)性[13-15]. 根據(jù)模型，旅游者獲取路線的方式有三種，一是在提供興趣需求和景點(diǎn)數(shù)量后智能輸出路線，二是定向選取若干景點(diǎn)特征編碼子集對應(yīng)的景點(diǎn)種類，根據(jù)所需子類景點(diǎn)數(shù)量隨機(jī)選取景點(diǎn)后輸出路線，三是定向選取所需個數(shù)景點(diǎn)特征編碼元素對應(yīng)景點(diǎn)后輸出路線. 前兩種方法適用于對陌生旅游城市認(rèn)知不足的旅游者[16-18].

(3)

2 單向動機(jī)迭代改進(jìn)規(guī)劃算法

Def.4 景點(diǎn)動機(jī)區(qū)間H. 1號景點(diǎn)與Pk號景點(diǎn)間的擺渡總行程為景點(diǎn)動機(jī)區(qū)間H. 景點(diǎn)動機(jī)區(qū)間是輸出動機(jī)迭代值的介質(zhì).

Def.5 景點(diǎn)動機(jī)子區(qū)間ΔH. ?Pi號景點(diǎn)與相鄰Pi-1號或Pi+1景點(diǎn)間的擺渡行程為景點(diǎn)動機(jī)子區(qū)間ΔHi，i∈(0,k)?Z+.

Def.6 景點(diǎn)動機(jī)區(qū)間迭代值W. 游覽所有選取景點(diǎn)后由1號景點(diǎn)至Pk號景點(diǎn)迭代輸出的動機(jī)值.

Def.7 景點(diǎn)動機(jī)子區(qū)間迭代值ΔW(Pi,Pi+1). ?Pi號景點(diǎn)擺渡至下一景點(diǎn)Pi+1迭代輸出的動機(jī)值，是構(gòu)成景點(diǎn)動機(jī)區(qū)間迭代值的子單元. 景點(diǎn)動機(jī)子區(qū)間是輸出局部最優(yōu)動機(jī)迭代值的介質(zhì)，景點(diǎn)動機(jī)作用值一定時，擺渡區(qū)間產(chǎn)生的動機(jī)迭代是景點(diǎn)動機(jī)區(qū)間輸出動機(jī)迭代值的數(shù)據(jù)源. 依據(jù)貪心算法思想，景點(diǎn)動機(jī)子區(qū)間迭代值各自獨(dú)立，區(qū)間迭代值即是各子區(qū)間迭代值的疊加，滿足式(4).

(4)

城市景點(diǎn)間擺渡產(chǎn)生的動機(jī)迭代值受區(qū)間距離z1(km)、公交地跌線路數(shù)z2、出租車費(fèi)用z3、道路節(jié)點(diǎn)(紅綠燈)z4、擁堵指數(shù)z5等因子影響. 表 1 定義各因子對旅游者動機(jī)利益的影響指標(biāo)，其中λ1為區(qū)間距離，λ2為公交地鐵線路數(shù)，λ3為出租車費(fèi)用，λ4為道路節(jié)點(diǎn)(紅綠燈)數(shù)，λ5為擁堵指數(shù)，參數(shù)g(j)為算法輸出的不同路徑編碼.

表 1 各因子對旅游者動機(jī)利益的影響指標(biāo)Tab.1 The influence indexes of various factors on tourists’ motive benefits

考慮旅游者心理要求，擺渡區(qū)間耗時越少、周折越少、擺渡越便捷，越能促使旅游者產(chǎn)生較大動機(jī)利益滿足和對旅游城市好感. 不同路線下不同景點(diǎn)間的動機(jī)子區(qū)間迭代值ΔW(Pi,Pi+1)不同. 根據(jù)旅游城市地理信息基礎(chǔ)數(shù)據(jù)構(gòu)建改進(jìn)景點(diǎn)子區(qū)間算法，如圖 1 所示.

圖 1 景點(diǎn)子區(qū)間改進(jìn)算法Fig.1 Improved algorithm for sub-interval of scenic spots

改進(jìn)算法如下：

Step 1：確定相鄰兩景點(diǎn)間通路包含的關(guān)鍵道路節(jié)點(diǎn)Qj，j∈(0,maxj]?Z+；

Step 2：令同一地點(diǎn)之間的距離為0，不可直接到達(dá)的兩點(diǎn)之間距離為∞. 以景點(diǎn)Pi為頂點(diǎn)，初始化路徑集合S0=Dist{Pi,Pi}=0； 待選節(jié)點(diǎn)路徑集合為:S1=Dist{Pi,Q1}=d1，S2=Dist{Pi,Q2}=d2，S3=Dist{Pi,Q3}=Dist{Pi,Q4}=Dist{Pi,Pi+1}=∞. 比較S1和S2并冒泡輸出最小值S1*=min(S1,S2)，清空S1,S2,…存儲值；

Step 3：同Step 2，以該段S1*所在邊末端節(jié)點(diǎn)為起點(diǎn)繼續(xù)搜索，輸出待選節(jié)點(diǎn)路徑集合S1,S2,S3,…. 比較S1*,S1,S2,S3,…，并替換原始S1*輸出最小值S1*=S1*+min(S1,S2,S3,…)；

Step 4：同Step 3，冒泡輸出從景點(diǎn)Pi到景點(diǎn)Pi+1最短路徑g(j)對應(yīng)的Sg(j)*，同時記錄其他δ-1條次優(yōu)路徑g(1),g(2),…,g(j-1),g(j+1),…,g(δ)對應(yīng)的S*；

Step 5：給定初始值，對每條路徑迭代影響指標(biāo)因子，輸出景點(diǎn)動機(jī)子區(qū)間迭代值ΔWij(Pi,Pi+1)，表示為

(5)

冒泡輸出迭代值最高的路徑為最優(yōu)路徑，每個景點(diǎn)動機(jī)子區(qū)間ΔHi均包含唯一對應(yīng)編號j的最優(yōu)路徑，定義為ΔWij′opt(Pi,Pi+1)；

(6)

傳統(tǒng)算法僅考慮路徑最短，而最短路徑的景點(diǎn)動機(jī)區(qū)間迭代值W可能并非最優(yōu). 改進(jìn)算法在考慮路徑最短基礎(chǔ)上融合迭代影響旅游者動機(jī)利益產(chǎn)生的各類影響因子，綜合輸出最優(yōu)路徑.

3 仿真算例

仿真算例以鄭州市內(nèi)景點(diǎn)和基礎(chǔ)地理信息數(shù)據(jù)為例. 根據(jù)屬性特征將其分為u=4類.U1為公園(綠地)編碼子集，U2為游(娛)樂場編碼子集，U3為場館編碼子集，U4為購物消費(fèi)編碼子集. 選取市內(nèi)最具代表性和熱門的大眾基礎(chǔ)旅游服務(wù)景點(diǎn)，取t∈(0,4]?Z+且maxt=4. 根據(jù)選取景點(diǎn)，e1=8，e2=4，e1=7，e1=6. 表 2 給出景點(diǎn)特征編碼子集元素景點(diǎn)編碼.

表 2 景點(diǎn)特征編碼子集元素景點(diǎn)編碼Tab.2 Subset element scenic spots code of scenic spots feature code

構(gòu)建1維景點(diǎn)特征編碼基向量a1=(U1V1,U1V2,…,U1V8)，a2=(U1V1,U1V2,U1V3,U1V4)，a3=(U3V1,U3V2,…,U3V7)，a4=(U4V1,U4V2,…,U4V6)，則有景點(diǎn)特征編碼矩陣A=[UtVr]

(7)

Ⅰ： ①P1→②P2→③P3；

Ⅱ： ①P1→③P2→②P3；

Ⅲ： ②P1→①P2→③P3；

Ⅳ： ②P1→③P2→①P3；

Ⅴ： ③P1→①P2→②P3；

Ⅵ： ③P1→②P2→①P3.

以第一條游覽順序①P1→②P2→③P3為例. 路線包含1個景點(diǎn)動機(jī)區(qū)間H： ①P1→②P2→③P3，2個景點(diǎn)動機(jī)子區(qū)間ΔH1： ①P1→②P2和ΔH2： ②P2→③P3以及對應(yīng)的景點(diǎn)動機(jī)區(qū)間迭代值W和景點(diǎn)動機(jī)子區(qū)間迭代值ΔW(Pi,Pi+1). 確定景點(diǎn)P1和P2間關(guān)鍵道路節(jié)點(diǎn)數(shù)和可行擺渡通路，如圖 2 所示.

根據(jù)本文改進(jìn)算法確定前5條最優(yōu)通路為：(1)P1Q1Q2Q3Q4P2； (2)P1Q1Q2Q3Q4Q5P2； (3)P1Q1Q6Q7P2； (4)P1Q1Q6Q7Q8P2； (5)P1Q1Q6Q7Q8Q9Q10P2及其各自對應(yīng)區(qū)間的動機(jī)影響因子，如表 3 所示. 迭代結(jié)果為通路(3)是景點(diǎn)P1和P2間產(chǎn)生動機(jī)利益最大的路徑，即ΔW13′opt(P1,P2)=0.316，且路徑長短與動機(jī)迭代值不成正比. 改進(jìn)算法后不僅考慮路徑最短，同時考慮旅游者動機(jī)利益. 同理迭代輸出景點(diǎn)P2和P3間最優(yōu)路徑，二者疊加為第一條游覽順序①P1→②P2→③P3的最佳動機(jī)迭代輸出路徑，獲得景點(diǎn)動機(jī)區(qū)間H(P1,P3)景點(diǎn)動機(jī)區(qū)間迭代值W1. 同理輸出其他5條游覽順序的景點(diǎn)動機(jī)區(qū)間迭代值Wμ并獲得最大值maxWμ，表 4 為改進(jìn)算法下各游覽順序輸出的景點(diǎn)動機(jī)區(qū)間迭代值.

圖 2 景點(diǎn)P1和P2間關(guān)鍵道路節(jié)點(diǎn)及通路Fig.2 Key road nodes and paths of sight spot P1 and P2

表 3 改進(jìn)算法下景點(diǎn)P1,P2間不同通路動機(jī)影響因子Tab.3 Different path motive impact factors between P1 and P2 of improved algorithm

表 4 改進(jìn)算法下各游覽順序景點(diǎn)動機(jī)區(qū)間迭代值Tab.4 Scenic spots’ motive interval iterative value of improved algorithm under each traveling sequence

分析仿真算例結(jié)果，改進(jìn)算法下游覽路線Ⅰ輸出最大動機(jī)迭代值，其次是路線Ⅵ，即當(dāng)前選中景點(diǎn)條件下旅游者首先游覽鄭州動物園，再游覽二七紀(jì)念館，最后游覽西元廣場，可以獲得最大動機(jī)利益滿足. 其次是按照先游覽西元廣場，再游覽二七紀(jì)念館，最后游覽鄭州動物園，也可獲得次優(yōu)動機(jī)利益滿足. 從一天游覽時間安排上看，該兩種游覽路線也較為合理，且為沿景點(diǎn)分布的順路方向，方便旅游者行程. 當(dāng)景點(diǎn)數(shù)量增多時，亦可獲得相同結(jié)論. 仿真算例證明，本文構(gòu)建算法充分考慮市內(nèi)景點(diǎn)旅游動機(jī)影響因子，為旅游者選擇景點(diǎn)及其游覽路線提供了優(yōu)化方案，促進(jìn)旅游者獲得最大動機(jī)利益滿足，同時也在提高旅游者對旅游城市的主觀印象、提升旅游城市形象、促進(jìn)旅游經(jīng)濟(jì)發(fā)展等方面起到積極作用.

4 結(jié)束語

本文在目前旅游者游覽城市景點(diǎn)存在問題的基礎(chǔ)上，根據(jù)旅游者游覽習(xí)慣和動機(jī)目的提出了一種單向動機(jī)迭代改進(jìn)旅游路線規(guī)劃算法. 對城市景點(diǎn)進(jìn)行特征編碼集建模，提出融合旅游動機(jī)影響因子算法的改進(jìn)最優(yōu)路線規(guī)劃算法，單向輸出動機(jī)利益迭代值最優(yōu)的旅游路線. 算例證明，本文所提算法能夠輸出滿足旅游者需求并產(chǎn)生最大動機(jī)利益滿足的旅游路線，具有一定可行性和實(shí)踐意義.