時間窗下的改進(jìn)蟻群算法在旅游路線規(guī)劃研究

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

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

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

中圖分類號：TP18? ? ? ? ?文獻(xiàn)標(biāo)志碼：A? ? ? ? ?文章編號：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

引言

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

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

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

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

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

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

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

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

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

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

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

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

3 算法的實現(xiàn)

3.1 參數(shù)的選擇

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

3.2 仿真實驗

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

4 結(jié)束語

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

參考文獻(xiàn)：

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

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

[3]徐鋒，杜軍平.改進(jìn)蟻群算法在旅游路線規(guī)劃中的應(yīng)用研究[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é)報（自然科學(xué)版），2017，36（05）：451-457.

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

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

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