基于TSP 模型的游覽路線設(shè)計(jì)研究
——以徐州潘安湖風(fēng)景區(qū)為例

肖人峰，陳 瑞，李靜雯，蘇小珂，張 斌

（成都信息工程大學(xué) 通信工程學(xué)院，四川 成都610225）

1 引言

本研究選取潘安湖景區(qū)的部分景點(diǎn)，完成徐州潘安湖風(fēng)景區(qū)游覽路線設(shè)計(jì)問題[1]。假設(shè)游客在景區(qū)停留的時(shí)間由景點(diǎn)之間的步行時(shí)間、景點(diǎn)游覽時(shí)間（即在景點(diǎn)內(nèi)游玩的時(shí)間）、在景區(qū)外的等待時(shí)間三部分組成，其他時(shí)間忽略不計(jì)。

2 模型建立

給每個(gè)景點(diǎn)編號(hào)：0 為景石，1 為游客服務(wù)中心，2 為陽光草坪，3 為森林小劇場(chǎng)，4 為兒童科普體驗(yàn)區(qū)，5 為兒童戲水場(chǎng)，6 為濕地博物館，7 為濕地商業(yè)街。

已知dij表示景點(diǎn)i和景點(diǎn)j之間的距離，則這8 個(gè)地點(diǎn)之間就存在著這樣一個(gè)距離矩陣D。它的特點(diǎn)為：D是一個(gè)8×8 的方陣，其對(duì)角線元素全部為0，其他元素是以對(duì)角線元素為對(duì)稱軸對(duì)稱分布的。

對(duì)于旅游路線優(yōu)化的問題，可以抽象地描述為從景石出發(fā)，遍訪7 個(gè)景點(diǎn)求總距離最短的閉合路徑。于是這個(gè)旅游路線問題的有效解為這7 個(gè)元素的一個(gè)循環(huán)排列C={C0，C1，…，C7}，（Ci∈[0，7]，當(dāng)i≠j時(shí)Ci≠Cj）。

求旅游路線問題的最優(yōu)解，就是尋找一個(gè)C，使得下列目標(biāo)函數(shù)值最小其中dCiCj表示景點(diǎn)Ci和景點(diǎn)Cj之間的距離。

游客旅游時(shí)未達(dá)到盡量縮短路程的目的，憑經(jīng)驗(yàn)一般會(huì)這樣確定路線：根據(jù)各景點(diǎn)的分布情況，將其劃分在不同的旅游區(qū)。游玩時(shí)先確定不同旅游區(qū)的先后順序，再確定同一旅游區(qū)內(nèi)各景點(diǎn)順序。此思想可看出，相距較近的兩景點(diǎn)形成直接通路的可能性較大，相距較遠(yuǎn)的兩景點(diǎn)由于可能分屬于不同的區(qū)，形成直接通路的可能性較小，而形成間接通路的可能性較大。

各景點(diǎn)根據(jù)“遠(yuǎn)近親疏”的關(guān)系，按遠(yuǎn)近分別劃分在不同的旅游區(qū)。應(yīng)用同樣的思想，同一旅游區(qū)內(nèi)各景點(diǎn)根據(jù)距離遠(yuǎn)近不同，又可劃分成次小區(qū)，次小區(qū)內(nèi)又可繼續(xù)劃分，直到劃分的最后區(qū)域只包含單個(gè)景點(diǎn)元素。

上述是一種遞歸的思想，與樹結(jié)構(gòu)的遞歸定義十分類似，所以可以把這種層次關(guān)系用樹的分支結(jié)構(gòu)表示的層次關(guān)系描述出來。本文用樹中結(jié)構(gòu)最筒單的二叉樹描述這種關(guān)系。根據(jù)上述確定最短路徑的原則和分析思路，建立一棵二叉樹把16 這個(gè)元素的相互距離關(guān)系描繪出來。

建立二叉樹的基本原則是：距離較近的景點(diǎn)應(yīng)位于二叉樹較近的分支上，距離相對(duì)最近兩個(gè)景點(diǎn)是“兄弟”關(guān)系，二者結(jié)合成一“景點(diǎn)組合”作為他們的“雙親”結(jié)點(diǎn)。這個(gè)“景點(diǎn)組合”作為一個(gè)整體元素再加人到下一輪的距離比較中。例如：在上述8 個(gè)元素（包括7 個(gè)景點(diǎn)和序號(hào)為0 的景石）中，景點(diǎn)6 與景點(diǎn)7 距離最短，首先把它們結(jié)合起來，并賦予編號(hào)8，可稱之為景點(diǎn)組合8。用二叉樹表示景點(diǎn)6和景點(diǎn)7 以及景點(diǎn)組合8 的關(guān)系為以6、7 作為孩子結(jié)點(diǎn)（這里同時(shí)也是葉子結(jié)點(diǎn)），8 作為結(jié)點(diǎn)6、7 的“雙親”。而景點(diǎn)組合8 與其他某景點(diǎn)k之間的距離用公式計(jì)算：

這里d8，k為景點(diǎn)組合8 與景點(diǎn)k的距離，d6，k為景點(diǎn)6與景點(diǎn)k的距離，d7，k為景點(diǎn)7 與景點(diǎn)k的距離。這時(shí)把景點(diǎn)6 和景點(diǎn)7 從原問題中消去，取而代之的是它們的元素組合8。因此，這個(gè)景點(diǎn)的旅游路線問題被改變?yōu)? 個(gè)景點(diǎn)來處理。類似的，可確定7 個(gè)景點(diǎn)中剩下相距最短的2 個(gè)景點(diǎn)，推算可知為景點(diǎn)1 和景點(diǎn)8。這2 個(gè)景點(diǎn)也被組合起來，編號(hào)為9。以此類推，不斷將各元素組合，這樣得到的最后一個(gè)元素組合15 就能把所有景點(diǎn)包括進(jìn)去。

使用下面公式計(jì)算距離時(shí)，將a、b、c、k可看作為一個(gè)整體。

式（1）是a，b的組合，而a，b，k可以是某一單點(diǎn)元素（當(dāng)編號(hào)在[0，7]內(nèi)時(shí)），也可以是一個(gè)元素組合（當(dāng)編號(hào)在[7，14]內(nèi)時(shí)）。若a、b、k之中還存在元素組合，假設(shè)b就是個(gè)組合，則將db，k繼續(xù)按照式（1）展開，直到最終導(dǎo)出葉子結(jié)點(diǎn)間的距離關(guān)系，將距離dc，k計(jì)算出來。

3 模型求解

遍歷二叉樹并建立最短閉合回路主要包括三個(gè)環(huán)節(jié)：把當(dāng)前分支結(jié)點(diǎn)i從當(dāng)前閉合路徑中刪除；找到當(dāng)前結(jié)點(diǎn)i的右孩子結(jié)點(diǎn)1，按照使當(dāng)前閉合路徑為最小的原則，將其插入到當(dāng)前閉合路徑；找到當(dāng)前結(jié)點(diǎn)i的左孩子結(jié)點(diǎn)h，按照使當(dāng)前閉合路徑為最小的原則，將其插入到當(dāng)前閉合路徑。

采用二叉樹方法描述旅游路線優(yōu)化問題的最終具體路徑，結(jié)果如表1 所示。

表1 結(jié)果表格