王楠，周紅磊，李金寶，黎玲利

（1. 黑龍江省數(shù)據(jù)庫與并行計算重點實驗室（黑龍江大學），黑龍江 哈爾濱 150080；

2. 黑龍江大學電子工程學院，黑龍江 哈爾濱 150080；

3. 黑龍江大學計算機科學技術學院，黑龍江 哈爾濱 150080）

1 引言

近年來，隨著無線通信和傳感器技術（如GPS、智能手機以及平板）的發(fā)展，定位服務應用應運而生，其中，基于GPS移動設備的路徑/路徑規(guī)劃（LBS）應用受到了人們的廣泛關注，人們從各式的傳感器以及社交網(wǎng)絡中獲取海量數(shù)據(jù)信息以輔助日常出行需求。

在信息技術蓬勃發(fā)展的大環(huán)境下，保障出行安全、提高游覽效率、降低擁堵概率、減少等待時間成為目前首要解決的問題。用戶在去往景點之前，會把該景點稱為用戶的興趣點（POI, point of interest），用戶怎樣才能更快或更省距離地從現(xiàn)處位置到達POI成為首要關注的問題。一些文獻研究了基于單目的地路徑的規(guī)劃算法，例如，Dijkstra算法、Floyd-warshall算法[1]等。但實際上單目的地路徑規(guī)劃已無法滿足現(xiàn)有用戶的出行需求，需涉及多地點路徑規(guī)劃。多地點路徑規(guī)劃可以歸結到旅行商問題（TSP，travelling salesman problem）上，TSP問題作為現(xiàn)有路徑規(guī)劃問題，已被研究者深入研究，TSP的目的是發(fā)現(xiàn)一條路徑可以到達用戶想去的所有POI，同時使路徑距離最短。蟻群算法和遺傳算法作為解決 TSP問題的2種主要算法現(xiàn)已被廣泛應用，但這2種算法主要用于解決靜態(tài)圖中的最短路徑[2]。在現(xiàn)實中，路徑的權值是經常變化的，如路程耗時權值會受到流量擁堵等因素的影響。所以現(xiàn)有的靜態(tài)算法不能滿足用戶實時路徑規(guī)劃需求。

為了解決上述問題，本文提出了利益貪心算法。該算法在設計時考慮了如下因素。

1) 景點的流行度

景點的流行度為該景點對于用戶的吸引程度，每個區(qū)域都有其景點流行度的排名。例如，在杭州旅游時，各大旅游網(wǎng)如攜程旅行網(wǎng)，把西湖作為推薦度第一的景點代表，該景點更容易吸引用戶前往。

2) 景點的合適訪問時間

不同景點合適的訪問時間也不同。例如，有些地方適合白天去，如靈隱寺。有些地方適合晚上去，如杭州西湖的音樂噴泉。

3) 地點的訪問次序

由于每個地方的特有屬性，地點的訪問次序會存在一定順序。例如，用戶在餐館吃完晚餐后回到酒店是一個較好的選擇。

4) 路程時間（排隊時間+景點間移動時間）

排隊時間體現(xiàn)了用戶在訪問某個地點的擁擠情況。因為用戶的游玩地點滿足隨機性，即景點的排隊人數(shù)滿足正態(tài)分布N(μ,σ2)，可以根據(jù)每個景點的人數(shù)到達速率μ設置正態(tài)分布函數(shù)，同時減去服務速率來預測排隊時間[3,4]。景點間的移動時間為用戶在景點間移動所耗費的時間。

本文所提算法能夠有效減少用戶的路程耗時，降低用戶遇到長時間排隊的概率，同時使用戶盡可能多地游覽流行度高的景點，使路線的利益達到最大化。

考慮用戶在游覽期間通常也會產生一些其他需求，例如，從景點1到景點2，用戶可能要解決的需求有取錢、加油和喝咖啡等，因此，需規(guī)劃一條路線解決該需求集合，本文根據(jù)該問題提出了前向擴展細化算法從而使訪問時間最短。

