基于景點距離動態(tài)模型的大景區(qū)行程規(guī)劃研究

李紅梅

(河南檢察職業(yè)學(xué)院 ， 河南 鄭州 451191)

基于景點距離動態(tài)模型的大景區(qū)行程規(guī)劃研究

李紅梅

(河南檢察職業(yè)學(xué)院 ， 河南 鄭州 451191)

針對大景區(qū)旅游行程規(guī)劃問題， 將其規(guī)約為非對稱TSP問題， 并根據(jù)景點游客數(shù)量動態(tài)變化這一特點， 提出一種景點距離動態(tài)模型， 然后通過單個體交叉遺傳算法對該模型進行求解和實驗驗證。 研究結(jié)果顯示景點距離動態(tài)模型能較好地解決大景區(qū)的行程規(guī)劃問題和景點游客負載均衡問題。 關(guān)鍵詞: 旅游大景區(qū)； 非對稱TSP問題； 遺傳算法

隨著社會的發(fā)展， 人們對旅游的內(nèi)在需求不斷提升， 旅游已進入“大景區(qū)時代”， 各地也紛紛采取措施適應(yīng)這一變化， 譬如甘肅省計劃建設(shè)“絲綢之路經(jīng)濟帶”甘肅段大景區(qū)， 陜西省韓城市計劃投資60億元打造司馬遷文化大景區(qū)等。 針對大景區(qū)時代的到來， 游客合理規(guī)劃游覽行程就顯得尤為重要。 景區(qū)行程規(guī)劃問題可以規(guī)約為一個非對稱TSP(行程動態(tài)規(guī)劃)問題， 非對稱TSP問題已經(jīng)被證明是一個計算復(fù)雜性很高的問題。 因此， 研究旅游景區(qū)不規(guī)則行程規(guī)劃問題具有重要的現(xiàn)實意義和理論意義。

大景區(qū)通常由多個分布在廣大區(qū)域的景點構(gòu)成， 其行程規(guī)劃與傳統(tǒng)的TSP問題有較大的差異。 主要體現(xiàn)在：景點的分布是三維的， 從而造成行程不對稱； 游客不一定遍歷全部景點， 有可能僅僅遍歷部分景點； 起點和終點有可能不同。 本文依據(jù)景區(qū)行程規(guī)劃的基本要素， 通過分析傳統(tǒng)TSP模型， 構(gòu)建基于景點人數(shù)的距離模型， 依據(jù)該模型可動態(tài)獲取游客游覽各景點的行程， 提高游客旅游體驗。

一、 大景區(qū)行程規(guī)劃模型

(一)問題描述

游客從大景區(qū)中某景點出發(fā)， 行程涵蓋全部感興趣的景點， 要求行進距離和耗時最少， 并且游覽的景點和行走行程不重復(fù)。 行程存在下列4種可能。

(1) 對景區(qū)部分景點感興趣， 行程僅包括部分景點， 起點與終點不同。

(2) 對景區(qū)部分景點感興趣， 行程僅包括部分景點， 起點與終點相同。

(3) 對景區(qū)全部景點感興趣， 行程包括全部景點， 起點與終點不同。

(4) 對景區(qū)全部景點感興趣， 行程包括全部景點， 起點與終點相同。

(二)景點距離動態(tài)模型

景區(qū)中各景點間距離并非直線距離， 無法用歐式距離描述景區(qū)間距離。 另外各景點在景區(qū)中呈三維分布， 導(dǎo)致景點i到景點j之間的距離dij不等于景點j到景點i之間的距離dji。 景點i到景點j之間的耗時不僅僅與距離dij相關(guān)， 還與景點i與景點j的游客數(shù)量相關(guān)， 因此， 本文描述的距離是以物理距離為基礎(chǔ)的動態(tài)距離， 景點i到景點j之間的距離用dij(t)表示

dij(t)=Nj(t)×dij

(1)

其中

(2)

其中αj(t)為t時刻景點j內(nèi)的游客數(shù)量；δj為景點j游客的最佳承載數(shù)量， 一般為常數(shù)。

從公式可以看出：景點i到景點j間的距離是一個動態(tài)變化的數(shù)值， 當(dāng)景點j在t時刻游客在景點j的數(shù)量αj(t)大于其最佳承載量的系數(shù)比時， 從景點i至景點j的距離增大， 反之則距離減小。

二、 算法設(shè)計

(一)基本遺傳算法流程

標(biāo)準(zhǔn)的遺傳算法包括群體的初始化、 染色體選擇、 染色體交叉、 染色體變異等操作。 其算法步驟可描述如下。

