邱智麟 黃云

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

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

中圖分類號：TP312 文獻標識碼：A 文章編號：1009-3044（2018）08-0172-03

1引言

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

a）知名景點的資源信息過載而不知名的景點卻缺少關注，導致了熱門更熱，冷門更冷。

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

c）網上的資源質量參差不齊，容易誤導游客。

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

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

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

綜上所述，本文的主要貢獻如下：

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

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

c）解決了網上資源質量參差不齊，推薦景點不準確的問題。

本文組織結構如下：第二章綜述相關研究工作；第三章為問題解決步驟；第四章為結束語。

2相關工作

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

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

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

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

3解決步驟

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

本文的景點信息來源于網絡。原始數(shù)據(jù)具有時間相關，位置相關以及非結構化特征。具體說明如下。

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

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

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

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

3.2原始數(shù)據(jù)的結構化表示

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

3.3聚類

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

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

（1）解析含有經緯度的數(shù)據(jù)文件，用合適的數(shù)據(jù)結構緩存到內存中。其中有照片的經緯度，還有景點的經緯度。

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

（3）計算每個點的K-距離值，對K-距離值集合進行排序。

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

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

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

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

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

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

具體步驟如下：

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

N（i）=簇內的點的數(shù)量

景點的評分公式為：

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

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

（3）當i不等于0時，可以選擇瀏覽此景點或不瀏覽，取最大值作為此景點的風景值，并且將最大值對應的景點加入集合。

（4）如果當前金額少于門票錢，則跳過當前景點。

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

3.5景點的季節(jié)性

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

3.6線路規(guī)劃方法

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

4結語

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