2 相關工作

現(xiàn)有的無線傳感器技術給定位和路徑規(guī)劃服務提供了很大的便利，在物流、導航、工業(yè)等領域都有廣泛的應用[5]。現(xiàn)有的導航方案和算法主要有Dijkstra、Floyd、啟發(fā)式搜索、蟻群以及遺傳算法等[6]。蟻群算法為現(xiàn)有的主流算法，其原理是模擬自然界螞蟻的覓食行為。螞蟻覓食存在隨機性，和景區(qū)中的游客游覽極為相似。

Yu等[7]通過在蟻群算法中引入特殊的遺傳算子，并將兩者結合，避免了蟻群算法本身所具有的局部搜索局限性，同時加快和加大了收斂的速度以及全局最優(yōu)的能力。

旅游路徑規(guī)劃問題（TTDP）[8,9]在近幾年受到相當大的關注，目前主要采用不同的啟發(fā)式算法解決該問題。這些算法從不同的角度以及不同的變量和約束，產生了各種各樣的模型。大多數(shù)TTDP模型中考慮的輸入?yún)?shù)[10]包括：一組候選POI，每個候選POI與一系列相關屬性（如類型、位置、開放天數(shù)/小時、入場費等）。每個POI具有其“利潤”，表示其相關重要性。每日還具有時間預算B，代表游客希望在旅游景點上花費的時間（每日游覽時間總和），即訪問時間加上從POI轉移到另一個POI的整體時間，應該在B之內。

TTDP建模的目標是推導出一組近乎最佳的每日不相交的行程（有序訪問POI），每個行程包含可用（候選）POI的子集，以便最大限度地提高旅游滿意度（即整體收益）。推導出的旅游路線應該尊重用戶約束/POI屬性，并滿足觀光所需的每日時間預算B。因此，可以根據(jù)用戶偏好來調整幾個問題參數(shù)，如POI利潤可以通過客觀和主觀的加權函數(shù)進行計算，同樣訪問POI的時間通過其訪問持續(xù)時間的平均值和用戶對該特定POI的潛在興趣得出[11]。

為了處理旅游規(guī)劃的流程，現(xiàn)在出現(xiàn)了很多旅游路徑規(guī)劃軟件（trip planner），例如，NileGuide、YourTour[12]等。國內的著名旅游網(wǎng)站有攜程旅行網(wǎng)、阿里旅行、去哪兒網(wǎng)等，這些網(wǎng)站都能為游客提供豐富的旅游資源信息。這些軟件首先把各景點的知名度進行排名，然后幫游客挑選有趣的景點，同時還能為游客規(guī)劃好這些景點的訪問順序。此外，隨著基于位置的社交網(wǎng)絡（LBSN）[13]的日益普及，人們在社交網(wǎng)絡上記錄各種足跡數(shù)據(jù)。其中，有關興趣點和用戶豐富有價值的信息，例如，POI的物理坐標、類別、人氣和簽到偏好也被包含在這樣的足跡數(shù)據(jù)中[14]，這些數(shù)據(jù)可以用于研究個性化的自助行程規(guī)劃?，F(xiàn)有可用的在線地圖服務，例如，GoogleMaps、百度地圖、商業(yè)GPS導航儀可以很方便地進行路徑規(guī)劃，但由于它們提供的只是靜態(tài)距離最短或時間最短的行進路線，因此，其規(guī)劃的旅行路線不能滿足用戶的個性化需求。現(xiàn)在以人為本的旅游模式越來越被人們所提倡，推薦排名靠前的旅游景點往往會出現(xiàn)人數(shù)爆滿的情況，同時不同景點的旅游順序以及不同景點的訪問時間都會影響游客旅游的質量，所以設計一個好的旅游路徑規(guī)劃系統(tǒng)具有重要意義。

本文算法基于OP（orientation problem）問題，通過情景利益設計動態(tài)規(guī)劃算法及優(yōu)化算法，可以使規(guī)劃的路線更能夠貼近用戶實際需求，還可以提高用戶的旅游質量。

