基于動態規劃策略的旅游路線規劃?

張皓然 孫冬璞 季發虎 徐銘秋 高 尚 徐 楊

（哈爾濱理工大學計算機科學與技術學院 哈爾濱 150080）

1 引言

隨著經濟的快速發展和社會的飛速進步，我國的旅游市場規模也日益龐大，各類旅游網站和應用軟件應運而生。但是這類應用多數以旅游訂票、預定酒店或者團購各個景點門票為主，在旅游路線規劃方面卻鮮少涉及。現實生活中的旅游需求因人而異，每個人期望的旅游內涵都不盡相同。簡單舉例，比如一個喜歡拍照的大學生來大連旅游，可能并不關心諸如圣亞海洋世界、發現王國這樣的娛樂場所，而更多的是想去濱海路、星海廣場拍一些與海親密接觸的照片，或者去十五庫、貓的天空之城這樣的充滿文藝氣息的場所尋找自己的拍攝靈感，此時各大主流應用軟件提供的旅游路線可能就不太適合，而需要的是一個可以自由定制旅行計劃、并可以根據計劃智能規劃旅游路線的應用軟件。

要解決上述的旅游路線規劃問題，其本質是一個旅行商問題，我們將需求簡化即可得到如下問題描述：用戶當前所在點為起始位置，給定n 個目標節點以及所有節點之間的兩兩相互距離（即駕車所需時間），求一個路徑使得游覽所有的景點后總用時最短。目前暫沒有一個多項式時間復雜度的算法來解決這個問題，所以其還是個NP問題。

目前關于最短路徑和路徑規劃方面已經取得了很多研究成果［1～3］。文獻［4］給出了兼顧查詢者熟悉路徑的個性化路徑規劃框架。文獻［5］提出了多目標路徑規劃，并以事先給出的路網靜態屬性重要程度來簡化最終路徑，不同屬性的重要程度即為駕駛偏好。文獻［6］建立興趣景點集模型和特征拐點集模型，確定多約束指標，以最短路徑規劃為基礎融合多約束指標設計動態旅游路線規劃算法。文獻［7］將“巡檢路線排班最佳”轉化為TSP 動態規劃問題，用貪婪算法分析每班每人近似最佳路線，得到可行路線方案，進行均衡度比較從而選定最佳巡查方案。文獻［8］提出并探討了幾種團隊會合模式，設計了一種基于動態位置的旅游團隊自動會合模型。文獻［9］采用兩階段法的先分組再定路線的策略，設計了一種基于攻略中景點出現頻率的啟發式旅行線路規劃策略用于自動規劃旅游行程。文獻［10］提出基于多源異構眾包數據的風景路線規劃系統，為用戶推薦給定兩點間景色最優的旅行路線。文獻［11］結合群體用戶的個人偏好，發現一條帶有局部分散興趣點且群體收益最大的訪問路線，設計了基于分支限界搜索策略的優化算法。文獻［12～13］根據旅游時間、費用、旅游體驗等數據，對全國5A景區旅游路線進行了規劃。

通過實際應用需求分析可知，用戶對于旅行地點的選擇不會很多，所以，在節點不多的情況下，本文采用能記錄路徑的狀態壓縮動態規劃方法實現用戶的個性化旅游路線規劃，并基于該方法，結合服務器端與客戶端開發技術，設計和開發了應用系統，該系統可以實現用戶常用的地點查詢、區域查詢、最近鄰查詢、群組查詢、天氣查詢等功能，并可以通過與用戶交互，實現個性化旅游路線規劃。

2 基本數據結構

數據結構1（Package）客戶端和服務器端數據傳輸的包頭結構，用于客戶端和服務器端進行數據交換，其內容包括：包的字節數，用戶要訪問的景點數量和景點列表，具體定義和說明如表1所示。

表1 Package結構

數據結構2（Task）服務器端對得到的請求報文進行解析后交給其他協程進行解析后得到的可供協程處理的結構體，其結構如表2所示。

表2 Task結構

數據結構3（Path）服務器端算法部分用來記錄最佳路徑的輔助數據結構，結構如表3所示。

表3 Path結構

3 算法

旅行商問題是NP 問題，如果集合表示用set實現效率很低。由于路線規劃應用中要保存的數都是不重復的較小整數，所以這里用二進制串表示集合。例如集合｛1，3，5，6，7｝表示成二進制串為1110101，其中集合里面有的數對應的位數寫成1，沒有的寫成0。要判斷第3 位是不是1，就把1110101 右移（3-1）位，得到11101，然后結果和00001 進行& 運算，如果結果是1 說明第3 位是1，否則說明第3位是0。

推廣一下，對于數字x，要看它的第i 位是不是1，那么可以通過判斷布爾表達式的真值來實現，表示如下：

要使用動態規劃，需要問題本身有最優子結構，因此需要找到要解決的問題的子問題。

首先將需求抽象，假定出發點編號是0，要去3個景點，編號從1～3，則問題抽象成：從0出發，經過［1，2，3］這三個景點，然后回到0，使得花費最少。要實現這個需求，需要從下面三個實現方案中選擇花費最少的方案：

1）從0 出發，到1，然后再從1 出發，經過［2，3］這兩個城市，最后回到0，使得花費最少。

2）從0 出發，到2，然后再從2 出發，經過［1，3］這兩個城市，最后回到0，使得花費最少。

3）從0 出發，到3，然后再從3 出發，經過［1，2］這兩個城市，最后回到0，使得花費最少。

