黃澤斌　林煥恒　王炯鹿　鄧艾嵐　羅柏瑞　林貴旭

摘? 要：當(dāng)今，大部分人們會(huì)選擇旅游進(jìn)行生活?yuàn)蕵?lè)，而如何規(guī)劃出更好的旅游路線，對(duì)提高旅游人群的出行體驗(yàn)有著極大的影響。通過(guò)對(duì)蟻群算法中啟發(fā)式函數(shù)的改良，變異搜索操作和隨機(jī)因子及時(shí)間窗約束策略的引入，優(yōu)化蟻群算法對(duì)景區(qū)的搜索，使得規(guī)劃出的旅游路線更貼合實(shí)際情況。仿真結(jié)果表明，該方法具有良好的實(shí)用性和有效性。

關(guān)鍵詞：蟻群算法;時(shí)間窗約束;路線規(guī)劃;旅游

中圖分類號(hào)：TP18? ? ? ? ?文獻(xiàn)標(biāo)志碼：A? ? ? ? ?文章編號(hào)：2095-2945（2019）29-0028-03

Abstract： Nowadays， most people will choose to travel to enjoy life and for entertainment， and how to plan a better tourism route has a great impact on improving the travel experience of tourists. Through the improvement of heuristic function in ant colony algorithm， as well as the introduction of mutation search operation and random factor and time window constraint strategy， the ant colony algorithm is optimized to search scenic spots， so that the planned tourism route is more in line with the actual situation. The simulation results show that the method has good practicability and effectiveness.

Keywords： ant colony algorithm; time window constraint; route planning; tourism

引言

如今，國(guó)內(nèi)旅游業(yè)蓬勃發(fā)展，路線規(guī)劃作為旅游中至關(guān)重要的一個(gè)環(huán)節(jié)，本質(zhì)上是一個(gè)TSP問(wèn)題。迄今為止，已出現(xiàn)諸多可解決此問(wèn)題的算法，譬如：蟻群算法、遺傳算法、禁忌搜索算法等[1]。

蟻群算法于1992年，由米蘭理學(xué)院學(xué)者M(jìn).Dorigo首次提出，算法的突出優(yōu)勢(shì)有信息的正反饋、支持分布計(jì)算以及啟發(fā)式搜索等[2]，該算法被廣泛應(yīng)用于TSP問(wèn)題的求解，并取得良好的結(jié)果。

在旅游路線規(guī)劃中，花費(fèi)在路途上的時(shí)間及游客滯留在景點(diǎn)上的時(shí)間對(duì)規(guī)劃有著極大的影響。我們通過(guò)加入時(shí)間窗的約束和定義啟發(fā)函數(shù)，將啟發(fā)函數(shù)與蟻群算法相結(jié)合，使求出的解更符合現(xiàn)實(shí)情況。

1 蟻群算法基本原理及模型

蟻群算法通過(guò)模擬自然界蟻群的覓食行為，根據(jù)螞蟻在路段上所留下信息素的量來(lái)尋找食物源的最短路徑，螞蟻所選擇的路段與該路段上信息素的量呈正相關(guān)關(guān)系，即路段上的信息素的量越多，則該路段被螞蟻選擇的可能性越大[3]。

2.2變異搜索操作和隨機(jī)因子的引入

為解決在循環(huán)多次后，出現(xiàn)得到的較優(yōu)解小于一開(kāi)始的較優(yōu)解，引入變異搜索操作，通過(guò)對(duì)部分路段的信息素量進(jìn)行恰當(dāng)變異，擴(kuò)展搜索范圍以避免算法陷入局部最優(yōu)狀態(tài)，本文通過(guò)使用2-Opt的方法實(shí)現(xiàn)。使用過(guò)程中，若出現(xiàn)下面的運(yùn)算關(guān)系：

為此，我們引入隨機(jī)因子：假設(shè)某個(gè)節(jié)點(diǎn)的下一次選擇有4個(gè)節(jié)點(diǎn)，通過(guò)計(jì)算可得選擇這4個(gè)位置節(jié)點(diǎn)的概率，依次為0.1、0.2、0.3、0.4，根據(jù)傳統(tǒng)蟻群算法會(huì)選擇概率為0.4的節(jié)點(diǎn)。但對(duì)隨機(jī)因子進(jìn)行改進(jìn)后，使得在0～0.15的范圍內(nèi)自動(dòng)選擇第一點(diǎn)，在0.25～0.39范圍內(nèi)選擇第三節(jié)點(diǎn)，這樣在確保大部分螞蟻依舊按照正常的路徑行走的同時(shí)又能進(jìn)行全局搜索，在這過(guò)程中能降低某些路段信息素?cái)?shù)量過(guò)大對(duì)螞蟻的導(dǎo)向作用，從而大大增加了找到全局最優(yōu)解的可能性。

2.3 時(shí)間窗系數(shù)的引入