3 系統(tǒng)框架和問題定義

3.1 系統(tǒng)框架

本文利用智能手機、手環(huán)等設備上的三軸加速度計和三軸陀螺儀傳感器搜集數(shù)據(jù)，將原始數(shù)據(jù)通過濾波降噪得到濾波數(shù)據(jù)，通過濾波數(shù)據(jù)得出步數(shù)，估計步長以及方向，再通過本文所提算法得到用戶到達下個目的地的大致移動時間。然后將景點的歷史客流量作為實驗數(shù)據(jù)并采用灰色 GM(1,1)馬爾可夫模型進行實時的客流量預測，系統(tǒng)框架如圖1所示。景點人數(shù)預測模型涉及的數(shù)據(jù)包含了歷史客流量數(shù)據(jù)以及實時的客流量數(shù)據(jù)，這些數(shù)據(jù)是通過微信公眾號（上海發(fā)布）的接口獲得，每隔15 min該公眾號會更新一次景點人數(shù)數(shù)據(jù)。

圖1 系統(tǒng)框架

數(shù)據(jù)以序列的方式存儲，具有時間標識。具體的預測過程在4.1節(jié)詳細說明。當預測完成后，根據(jù)利益函數(shù)對各景點利益進行計算。如果期間用戶產生需求則進行需求的路徑規(guī)劃，最后得出一條完整的利益路徑。

3.2 問題定義

本文的研究問題可以分為2個部分：用戶需求路徑規(guī)劃和基于利益的景點路徑規(guī)劃。

3.2.1 用戶需求路徑規(guī)劃

該問題是考慮解決用戶在旅行過程中需求的路徑規(guī)劃。例如，用戶要從圖2所示的社交區(qū)域中的一個景點s出發(fā)，去往景點d，但是在從s去往d的過程中有一些需求要解決，如需要取錢、買東西等。即給定一個POI網(wǎng)絡M=(P,E)、起點s、終點d以及用戶的需求集合R'，多需求路徑規(guī)劃的目的是發(fā)現(xiàn)一條從s到d的總路程時間最短的路線，但是這需要在解決用戶需求集合R'的前提下進行。表1為該問題涉及的一些符號定義。

圖2 區(qū)域加權圖的一個示例

表1 符號定義

定義1 Request（需求）。Request代表用戶所要做的一件事或一個服務，即需求。R={r1,r2,r3,…,r|R|}表示需求集合。

定義2 POI（興趣點）。POI代表一個節(jié)點或一個地點。用p={p1,p2,p3,…,p|p|}表示POI的集合。對于每個p，函數(shù)c(p)代表其所屬種類，如商場、飯店等。

定義3PSR()和RSP()函數(shù)。對于給定的一個需求r∈R和一個p∈P，PSR(r)代表能解決需求r的POI集合，PSR(r)?P。RSP(p)代表興趣點p所能解決的需求集合RSP(p)?R。

定義4 POI網(wǎng)絡。M=(P,E)，M代表區(qū)域社交網(wǎng)絡，P、E分別為其頂點和邊集合。圖 2為區(qū)域加權圖的一個示例。

定義5 路徑?。表示由一個或多個POI組成的路徑，即對于?p'∈?,p'∈P，P為POI點集合。

定義6 合法路徑?′。給定用戶的個性需求集合R'={r1',r2',…,rn'}，設定R為總的需求集合，所以R'?R。當R'?PSR('?)，即路徑?′中包含所有用戶的個性需求，則稱該路徑為合法路徑。

定義7 路程時間τ。開始時給定起點s和終點d，還有用戶的個性需求集合R'={r1',r2',…,rn'}，路程時間τ(s,d,?)為停留時間加上移動時間，則有

3.2.2 基于利益的景點路徑規(guī)劃

考慮到現(xiàn)有的路徑規(guī)劃算法在動態(tài)環(huán)境下的結果準確性較差，本文對此進行了深入的研究，考慮了景點的4個屬性，各個屬性定義如下。

