基于DST—ROPT算法的貴陽(yáng)市旅行線路設(shè)計(jì)與優(yōu)化

摘 要：針對(duì)旅游線路的特征，把雙生成樹(shù)啟發(fā)式算法得到的解作為局部搜索算法R-OPT的初始解，在此基礎(chǔ)上進(jìn)行局部搜索優(yōu)化，得到高效率的DST-ROPT算法。實(shí)驗(yàn)表明：DST-ROPT算法與精確算法分支界定法得到的解幾乎一樣，DST-ROPT算法得到的解是較為優(yōu)化的。最后將DST-ROPT算法應(yīng)用到貴陽(yáng)市旅游線路的設(shè)計(jì)與優(yōu)化中，為游客提供滿意的服務(wù)。

關(guān)鍵詞：旅游線路；雙生成樹(shù)啟發(fā)式算法；R-OPT算法；局部?jī)?yōu)化；DST-ROPT

中圖分類(lèi)號(hào)：TP391.9

近年來(lái)，在貴州省委、省政府的高度重視下，貴州的旅游業(yè)有了長(zhǎng)足發(fā)展，但在旅游業(yè)的信息化建設(shè)方面相對(duì)滯后。貴州旅游業(yè)要快速發(fā)展，科技要先行。對(duì)于初到貴州、初到貴陽(yáng)的游客怎樣在有限的時(shí)間內(nèi)合理游覽更多的景點(diǎn)，在游客選出的旅游景點(diǎn)中怎樣為游客推薦一條最優(yōu)或較優(yōu)的旅游路線，這是提高游客滿意度的重要內(nèi)容，也是本文主要研究的問(wèn)題。

1 DST-ROPT算法概述

1.1 問(wèn)題描述及DST-ROPT算法思想

旅游線路的設(shè)計(jì)實(shí)際上是旅行商TPS問(wèn)題。本文研究的TPS問(wèn)題：已知N個(gè)景點(diǎn)的相互距離，現(xiàn)有游客要游遍這N個(gè)景點(diǎn)，并且每個(gè)景點(diǎn)只走一次，最后回到出發(fā)景點(diǎn)。如何為游客設(shè)計(jì)旅游路線，才能使其旅行線路總路程最短？旅游商問(wèn)題是組合優(yōu)化問(wèn)題中典型的NP-Hard問(wèn)題，也被證明是NPC問(wèn)題，如果能從旅行商問(wèn)題中找到多項(xiàng)式算法，那么所有的P=NP問(wèn)題就能夠得到完美的解決，所以旅行商問(wèn)題具有較高的理論價(jià)值和實(shí)際應(yīng)用價(jià)值[1]。目前也存在一些求解TPS問(wèn)題的精確算法，在這些精確算法中很多運(yùn)行時(shí)間讓人無(wú)法忍受，解決實(shí)際問(wèn)題的可行性還較低，真正有效的算法還很少，因此產(chǎn)生了很多啟發(fā)式近似算法，近似算法雖然從運(yùn)行時(shí)間上得到了很大地改善，但運(yùn)行結(jié)果距離最優(yōu)解的程度還不能讓人滿意[2]。

本文在前人研究的基礎(chǔ)上，針對(duì)旅游數(shù)據(jù)不算大的特點(diǎn)，將雙生成樹(shù)啟發(fā)式算法與局部搜索算法r-opt結(jié)合得到組合算法DST-ROPT算法。DST-ROPT算法的思想：雙生成樹(shù)啟發(fā)式算法具有運(yùn)行速度快、簡(jiǎn)單、編程容易實(shí)現(xiàn)以及占用空間少等優(yōu)點(diǎn)，但是在最壞情況下時(shí)間復(fù)雜度是O（n3）[3]。雙生成樹(shù)啟發(fā)式算法求出的結(jié)果還不夠好，于是想到把雙生成樹(shù)輸出的結(jié)果作為r-opt算法的初始解，采用r-opt算法在初始解上每次交換r條邊來(lái)進(jìn)行局部?jī)?yōu)化，得到一個(gè)較優(yōu)解，從而提高整個(gè)算法的效率。

1.2 DST-ROPT算法描述

大量計(jì)算證明，3-opt算法比2-opt算法好，4-opt算法和5-opt算法并不比3-opt算法優(yōu)越，而R值越大，運(yùn)行時(shí)間越長(zhǎng)[3]，因此在DST-ROPT算法中R值取3，DST-ROPT的實(shí)現(xiàn)步驟如下：

輸入：連通圖上任意兩點(diǎn)間的最短距離

輸出：一條Hamilton回路

第一階段：雙生成樹(shù)算法得到初始解[3]：

step1：通過(guò)floyd算法求出最小生成樹(shù)；

step2：在最小生成樹(shù)中將各邊都增加一條重復(fù)邊，求出其Euler回路；

