(同濟(jì)大學(xué) 上海 200092)

基于自適應(yīng)蟻群算法的車輛路徑問(wèn)題研究

胡萌萌

(同濟(jì)大學(xué)上海200092)

車輛路徑的選擇本質(zhì)上是一個(gè)非確定性多項(xiàng)式問(wèn)題，當(dāng)其規(guī)模相對(duì)較小時(shí)可以利用多種傳統(tǒng)方法求得最優(yōu)解；但是隨著問(wèn)題規(guī)模的逐漸增大，方法的適用性也越來(lái)越差。本文首先論述了蟻群算法在解決該類問(wèn)題中的適用性以及應(yīng)用過(guò)程中的優(yōu)勢(shì)和劣勢(shì)，最后提出在不同搜索階段對(duì)其參數(shù)進(jìn)行相應(yīng)調(diào)整的改進(jìn)措施，最大程度上提升其收斂速度，滿足問(wèn)題解決的需要。

車輛路徑問(wèn)題；蟻群算法；自適應(yīng)策略

一、問(wèn)題描述

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

數(shù)學(xué)模型可以概化為：

s.t.

二、算法概述

昆蟲學(xué)家在對(duì)螞蟻生活研究過(guò)程中發(fā)現(xiàn)，其從野外覓食點(diǎn)到蟻巢之間的路徑選擇過(guò)程中依靠的是螞蟻之間的相互溝通，其中最為重要的媒介是螞蟻的分泌物—信息素。其中的任何一只螞蟻都會(huì)在根據(jù)路徑上信息素的濃度來(lái)選擇其下一步的路徑，而隨著最優(yōu)路徑上信息素濃度的不斷累計(jì)，后續(xù)的螞蟻都會(huì)選擇該路徑完成食物的搬運(yùn)。

蟻群算法簡(jiǎn)稱做ACO，最早由Dorigo等人在上世紀(jì)九十年代提出；在該算法提出之前學(xué)術(shù)界內(nèi)針對(duì)組合優(yōu)化問(wèn)題采用的較為成熟的算法有模擬退火算法、遺傳算法、人工神經(jīng)網(wǎng)絡(luò)等。截止目前該算法已經(jīng)經(jīng)過(guò)了眾多學(xué)者的研究和使用，已經(jīng)基本趨于成熟。

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

三、自適應(yīng)蟻群算法

(一)自適應(yīng)轉(zhuǎn)移規(guī)則

基本蟻群算法計(jì)算過(guò)程中通常會(huì)將“信息素”濃度不同作為路徑選擇的依據(jù)?？紤]到最優(yōu)解位置的未知性，搜索過(guò)程中需要保證搜索過(guò)程中的隨機(jī)性；但是算法的應(yīng)用有要求能夠高效的解決具體的問(wèn)題，所以必須有一定的確定性；兩方面綜合作用下就要求算法的轉(zhuǎn)移規(guī)則能夠最大程度上滿足這兩方面的需求，從而保證算法執(zhí)行的效率。

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

鑒于此，本次在基本蟻群算法的基礎(chǔ)上引入了自適應(yīng)的機(jī)制，以第i點(diǎn)的第k只螞蟻?zhàn)鳛檎撌鰧?duì)象，其在下一個(gè)階段向j點(diǎn)運(yùn)動(dòng)的概率為：

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

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

算法運(yùn)行過(guò)程中不同的螞蟻都能夠感知信息素的濃度，從而完成相互之間的信息溝通；過(guò)程中螞蟻會(huì)根據(jù)預(yù)先設(shè)定好的轉(zhuǎn)移規(guī)則進(jìn)行運(yùn)動(dòng)，其最終運(yùn)動(dòng)曲線則構(gòu)成了某個(gè)具體問(wèn)題的優(yōu)化解決方案。并且各次循環(huán)結(jié)束之后，每條邊上的信息素濃度都會(huì)發(fā)生相應(yīng)的變化；其變化的最終依據(jù)就是確定好的更新策略。

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

四、結(jié)論

車輛路徑選擇和優(yōu)化問(wèn)題是物流分配過(guò)程中的重要環(huán)節(jié)，研究過(guò)程中要充分考慮每個(gè)車輛的最大載重等因素，在保證客戶需求的同時(shí)又要盡可能的降低物流運(yùn)送過(guò)程中的成本；其本質(zhì)上是一個(gè)非確定性多項(xiàng)式問(wèn)題，當(dāng)其規(guī)模相對(duì)較小時(shí)可以利用多種傳統(tǒng)方法求得最優(yōu)解；但是隨著問(wèn)題規(guī)模的逐漸增大，方法的適用性也越來(lái)越差。本文在基本蟻群算法的基礎(chǔ)上在更新策略中加入了自適應(yīng)的機(jī)制，既能夠提高算法的收斂速度，同時(shí)還能夠有效降低局部最優(yōu)解的出現(xiàn)幾率。

[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ì)會(huì),徐心和:具有變異特征的蟻群算法[J].計(jì)算機(jī)研究與發(fā)展，36(10):1240-1245(1999).

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

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

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