定義8pop(li)。景點li的流行度，代表該景點對于游客的吸引程度，為

則路線Route的流行利益度函數(shù)為

定義 9DKL。景點的訪問時間散度如圖 3所示，用散度表示用戶訪問景點的時間與景點合適訪問時間分布的離散程度，DKL越小代表訪問時間越合適，如式(4)所示。其中，fli(t)為用戶訪問景點的時間分布，如實線所示；G(t;μ,σ2)為景點的合適訪問時間分布，如虛線所示。景點合適訪問時間分布選取正態(tài)分布函數(shù)的原因是，通過正態(tài)分布函數(shù)可直接顯示出景點的合適訪問時間分布與用戶的訪問景點的時間分布的差異性，以此來計算散度。

圖3 景點訪問時間散度

所以路線Route的合適訪問時間的利益函數(shù)為

定義 10 visit_order。地點訪問次序，需要研究這種順序并利用它們評估路線的質量。首先給定路線Route={(l1,t1),(l2,t2)…(ln,tn)}，然后計算N-GRAM 的概率，其中，N-GRAM 表示該序列的合理性，概率越大代表次序越合理。

則路線Route的訪問次序的利益函數(shù)為

定義11Routet(Movet+Queuet)。移動時間和排隊時間分別為

則路線Route的路程時間利益函數(shù)為

根據(jù)景點的上述4個屬性可以得出路徑的利益函數(shù)Fitness(Route)，其中，α為時間利益調整參數(shù)。

4 處理算法

本文涉及3個主要算法：基于灰色馬爾可夫的人數(shù)預測算法、前向細化算法以及基于利益最大化的路徑規(guī)劃算法。

4.1 基于灰色馬爾可夫的人數(shù)預測算法

景點人數(shù)預測為本文景點利益路徑規(guī)劃算法的前提，式(2)中的n(li)為景點li的預測人數(shù)?；疑Ｐ偷膬?yōu)點是[15]：1)不需要大量的樣本；2)樣本不需要有規(guī)律性分布；3)計算工作量小；4)定量分析結果和定性分析結果一致；5)可進行短期和中長期預測；6)該模型預測準確率高。在實際應用中，系統(tǒng)可以收集景區(qū)部門的專業(yè)實時統(tǒng)計數(shù)據(jù)，這樣的數(shù)據(jù)具有更高的可靠性和精確度。

本文在灰色模型的基礎上加入了殘差作為修正項，殘差定義為預測值與真實值之間的差值。

首先設置原始數(shù)據(jù)序列為以下形式的序列：X(0)={x(0)(1),x(0)(2),…,x(0)(n)}，為了預測其未來的數(shù)據(jù)，需要對數(shù)據(jù)進行累加，得到累加序列X(1)={x(1)(1),x(1)(2),… ,x(1)(n)}，其中，n為序列長度。再根據(jù)X(1)(t)建立灰色模型所對應的微分方程為

當t=t0時，x(1)=x(1)(t0)，求解該微分方程，可以得出該方程的解為

然后根據(jù)最小二乘法進行求解

其中，Y和B分別為

其中，Y和B中的n為數(shù)據(jù)序列長度，序列長度n將會影響?α，從而影響預測值的精度。把殘差值作為序列項進行累加，重建偏差值的 GM(1,1)模型，式(18)為GM(1,1)模型。由于殘差具有正負，如表2所示，所以建立馬爾可夫轉移矩陣。

表2 殘差狀態(tài)

根據(jù)Pij和表 3可以得出 3×3的概率轉移矩陣為

表3 殘差狀態(tài)轉移

把殘差值和馬爾可夫狀態(tài)轉移矩陣作為修正和轉移參數(shù)加入灰色模型，建立灰色馬爾可夫模型為

4.2 前向細化算法

