基于旅游線路規(guī)劃的蟻群優(yōu)化算法研究

李磊 張延星 謝超

摘? 要： 傳統(tǒng)的鄉(xiāng)村旅游線路規(guī)劃方法存在進(jìn)化速度慢的缺點(diǎn)，導(dǎo)致搜索速度慢，為此提出一種基于蟻群優(yōu)化算法的鄉(xiāng)村旅游線路規(guī)劃方法。在建立蟻群優(yōu)化算法模型的基礎(chǔ)上，針對(duì)擁堵?tīng)顟B(tài)和非擁堵?tīng)顟B(tài)分別優(yōu)化信息素更新策略，對(duì)最優(yōu)線路求解，完成基于蟻群優(yōu)化算法的鄉(xiāng)村旅游線路規(guī)劃方法的設(shè)計(jì)。通過(guò)對(duì)比實(shí)驗(yàn)，與模擬退火算法、基本蟻群算法作比較。實(shí)驗(yàn)結(jié)果表明，提出的蟻群優(yōu)化算法因在每次迭代中優(yōu)化信息素更新策略，明顯提高了搜索速度，且緩解了景點(diǎn)擁堵情況。

關(guān)鍵詞： 蟻群優(yōu)化算法; 旅游線路規(guī)劃; 信息素更新; 線路規(guī)劃模型; 旅游線路設(shè)計(jì); 最優(yōu)路徑

中圖分類(lèi)號(hào)： TN911.1?34; TP311? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A? ? ? ? ? ? ? ? ? 文章編號(hào)： 1004?373X（2020）17?0115?04

Abstract： The traditional rural tourism route planning method has the disadvantage of slow evolution speed， which leads to slow search speed. Therefore， a rural tourism route planning method based on ant colony optimization algorithm is proposed. The model of ant colony optimization algorithm is established. On the basis of the model， the pheromone update strategy is optimized for dealing with both the congestion state and non?congestion state， and the optimal route is solved， so as to complete the design of rural tourism route planning method based on ant colony optimization algorithm. The proposed method is compared with simulated annealing algorithm and basic ant colony algorithm in the comparative experiments. The results show that the ant colony optimization algorithm proposed in this paper can obviously raise the search speed and alleviate the congestion of scenic spots because the pheromone update strategy is optimized in each iteration.

Keywords： ant colony optimization algorithm; tourism route planning; pheromone update; route planning model; tourism route design; optimal path

0? 引? 言

隨著人們生活水平的提高，越來(lái)越多的人選擇旅游作為放松方式之一，旅游產(chǎn)業(yè)隨之得到了發(fā)展。旅游產(chǎn)業(yè)不僅可以加速區(qū)域之間的資金流轉(zhuǎn)，還可以創(chuàng)造高效的消費(fèi)模式，帶動(dòng)周邊地區(qū)的經(jīng)濟(jì)發(fā)展[1]。為帶動(dòng)農(nóng)村經(jīng)濟(jì)發(fā)展，國(guó)家大力支持鄉(xiāng)村文化旅游產(chǎn)業(yè)，針對(duì)鄉(xiāng)村旅游線路規(guī)劃問(wèn)題開(kāi)展研究，對(duì)于促進(jìn)鄉(xiāng)村旅游的發(fā)展十分重要?，F(xiàn)有的旅游線路規(guī)劃方法仍然存在所得線路非最優(yōu)、搜索時(shí)間長(zhǎng)的缺點(diǎn)，需要對(duì)其作進(jìn)一步研究[2]。在旅游線路規(guī)劃的研究中，為尋找最優(yōu)線路，很多研究者均采用蟻群算法。然而，蟻群算法存在搜索時(shí)間長(zhǎng)、易于停滯的缺點(diǎn)，需要對(duì)其作進(jìn)一步優(yōu)化[3]。近年來(lái)，蟻群優(yōu)化算法被廣泛應(yīng)用在各個(gè)領(lǐng)域中，很好地改進(jìn)了蟻群算法的不足[4]?；谏鲜龇治觯疚奶岢鲆环N基于蟻群優(yōu)化算法的鄉(xiāng)村旅游線路規(guī)劃方法，并通過(guò)對(duì)比實(shí)驗(yàn)驗(yàn)證了提出的蟻群優(yōu)化算法具有更快的搜索速度。

1? 基于蟻群優(yōu)化算法的鄉(xiāng)村旅游線路規(guī)劃方法

1.1? 建立蟻群優(yōu)化算法模型

蟻群算法是一種用來(lái)尋找優(yōu)化路徑的概率型算法。這種算法具有分布計(jì)算、信息正反饋和啟發(fā)式搜索的特征，本質(zhì)上是進(jìn)化算法中的一種啟發(fā)式全局優(yōu)化算法[5]。蟻群尋優(yōu)示意圖如圖1所示。

