李紅梅

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

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

李紅梅

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

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

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

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

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

(一)問(wèn)題描述

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

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

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

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

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

(二)景點(diǎn)距離動(dòng)態(tài)模型

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

dij(t)=Nj(t)×dij

(1)

其中

(2)

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

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

二、 算法設(shè)計(jì)

(一)基本遺傳算法流程

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

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

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

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

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

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

(6)返回步驟(2)。

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

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

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

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

1.編碼

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

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

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

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

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

(3)

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

3.交叉算子

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

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

第1步：在染色體上任意選擇兩個(gè)分割點(diǎn)。 由兩個(gè)分割點(diǎn)定義的字串稱(chēng)作影射片斷。

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

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

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

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

第1步：按照交叉概率確定一個(gè)待進(jìn)行交叉操作的個(gè)體。

第2步：選擇兩個(gè)不相同位置。

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

圖2

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

4.變異算子

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

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

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

圖3 變異算子

5.精英保留策略

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

6.選擇算子

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

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

(4)

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

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

(5)

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

(6)

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

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

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

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

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

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

圖4 景點(diǎn)分布

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

圖5 技術(shù)原理圖

圖6t=0時(shí)刻最佳行程

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

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

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

圖7t=T時(shí)刻最佳行程

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

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

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

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

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

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

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

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

[8] 周辰紅，李中．基于多目標(biāo)進(jìn)化算法和遺傳算法的最佳旅游套餐設(shè)計(jì)：以上海市為例[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