關(guān)于蟻群算法的研究與分析

吳海俠 武曉霞

一、題目分析

電子商務(wù)的普及促進(jìn)了物流行業(yè)的發(fā)展，然而與發(fā)達(dá)國(guó)家相比我國(guó)物流業(yè)仍處于起步階段。物流信息化的程度較低，配送成本較高成為了急需解決的問(wèn)題。物流路徑的選擇是物流體系當(dāng)中至關(guān)重要的一環(huán)，路徑直接決定了物流配送的效率。因此物流路徑優(yōu)化對(duì)降低企業(yè)成本、提高物流配送效率、合理資源配置有著重要的意義。物流路徑優(yōu)化問(wèn)題的核心就是車輛路徑優(yōu)化（Vehicle Routing Problem），即VRP問(wèn)題。針對(duì)該問(wèn)題，目前已經(jīng)有了很多研究方法，但是不同的方法的優(yōu)缺點(diǎn)不同，本文主要針對(duì)蟻群算法的優(yōu)缺點(diǎn)，以及如何優(yōu)化蟻群算法展開分析。

二、檢索過(guò)程

（一）在“知網(wǎng)”中檢索

首先，在“知網(wǎng)”中輸入“蟻群算法”，搜索出下圖所示結(jié)果：

此次的搜索結(jié)果較為滿意，下載相關(guān)文獻(xiàn)。

（二）在“OA”中檢索：

首先在“OA”中輸入“Ant colony algorithm”，然后把選擇的文獻(xiàn)的DOI在SCI-HUB中搜索就可以看英文文獻(xiàn)了。步驟如下：

三、文獻(xiàn)閱讀與分析

3.1 文獻(xiàn)下載和管理

用Endnot來(lái)整理下載的文獻(xiàn)。用CNKI E-Study也可以整理下載的文獻(xiàn)以及導(dǎo)入?yún)⒖嘉墨I(xiàn)。

3.2 文獻(xiàn)閱讀和分析

（1）軍事定向越野路徑優(yōu)化問(wèn)題建模及混合蟻群算法求解 作者：王書勤，黃茜

本文對(duì)軍事定向越野中的路徑優(yōu)化問(wèn)題，建立了數(shù)學(xué)模型，通過(guò)蟻群算法的改進(jìn)和與遺傳算法的結(jié)合，提出了一種混合蟻群算法，成功求解了軍事定向越野中的路徑優(yōu)化問(wèn)題，解決了軍事定向越野中在點(diǎn)位多，分布散，時(shí)間緊的條件下如何選擇最優(yōu)路徑問(wèn)題。軍事定向越野運(yùn)動(dòng)中存在點(diǎn)位多、分布散、時(shí)間緊、得分要求高等條件，為在規(guī)定時(shí)間內(nèi)找到一條得分高的行進(jìn)線路，找到衡量和分析運(yùn)動(dòng)成績(jī)好壞的標(biāo)準(zhǔn)，文中對(duì)軍事定向越野中的路徑優(yōu)化問(wèn)題進(jìn)行了深入分析，建立了混合整數(shù)規(guī)劃模型，設(shè)計(jì)了一種混合蟻群算法。算法中，首先由改進(jìn)蟻群算法找到初始解，然后再利用選擇、交叉和變異算子進(jìn)行解的優(yōu)化，通過(guò)仿真實(shí)驗(yàn)和算法對(duì)比驗(yàn)證了混合蟻群算法的可行性和優(yōu)越性，并在最后用遺傳算法進(jìn)行收斂，得到最優(yōu)解。

（2）基于改進(jìn)蟻群算法的眾包配送路徑研究? 作者：蔣麗

文章以O(shè)2O 外賣平臺(tái)的眾包配送路徑優(yōu)化為研究對(duì)象，建立了帶有單側(cè)軟時(shí)間窗的需求可延遲的開放式車輛路徑優(yōu)化模型，并使用高德地圖API 獲取實(shí)際節(jié)點(diǎn)。改進(jìn)蟻群算法將下一步移動(dòng)的潛在客戶數(shù)量作為路徑選擇的影響因素，在求解質(zhì)量和效率上具有明顯優(yōu)勢(shì)，仿真對(duì)比實(shí)驗(yàn)驗(yàn)證了模型的合理性和算法的有效性，使路徑選擇和規(guī)劃更具科學(xué)性，有助于有效降低配送成本。下一步研究工作是在靜態(tài)路徑規(guī)劃基礎(chǔ)上，著重研究配送員位置時(shí)刻變化以及繼續(xù)接單的情況，考慮到配送員位置時(shí)刻變化以及繼續(xù)接單的情況，建立軟時(shí)間窗約束下的動(dòng)態(tài)開放式路徑優(yōu)化模型，探討動(dòng)態(tài)路徑優(yōu)化的求解方法。

