基于動(dòng)態(tài)規(guī)劃策略的旅游路線規(guī)劃?

張皓然 孫冬璞 季發(fā)虎 徐銘秋 高 尚 徐 楊

（哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 哈爾濱 150080）

1 引言

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

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

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

通過實(shí)際應(yīng)用需求分析可知，用戶對(duì)于旅行地點(diǎn)的選擇不會(huì)很多，所以，在節(jié)點(diǎn)不多的情況下，本文采用能記錄路徑的狀態(tài)壓縮動(dòng)態(tài)規(guī)劃方法實(shí)現(xiàn)用戶的個(gè)性化旅游路線規(guī)劃，并基于該方法，結(jié)合服務(wù)器端與客戶端開發(fā)技術(shù)，設(shè)計(jì)和開發(fā)了應(yīng)用系統(tǒng)，該系統(tǒng)可以實(shí)現(xiàn)用戶常用的地點(diǎn)查詢、區(qū)域查詢、最近鄰查詢、群組查詢、天氣查詢等功能，并可以通過與用戶交互，實(shí)現(xiàn)個(gè)性化旅游路線規(guī)劃。

2 基本數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)1（Package）客戶端和服務(wù)器端數(shù)據(jù)傳輸?shù)陌^結(jié)構(gòu)，用于客戶端和服務(wù)器端進(jìn)行數(shù)據(jù)交換，其內(nèi)容包括：包的字節(jié)數(shù)，用戶要訪問的景點(diǎn)數(shù)量和景點(diǎn)列表，具體定義和說明如表1所示。

表1 Package結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)2（Task）服務(wù)器端對(duì)得到的請(qǐng)求報(bào)文進(jìn)行解析后交給其他協(xié)程進(jìn)行解析后得到的可供協(xié)程處理的結(jié)構(gòu)體，其結(jié)構(gòu)如表2所示。

表2 Task結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)3（Path）服務(wù)器端算法部分用來記錄最佳路徑的輔助數(shù)據(jù)結(jié)構(gòu)，結(jié)構(gòu)如表3所示。

表3 Path結(jié)構(gòu)

3 算法

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

推廣一下，對(duì)于數(shù)字x，要看它的第i 位是不是1，那么可以通過判斷布爾表達(dá)式的真值來實(shí)現(xiàn)，表示如下：

要使用動(dòng)態(tài)規(guī)劃，需要問題本身有最優(yōu)子結(jié)構(gòu)，因此需要找到要解決的問題的子問題。

首先將需求抽象，假定出發(fā)點(diǎn)編號(hào)是0，要去3個(gè)景點(diǎn)，編號(hào)從1～3，則問題抽象成：從0出發(fā)，經(jīng)過［1，2，3］這三個(gè)景點(diǎn)，然后回到0，使得花費(fèi)最少。要實(shí)現(xiàn)這個(gè)需求，需要從下面三個(gè)實(shí)現(xiàn)方案中選擇花費(fèi)最少的方案：

1）從0 出發(fā)，到1，然后再從1 出發(fā)，經(jīng)過［2，3］這兩個(gè)城市，最后回到0，使得花費(fèi)最少。

2）從0 出發(fā)，到2，然后再從2 出發(fā)，經(jīng)過［1，3］這兩個(gè)城市，最后回到0，使得花費(fèi)最少。

3）從0 出發(fā)，到3，然后再從3 出發(fā)，經(jīng)過［1，2］這兩個(gè)城市，最后回到0，使得花費(fèi)最少。

根據(jù)分析，設(shè)置一個(gè)二維的動(dòng)態(tài)規(guī)劃表dp，定義｛1，2，3｝表示經(jīng)過［1，2，3］這三個(gè)城市，然后回到0。則目標(biāo)函數(shù)表示為dp［0］［｛1，2，3｝］。依據(jù)前面討論的集合二進(jìn)制串表示方式，將｛1，2，3｝表示成二進(jìn)制串111，其對(duì)應(yīng)的十進(jìn)制數(shù)為7，則最終目標(biāo)函數(shù)表示為dp［0］［7］。

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

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

觀察可知，三個(gè)小問題的解決方案的最優(yōu)解，構(gòu)成了大的解決方案，所以這個(gè)問題具有最優(yōu)子結(jié)構(gòu)，可以用動(dòng)態(tài)規(guī)劃來實(shí)現(xiàn)。

假設(shè)算上起點(diǎn)后四個(gè)景點(diǎn)之間的車行距離如表4所示。

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