前向細化算法（forward refinement）在k-near算法和TMT（transferred moving time）算法的基礎上進行了擴展。路徑演示如圖4所示，可能會出現(xiàn)如下情況：用戶從s出發(fā)去往d，用戶的需求為喝咖啡、加油以及取錢。根據(jù)上述 2個算法得出的Route結果是{coffee, 加油站, 商場}，但是發(fā)現(xiàn)商場中包含取錢和喝咖啡這 2個需求，所以可以把coffee這個地點去掉，直接從s出發(fā)到達加油站加油，然后到商場喝咖啡和取錢。這樣可以減少POI的訪問次數(shù)，減少停留時間。前向細化算法如算法1所示。

圖4 路徑演示

算法1 前向細化算法

輸入s、d、M、R′、R、k

輸出 min_Route(s,d)//s到d的最短路徑

procedureFR(s,d)

1)初始化M,Presult,Route={s}

2)whileR≠ {?} do

3) for eachpi∈ |M|

4) SORT(|PSR(pi) ∩R′|)

5)A[k]= |PSR(pi) ∩R′|

6) 把A[k]插入A[0…j]已排序數(shù)組中

7) for eachpj∈|M|

8) if |PSR(pj) ∩R′|=max(A) do∶

9) 比較TMT(pi,s)和TMT(pj,s)

10) ifTMT(pj,s)＞TMT(pi,s) do∶

11) 把pj加入集合Route并令s=pj

12) 移除R′中的元素PSR(pj)∩R′

13) else

14) 把pi加入集合Route并令s=pi

15) 移除R′中的元素PSR(pi)∩R′

16) end if

17) end if

18) end for

19) end for

20) end while

21) returnRoute

22) end procedure

以圖2為例，算法1首先初始化Route={s}，對于區(qū)域網(wǎng)絡M中的所有POI進行|PSR(pi) ∩R′|的排序，然后選擇最大的POI，可以發(fā)現(xiàn)其為p6、p9，因為|PSR(p6)∩R′|=|PSR(p9)∩R′|=2，計算d到p6、p9的距離，選擇最短的距離點為p9，啟動細化機制，然后把p9加入Route集合。移除R′中的r7、r8需求。啟動細化機制把s移向p9，繼續(xù)執(zhí)行步驟2)，對剩下的POI進行排序，可以得出剩下所有的POI都只能提供一個R′的需求。在這些 POI中選擇距離p9最近的點，為p10。然后啟動細化機制判斷p10與p9距離s的距離，TMT(p9,s)＞ TMT(p10,s)則p9不需要移到p10，因為p9距離s比p10距離s遠，該機制是前向擴展所以不需要往回移動。把R'中的r3移除，然后繼續(xù)擴展p9，發(fā)現(xiàn)TMT(p5,p9)＞TMT(p6,p9)，選擇p5作為候選點，啟動機制ω，然后把p5加入Route。把R'中的r6移除，然后繼續(xù)擴展p5，選擇p3，然后就直接到起點s。根據(jù)算法 1可以得出Route={s,p3,p5,p9,p10,d}。路程時間τ為820，比算法TMT提高了270個時間單位。

4.3 基于利益最大化的路徑規(guī)劃算法

本算法根據(jù)利益函數(shù)得出基于利益最大化的貪心算法，給定用戶簽到數(shù)據(jù)、用戶的初始地點以及時間(lq,tq)、用戶需游覽的景點總數(shù)ω，該算法可利用上述信息建立一條具有ω個點的路線使Fitness(Route)利益最大化。算法2為基于利益最大化的路徑規(guī)劃算法。

算法2 基于利益最大化的路徑規(guī)劃算法

輸入DB(Route)、ω、start_location=(lq,tq),t輸出 profit_Route

procedureFitness(DB(Route))

1)初始化Route=(l1=lq,t1=tq)

2)foritoωdo∶

3)ci={lc|li?1?＞lcin RouteDB}

4)fmax=0

5) for eachlc∈ci

6)Routetmp=Route+＜(lc,tc)＞

7) 計算Fitnessf(Routetmp)

8) iff(Routetmp)＞fmaxdo∶

9)Route=Routetmp