時(shí)間窗在眾多路徑規(guī)劃問(wèn)題中有著廣泛的討論[5]，尤其在商旅路徑規(guī)劃的研究中對(duì)諸多因素有影響[6]，例如游客不愿在路途上花費(fèi)過(guò)多時(shí)間時(shí)，就對(duì)路途時(shí)間提出了高要求，進(jìn)而影響整體路線的規(guī)劃。因此通過(guò)在蟻群算法中引入時(shí)間窗系數(shù)，使得求出的解更符合現(xiàn)實(shí)情況。

在時(shí)間窗啟發(fā)函數(shù)的設(shè)計(jì)中[7]，定義了以下變量：wij為時(shí)間窗系數(shù)，STi為滯留在i點(diǎn)的時(shí)間，Tij為i點(diǎn)到j(luò)點(diǎn)所需的時(shí)間，Tik為到達(dá)i點(diǎn)的時(shí)刻，[ETi，LTi]為到達(dá)i點(diǎn)可接受的時(shí)間窗;并設(shè)計(jì)了以下的時(shí)間窗約束條件：

其中，Nc為景點(diǎn)的集合，K為車輛的集合，同時(shí)設(shè)計(jì)了時(shí)間窗系數(shù)與相關(guān)變量的關(guān)系如下：

3 算法的實(shí)現(xiàn)

3.1 參數(shù)的選擇

由上述可知，參數(shù)的大小對(duì)算法得到的解有很大的影響，因此在參數(shù)選擇時(shí)，需確定不同參數(shù)對(duì)算法的影響，首先確定影響較大的參數(shù)，其次再確定影響較小的參數(shù)。通過(guò)參閱相關(guān)資料[8]，啟發(fā)因子？琢，期望啟發(fā)因子？茁，時(shí)間窗啟發(fā)式因子？茲，信息素?fù)]發(fā)系數(shù)？籽，會(huì)對(duì)算法有著很大的影響，螞蟻數(shù)量m和信息素強(qiáng)度Q對(duì)算法的影響不大。文獻(xiàn)[8]中詳細(xì)討論了各種參數(shù)，確定信息素的強(qiáng)度Q=100，揮發(fā)系數(shù)ρ=0.1，螞蟻的數(shù)量m=15;啟發(fā)因子？琢=1，期望啟發(fā)因子？茁=5，時(shí)間窗啟發(fā)式因子θ=4，迭代次數(shù)100。

3.2 仿真實(shí)驗(yàn)

用以上的模擬數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)，算法在MATLAB R2018b中編寫，并于Windows10，8.00GB等配置下進(jìn)行操作。在擬定的坐標(biāo)系下選取了10個(gè)坐標(biāo)作為模擬起點(diǎn)、終點(diǎn)及景點(diǎn)，并制定相關(guān)的時(shí)間窗數(shù)據(jù)，通過(guò)10次的模擬實(shí)驗(yàn)得出了相關(guān)的結(jié)果數(shù)據(jù)，如圖表所示。

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

隨著人們對(duì)旅游規(guī)劃提出更高的要求，在改進(jìn)的蟻群算法加入時(shí)間窗約束，使得旅游的安排更為人性化和個(gè)性化更為貼合實(shí)際。在未來(lái)的研究上，將不斷的研究及改進(jìn)算法，并與人工智能等新技術(shù)相結(jié)合，使算法的性能與解更為精確。

參考文獻(xiàn)：

[1]黃于欣，蔣洪杰.基于改進(jìn)蟻群算法的旅游景區(qū)路徑規(guī)劃[J].河南科學(xué)，2018，36（06）：823-829.

[2]汪越，王向前，劉敏.一種基于蟻群算法的帶時(shí)間窗物流運(yùn)輸車輛路徑優(yōu)化方法[J].宿州學(xué)院學(xué)報(bào)，2018，33（10）：21-24+28.

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

[4]黃于欣，蔣洪杰.基于改進(jìn)蟻群算法的旅游景區(qū)路徑規(guī)劃[J].河南科學(xué)，2018，36（06）：823-829.

[5]李鵬飛，沈最意.基于改進(jìn)蟻群算法的水產(chǎn)品運(yùn)輸車路徑優(yōu)化策略[J].浙江海洋大學(xué)學(xué)報(bào)（自然科學(xué)版），2017，36（05）：451-457.

[6]胡俊橋.蟻群混合算法求解帶時(shí)間窗車輛路徑問(wèn)題[D].西安科技大學(xué)，2017.

[7]辜勇，張列，李志遠(yuǎn)，等.基于GA-ACO的帶時(shí)間窗車輛路徑問(wèn)題研究[J].物流技術(shù)，2019，38（02）：53-60.

[8]牛悅誠(chéng).基于蟻群算法的智慧旅游路線規(guī)劃研究[D].南京郵電大學(xué)，2017.