(1)隨機產(chǎn)生一組染色體構(gòu)成的初始種群， 根據(jù)適應(yīng)度函數(shù)評價每個染色體的適應(yīng)度。

(2)判斷算法的收斂準(zhǔn)則是否滿足。 若滿足輸出搜索結(jié)果， 否則執(zhí)行以下步驟。

(3)根據(jù)適應(yīng)值以一定方式執(zhí)行選擇操作。

(4)按交叉概率Pc執(zhí)行交叉操作。

(5)按變異概率Pm執(zhí)行變異操作。

(6)返回步驟(2)。

基本遺傳算法優(yōu)化流程圖見圖1。

圖1 基本遺傳算法優(yōu)化流程

(二)單個體交叉遺傳算法設(shè)計

單個體遺傳算法的基本思想是改變傳統(tǒng)交叉算子使用雙染色體進行交叉的方法， 交叉操作和變異操作均在單個染色體上進行。 這種算法簡化了遺傳操作， 計算效率有較大提高， 且對初始種群多樣性的依賴性降低。

1.編碼

遺傳算法的編碼方式有二進制編碼、 格雷碼編碼、 浮點數(shù)編碼和序號編碼(自然數(shù)編碼)等多種編碼形式。 二進制編碼等遺傳算法的研究理論較為成熟， 實際應(yīng)用也相當(dāng)廣泛。 在用遺傳算法求解組合優(yōu)化問題時， 使用序號編碼比非序號編碼更容易描述解空間和編碼空間的一一映射關(guān)系。 但傳統(tǒng)序號編碼遺傳算法是模仿非序號編碼遺傳算法的， 主要遺傳算子仍為交叉算子， 而序號編碼遺傳算法的染色體不能在任意位置進行交叉， 隨意交叉后的染色體很可能發(fā)生序號的缺失或重負， 這樣的染色體無法映射至解空間， 需要對這些染色體進行偽解校正， 從而增加了計算復(fù)雜性。

針對本文的大景區(qū)行程規(guī)劃問題， 采用序號編碼方式， 即染色體(1， 2， …,n)代表行程為1->2->…->n。 用單個染色體實現(xiàn)交叉和變異操作， 避免了校正偽解的過程， 從而降低了算法計算復(fù)雜性。

2.目標(biāo)函數(shù)和適應(yīng)度函數(shù)

遺傳算法的一個特點是它僅根據(jù)問題的目標(biāo)函數(shù)值就可以得到下一步的有關(guān)搜索信息， 而對目標(biāo)函數(shù)值的使用是通過評價個體適應(yīng)值來實現(xiàn)的。

最優(yōu)化問題主要分為兩大類： 一類求解目標(biāo)函數(shù)的全局最大值， 另一類求解目標(biāo)函數(shù)的全局最小值。 本文涉及的計劃優(yōu)化是一個將保障時間最小化為目標(biāo)的目標(biāo)函數(shù)全局最小化的最優(yōu)化問題。 對于目標(biāo)函數(shù)全局最小化問題由解空間中某一點的目標(biāo)函數(shù)值f(x)到搜索空間中對應(yīng)的個體適應(yīng)函數(shù)值F(x)的轉(zhuǎn)換可用下面的方法：

(3)

式(3)中Cmax為一個相對較大的數(shù)。

3.交叉算子

交叉算子是遺傳算法中關(guān)鍵的遺傳操作， 它是模擬自然界有性繁殖、 基因重組過程， 對父代兩個個體進行基因操作， 把原有個體優(yōu)良基因遺傳到下一代種群中， 并生成包含嶄新基因結(jié)構(gòu)的新個體。 交叉算子可看作為父代空間到子代空間的隨機映射。

部分影射雜交(PMX)方法可以看作兩點雜交的變形， 它通過一種特殊的修補過程來處理可能的非法現(xiàn)象。PMX的主要步驟如下。

第1步：在染色體上任意選擇兩個分割點。 由兩個分割點定義的字串稱作影射片斷。

第2步：在兩個父代間交換字串從而產(chǎn)生原型后代。

第3步：確定兩個影射片斷間的影射關(guān)系。

第4步：采用影射關(guān)系使后代合法化。

部分映射交叉由于存在對新個體的修正來保證新個體合法化的步驟而增大了遺傳算法的復(fù)雜程度， 本文采用單個體交叉方法， 具體實現(xiàn)步驟如下：

第1步：按照交叉概率確定一個待進行交叉操作的個體。

第2步：選擇兩個不相同位置。

