基于旅游互動平臺的線路規(guī)劃

邱智麟 黃云

摘要：為幫助旅行者更好的規(guī)劃旅游線路，以旅行者對這次旅游所能投入的金錢和時間為約束條件，通過對含有位置信息的圖片聚類得出當(dāng)前季節(jié)熱度最高的景點(diǎn)，然后利用漢密爾頓最短回路算法得出滿足條件的路徑。

關(guān)鍵詞：路徑規(guī)劃；最短路徑；漢密爾頓回路；聚類；動態(tài)規(guī)劃

中圖分類號：TP312 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）08-0172-03

1引言

現(xiàn)在人們在休息時間大多選擇出外旅行，這樣不僅可以增加和同伴之間的感情，也可以增長自己的見識，放松自己的身心。然而在選擇景點(diǎn)的時候，只考慮了哪個景點(diǎn)好玩，沒有考慮景點(diǎn)間的路程，因而花費(fèi)了大量的時間奔走在景點(diǎn)之間。很顯然，如果將路徑規(guī)劃應(yīng)用于此，將減少人們在行程中花費(fèi)的時間，從而有更多的時間游玩景點(diǎn)。路徑規(guī)劃是指，在具有障礙物的環(huán)境中，按照一定的評價標(biāo)準(zhǔn)，尋找一條從起始狀態(tài)到目標(biāo)狀態(tài)的無碰撞路徑。也就是說，給定起點(diǎn)和終點(diǎn)，一些約束條件，那么可以返回一條通過各個景點(diǎn)的最短路徑?，F(xiàn)在也有很多的應(yīng)用實現(xiàn)了路徑規(guī)劃。如百度地圖，可以通過指定起點(diǎn)和終點(diǎn)，出行方式，百度地圖返回一條最短路徑，而且有考慮當(dāng)時的交通狀況。但是人們出外旅行往往會選擇很多的景點(diǎn)，有時甚至不知道該去什么景點(diǎn)，那么路徑規(guī)劃算法就不僅需要考慮所有的景點(diǎn)之間的聯(lián)系，還要考慮到什么樣的景點(diǎn)應(yīng)該在這條路徑上。因為百度地圖面向的用戶群并不是游客，所以景點(diǎn)推薦功能做的并不完善，只推薦了非常熱門的景點(diǎn)，然而很多游客并不看重景點(diǎn)的熱門度。攜程網(wǎng)上有很多旅游攻略，大多是由本地人所寫，所以行程安排可以安排得很妥當(dāng)，但是攻略數(shù)量非常多，這對游客來說，需要閱讀大量文章才可能找到一條符合自己期望的路線，這浪費(fèi)了很多的時間，而且攻略質(zhì)量參差不齊?？偟膩碚f，問題可以總結(jié)為以下幾點(diǎn)：

a）知名景點(diǎn)的資源信息過載而不知名的景點(diǎn)卻缺少關(guān)注，導(dǎo)致了熱門更熱，冷門更冷。

b）沒有提供一些旅游線路的推薦，傳統(tǒng)的地圖軟件只能從快速便捷的角度推薦一些行走路線，并沒有考慮旅游實際過程中（如天氣改變）游客的感受等一些問題，這就將導(dǎo)致游客的旅游體驗大大下降。

c）網(wǎng)上的資源質(zhì)量參差不齊，容易誤導(dǎo)游客。

隨著互聯(lián)網(wǎng)和智能手機(jī)的快速發(fā)展，越來越多的游客習(xí)慣用手機(jī)拍攝景點(diǎn)并分享到自己的朋友圈，于是，便產(chǎn)生了大量含有重要信息的圖片，信息包括照片拍攝的位置，時間，其他用戶對照片的評分等，這些信息反映了游客的行為模式以及景點(diǎn)的流行度，這為路線規(guī)劃提供了巨大的幫助。

