基于用戶(hù)需求的景點(diǎn)路線(xiàn)利益規(guī)劃算法

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

（1. 黑龍江省數(shù)據(jù)庫(kù)與并行計(jì)算重點(diǎn)實(shí)驗(yàn)室（黑龍江大學(xué)），黑龍江 哈爾濱 150080；

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

3. 黑龍江大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，黑龍江 哈爾濱 150080）

1 引言

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

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

為了解決上述問(wèn)題，本文提出了利益貪心算法。該算法在設(shè)計(jì)時(shí)考慮了如下因素。

1) 景點(diǎn)的流行度

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

2) 景點(diǎn)的合適訪(fǎng)問(wèn)時(shí)間

不同景點(diǎn)合適的訪(fǎng)問(wèn)時(shí)間也不同。例如，有些地方適合白天去，如靈隱寺。有些地方適合晚上去，如杭州西湖的音樂(lè)噴泉。

3) 地點(diǎn)的訪(fǎng)問(wèn)次序

由于每個(gè)地方的特有屬性，地點(diǎn)的訪(fǎng)問(wèn)次序會(huì)存在一定順序。例如，用戶(hù)在餐館吃完晚餐后回到酒店是一個(gè)較好的選擇。

4) 路程時(shí)間（排隊(duì)時(shí)間+景點(diǎn)間移動(dòng)時(shí)間）

排隊(duì)時(shí)間體現(xiàn)了用戶(hù)在訪(fǎng)問(wèn)某個(gè)地點(diǎn)的擁擠情況。因?yàn)橛脩?hù)的游玩地點(diǎn)滿(mǎn)足隨機(jī)性，即景點(diǎn)的排隊(duì)人數(shù)滿(mǎn)足正態(tài)分布N(μ,σ2)，可以根據(jù)每個(gè)景點(diǎn)的人數(shù)到達(dá)速率μ設(shè)置正態(tài)分布函數(shù)，同時(shí)減去服務(wù)速率來(lái)預(yù)測(cè)排隊(duì)時(shí)間[3,4]。景點(diǎn)間的移動(dòng)時(shí)間為用戶(hù)在景點(diǎn)間移動(dòng)所耗費(fèi)的時(shí)間。

本文所提算法能夠有效減少用戶(hù)的路程耗時(shí)，降低用戶(hù)遇到長(zhǎng)時(shí)間排隊(duì)的概率，同時(shí)使用戶(hù)盡可能多地游覽流行度高的景點(diǎn)，使路線(xiàn)的利益達(dá)到最大化。

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

2 相關(guān)工作

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

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

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

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

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

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

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

3.1 系統(tǒng)框架

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

圖1 系統(tǒng)框架

數(shù)據(jù)以序列的方式存儲(chǔ)，具有時(shí)間標(biāo)識(shí)。具體的預(yù)測(cè)過(guò)程在4.1節(jié)詳細(xì)說(shuō)明。當(dāng)預(yù)測(cè)完成后，根據(jù)利益函數(shù)對(duì)各景點(diǎn)利益進(jìn)行計(jì)算。如果期間用戶(hù)產(chǎn)生需求則進(jìn)行需求的路徑規(guī)劃，最后得出一條完整的利益路徑。

3.2 問(wèn)題定義

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

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

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

圖2 區(qū)域加權(quán)圖的一個(gè)示例

表1 符號(hào)定義

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

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

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

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

定義5 路徑?。表示由一個(gè)或多個(gè)POI組成的路徑，即對(duì)于?p'∈?,p'∈P，P為POI點(diǎn)集合。

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

定義7 路程時(shí)間τ。開(kāi)始時(shí)給定起點(diǎn)s和終點(diǎn)d，還有用戶(hù)的個(gè)性需求集合R'={r1',r2',…,rn'}，路程時(shí)間τ(s,d,?)為停留時(shí)間加上移動(dòng)時(shí)間，則有

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

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

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

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

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

圖3 景點(diǎn)訪(fǎng)問(wèn)時(shí)間散度

所以路線(xiàn)Route的合適訪(fǎng)問(wèn)時(shí)間的利益函數(shù)為

定義 10 visit_order。地點(diǎn)訪(fǎng)問(wèn)次序，需要研究這種順序并利用它們?cè)u(píng)估路線(xiàn)的質(zhì)量。首先給定路線(xiàn)Route={(l1,t1),(l2,t2)…(ln,tn)}，然后計(jì)算N-GRAM 的概率，其中，N-GRAM 表示該序列的合理性，概率越大代表次序越合理。

則路線(xiàn)Route的訪(fǎng)問(wèn)次序的利益函數(shù)為

定義11Routet(Movet+Queuet)。移動(dòng)時(shí)間和排隊(duì)時(shí)間分別為

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

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

4 處理算法

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

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

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

本文在灰色模型的基礎(chǔ)上加入了殘差作為修正項(xiàng)，殘差定義為預(yù)測(cè)值與真實(shí)值之間的差值。

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

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

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

其中，Y和B分別為

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

表2 殘差狀態(tài)

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

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

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

4.2 前向細(xì)化算法

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

圖4 路徑演示

算法1 前向細(xì)化算法

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

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

本算法根據(jù)利益函數(shù)得出基于利益最大化的貪心算法，給定用戶(hù)簽到數(shù)據(jù)、用戶(hù)的初始地點(diǎn)以及時(shí)間(lq,tq)、用戶(hù)需游覽的景點(diǎn)總數(shù)ω，該算法可利用上述信息建立一條具有ω個(gè)點(diǎn)的路線(xiàn)使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) 計(jì)算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ī)劃算法為貪心算法，需要證明其滿(mǎn)足最優(yōu)子結(jié)構(gòu)和貪心選擇性。

1) 最優(yōu)子結(jié)構(gòu)證明

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

2) 貪心選擇性證明

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

采用歸納法證明。

當(dāng)N=1時(shí)，假設(shè) max(M)=li，則有Fitness(li)＞?p∈N&p≠I(mǎi) Fitness(lp)。

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

5 實(shí)驗(yàn)與分析

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

表4 實(shí)驗(yàn)參數(shù)

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

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

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

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

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

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

表5 利益參數(shù)

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

將Request個(gè)數(shù)從6到10進(jìn)行實(shí)驗(yàn)，結(jié)果如圖9所示。本文所提算法的效果更好是因?yàn)橐肓思?xì)化機(jī)制概念，從而把不必要的環(huán)節(jié)刪除。

圖7 不同k值下的路程時(shí)間結(jié)果比較

圖8 不同k值下的程序運(yùn)行時(shí)間結(jié)果比較

圖9 不同Request值下的路程時(shí)間結(jié)果比較

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

圖10 不同時(shí)間點(diǎn)下的路程時(shí)間

由圖10可以看出，Time_Based算法的時(shí)間比本文所提算法時(shí)間略?xún)?yōu)，主要原因是 Time_Based算法只考慮時(shí)間的規(guī)劃而不考慮用戶(hù)的體驗(yàn)度。Rand_GA算法的路程時(shí)間高的原因是它沒(méi)有考慮動(dòng)態(tài)的流量這個(gè)因素。

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

6 結(jié)束語(yǔ)

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

圖11 不同時(shí)間點(diǎn)下的路徑利益

圖12 不同時(shí)間限制下的拓展景點(diǎn)數(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ìn)的灰色模型在交通量預(yù)測(cè)中的應(yīng)用[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)境感知的智能場(chǎng)景分析技術(shù)的研究[D]. 哈爾濱∶ 黑龍江大學(xué), 2015.

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