第3步：將兩個位置之間的基因反轉(zhuǎn)， 實現(xiàn)新個體的誕生。

圖2

圖2-1為兩個被選中進行部分映射交叉的個體。 圖2-2為根據(jù)交叉的部位兩個個體交叉后產(chǎn)生的新個體。 第一個個體表述的是景點3和景點5在同一行程上遍歷了兩次， 第二個個體表述的是景點11和景點8在同一行程上遍歷了兩次， 顯然， 這兩個個體對應(yīng)的解都是“偽解”。 因此， 需要對這兩個偽解進行合法化， 圖2-3表述的是合法化后的兩個新個體。 圖2-4中上面的個體為舊個體， 下面的個體為經(jīng)過單個體交叉操作后產(chǎn)生的新個體， 這種交叉算子不存在對不合法解進行合法化的處理， 因此大大降低了計算的復(fù)雜性。

4.變異算子

變異操作通過隨機改變種群中個別個體的某些基因而產(chǎn)生新個體， 變異操作增加種群中的個體多樣性， 在一定程度上避免早熟收斂(非全局最優(yōu))。

本文中變異操作采用互換操作算子(swap)， 即按照變異概率隨機選擇染色體中兩個不同基因編碼的位置并進行基因交換，swap相對于INV(逆序操作)和INS(插入操作)更有助于算法的大范圍搜索， 增強算法的廣度搜索能力。

對于一個行程的染色體的變異操作， 根據(jù)變異概率確定是否進行變異操作， 隨機選擇行程上的兩個景點進行交換。 例如：變異交換位置為2和8， 變異算子見圖3。

圖3 變異算子

5.精英保留策略

當(dāng)前種群中適應(yīng)度最高的個體不參與交叉運算和變異運算， 用它來替換掉本代群體中經(jīng)過交叉、 變異等遺傳操作后所產(chǎn)生的適應(yīng)度最低的個體。 采用精英保留策略可在概率上保證遺傳算法能夠在解空間得到最優(yōu)解。

6.選擇算子

遺傳算法最基本的選擇方式是根據(jù)個體適應(yīng)值的比例進行選擇， 即輪盤賭選擇。 這種選擇方式嚴(yán)格按照群體中個體適應(yīng)值的比例進行選擇， 適應(yīng)值高的個體被選擇來繁殖后代的機會大， 適應(yīng)值低的個體被選擇來繁殖后代的機會小。 選擇操作按照以下步驟進行。

(1)計算種群中全部個體適應(yīng)值之和。

(4)

式中f(xi)是個體xi的適應(yīng)度，i=1， 2， …，N。

(2)計算種群中每個個體的選擇概率。

(5)

(3)計算群體中全部個體選擇概率的累積和。

(6)

(4)產(chǎn)生一個隨機數(shù)r∈[0,1]， 若r∈[q(xi-1),q(xi)]， 則選擇個體xi，i∈{1,2,…N}，q0=0。

三、 景區(qū)行程規(guī)劃與算法應(yīng)用

(一)景區(qū)行程規(guī)劃

某景區(qū)中的10個景點分布抽象為圖4的二維分布， 各景點最佳游客數(shù)量均為500人。 在景區(qū)各個景點出入口處分別設(shè)置游客計數(shù)器， 實時統(tǒng)計景點游客數(shù)量， 每小時向景區(qū)數(shù)據(jù)中心發(fā)送該時段的游客數(shù)量， 數(shù)據(jù)中心根據(jù)本文提出的景點距離動態(tài)模型計算各景點間的距離， 并通過本文提出的單個體交叉算子遺傳算法對路徑進行優(yōu)化， 每小時通過景區(qū)公共信息網(wǎng)絡(luò)對游客發(fā)布一次最佳路徑， 技術(shù)原理如圖5。

(二)算法應(yīng)用

在初始狀態(tài)下， 各景點的游客數(shù)量均為0， 此時景點i與景點j之間的距離dij(0)=dij。 遺傳算法的控制參數(shù)為：種群規(guī)模(PopSize)100， 交叉概率Pc=0.6， 變異概率Pm=0.1， 迭代次數(shù)(Generation)50。VS2010環(huán)境下用C#進行編程， 得到的最佳行程見圖6。t=0時刻， 最佳行程為1->10->9->8->7->2->6->5->4->3。

圖4 景點分布

為方便計算， 假定各景點的最佳游客數(shù)量均為500。t=T時刻αj(t)為200—800內(nèi)的隨機數(shù)， 該時刻各個景點的人數(shù)分布見表1。

圖5 技術(shù)原理圖

