基于自適應蟻群算法的車輛路徑問題研究

(同濟大學 上海 200092)

基于自適應蟻群算法的車輛路徑問題研究

胡萌萌

(同濟大學上海200092)

車輛路徑的選擇本質上是一個非確定性多項式問題，當其規模相對較小時可以利用多種傳統方法求得最優解；但是隨著問題規模的逐漸增大，方法的適用性也越來越差。本文首先論述了蟻群算法在解決該類問題中的適用性以及應用過程中的優勢和劣勢，最后提出在不同搜索階段對其參數進行相應調整的改進措施，最大程度上提升其收斂速度，滿足問題解決的需要。

車輛路徑問題；蟻群算法；自適應策略

一、問題描述

隨著電子商務的快速發展，物流配送過程中常見的問題是物流車輛對區域內用戶配送過程中的最佳路徑：假設該配送中心共有n輛車，每一輛快遞車的最大運送量為G；配送范圍內共有m個客戶，每個客戶的貨物重量都各不相同，用qi表示(i=1,2……m)；快遞車輛的節點用p表示，其中p0代表快遞中心，pi代表客戶點(i=1,2……m)；快遞運送過程中的成本用ci表示，其成本包括時間、人力和運輸過程中的各種費用。則這一問題的變量可通過以下的公式定義：

數學模型可以概化為：

s.t.

二、算法概述

昆蟲學家在對螞蟻生活研究過程中發現，其從野外覓食點到蟻巢之間的路徑選擇過程中依靠的是螞蟻之間的相互溝通，其中最為重要的媒介是螞蟻的分泌物—信息素。其中的任何一只螞蟻都會在根據路徑上信息素的濃度來選擇其下一步的路徑，而隨著最優路徑上信息素濃度的不斷累計，后續的螞蟻都會選擇該路徑完成食物的搬運。

蟻群算法簡稱做ACO，最早由Dorigo等人在上世紀九十年代提出；在該算法提出之前學術界內針對組合優化問題采用的較為成熟的算法有模擬退火算法、遺傳算法、人工神經網絡等。截止目前該算法已經經過了眾多學者的研究和使用，已經基本趨于成熟。

M.Dorigo等人在TSP問題中對該算法進行了成功的應用，之后由根據其特點將其應用范圍拓展至不均衡的TSP、QAP和job-shop調度問題，并且效果良好[1]。鑒于該算法應用過程中會出現收斂停滯的現象，Stützle,T.等人對傳統的蟻群算法做了進一步的完善，提出了MAX-MIN蟻群算法(簡稱做MMAS)其中最重要一處改進是將不同路徑內的信息濃度都進行了限制，為其設定了最大和最小值，同時規定某次循環結束之后只將最短路徑的信息素添加進去；這樣就能夠有效限制過早收斂非全局最優解的出現；吳慶洪在其研究成果中將變異機制引入到蟻群算法中，將算法的收斂變得更加簡潔和高效[2]；姚寶珍則是在基本算法中加入了自適應的機制，能夠根據算法搜索階段的不同對其中的部分參數進行調整[3]；陳陵也提出了新的基于自適應機制的蟻群算法，其依靠的是解的分布均勻度，根據其變化來選取最佳的概率確定和信息量更新方法[4]。

三、自適應蟻群算法

(一)自適應轉移規則

基本蟻群算法計算過程中通常會將“信息素”濃度不同作為路徑選擇的依據。考慮到最優解位置的未知性，搜索過程中需要保證搜索過程中的隨機性；但是算法的應用有要求能夠高效的解決具體的問題，所以必須有一定的確定性；兩方面綜合作用下就要求算法的轉移規則能夠最大程度上滿足這兩方面的需求，從而保證算法執行的效率。

一般情況下，如果源問題確定之后，算法執行過程中信息素強度和期望度也不會出現大的變化，所以精確找到兩個啟發式因子(α和β)成為算法中的重要環節。通常來講，會利用仿真來獲得這兩個參數，并且選擇固定值貫穿于算法應用過程中；但這樣一來就忽略了蟻群計劃過程中這兩個參數的地位的變化。例如算法運行初期，信息素還沒在系統中形成，期望信息能夠在很大程度上決定蟻群的運動；但是隨著算法的不斷運行，信息素基本成型，這時信息素強度將成為決定蟻群運動的重要參數。

鑒于此，本次在基本蟻群算法的基礎上引入了自適應的機制，以第i點的第k只螞蟻作為論述對象，其在下一個階段向j點運動的概率為：

式中：τij代表(i,j)邊信息素的濃度；ηij則代表其能見度；α和β是算法中相應的啟發因子，其中前者能夠代表搜索過程的隨機性，而后者能夠代表搜索過程的確定性；tabuk代表問題中的禁忌點組合；t是進化代數，其取值范圍為1～T，取整數。

(二)自適應信息素更新策略

算法運行過程中不同的螞蟻都能夠感知信息素的濃度，從而完成相互之間的信息溝通；過程中螞蟻會根據預先設定好的轉移規則進行運動，其最終運動曲線則構成了某個具體問題的優化解決方案。并且各次循環結束之后，每條邊上的信息素濃度都會發生相應的變化；其變化的最終依據就是確定好的更新策略。

式中，ρ代表了信息素殘留系數，本次算法優化中取值0.8；τ是螞蟻k在本次循環過程中在(i,j)邊處信息素的變化量；p代表蟻群中螞蟻的數量。通常來說，運動路徑越短，其邊上的信息素濃度也會越大；對于具體的問題來說，如果某一個路徑越與最優方案的相似程度越高，其信息素農業也會越大，越能夠在下一個循環過程中吸引更多的螞蟻。

四、結論

車輛路徑選擇和優化問題是物流分配過程中的重要環節，研究過程中要充分考慮每個車輛的最大載重等因素，在保證客戶需求的同時又要盡可能的降低物流運送過程中的成本；其本質上是一個非確定性多項式問題，當其規模相對較小時可以利用多種傳統方法求得最優解；但是隨著問題規模的逐漸增大，方法的適用性也越來越差。本文在基本蟻群算法的基礎上在更新策略中加入了自適應的機制，既能夠提高算法的收斂速度，同時還能夠有效降低局部最優解的出現幾率。

[1]Dorigo,M,Maniezzo,V,Colorni,A,(1996);The Ant System:Optimization by a Colony of Cooperating Agents,IEEE Transactions onSystems,Mans,and Cybernetics 1(26):29-41

[2]吳慶洪,張紀會,徐心和:具有變異特征的蟻群算法[J].計算機研究與發展，36(10):1240-1245(1999).

[3]姚寶珍:自適應并行蟻群算法[J].模式識別與人工智能.2015,20(4):458-461

[4]陳陵,沈潔,秦玲等:基于分布均勻度的自適應蟻群算法[J].軟件學,2013.14(08):1379-1387

胡萌萌(1992.2-)，女，漢，河北邯鄲，同濟大學，學生，碩士，研究方向車輛路徑規劃。