由圖1可知，從巢穴到食物之間，蟻群通過(guò)消息互通尋找到共同認(rèn)可的最短路徑。蟻群算法的優(yōu)勢(shì)在于搜索過(guò)程采用分布式計(jì)算方式，多個(gè)個(gè)體同時(shí)進(jìn)行并行計(jì)算，大大提高了算法的計(jì)算能力和運(yùn)行效率。所以利用蟻群優(yōu)化算法建立旅游線路規(guī)劃模型。

式中：[tabuaa=1，2，…，m]代表螞蟻[a]歷經(jīng)景點(diǎn)的集合;[ηij]代表螞蟻從景點(diǎn)[i]向景點(diǎn)[j]移動(dòng)的期望值，是一種啟發(fā)式函數(shù)，[ηij=1/dij];[α]代表景點(diǎn)之間路徑上信息素的重要程度，其值越大，則表明信息素產(chǎn)生的影響越大[6];[β]代表景點(diǎn)間距離的啟發(fā)函數(shù)的重要程度，其值越大，則表明其產(chǎn)生的影響越大。

為了描述螞蟻在歷經(jīng)景點(diǎn)時(shí)信息素的揮發(fā)狀態(tài)，通過(guò)揮發(fā)因子[ρ]對(duì)路徑信息作調(diào)整，當(dāng)所有螞蟻完成一次完整的景點(diǎn)走訪后，更新所有景點(diǎn)之間信息素的值，通過(guò)式（2）實(shí)現(xiàn)：

式中：[1-ρ]代表信息素的剩余調(diào)整程度值;[Δτaij]代表第[a]只螞蟻完成本次訪問(wèn)后，在景點(diǎn)[i]和景點(diǎn)[j]之間分泌出的信息素的增加量;[Δτij]代表全部螞蟻在完成本次訪問(wèn)后，在景點(diǎn)[i]和景點(diǎn)[j]之間分泌出的總信息素的濃度。其中，[Δτaij]的計(jì)算公式如下：

通過(guò)上述內(nèi)容，完成蟻群優(yōu)化算法模型的建立。

1.2? 優(yōu)化信息素更新策略

蟻群算法在初始化時(shí)，每條路徑上信息素的量值是相同的[7]。在算法初期，螞蟻以相等的狀態(tài)轉(zhuǎn)移概率選擇路徑?？紤]擁堵因素后，如果每條路徑的信息素量值相同，會(huì)降低螞蟻尋找最優(yōu)路徑的效率，增加尋求最優(yōu)解的時(shí)間[8]。因此，需要對(duì)信息素的更新策略作優(yōu)化。對(duì)于全部路徑來(lái)說(shuō)，交通信息時(shí)刻都在變化。最優(yōu)路徑上可能存在擁堵?tīng)顩r，其他路徑可能會(huì)從擁堵變成暢通的狀況，如圖2所示。

在圖2中，虛線表示擁堵路段。從景點(diǎn)1到景點(diǎn)6的最優(yōu)路徑為[1→2→7→10→6]，其中，[2→7]路段突然變成擁堵?tīng)顟B(tài)。此時(shí)，原來(lái)的最優(yōu)路徑已經(jīng)不再是最優(yōu)選擇，則信息素會(huì)更新策略，重新選擇交通暢通的路徑[9?12]。通過(guò)限定各條路徑上的信息素強(qiáng)度，使每?jī)蓚€(gè)景點(diǎn)之間路徑上的信息素強(qiáng)度保持在穩(wěn)定的范圍內(nèi)，并使信息素強(qiáng)度盡可能集中在較優(yōu)路徑上，使其最終可以找到全局最優(yōu)解。

當(dāng)無(wú)擁堵?tīng)顩r時(shí)，對(duì)信息素更新策略的具體內(nèi)容如下：當(dāng)所有螞蟻完成一次走訪后，從中隨機(jī)選擇一只螞蟻的走訪路徑[Lk]的長(zhǎng)度作為標(biāo)準(zhǔn)，將其他螞蟻的走訪路徑[Lj]的長(zhǎng)度與該條路徑長(zhǎng)度作比較，更新[Lk]的信息素，以及比該路徑更短的路徑上的信息素濃度，以便最后所得最優(yōu)解為全局最優(yōu)解而非局部最優(yōu)解。

1.3? 最優(yōu)線路求解

在優(yōu)化信息素更新策略后，求解最優(yōu)線路，具體實(shí)現(xiàn)步驟如下：

初始化：將信息素[τij]的值初始化設(shè)為1，啟發(fā)式信息在迭代過(guò)程中保持不變;