在現(xiàn)有的線路規(guī)劃方法中，大多是以用戶的GPS軌跡，帶有位置信息的圖片，旅游攻略為基礎(chǔ)，來規(guī)劃線路。于是，針對以上提出的問題，并結(jié)合基于旅游的互動平臺的各種數(shù)據(jù)，我們提出了新的解法。問題假設(shè)我們從某一起點(diǎn)出發(fā)，最終回到起點(diǎn)，其間經(jīng)過的路程最短，景點(diǎn)總體風(fēng)景值最高，并且沒有超過用戶規(guī)定的時間和金錢。具體定義見第三章。其主要流程如圖所示。

為解決資源質(zhì)量參差不齊的情況，我們從網(wǎng)絡(luò)上爬取大量攻略，將其轉(zhuǎn)換成景點(diǎn)資源描述三元組然后從旅游互動平臺上獲取帶有位置信息的圖片，將景點(diǎn)的位置和圖片的位置一起進(jìn)行聚類，得到一個人氣很高的景點(diǎn)集合，而不再是那些典型的景點(diǎn)。然后用貪心算法篩選出即滿足用戶時間約束，也滿足金錢約束的景點(diǎn)，最后以景點(diǎn)間的距離為權(quán)重，采用哈密頓最短回路方法規(guī)劃景點(diǎn)間旅游順序。這樣便解決上面說明的問題。

綜上所述，本文的主要貢獻(xiàn)如下：

a）針對景點(diǎn)的季節(jié)性以及用戶多樣的需求，提出了更加完善的路線推薦。

b）不僅考慮了知名景點(diǎn)，也考慮了冷門但好玩的景點(diǎn)。

c）解決了網(wǎng)上資源質(zhì)量參差不齊，推薦景點(diǎn)不準(zhǔn)確的問題。

本文組織結(jié)構(gòu)如下：第二章綜述相關(guān)研究工作；第三章為問題解決步驟；第四章為結(jié)束語。

2相關(guān)工作

文獻(xiàn)1設(shè)計改進(jìn)了一種基于攻略中景點(diǎn)詞頻的先分組再定路線的啟發(fā)式旅行線路規(guī)劃策略，即首先基于旅游攻略中所提景點(diǎn)頻數(shù)對景點(diǎn)進(jìn)行受歡迎程度的排序，然后根據(jù)旅行時間、景點(diǎn)類型、景點(diǎn)間距離等過濾條件使用點(diǎn)分配聚類方法將景點(diǎn)進(jìn)行聚類，最后再在各類中規(guī)劃最優(yōu)路線。最終證明了這種啟發(fā)式策略使得旅行線路的時間分配更加均勻，景點(diǎn)間路程更短，線路的游覽時間與景點(diǎn)間距離的費(fèi)效比更高。因此文獻(xiàn)1具有很高的實用價值。但是文獻(xiàn)1重點(diǎn)并不在于研究如何規(guī)劃各個景點(diǎn)間的具體的最優(yōu)行進(jìn)路線，而是研究各個景點(diǎn)的游覽順序，以滿足線路中各景點(diǎn)間的路程最短，銜接的時間最小。

文獻(xiàn)2則是通過大量多源異構(gòu)的眾包數(shù)據(jù)對路段風(fēng)景值進(jìn)行評分，利用基于規(guī)則的路線規(guī)劃算法，在整體路線長度約束下，增加一個或多個風(fēng)景路段，達(dá)到找出起點(diǎn)和終點(diǎn)之間的近似最優(yōu)風(fēng)景路線的目的。實驗表明，這種方法有效地提高了整體路線的風(fēng)景值。

文獻(xiàn)3則考慮了群體旅游路線推薦，通過研究用戶偏好，給出一條整體滿意度最高，線路風(fēng)景值最佳的線路。以上策略存在的一個問題就是沒有考慮用戶多樣的需求，如用戶出游的時間，需要花費(fèi)的金錢等，文獻(xiàn)[1-3]只是將風(fēng)景值高的景點(diǎn)以最短的路徑連接起來推薦給用戶，這樣大大降低了用戶的旅游體驗。