圖6t=0時刻最佳行程

表1 t=T時刻各景區(qū)游客數(shù)量(人)

從表1可以看出在t=T時刻， 景點2、 景點3、 景點4和景點6的游客數(shù)量均小于最佳游客承載數(shù)量， 因此， 根據(jù)公式可以得到其他景點到這些景點的距離均小于物理距離， 而到其他景點的距離由于超出了經(jīng)典最佳游客承載數(shù)量而大于其物理距離。 根據(jù)公式重新計算得到景點之間距離， 得到的最佳行程見圖7。

從圖7可以看出，t=T時刻， 最佳行程為1->3->4->2->5->6->7->8->9->10。t=T時刻由于景點3的游客數(shù)量小于最佳游客承載數(shù)量， 導(dǎo)致景點1至景點3的距離等于物理距離， 而景點1至景點10的距離由于景點10超出了最佳承載數(shù)量而大于其物理距離， 因此， 盡管景點1至景點10的物理距離小于景點1至景點3的物理距離， 尋優(yōu)行程還是選擇了景點3作為景點1的后續(xù)景點。 由以上分析可知， 本文提出的基于游客數(shù)量景點間距離模型具有動態(tài)的旅游路線規(guī)劃的能力， 在路線規(guī)劃中避開了人數(shù)較多的景點， 可實現(xiàn)旅游景區(qū)的游客數(shù)量的負載均衡。

圖7t=T時刻最佳行程

針對大景區(qū)內(nèi)景點行程規(guī)劃問題， 本文提出一種景點距離動態(tài)模型， 該模型將景點游客數(shù)量和景點間物理距離進行關(guān)聯(lián)， 根據(jù)景點游客最佳承載數(shù)量與實際游客的數(shù)量對物理距離進行動態(tài)變化， 根據(jù)不同時刻景區(qū)內(nèi)游客分布， 利用遺傳算法與TSP問題的有機結(jié)合求出不同時刻的景區(qū)行程規(guī)劃。 實驗證明， 該模型可根據(jù)景點游客數(shù)量合理規(guī)劃景區(qū)行程， 可為游客和景區(qū)提供較為合理的旅游方案。

[1] 胡軍國，祁享年，董峰，等.一種改進蟻群算法研究和旅游景區(qū)路徑規(guī)劃問題求解[J].計算機應(yīng)用研究，2011(5):1647-1650.

[2] 鄒時林，阮見，劉波，等.最短路徑算法在旅游線路規(guī)劃中的應(yīng)用：以廬山為例[J].測繪科學(xué)，2008(9):190-192.

[3] 徐鋒，杜軍平.改進蟻群算法在旅游線路中的應(yīng)用研究[J].計算機工程與應(yīng)用，2009,45(23):193-195,226.

[4] 潘玉俠，梁勤歐.基于遺傳算法的旅游線路優(yōu)化[J].浙江師范大學(xué)學(xué)報，2011(8)：350-354．

[5] 滕聰，曹文．旅游景點篩選組合及旅游線路的優(yōu)化算法與應(yīng)用[J]．地球信息科學(xué)學(xué)報，2010(5):668-673．

[6] 王兆峰．基于遺傳算法的理想?yún)^(qū)間法在旅游環(huán)境質(zhì)量評價中的應(yīng)用[J]．系統(tǒng)工程，2013(2)：106-114.

[7] 宋國峰，梁昌勇，梁焱，等．改進遺傳算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的旅游景區(qū)日客流量預(yù)測[J]．小型微型計算機系統(tǒng)，2014(9)：2136-2141.

[8] 周辰紅，李中．基于多目標(biāo)進化算法和遺傳算法的最佳旅游套餐設(shè)計：以上海市為例[J]．信息科技，2014(10)：245-248.

[責(zé)任編輯 李繼峰]

A Study of Large Tourist Attraction Path Planning Based on Scenic Spot Dynamic Distance Model

LI Hong-mei
(HenanProcuratorialVocationalCollege,Zhengzhou451191,China)

This paper discusses the problem of large tourist attraction path planning, which is re-defined with asymmetric TSP. A scenic spot dynamic distance model is proposed to approach the topic problem, which is solved and demonstrated with individual crossover genetic algorithm. As the results indicate, the problem of large tourist attraction and scenic spot tourist load coordination can be effectively solved with scenic spot dynamic distance model.

large tourism attraction; asymmetric TSP; genetic algorithm

2016-12-02

李紅梅(1983—)， 女， 河南偃師人， 助教。

F590

A

1009-4970(2017)04-0023-04