構(gòu)造解：隨機(jī)選擇一個(gè)景點(diǎn)作為螞蟻[a]的出發(fā)景點(diǎn)，從景點(diǎn)出發(fā)并歷經(jīng)所有景點(diǎn)，假設(shè)螞蟻[a]還沒(méi)有走訪完全部景點(diǎn)，則從螞蟻[a]當(dāng)前的位置開(kāi)始，隨機(jī)選擇下一個(gè)景點(diǎn)。當(dāng)還有沒(méi)走訪到的景點(diǎn)時(shí)，隨機(jī)產(chǎn)生一個(gè)（0，1）之間的隨機(jī)數(shù)，如果隨機(jī)數(shù)小于控制參數(shù)，則從未走訪到的景點(diǎn)中，選擇有最大可行性的景點(diǎn)作為下一個(gè)要?dú)v經(jīng)的景點(diǎn)，否則以輪盤(pán)賭的方式選出下一個(gè)走訪景點(diǎn)。如果螞蟻在歷經(jīng)完全部景點(diǎn)后，則返回歷經(jīng)景點(diǎn)的先后順序。螞蟻遍歷景點(diǎn)的具體步驟如圖3所示。

在螞蟻遍歷景點(diǎn)的過(guò)程中，采用輪盤(pán)賭的方式[13?15]，通過(guò)每個(gè)螞蟻個(gè)體的選擇概率計(jì)算出累積概率，再通過(guò)隨機(jī)產(chǎn)生的隨機(jī)數(shù)，與累積概率作比較，決定下一個(gè)要選擇的景點(diǎn)，通過(guò)不斷地迭代直到找到最短線路，將其輸出。

至此，完成基于蟻群優(yōu)化算法的鄉(xiāng)村旅游線路規(guī)劃方法的設(shè)計(jì)。

2? 仿真實(shí)驗(yàn)與分析

為驗(yàn)證此次提出方法的有效性，采用提出的基于蟻群優(yōu)化算法的鄉(xiāng)村旅游線路規(guī)劃方法，以河北某地區(qū)旅游鄉(xiāng)村為例，對(duì)其旅游線路展開(kāi)規(guī)劃，并與基本蟻群算法、模擬退火算法的鄉(xiāng)村旅游線路規(guī)劃方法作對(duì)比。

2.1? 實(shí)驗(yàn)環(huán)境

搭建實(shí)驗(yàn)環(huán)境，通過(guò)Matlab平臺(tái)進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)環(huán)境參數(shù)設(shè)置如表1所示。

在上述實(shí)驗(yàn)環(huán)境下，對(duì)該地區(qū)的鄉(xiāng)村旅游景點(diǎn)排序，分別為1～10。設(shè)置信息素量值的最小值為10，最大值為1 000。景點(diǎn)的位置分布如圖4所示。

2.2? 旅游景點(diǎn)全局擁堵

為驗(yàn)證提出方法的路徑規(guī)劃性能，以景點(diǎn)擁堵情況為實(shí)驗(yàn)指標(biāo)，采用提出的基于蟻群優(yōu)化算法、模擬退火算法及基本蟻群算法的線路規(guī)劃方法，對(duì)上述10個(gè)旅游景點(diǎn)展開(kāi)規(guī)劃?；谏鲜鰧?shí)驗(yàn)環(huán)境進(jìn)行仿真實(shí)驗(yàn)，記錄旅游高峰時(shí)間段10：00—14：00景點(diǎn)的擁堵情況，得到的實(shí)驗(yàn)結(jié)果如圖5所示。

由圖5可知：利用模擬退火算法與基本蟻群算法規(guī)劃后的景點(diǎn)擁堵情況未得到較好地緩解，尤其是必經(jīng)景點(diǎn)1，4，5，6的擁堵較為嚴(yán)重;而利用提出的蟻群優(yōu)化算法規(guī)劃后的景點(diǎn)擁堵情況有所緩解，各景點(diǎn)的游客負(fù)載量較為均衡。因?yàn)樘岢鏊惴紤]了擁堵因素，如果每條路徑的信息素量值相同，會(huì)降低螞蟻尋找最優(yōu)路徑的效率，對(duì)信息素的更新策略進(jìn)行了優(yōu)化，緩解了高峰時(shí)間段景點(diǎn)擁堵的情況。

2.3? 算法進(jìn)化速度

為驗(yàn)證提出方法在進(jìn)化速度的性能，設(shè)計(jì)實(shí)驗(yàn)驗(yàn)證蟻群優(yōu)化算法、基本蟻群算法和模擬退火算法執(zhí)行過(guò)程中的進(jìn)化速度（搜索速度）。算法的收斂速度越快，搜索速度越快，說(shuō)明進(jìn)化速度性能越好。對(duì)比結(jié)果如圖6所示。