10)fmax=f(Routetmp)

11) end if

12) end for

13) end for

14) returnRoute15) end procedure基于利益最大化的路徑規(guī)劃算法為貪心算法，需要證明其滿足最優(yōu)子結構和貪心選擇性。

1) 最優(yōu)子結構證明

使用反證法，假設不存在貪心策略的最優(yōu)子結構，則存在全局最優(yōu)解利益值Fp，且Fp中用戶經過的某幾個節(jié)點的路徑并不是利益最大的路徑。假設它們的利益值和為F1，剩下部分節(jié)點的利益值和為Ft，即Fp=F1+Ft。因為經過這些節(jié)點的路徑不是最短路徑，所以總能找到某條路徑使經過這些點的利益值更大，即1F′＜F1。則存在1F′+Ft＜F1+Qt，即存在一個新的最優(yōu)解比原解更小，與假設矛盾，則該算法最優(yōu)子結構得證。

2) 貪心選擇性證明

設M={l1,l2,…,ln}是具有利益權值的序列，且權值的大小按從大到小排列，每次選擇都是從M中選擇利益最大的地點。

采用歸納法證明。

當N=1時，假設 max(M)=li，則有Fitness(li)＞?p∈N&p≠I Fitness(lp)。

假設當N=ω時，F(xiàn)itness(Route)也成立，其中，F(xiàn)itness(Route)=Profit(Routep)且Route={l1,l2,…,lp}。當N=p+1時，F(xiàn)itness(Route) =Profit(Routep) +Fitness(lp+1)＞Profit(Routep)+Fitness(?p∈N&p≠ili) ， 所 以Fitness(Route)成立，即該算法貪心選擇性成立。

5 實驗與分析

本文實驗環(huán)境為上海地區(qū)景點的模擬環(huán)境，實驗參數(shù)如表4所示。其中，每個地點都具有其所特有的服務項，同時為了方便計算，統(tǒng)一把每個地點的服務需求時間設置為3 min。網(wǎng)絡區(qū)域點的個數(shù)和用戶需求種類的個數(shù)以及總服務種類的個數(shù)都按照實際的情況進行設置，同時這些屬性設置對于本文的算法結果不會產生實質性的影響，即不會改變算法相較于其他算法的效率。

表4 實驗參數(shù)

對于景點人數(shù)預測，本文搜集了從2017年1月12日—4月18日的上海方塔園游客數(shù)據(jù)，分別對于其數(shù)據(jù)進行模擬和預測，得出平均每個時刻的估計值與真實值的偏差。

將殘差值進行 GM(1,1)建模，得到殘差值的GM(1,1)模型。然后將未加入殘差參數(shù)項的預測值和加入偏差參數(shù)項的預測值進行比較，結果如圖 5所示。由圖5可以看出，本文加入殘差項的GM(1,1)模型比原來的模型偏差更小且穩(wěn)定。

圖5 加入殘差項的GM(1,1)與普通GM(1,1)比較

本文對不同的數(shù)據(jù)序列長度n值進行實驗。由于公眾號接口的數(shù)據(jù)從7∶00開始統(tǒng)計，為了保證實驗數(shù)據(jù)的預測準確性，選取序列長度 6～10作為實驗參數(shù)，圖6為n值分別為6、8、10時的實驗結果。由圖6可以看出，當n=8時，數(shù)據(jù)預測性能較好。原因是n=6時數(shù)據(jù)序列長度較短，對于數(shù)據(jù)的預測效果較差；但是n=10時，即在9∶30時會產生景區(qū)人數(shù)激增現(xiàn)象，造成整體的數(shù)據(jù)序列波動較大，這對于預測效果造成很大影響。

圖6 不同n值的模擬值偏差