文獻(xiàn)[5-6]則是模擬游客游覽全國201個5A景區(qū)，很明顯，并不是所有的游客都想去游覽全國201個5A景區(qū)，但是文獻(xiàn)[5-6]提出了基于多目標(biāo)優(yōu)化的旅游模型，也就是說考慮了用戶很多的需求，如游客的出行工具等，這為本文提供了思路。

3解決步驟

3.1數(shù)據(jù)特點(diǎn)分析

本文的景點(diǎn)信息來源于網(wǎng)絡(luò)。原始數(shù)據(jù)具有時間相關(guān)，位置相關(guān)以及非結(jié)構(gòu)化特征。具體說明如下。

（1）時間相關(guān)：時間相關(guān)是指原始數(shù)據(jù)中含有大量與時間有關(guān)的信息，如景點(diǎn)參觀時長，景點(diǎn)開放時間等。

（2）位置相關(guān)：位置相關(guān)是指原始數(shù)據(jù)中含有景點(diǎn)位置，地點(diǎn)名詞等信息。

（3）非結(jié)構(gòu)化：對于原始數(shù)據(jù)，是通過網(wǎng)絡(luò)爬蟲直接獲取網(wǎng)頁的html文件，其中包含了大量的無用信息，不具備結(jié)構(gòu)化特征，因此需要將其轉(zhuǎn)換。

另外，本文還是用了來自基于Map的旅游平臺的數(shù)據(jù)，主要是包含了位置，時間信息的圖片。

3.2原始數(shù)據(jù)的結(jié)構(gòu)化表示

原始數(shù)據(jù)的結(jié)構(gòu)化表示是指將需要的數(shù)據(jù)提取出來，選擇合適的數(shù)據(jù)結(jié)構(gòu)來表示，這樣方便于程序設(shè)計。根據(jù)本文的需要，使用并改進(jìn)了文獻(xiàn)中的景點(diǎn)表述三元組來建立景點(diǎn)信息庫。如下表所示，其中url為景點(diǎn)的唯一標(biāo)識。

3.3聚類

聚類的目的是為了找出熱門的景點(diǎn)，因此提出一個假設(shè)。如果某個區(qū)域分布的照片數(shù)量越多，那么該區(qū)域的風(fēng)景質(zhì)量越好。有日常經(jīng)驗可知，如果人們外出游玩，遇到了一個風(fēng)景優(yōu)美的地方，都會通過拍照來記錄這個地方，因此，如果某個區(qū)域的照片數(shù)量非常多，那么這個區(qū)域定是一個風(fēng)景優(yōu)美的景點(diǎn)。

于是，通過分析照片的空間分布，可以得出熱門景點(diǎn)的分布。本文采用的方法是一種基于密度的聚類算法，它能夠?qū)⒆銐蚋呙芏鹊膮^(qū)域劃分為簇，并且可以在具有噪聲的數(shù)據(jù)中發(fā)現(xiàn)任意形狀的簇。由上文可知某個區(qū)域圖片密度越高，就也有可能是一個景點(diǎn)。所以DBSCAN算法符合我們的要求。主要步驟如下。

（1）解析含有經(jīng)緯度的數(shù)據(jù)文件，用合適的數(shù)據(jù)結(jié)構(gòu)緩存到內(nèi)存中。其中有照片的經(jīng)緯度，還有景點(diǎn)的經(jīng)緯度。

（2）計算每個點(diǎn)與其他點(diǎn)之間的歐幾里得距離。

（3）計算每個點(diǎn)的K-距離值，對K-距離值集合進(jìn)行排序。

（4）將K-距離值用散點(diǎn)圖的形式表示出來。

（5）根據(jù)散點(diǎn)圖確定半徑Eps的值。