根據分析，設置一個二維的動態規劃表dp，定義｛1，2，3｝表示經過［1，2，3］這三個城市，然后回到0。則目標函數表示為dp［0］［｛1，2，3｝］。依據前面討論的集合二進制串表示方式，將｛1，2，3｝表示成二進制串111，其對應的十進制數為7，則最終目標函數表示為dp［0］［7］。

求解上述三個方案的最小值意味著：

其中Costa?b表示從a 出發到b 的距離。dp［3］［｛｝］即是從3出發，不經過任何城市回到0的花費，所以dp［3］［｛｝］=Cost3?0。

觀察可知，三個小問題的解決方案的最優解，構成了大的解決方案，所以這個問題具有最優子結構，可以用動態規劃來實現。

假設算上起點后四個景點之間的車行距離如表4所示。

表4 車行距離（單位：min，-1代表不可達）

首先確定dp 表的大小，有n 個景點，從0 開始編號，那么dp 表的行數為n，列數為2（n-1）。在求解時，第一列的值可以從鄰接矩陣導出，后面的列可以由前面的列結合鄰接矩陣導出，所以求出的動態規劃表如表5所示。

表5 動態規劃表（-1代表不可達）

關于最佳路徑的記錄問題，只需要在狀態轉移過程中記錄下每一狀態是從已經計算出來的哪個狀態轉移過來并實時更新即可。

路線規劃具體算法如算法1和算法2所示。

算法1.GetMinTime（Q）

輸入：數據點集Q；

輸出：最佳路徑Path；

Begin

mp?計算所有點之間的相互距離；

for（State?from 0 to（1＜＜n）-1）

for（i?from 0 to n）

for（j?from 0 to n）

if（i=j）then continue；

NewState?State|（1 ＜＜j）；

if（dp［NewState］［j］>mp［i］［j］+dp［State］［i］）

Path［NewState］［j］.pre=State；

Path［NewState］［j］.id=i；

dp［NewState］［j］=mp［i］［j］+dp［State］［i］；

return P；

End.

算法2.GetBestPath（Path）

輸入：得到的最佳路徑記錄數據結構Path；

輸出：最佳訪問路徑BestP；

Begin

PState?Path［State］［i］.pre；

j?P［State］［i］.id；

if（PState！=1&&j=0）then GetBestPath（Path）

append（BestP）；

return BestP；

End.

4 服務器端的構建

本服務器的構建采用Reactor 模式［14］進行設計。Reactor 要求主線程只負責監聽是否有事件發生，如果有就立即將該事件通知工作線程，除此之外不進行任何實質性工作，讀寫數據、接受新連接以及處理客戶請求都由工作線程完成，主線程只負責監聽和分發事件。這種模式很適合Golang 編程語言，主線程負責監聽端口并接受報文，接收到請求后直接調起一個協程對數據進行處理并返回結果。

進行TCP 編程時應注意當面對高并發時TCP的沾包問題［15］，所以在設計數據結構時首先設計了整個包的數據長度，當主線程接收到請求時，首先判斷其字節數與包大小是否相符，再決定是繼續讀取還是丟棄。具體算法如算法3所示。

算法3.CheckData（P）

輸入：數據包P；

輸出：工作協程的任務T；

Begin

if（len>0）then tot+=len；

if（len>=4）then get（P.numByte）；

if（len>=8）then get（P.numSpot）；

if（tot=P.numByte）then return T；

else return Error；

End.

5 客戶端的構建

客戶端的構建使用傳統安卓程序設計架構，具有輕、快、小且節省資源的特點。軟件使用XML 語言設計友好的交互界面，可以良好地反饋結果以及準確的反饋異常。客戶端使用Java 語言處理事務邏輯，并且考慮到移動端計算能力的限制和網絡傳輸的壓力，將復雜的功能交于服務器端進行計算，與服務器端通信的方式采用SOCKET中的TCP編程。

客戶端向用戶提供地點查詢、區域查詢、最近鄰查詢、群組查詢等必要的空間查詢服務接口，并調用API向用戶提供可能需要的服務接口，比如定位、天氣查詢等。例如對于用戶的地點查詢及區域查詢需求，查詢請求及相應查詢結果如圖1 和圖2所示。

圖1 地點查詢

圖2 區域查詢

對于旅游路線規劃功能，使用列表視圖供用戶自由選擇，用戶提交后分步顯示服務器返回的景點順序和具體路徑，并將其在地圖上直觀地顯示出來，用戶可以根據返回的時間和路徑，靈活地安排和調整計劃，如用戶想要游覽金龍山、龍鳳山和中國亭園，可以進入助手界面并選中這三個景點提交查詢，結果如圖3和圖4所示。

圖3 旅游路線規劃結果（1）

圖4 旅游路線規劃結果（2）

如果想要得到具體路線，也可點擊詳情。

6 結語

動態規劃在經濟管理、生產調度、工程技術和最優控制等方面得到了廣泛的應用。例如最短路徑、庫存管理、資源分配、設備更新、排序、裝載等問題，用動態規劃方法比用其他方法求解更為方便。本文利用動態規劃算法，結合服務器端與客戶端開發技術，實現了交互查詢和旅游路線規劃，給出了實際解決方法和過程，同時討論了基于路徑記錄的狀態壓縮動態規劃策略在解決帶有節點數量限制的旅游路線規劃問題中的應用。