將本文的前向細化算法與文獻[2]的k-near和TMT算法進行比較，實驗評價的主要標準為路線移動時間和地點停留時間之和。分別根據(jù)k值以及用戶需求個數(shù)來得出實驗結果。把k的默認值設為2，該值一般都默認作為實驗中設定的值，α為路程時間利益的調整參數(shù)，可以根據(jù)其他屬性對α進行調整，所以本文把α設置為0.02，其目的是為了均衡路程時間相較于其他的利益因素。本文對景點的利益參數(shù)進行設置，把景點的流行度、時間KL散度、訪問次序都分為3個區(qū)間，每個區(qū)間對應不同的利益值。同時為了便于計算，統(tǒng)一把每個景點的排隊服務時間都設置為 5人/分鐘，景點的平均單位時間到達人數(shù)為2～8人/分鐘。景點預測人數(shù)越多代表平均單位時間到達人數(shù)越多，其中，Rank 1-2為6～8人/分鐘的隨機，Rank 3-5為 4～6人/分鐘的隨機，Rank 6-9為 2～3人/分鐘的隨機。對于流行度、時間 KL散度、訪問次序分別設置成（5,4,3）這3個利益級別，是為了說明3個屬性具有相同的重要性和參考度，這些屬性的取值對實驗結果以及和其他算法比較性能不會產生顯著影響。后一項路程時間的利益值為time×α，利益參數(shù)如表5所示。

表5 利益參數(shù)

圖7和圖8為k在2～7條件下的各實驗比較結果。為了讓實驗結果更具有代表性，本文在圖上隨機設定一個起點、一個終點。3種算法分別從路程時間和程序運行時間的結果進行比較，可以得出本文所提算法較k-near和TMT算法效果更好。

將Request個數(shù)從6到10進行實驗，結果如圖9所示。本文所提算法的效果更好是因為引入了細化機制概念，從而把不必要的環(huán)節(jié)刪除。

圖7 不同k值下的路程時間結果比較

圖8 不同k值下的程序運行時間結果比較

圖9 不同Request值下的路程時間結果比較

本文基于利益最大化算法（Profit算法）在需游覽完隨機|Route|個景點的前提下，在不同時間點（8∶00、12∶00 以及 18∶00）與文獻[7]的 Rand_GA 算法和文獻[16]的Time_Based算法進行比較。這樣比較的意義在于在不同時間點，景點具有不同的流行度（因為景點流行度具有時效性，有些景點在早晨吸引人，有些景點在下午或晚上吸引人），造成景點的人數(shù)產生變化，即造成路程時間產生變化，結果如圖10所示。

圖10 不同時間點下的路程時間

由圖10可以看出，Time_Based算法的時間比本文所提算法時間略優(yōu)，主要原因是 Time_Based算法只考慮時間的規(guī)劃而不考慮用戶的體驗度。Rand_GA算法的路程時間高的原因是它沒有考慮動態(tài)的流量這個因素。

圖11為3種算法在不同時間點下的路徑利益。由圖11可以看出，本文所提算法所產生路徑的利益值（為式(13)的Fitness(Route)值）比其他2種算法高，這是因為本文考慮了多重屬性的利益，而Time_Based只考慮了路程時間，Rand_GA只考慮了路徑長度。同時在不同時間限制內，本文所提算法能更多地拓展排名靠前的景點，因為本文考慮了景點流行度等因素，更符合出行需求，結果如圖12所示。

6 結束語

本文研究了基于用戶需求的利益路徑規(guī)劃算法，提出了基于灰色馬爾可夫的人數(shù)預測算法、前向細化算法和基于利益的路徑規(guī)劃算法。其中，景點游客量預測算法采用了灰色模型和隱馬爾可夫轉移矩陣的結合來預測景區(qū)的人數(shù)，把預測殘差項作為修正項加入原有預測模型中，可以克服灰色模型的本身缺陷（對于波動大的隨機序列預測效果差），預測結果可以達到預期效果。基于用戶多需求路徑規(guī)劃，在TMT算法的基礎上提出了細化機制，通過從后往前擴展，挑選需求最大的地點作為候選點，實驗效果有了很大提高。本文基于多目的地路徑規(guī)劃算法考慮了地點的多個屬性：景點流行度、時間KL散度、地點訪問次序以及路程時間，每個屬性代表利益，證明了該算法滿足貪心選擇策略并根據(jù)貪心策略選擇利益最大的路徑實現(xiàn)局部最優(yōu)解，最終得到近似優(yōu)化解，取得了較好的效果。