（6）根據(jù)MinPts=4和Eps的值，計算所有核心點(diǎn)，并建立核心點(diǎn)與到核心點(diǎn)距離小于半徑Eps的點(diǎn)的映射。

（7）根據(jù)得到的核心點(diǎn)集合，以及半徑Eps的值，計算能夠連通的核心點(diǎn)，并得到離群點(diǎn)。

（8）將能夠連通的每一組核心點(diǎn)，以及到核心點(diǎn)距離小于半徑Eps的點(diǎn)，都放到一起，形成一個。

（9）遍歷每個簇，如果其中包含了已知的景點(diǎn)，則將該景點(diǎn)放入集合，如果沒有，則說明這是一個未發(fā)掘的景點(diǎn)，任取一點(diǎn)放入集合。

具體步驟如下：

圖中的點(diǎn)即為圖片的拍攝位置，圖中含有兩個簇，即兩個景點(diǎn)，景點(diǎn)范圍內(nèi)照片數(shù)量計算公式為：

N（i）=簇內(nèi)的點(diǎn)的數(shù)量

景點(diǎn)的評分公式為：

（1）初始化。根據(jù)需要初始化總金額money和景點(diǎn)數(shù)i，以及每個景點(diǎn)的評分grade[i]，每個景點(diǎn)的門票錢moneyNeeded[i]和一個空集合，來存放合格的景點(diǎn)。

（2）當(dāng)i等于0時，也就是瀏覽最后一個景點(diǎn)時，如果當(dāng)前剩余的錢能夠購買門票，返回這個景點(diǎn)的風(fēng)景值并將此景點(diǎn)加人集合，否則返回0。

（3）當(dāng)i不等于0時，可以選擇瀏覽此景點(diǎn)或不瀏覽，取最大值作為此景點(diǎn)的風(fēng)景值，并且將最大值對應(yīng)的景點(diǎn)加入集合。

（4）如果當(dāng)前金額少于門票錢，則跳過當(dāng)前景點(diǎn)。

到此，我們找出了所有景點(diǎn)門票和不超過用戶的規(guī)定金額，并且景點(diǎn)評分綜合最高的一組景點(diǎn)組合。

3.5景點(diǎn)的季節(jié)性

由上一小節(jié)可知，我們已經(jīng)得出了門票總和不超過用戶規(guī)定金額的所有景點(diǎn)集合，因為景點(diǎn)帶有季節(jié)性，所以我們只比對景點(diǎn)的季節(jié)性和用戶旅游時間所在的季節(jié)，如果不同，則將該景點(diǎn)從集合中剔除。此功能看似簡單，然而確實各個旅游平臺路線推薦時沒有考慮到的。這也是本文的亮點(diǎn)所在。

3.6線路規(guī)劃方法

根據(jù)假設(shè)，我們從起點(diǎn)出發(fā)，經(jīng)過所有的景點(diǎn)僅且一次，最終回到起點(diǎn)，這是典型的漢密爾頓回路問題。又因為我們希望總路程最短，以景點(diǎn)間的距離作為權(quán)重，所以該問題演變成了賦權(quán)漢密爾頓回路最小化問題。具體定義如下。給定i個點(diǎn)及i個點(diǎn)兩兩之間的距離，求一條回路，使之經(jīng)過所有的點(diǎn)，且經(jīng)過每個點(diǎn)僅一次，而整條回路的總距離最小。具體解決辦法見文獻(xiàn)4。

4結(jié)語

旅游已經(jīng)是人們生活中一個必不可少的組成部分，而線路規(guī)劃是開始旅游前面臨的一個非常重要的問題，本文通過對照片的位置進(jìn)行聚類分析，得出風(fēng)景值高的景點(diǎn)，然后運(yùn)用動態(tài)規(guī)劃策略得出在不超過用戶的限定金額下的風(fēng)景值總和最高的風(fēng)景點(diǎn)集合，然后通過哈密頓最短回路算法得出路徑。