step3：在Euler回路序列中刪除重復(fù)點(diǎn)，得到一條Hamilton回路。

第二階段：用R-OPT算法對(duì)初始解加以改進(jìn)

R-OPT算法的思想：設(shè)T為一條初始回路，該算法每次都試圖找到兩個(gè)邊的集合A={a1，a2，a3，…，ar}A∈T和B={b1，b2，b3，…，br}B T，如果用A集合中的邊替換B集合中的相應(yīng)邊，能夠得到的一條新的回路T’，并且T’回路的總路程比T回路的總路程要短，那么就用A集合中的邊替換B集合中的相應(yīng)邊，這R條邊的交換就叫R-OPT交換[4][5]。針對(duì)本文的實(shí)際應(yīng)用，設(shè)計(jì)了R-OPT算法的實(shí)現(xiàn)步驟：

step1：把第一階段得到的回路作為初始線路T；

step2：令i=1，在回路T上選擇一個(gè)未被選過(guò)的點(diǎn)作為t1；

step3：在回路T上選擇一條邊x1=（t1，t2），則邊x1的端點(diǎn)分別是t1，t2；

step4：以t2為一端點(diǎn)，在回路T外選擇一條邊y1=（t2，t3），使得G1（G1=x1-y1）得到最大值，如所有y1都不能使得G1>0，轉(zhuǎn)到步驟12；

step5：令i=i+1；

step6：在回路T上選擇一條邊xi=（t2i-1，t2i），如：

（1）t2i與t1相連，則可構(gòu)成一條新回路T’；（2）且xi（ys，（s

如回路T’優(yōu)于T，則用T’替，返回到步驟2。

step7：在回路T外選擇yi=（t2i，t2i+1），如：

（1）Gi>0；（2）且xi（ys，（s

step8：如存在一個(gè)沒(méi)有選擇過(guò)的點(diǎn)y2，令i=2，轉(zhuǎn)到步驟7；

step9：如存在一個(gè)沒(méi)有選擇過(guò)的點(diǎn)x2，令i=2，轉(zhuǎn)到步驟6；

step10：如存在一個(gè)沒(méi)有選擇過(guò)的點(diǎn)y1，令i=1，轉(zhuǎn)到步驟4；

step11：如存在一個(gè)沒(méi)有選擇過(guò)的點(diǎn)x1，令i=1，轉(zhuǎn)到步驟3；

step12：如存在一個(gè)沒(méi)有選擇過(guò)的點(diǎn)t1，轉(zhuǎn)到步驟2；

step13：結(jié)束或是返回到步驟1。

1.3 DST-ROPT算法的精確性驗(yàn)證

（1→11→10→9→10→11→12→13→16→15→14→15→16→13→12→8→6→5→4→3→4→2→4→5→6→7→20→19→18→17→18→19→20→7→6→8→12→11→1）

最后，把上述的歐拉回路中重復(fù)的景點(diǎn)去掉，可以得到一條漢密爾頓回路。在將歐拉回路中刪除重復(fù)的點(diǎn)可以采取從前往后取遍所有點(diǎn)和從后往前取遍所有點(diǎn)兩種方式，不同的方式得到的結(jié)果會(huì)有所區(qū)別，分別采取這兩種方式對(duì)重復(fù)的景點(diǎn)進(jìn)行刪除，得到的漢密爾頓回路如下：

方法一：從前往后取遍所有景點(diǎn)，每個(gè)景點(diǎn)有且僅能出現(xiàn)一次：（1→11→10→9→12→13→16→15→14→8→6→5→4→3→2→7→20→19→18→17→1）

方法二：從后往前取遍所有景點(diǎn)，每個(gè)景點(diǎn)有且僅能出現(xiàn)一次：（1→9→10→14→15→16→13→3→2→4→5→17→18→19→20→7→6→8→12→11→1）

通過(guò)方法一得到的漢密爾頓回路長(zhǎng)度是609.7KM，方法二得到的漢密爾頓回路長(zhǎng)度是766.6KM。由于方法二得到的回路比方法一得到的回路長(zhǎng)156.9KM，所以在本實(shí)驗(yàn)中選擇方法一得到的漢密爾頓回路，如圖3所示。在歐拉回路轉(zhuǎn)變?yōu)闈h密爾頓回路的過(guò)程中，由于每次使用的實(shí)驗(yàn)數(shù)據(jù)不一樣，所以不能簡(jiǎn)單地說(shuō)方法一好還是方法二好，在具體的操作過(guò)程中，需要比較兩種方式哪種得到的路徑較短，最后程序自動(dòng)選擇路徑較短的回路作為最終的漢密爾頓回路。