圖11 不同時間點下的路徑利益

圖12 不同時間限制下的拓展景點數(shù)量

[1] GOERIGK M, SCHMIDT M. Line planning with user-optimal route choice[J]. European Journal of Operational Research, 2016, 259(2)∶1-23.

[2] LU E H C, CHEN H S, TSENG V S. Efficient approaches for multi-requests route planning in urban areas[C]//IEEE 14th International Conference on Mobile Data Management (MDM). 2013∶ 36-45.

[3] LI H, YANG T. Queues with a variable number of servers[J]. European Journal of Operational Research, 2000, 124(3)∶ 615-628.

[4] BRAJDIC A, HARLE R. Walk detection and step counting on uncon-strained smartphones[C]//The 2013 ACM International Joint Conference on Pervasive and Ubiquitous Computing. 2013∶ 225-234.

[5] CHEN C, CHEN X, WANG Z, et al. Scenic planner∶ planning scenic travel routes leveraging heterogeneous user-generated digital footprints[J]. Frontiers of Computer Science, 2017, 11(1)∶ 1-14.

[6] VANAJAKSHI L, SUBRAMANIAN S C, SIVANANDAN R. Travel time prediction under heterogeneous traffic conditions using global positioning system data from buses[J]. Intelligent Transport Systems Iet, 2009, 3(1)∶ 1-9.

[7] YU Y, SZETO K Y. Minimize the average mean first passage time of random walk in complex networks by genetic algorithm[C]// Evolutionary Computation. 2016∶ 2352-2359.

[8] CARRABS F, CERRONE C, CERULLI R, et al. A novel discretization scheme for the close enough traveling salesman problem[J].Computers & Operations Research, 2017, 78(2)∶ 163-171.

[9] GAVALAS D, KASAPAKIS V, KONSTANTOPOULOS C, et al.Scenic route planning for tourists[J]. Personal & Ubiquitous Computing, 2017, 21(1)∶ 137-155.

[10] DE PAOLA A, FERRARO P, GAGLIO S, et al. Context-awareness for multi-sensor data fusion in smart environments[M]//AI* IA 2016 Advances in Artificial Intelligence. Springer International Publishing.2016∶ 377-391.

[11] HSIEH H P, LI C T, LIN S D. Exploiting large-scale check-in data to recommend time-sensitive routes[C]//The ACM SIGKDD International Workshop on Urban Computing. 2015∶ 55-62.

[12] VANSTEENWEGEN P, SOUFFRIAU W, BERGHE G V, et al. The city trip planner∶ an expert system for tourists[J]. Expert Systems with Applications, 2016, 38(6)∶ 6540-6546.

[13] QUERCIA D, SCHIFANELLA R, AIELLO L M. The shortest path to happiness∶ recommending beautiful, quiet, and happy routes in the city[C]//ACM Conference on Hypertext and Social Media. 2014∶116-125.

[14] GAVALAS D, KONSTANTOPOULOS C, MASTAKAS K, et al. A survey on algorithmic approaches for solving tourist trip design problems[J]. Journal of Heuristics, 2014, 20(3)∶ 291-328.

[15] 陳淑燕, 陳家勝. 一種改進的灰色模型在交通量預測中的應用[J].公路交通科技, 2014, 21(2)∶ 81-83.CHEN S Y , CHEN J S. Application of an improved grey model in traffic prediction[J]. Highway Traffic Technology, 2014, 21(2)∶ 81-83.

[16] 許博聞. 環(huán)境感知的智能場景分析技術的研究[D]. 哈爾濱∶ 黑龍江大學, 2015.

XU B W. Research on intelligent scene analysis technology of environmental perception [D]. Harbin∶ Heilongjiang University, 2015.