關于蟻群算法的研究與分析

吳海俠 武曉霞

一、題目分析

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

二、檢索過程

（一）在“知網”中檢索

首先，在“知網”中輸入“蟻群算法”，搜索出下圖所示結果：

此次的搜索結果較為滿意，下載相關文獻。

（二）在“OA”中檢索：

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

三、文獻閱讀與分析

3.1 文獻下載和管理

用Endnot來整理下載的文獻。用CNKI E-Study也可以整理下載的文獻以及導入參考文獻。

3.2 文獻閱讀和分析

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

本文對軍事定向越野中的路徑優化問題，建立了數學模型，通過蟻群算法的改進和與遺傳算法的結合，提出了一種混合蟻群算法，成功求解了軍事定向越野中的路徑優化問題，解決了軍事定向越野中在點位多，分布散，時間緊的條件下如何選擇最優路徑問題。軍事定向越野運動中存在點位多、分布散、時間緊、得分要求高等條件，為在規定時間內找到一條得分高的行進線路，找到衡量和分析運動成績好壞的標準，文中對軍事定向越野中的路徑優化問題進行了深入分析，建立了混合整數規劃模型，設計了一種混合蟻群算法。算法中，首先由改進蟻群算法找到初始解，然后再利用選擇、交叉和變異算子進行解的優化，通過仿真實驗和算法對比驗證了混合蟻群算法的可行性和優越性，并在最后用遺傳算法進行收斂，得到最優解。

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

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

優點是針對現有O2O外賣眾包配送的經驗依賴性和隨機性問題，建立以距離成本和時間懲罰成本之和最小化為目標的帶有單側軟時間窗的需求可延遲的開放式車輛路徑優化模型，并借助高德地圖API 接口獲得各實際節點的經緯度信息和各節點間距離。改進蟻群算法在狀態轉移規則中添加下一步移動的潛在客戶數量影響因子，同時將確定性搜索與隨機性搜索結合，縮小螞蟻搜索范圍。

（3）基于蟻群算法的雙分區倉庫揀貨路徑的優化? 作者：劉建勝

合理地選擇揀貨路徑對于降低物流配送成本有重大作用。針對問題的特點，建立了數學模型，設計了蟻群算法對其求解，并與多種方法對比了優化結果，結果顯示蟻群算法能令人滿意地解決問題。針對一單多車的情況，本文修改了一單一車時算法部分編碼，對一單多車的倉庫撿貨情況進行了優化求解，兩種情況表明蟻群算法能夠很好地解決倉庫揀貨路徑優化問題。本文用的三比較傳統的蟻群算法，沒有進行優化。

（4）基于改進蟻群算法物流配送路徑優化的研究? 作者：張勇

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

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

針對4個基于多目標路徑的車輛路徑選擇問題，提出了3種并行多啟動非支配排序差分進化算法，并將其結果與并行多啟動NSGA算法的結果進行了比較。所有這些算法都使用多個初始解的總體。在每一種算法中都使用了一個變量領域搜索算法來分別改進每個解，用兩個目標函數表示的問題是基于多個目標對稱和非對稱的車輛路徑問題。優化目標函數對應于所需的時間之間的汽車旅行兩個客戶的旅行距離，所以本文采用的是蟻群算法來優化目標函數。

四、心得

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

通過學習信息檢索課，收獲頗大。明白了怎么合理的選擇自己需要的文獻，怎么擇優選擇，同時也會查閱外文文獻，避免了之前盲目看文獻的陋習。在創新的方面也有很大收獲，不論對以后的學習還是工作都有很大的幫助。

（石家莊鐵道大學 經濟管理學院）