第二階段：采用局部搜索算法R-OPT對(duì)圖3的Hamilton回路進(jìn)行局部?jī)?yōu)化處理，得到優(yōu)化后的漢密爾頓回路路程是606.7KM，圖3所示的沒(méi)有進(jìn)行優(yōu)化處理的Hamilton回路路程是609.7KM，也就是說(shuō)采用R-OPT算法對(duì)雙生成樹(shù)算法得到的Hamilton回路進(jìn)行優(yōu)化處理后路程少了2KM。優(yōu)化后的Hamilton回路如圖4所示：

為了說(shuō)明本文采用的DST-ROPT算法得到的線路是優(yōu)化的，將圖4所得的結(jié)果與文獻(xiàn)[6]采用分支界定法得到的結(jié)果進(jìn)行比較，由于文獻(xiàn)[6]采用的景點(diǎn)表示與本文不一樣，所以進(jìn)行了相應(yīng)的轉(zhuǎn)換，根據(jù)表1所示的任意兩個(gè)景點(diǎn)間的最短距離，可以計(jì)算出DST-ROPT算法和分支界定法所得線路的總路程：

2 DST-ROPT算法在貴陽(yáng)市旅行線路設(shè)計(jì)中的應(yīng)用

每年的三月到十月，到貴州旅游的游客絡(luò)繹不絕，作為省會(huì)城市的貴陽(yáng)，更是游客必到的城市，貴陽(yáng)市內(nèi)和周邊的大小景點(diǎn)也有幾十上百個(gè)，怎樣設(shè)計(jì)一條最優(yōu)的旅游線路是本文研究的核心內(nèi)容。為了實(shí)驗(yàn)數(shù)據(jù)具有說(shuō)服力，文中選用每年游覽人次較高的15個(gè)景點(diǎn)作為代表，標(biāo)號(hào)如下：1、甲秀樓，2、黔靈公園，3、青巖古鎮(zhèn)，4、天河潭，5、情人谷，6、南江大峽谷，7、白云公園，8、息烽集中營(yíng)，9、野生動(dòng)物園，10、小車(chē)河濕地公園，11、花溪十里河灘，12、保利國(guó)際溫泉，13、紅楓湖，14、香紙溝，15、息烽溫泉。

3 結(jié)束語(yǔ)

本文針對(duì)貴陽(yáng)市旅游景點(diǎn)的具體情況，采用雙生成樹(shù)啟發(fā)式算法的結(jié)果作為局部搜索算法的初始路線，這樣可以充分利用雙生成樹(shù)啟發(fā)式算法的優(yōu)點(diǎn)，也可以通過(guò)R-OPT算法來(lái)局部修改雙生成樹(shù)啟發(fā)式算法生成的結(jié)果，較好地對(duì)雙生成樹(shù)啟發(fā)式算法得到最壞結(jié)果的情況進(jìn)行了優(yōu)化處理。由于該算法得到的結(jié)果與精確算法分支界定法得到的結(jié)果差不多，因此可以認(rèn)為DST-ROPT算法是一種精確有效的算法。把該算法應(yīng)用到作者正在研究的“貴州省旅游線路設(shè)計(jì)算法研究”項(xiàng)目中，可以彌補(bǔ)貴州省目前在旅游業(yè)發(fā)展中“旅行線路設(shè)計(jì)智能化”上的不足，對(duì)推動(dòng)貴州省旅游業(yè)的發(fā)展作出一點(diǎn)點(diǎn)的幫助。

參考文獻(xiàn)：

[1]馮昊.旅行商問(wèn)題的兩種算法[D].大連理工大學(xué)，2007.

[2]周康，強(qiáng)小利，周小軍.求解TPS算法[J].計(jì)算機(jī)工程與應(yīng)用，2007（29）.

[3]馬良.旅行推銷(xiāo)員問(wèn)題的算法綜述[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2000（02）：156-162.

[4]Keld Helsgaun.An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic[J].European Journal of Operational Research，2000（01）：8-16.

[5]Michel Gendreau，Gilbert Laporte，Daniele Vigo.Heuristics for the traveling salesman problem with pickup and delivery[J].computeroperations research，1999（07）：699-714.

[6]馮愛(ài)芬.最佳旅游線路的設(shè)計(jì)與算法[A].第二屆智能計(jì)算大會(huì)論文集[C].中國(guó)運(yùn)籌學(xué)會(huì)，2008：23-27.

作者簡(jiǎn)介：令狐紅英（1982-），女，講師，研究方向：數(shù)據(jù)庫(kù)技術(shù)與軟件工程；姜季春（1981-），女，講師，研究方向：數(shù)據(jù)庫(kù)技術(shù)與軟件工程。

作者單位：貴州師范學(xué)院，貴陽(yáng) 550018

基金項(xiàng)目：貴州師范學(xué)院自然科學(xué)研究基金項(xiàng)目“貴州省旅游線路設(shè)計(jì)算法研究”。