首先確定dp 表的大小，有n 個(gè)景點(diǎn)，從0 開始編號(hào)，那么dp 表的行數(shù)為n，列數(shù)為2（n-1）。在求解時(shí)，第一列的值可以從鄰接矩陣導(dǎo)出，后面的列可以由前面的列結(jié)合鄰接矩陣導(dǎo)出，所以求出的動(dòng)態(tài)規(guī)劃表如表5所示。

表5 動(dòng)態(tài)規(guī)劃表（-1代表不可達(dá)）

關(guān)于最佳路徑的記錄問題，只需要在狀態(tài)轉(zhuǎn)移過程中記錄下每一狀態(tài)是從已經(jīng)計(jì)算出來的哪個(gè)狀態(tài)轉(zhuǎn)移過來并實(shí)時(shí)更新即可。

路線規(guī)劃具體算法如算法1和算法2所示。

算法1.GetMinTime（Q）

輸入：數(shù)據(jù)點(diǎn)集Q；

輸出：最佳路徑Path；

Begin

mp?計(jì)算所有點(diǎn)之間的相互距離；

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）

輸入：得到的最佳路徑記錄數(shù)據(jù)結(jié)構(gòu)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 服務(wù)器端的構(gòu)建

本服務(wù)器的構(gòu)建采用Reactor 模式［14］進(jìn)行設(shè)計(jì)。Reactor 要求主線程只負(fù)責(zé)監(jiān)聽是否有事件發(fā)生，如果有就立即將該事件通知工作線程，除此之外不進(jìn)行任何實(shí)質(zhì)性工作，讀寫數(shù)據(jù)、接受新連接以及處理客戶請(qǐng)求都由工作線程完成，主線程只負(fù)責(zé)監(jiān)聽和分發(fā)事件。這種模式很適合Golang 編程語言，主線程負(fù)責(zé)監(jiān)聽端口并接受報(bào)文，接收到請(qǐng)求后直接調(diào)起一個(gè)協(xié)程對(duì)數(shù)據(jù)進(jìn)行處理并返回結(jié)果。

進(jìn)行TCP 編程時(shí)應(yīng)注意當(dāng)面對(duì)高并發(fā)時(shí)TCP的沾包問題［15］，所以在設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)時(shí)首先設(shè)計(jì)了整個(gè)包的數(shù)據(jù)長(zhǎng)度，當(dāng)主線程接收到請(qǐng)求時(shí)，首先判斷其字節(jié)數(shù)與包大小是否相符，再?zèng)Q定是繼續(xù)讀取還是丟棄。具體算法如算法3所示。

算法3.CheckData（P）

輸入：數(shù)據(jù)包P；

輸出：工作協(xié)程的任務(wù)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 客戶端的構(gòu)建

客戶端的構(gòu)建使用傳統(tǒng)安卓程序設(shè)計(jì)架構(gòu)，具有輕、快、小且節(jié)省資源的特點(diǎn)。軟件使用XML 語言設(shè)計(jì)友好的交互界面，可以良好地反饋結(jié)果以及準(zhǔn)確的反饋異常。客戶端使用Java 語言處理事務(wù)邏輯，并且考慮到移動(dòng)端計(jì)算能力的限制和網(wǎng)絡(luò)傳輸?shù)膲毫Γ瑢?fù)雜的功能交于服務(wù)器端進(jìn)行計(jì)算，與服務(wù)器端通信的方式采用SOCKET中的TCP編程。

客戶端向用戶提供地點(diǎn)查詢、區(qū)域查詢、最近鄰查詢、群組查詢等必要的空間查詢服務(wù)接口，并調(diào)用API向用戶提供可能需要的服務(wù)接口，比如定位、天氣查詢等。例如對(duì)于用戶的地點(diǎn)查詢及區(qū)域查詢需求，查詢請(qǐng)求及相應(yīng)查詢結(jié)果如圖1 和圖2所示。

圖1 地點(diǎn)查詢

圖2 區(qū)域查詢

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

圖3 旅游路線規(guī)劃結(jié)果（1）

圖4 旅游路線規(guī)劃結(jié)果（2）

如果想要得到具體路線，也可點(diǎn)擊詳情。

6 結(jié)語

動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路徑、庫存管理、資源分配、設(shè)備更新、排序、裝載等問題，用動(dòng)態(tài)規(guī)劃方法比用其他方法求解更為方便。本文利用動(dòng)態(tài)規(guī)劃算法，結(jié)合服務(wù)器端與客戶端開發(fā)技術(shù)，實(shí)現(xiàn)了交互查詢和旅游路線規(guī)劃，給出了實(shí)際解決方法和過程，同時(shí)討論了基于路徑記錄的狀態(tài)壓縮動(dòng)態(tài)規(guī)劃策略在解決帶有節(jié)點(diǎn)數(shù)量限制的旅游路線規(guī)劃問題中的應(yīng)用。