優(yōu)點(diǎn)是針對(duì)現(xiàn)有O2O外賣眾包配送的經(jīng)驗(yàn)依賴性和隨機(jī)性問(wèn)題，建立以距離成本和時(shí)間懲罰成本之和最小化為目標(biāo)的帶有單側(cè)軟時(shí)間窗的需求可延遲的開放式車輛路徑優(yōu)化模型，并借助高德地圖API 接口獲得各實(shí)際節(jié)點(diǎn)的經(jīng)緯度信息和各節(jié)點(diǎn)間距離。改進(jìn)蟻群算法在狀態(tài)轉(zhuǎn)移規(guī)則中添加下一步移動(dòng)的潛在客戶數(shù)量影響因子，同時(shí)將確定性搜索與隨機(jī)性搜索結(jié)合，縮小螞蟻搜索范圍。

（3）基于蟻群算法的雙分區(qū)倉(cāng)庫(kù)揀貨路徑的優(yōu)化? 作者：劉建勝

合理地選擇揀貨路徑對(duì)于降低物流配送成本有重大作用。針對(duì)問(wèn)題的特點(diǎn)，建立了數(shù)學(xué)模型，設(shè)計(jì)了蟻群算法對(duì)其求解，并與多種方法對(duì)比了優(yōu)化結(jié)果，結(jié)果顯示蟻群算法能令人滿意地解決問(wèn)題。針對(duì)一單多車的情況，本文修改了一單一車時(shí)算法部分編碼，對(duì)一單多車的倉(cāng)庫(kù)撿貨情況進(jìn)行了優(yōu)化求解，兩種情況表明蟻群算法能夠很好地解決倉(cāng)庫(kù)揀貨路徑優(yōu)化問(wèn)題。本文用的三比較傳統(tǒng)的蟻群算法，沒有進(jìn)行優(yōu)化。

（4）基于改進(jìn)蟻群算法物流配送路徑優(yōu)化的研究? 作者：張勇

本文從物流配送路徑優(yōu)化問(wèn)題的自身特點(diǎn)出發(fā)，采用蟻群算法加以分析，并進(jìn)行了相應(yīng)的改進(jìn)，通過(guò)進(jìn)行局部?jī)?yōu)化處理，盡量減少算法可能出現(xiàn)的停滯現(xiàn)象，同時(shí)對(duì)信息素的更新方式加以改進(jìn)，增強(qiáng)了改進(jìn)后蟻群算法的正反饋機(jī)制，提升了算法的自適應(yīng)性，進(jìn)一步加快了收斂的速度以及算法的全局搜索能力。結(jié)合實(shí)例計(jì)算與分析，我們不難發(fā)現(xiàn)，改進(jìn)后的蟻群算法能更快速、有效地對(duì)物流配送路徑問(wèn)題進(jìn)行優(yōu)化處理，進(jìn)而尋得最優(yōu)解。由此得知，本文得出的相關(guān)結(jié)論，對(duì)物流配送路徑優(yōu)化問(wèn)題具有一定的實(shí)用性與參考性。

（5）Non-dominated sorting differential evolution algorithm for the minimization of route based fuel consumption multiobjective vehicle routing problems

針對(duì)4個(gè)基于多目標(biāo)路徑的車輛路徑選擇問(wèn)題，提出了3種并行多啟動(dòng)非支配排序差分進(jìn)化算法，并將其結(jié)果與并行多啟動(dòng)NSGA算法的結(jié)果進(jìn)行了比較。所有這些算法都使用多個(gè)初始解的總體。在每一種算法中都使用了一個(gè)變量領(lǐng)域搜索算法來(lái)分別改進(jìn)每個(gè)解，用兩個(gè)目標(biāo)函數(shù)表示的問(wèn)題是基于多個(gè)目標(biāo)對(duì)稱和非對(duì)稱的車輛路徑問(wèn)題。優(yōu)化目標(biāo)函數(shù)對(duì)應(yīng)于所需的時(shí)間之間的汽車旅行兩個(gè)客戶的旅行距離，所以本文采用的是蟻群算法來(lái)優(yōu)化目標(biāo)函數(shù)。

四、心得

通過(guò)閱讀這些文獻(xiàn)，掌握了蟻群算法的模型的建立，該模型在物流專業(yè)主要用于路徑優(yōu)化的問(wèn)題上，能解決資源配置的優(yōu)化以及成本最小化等問(wèn)題。但是，該模型的不足之處在于后期收斂慢，需要再次進(jìn)行優(yōu)化。有些文獻(xiàn)在蟻群算法模型上加上時(shí)間窗或者有多個(gè)目標(biāo)的蟻群算法，都是對(duì)蟻群算法的進(jìn)一步優(yōu)化，其他的優(yōu)化還有待考察。

通過(guò)學(xué)習(xí)信息檢索課，收獲頗大。明白了怎么合理的選擇自己需要的文獻(xiàn)，怎么擇優(yōu)選擇，同時(shí)也會(huì)查閱外文文獻(xiàn)，避免了之前盲目看文獻(xiàn)的陋習(xí)。在創(chuàng)新的方面也有很大收獲，不論對(duì)以后的學(xué)習(xí)還是工作都有很大的幫助。

（石家莊鐵道大學(xué) 經(jīng)濟(jì)管理學(xué)院）