從圖6中可以看出：模擬退火算法在第198次開(kāi)始收斂，達(dá)到最優(yōu);基本蟻群算法在第169次開(kāi)始收斂到最優(yōu);而提出的蟻群優(yōu)化算法在第100次收斂到最優(yōu)。通過(guò)對(duì)比發(fā)現(xiàn)，提出的蟻群優(yōu)化算法通過(guò)在每次進(jìn)化過(guò)程中更新信息素策略，極大地提高了算法找到更優(yōu)解的概率，提高了進(jìn)化速度，從而使搜索時(shí)間加快，具有更好的全局搜索能力。

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

針對(duì)傳統(tǒng)的鄉(xiāng)村旅游線路規(guī)劃算法存在的進(jìn)化速度慢而導(dǎo)致搜索時(shí)間長(zhǎng)的缺點(diǎn)，本文設(shè)計(jì)了基于蟻群優(yōu)化算法的鄉(xiāng)村旅游線路規(guī)劃方法。通過(guò)對(duì)比實(shí)驗(yàn)，與基本蟻群算法和模擬退火算法作比較，實(shí)驗(yàn)結(jié)果證明了提出的蟻群優(yōu)化算法具有更快的搜索速度，緩解了景點(diǎn)擁堵情況。希望本次研究可以為鄉(xiāng)村旅游線路規(guī)劃及其他優(yōu)化研究提供一定的參考價(jià)值。

參考文獻(xiàn)

[1] 趙希勇，張璐，吳鴻燕，等.哈爾濱地區(qū)鄉(xiāng)村旅游資源評(píng)價(jià)與開(kāi)發(fā)潛力研究[J].中國(guó)農(nóng)業(yè)資源與區(qū)劃，2019，40（5）：180?187.

[2] 余瑞林，陳慧媛，陳廣平，等.湖北省鄉(xiāng)村旅游地空間分布及其影響因素：以高星級(jí)農(nóng)家樂(lè)為例[J].經(jīng)濟(jì)地理，2018，38（6）：210?217.

[3] 唐瑞雪，高鵬，王凱，等.青城山旅游區(qū)觀光車(chē)運(yùn)營(yíng)規(guī)劃研究[J].交通運(yùn)輸工程與信息學(xué)報(bào)，2018，16（2）：131?135.

[4] 周?chē)[，李少梅，王旭，等.興趣旅游地理信息服務(wù)系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].測(cè)繪工程，2018，27（5）：46?51.

[5] 羅勁文.西安市跨坐式單軌旅游示范線線路方案比選[J].城市軌道交通研究，2018，21（6）：66?70.

[6] 郭偉，薛耀文.不同對(duì)接條件下的旅游線路設(shè)計(jì)研究：以臨汾市為例[J].山西師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2019，33（2）：50?57.

[7] 那守海，徐兆敏，趙希勇.“反規(guī)劃”視角下的濕地旅游規(guī)劃控制指標(biāo)體系研究[J].中國(guó)農(nóng)業(yè)資源與區(qū)劃，2018，39（11）：219?224.

[8] 李強(qiáng).長(zhǎng)治市太行山大峽谷旅游軌道交通布局規(guī)劃研究[J].鐵道運(yùn)輸與經(jīng)濟(jì)，2019，41（3）：80?84.

[9] 馮立新，王杏，梁兀銘.中國(guó)風(fēng)景道規(guī)劃設(shè)計(jì)創(chuàng)新點(diǎn)及創(chuàng)新本源探究[J].云南地理環(huán)境研究，2017，29（5）：38?43.

[10] 朱明，史春云.長(zhǎng)三角旅游線路空間模式的動(dòng)態(tài)演變：基于2010，2016年數(shù)據(jù)的比較研究[J].江蘇師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2018，36（1）：71?74.

[11] 楊臨澗，趙祥模，賀冰花，等.隨機(jī)用戶均衡交通分配問(wèn)題的蟻群優(yōu)化算法[J].交通運(yùn)輸工程學(xué)報(bào)，2018，18（3）：189?198.

[12] 王海鷹，秦奮，張新長(zhǎng)，等.基于蟻群優(yōu)化算法的城市生態(tài)用地空間規(guī)劃模型[J].地理科學(xué)，2017，37（3）：426?436.

[13] 史先鵬，解方宇，張波濤.一種基于改進(jìn)蟻群優(yōu)化算法的載人潛水器全局路徑規(guī)劃[J].海洋工程，2019，37（3）：86?94.

[14] 王恩重，陶傳奇.基于改進(jìn)蟻群優(yōu)化算法的云計(jì)算調(diào)度方法[J].計(jì)算機(jī)與數(shù)字工程，2019，47（4）：743?747.

[15] 王嘉怡，房俊，高鵬.面向電能質(zhì)量數(shù)據(jù)采集的蟻群優(yōu)化算法[J].計(jì)算機(jī)與數(shù)字工程，2019，47（3）：524?529.