面向物流車輛路徑規(guī)劃的自適應(yīng)蟻群算法

鄭娟毅，付姣姣，程秀琦

(西安郵電大學(xué)通信與信息工程學(xué)院，陜西西安 710121)

1 引言

隨著城市信息化的快速發(fā)展，物流發(fā)展的愈加迅速，企業(yè)間的競(jìng)爭(zhēng)也愈加激烈，若能在物流末端配送環(huán)節(jié)加以改進(jìn)，則能更好的滿足需求[1]。車輛路徑問題是物流車輛路徑規(guī)劃的關(guān)鍵環(huán)節(jié)，車輛路徑問題(vehicle routing problem,VRP)是指由一個(gè)負(fù)責(zé)配送貨物的車隊(duì)選擇較為合適的配送路線，完成具有一定數(shù)量的配送點(diǎn)要求并回到配送中心且滿足所有約束條件后達(dá)到路徑最優(yōu)的問題[2]。在求解VRP中，啟發(fā)式算法一直是研究路徑優(yōu)化問題的重點(diǎn)，啟發(fā)式算法主要有節(jié)約法[3]，掃描法[4]，遺傳算法[5]，粒子群算法[6]，蟻群算法[7](ant colony algorithm，ACA)和模擬退火算法[8](simulated annealing，SA)等，蟻群算法具有較好的并行性和魯棒性，并且易于其它算法結(jié)合，模擬退火算法運(yùn)算效率高，求解方向與算法的初始狀態(tài)無關(guān)。文獻(xiàn)[9]采用并行搜索方式進(jìn)行信息素交互的雙種群最大最小蟻群算法，改善了解的質(zhì)量但是收斂速度下降了。文獻(xiàn)[9]提出一種解決Job-Shop的模擬退火蟻群算法，算法的收斂速度提高了，但出現(xiàn)早熟現(xiàn)象。文獻(xiàn)[10]提出求解旅行商問題的模擬退火蟻群算法，它在一定程度上避免了早熟現(xiàn)象，但是收斂速度降低了。

針對(duì)以上算法在求解車輛路徑問題易陷入局部最優(yōu)和收斂速度較慢等問題，本文提出一種自適應(yīng)蟻群算法，將模擬退火算法得到的解作為蟻群算法的初始值；在蟻群算法的狀態(tài)轉(zhuǎn)移規(guī)則引入道路阻抗系數(shù)，以滿足實(shí)際路徑需求，并對(duì)信息素?fù)]發(fā)因子進(jìn)行自適應(yīng)調(diào)整，結(jié)合2-opt鄰域搜索算法對(duì)蟻群算法得到的解二次交換，改變解的質(zhì)量并進(jìn)行優(yōu)選，前期避免陷入局部最優(yōu)，后期加快算法收斂速度。

2 車輛路徑問題的數(shù)學(xué)模型

在車輛路徑問題中假定配送中心滿足配送點(diǎn)的要求，能夠合理安排服務(wù)車輛的配送路線，使得配送成本達(dá)到最低。假設(shè)滿足以下條件：

1)已知只有一個(gè)配送中心與多個(gè)配送點(diǎn)位置坐標(biāo)；

2)從配送中心出發(fā)的車輛必須返回配送中心，車輛類型一致；

3)每輛車的車載量盡量達(dá)到滿載，但不能超過車容量限制；

其中s表示配送中心，有m輛配送車輛為n處配送點(diǎn)服務(wù)。dij表示城市i與j的距離，w表示服務(wù)車輛配送貨物時(shí)的配送成本，c表示服務(wù)車輛出行任務(wù)時(shí)的固定成本，每輛車的負(fù)荷量為D，每個(gè)配送點(diǎn)的需求為vi.則相應(yīng)的數(shù)學(xué)模型如下。

目標(biāo)函數(shù)

(1)

約束條件：

(2)

(3)

(4)

(5)

(6)

(7)

(8)

式(1)是求解車輛路徑規(guī)劃配送所需費(fèi)用最低的目標(biāo)函數(shù)，其中配送所需費(fèi)用與路徑成正比例關(guān)系；式(2)-(4)保證每個(gè)配送點(diǎn)僅有一輛車進(jìn)行配送服務(wù)；式(5)保證每輛車的負(fù)荷量不超過其自身最大負(fù)荷量；式(6)保證每輛車的軌跡路線必須為一個(gè)閉環(huán)，且每輛車必須從配送中心出發(fā)。

3 基本蟻群算法的最短路徑尋優(yōu)

蟻群算法是一種仿生優(yōu)化算法，它主要通過人工模擬螞蟻的行為實(shí)現(xiàn)最短路徑的獲取。因?yàn)槲浵亴?duì)周圍環(huán)境并不敏感，環(huán)境的變化不會(huì)影響螞蟻在短時(shí)間內(nèi)找到新的最短路徑。對(duì)于螞蟻而言，真正起到?jīng)Q定性因素的是一種名叫“信息素”的物質(zhì)，它是螞蟻釋放的一種特別的分泌物，在找尋最短路徑的途中，通過感應(yīng)這種物質(zhì)來找到最短路徑。每只螞蟻在經(jīng)過的路徑上都會(huì)釋放信息素，可以根據(jù)每條路徑上信息素濃度的不同找到最短路徑。

對(duì)于最短路徑問題，基本蟻群算法描述如下：

1)城市車輛路徑集群為Path，蟻群數(shù)量為m，節(jié)點(diǎn)i和節(jié)點(diǎn)j間的距離為Dij，t時(shí)刻路徑的(i，j)信息素濃度為Tij。

2)每只螞蟻的爬行方向由信息素濃度確定，用禁忌表存儲(chǔ)螞蟻所經(jīng)過的節(jié)點(diǎn)。

3)在路徑搜索過程中，通過信息素濃度和啟發(fā)信息計(jì)算狀態(tài)轉(zhuǎn)移概率。

4)當(dāng)螞蟻完成一次遍歷后，需要對(duì)其路徑上的信息素濃度進(jìn)行調(diào)整。

5)當(dāng)達(dá)到搜索最大次數(shù)時(shí)，找到最短路徑。

基本蟻群算法具有正反饋機(jī)制、魯棒性強(qiáng)的優(yōu)點(diǎn)，同時(shí)也具有許多不足之處，如初期信息素缺乏，導(dǎo)致初始解精度不高，長時(shí)間搜索導(dǎo)致選擇趨于兩極化，算法收斂速度和解的質(zhì)量降低。為了克服基本蟻群算法的不足，提高收斂速度和解的質(zhì)量，本文對(duì)其進(jìn)行改進(jìn)。

4 混合算法的改進(jìn)

4.1 模擬退火算法的引進(jìn)

針對(duì)基本蟻群算法因初期信息素濃度缺乏，導(dǎo)致初始解精度不高問題，引進(jìn)全局搜索智能模擬退火算法。初始時(shí)從一個(gè)較高溫度出發(fā)產(chǎn)生一個(gè)解，然后逐漸降低溫度產(chǎn)生一個(gè)新解，計(jì)算當(dāng)前新解和前一個(gè)解的差值，再根據(jù)Metropolis抽樣準(zhǔn)則來判斷在最低溫度時(shí)能獲取能量最低態(tài)。模擬退火算法的冷卻過程為

Ta+1=hTaa=1，2，……，A-1

(9)

4.2 狀態(tài)轉(zhuǎn)移概率的改進(jìn)

蟻群算法中，螞蟻會(huì)根據(jù)每條路徑上的信息素濃度的含量來選擇下一個(gè)覓食點(diǎn)，假設(shè)螞蟻在t時(shí)刻以概率p選擇下一個(gè)覓食點(diǎn)，此時(shí)狀態(tài)轉(zhuǎn)移概率公式如下

(10)

當(dāng)螞蟻完成一次遍歷后，對(duì)路徑上的信息素濃度按照式(12)進(jìn)行更新

τij(t+1)=(1-ρ)τij(t)+Δτij(t，t+1)

(11)

(12)

(13)

其中α表示信息啟發(fā)因子，β表示期望啟發(fā)因子，τij表示路徑間信息素濃度，ρ表示信息素?fù)]發(fā)因子，Q表示信息素總量；Lk表示在當(dāng)前遍歷中最優(yōu)螞蟻所經(jīng)過的路徑。

在實(shí)際路況中，車輛路徑問題需要考慮出現(xiàn)道路擁堵的狀況，因此引入交通工程學(xué)中的道路阻抗系數(shù)，此時(shí)將狀態(tài)轉(zhuǎn)移概率式(10)修改為

(14)

(15)

本文引用蟻群系統(tǒng)[12](AntColonySystem，ACS)的狀態(tài)轉(zhuǎn)移規(guī)則，對(duì)蟻群算法狀態(tài)轉(zhuǎn)移規(guī)則進(jìn)行調(diào)整。因此改進(jìn)后的狀態(tài)轉(zhuǎn)移規(guī)則為

(16)

其中qij表示單位時(shí)間內(nèi)通過的車輛數(shù)，cij表示單位時(shí)間內(nèi)車輛的成本，a和b為阻滯系數(shù)，a的取值范圍(0.1，0.2)，b的取值范圍(1，4)。q0是設(shè)定好的的閾值，q為[0，1]的隨機(jī)值。

4.3 信息素?fù)]發(fā)因子的改進(jìn)

信息素?fù)]發(fā)因子表示信息素濃度的揮發(fā)減少程度，它是影響蟻群算法全局搜索能力和收斂速度的。信息素?fù)]發(fā)因子過大，會(huì)使各條路徑上的信息素濃度揮發(fā)的比較快，導(dǎo)致算法收斂速度慢；信息素?fù)]發(fā)因子過小，會(huì)使各條路徑上的信息素濃度揮發(fā)的比較慢，路徑上的信息素聚集過多導(dǎo)致陷入局部最優(yōu)。為了避免算法收斂速度過慢或者陷入局部最優(yōu)等問題，對(duì)原有算法的信息素?fù)]發(fā)因子進(jìn)行改進(jìn)，在算法前期，將信息素?fù)]發(fā)系數(shù)設(shè)置較大，使算法具有較強(qiáng)的全局搜索能力，在達(dá)到一定迭代次數(shù)后，將信息素?fù)]發(fā)系數(shù)逐漸減小，使蟻群算法具有較好的收斂速度。因此將信息素?fù)]發(fā)系數(shù)改進(jìn)為

(17)

4.4 2-opt算法

2-opt算法可以通過對(duì)較優(yōu)解的兩條邊進(jìn)行交換來獲取另一個(gè)解，這樣經(jīng)過交換搜索可以改變解的質(zhì)量[12]，是一種局部搜索算法。在所有配送點(diǎn)中隨機(jī)選擇第n1、n2次訪問的配送點(diǎn)，交換兩者的位置。

圖1是常規(guī)選擇路徑圖，假設(shè)其順序?yàn)锳-B-C-D-A，若將其應(yīng)用到2-opt算法中則如圖2所示其順序?yàn)锳-D-C-B-A，為提高算法的精度，本文對(duì)蟻群算法每一次迭代產(chǎn)生較優(yōu)解的路徑利用2-opt算法進(jìn)行優(yōu)化。具體做法如下：首先對(duì)每一次迭代產(chǎn)生的較優(yōu)路徑按照2-opt算法的交換方法進(jìn)行調(diào)整，重新計(jì)算路徑的較優(yōu)解，若新的解優(yōu)于調(diào)整前的解，則更新蟻群算法的最優(yōu)路徑，否則保持路徑不變。

圖1 路徑選擇圖

圖2 2-opt方法選擇圖

5 改進(jìn)算法的流程

改進(jìn)后算法的思想是將模擬退火算法得到的解作為蟻群算法的初始解，然后采用2-opt算法對(duì)蟻群算法得到的路徑進(jìn)行交換得到一個(gè)新的路徑，并對(duì)蟻群算法和2-opt法相應(yīng)路徑解的距離值進(jìn)行比較獲得全局最優(yōu)解。組合算法流程如圖3所示。

圖3 改進(jìn)后算法流程圖

算法具體實(shí)現(xiàn)步驟：

Step1：模擬退火參數(shù)初始化并得到較優(yōu)解；

Step2：將模擬退火算法得到的較優(yōu)解作為蟻群算法的初始解，并對(duì)參數(shù)進(jìn)行初始化；

Step3：num=1，將各個(gè)螞蟻放在配送中心，并根據(jù)式(16)改進(jìn)的狀態(tài)轉(zhuǎn)移規(guī)律選擇下一個(gè)節(jié)點(diǎn)，并得到當(dāng)前最優(yōu)解L1；

Step4：在L1的較優(yōu)路徑通過2-opt算法的找到另一個(gè)解L2；

Step5：比較L1和L2的大小，并判斷是否接受新解作為當(dāng)前解；

Step6：對(duì)路徑上的信息素按照式(11)改進(jìn)的全局信息素公式進(jìn)行更新；

Step7：num=num+1，判斷num是否達(dá)到最大迭代次數(shù)，若達(dá)到轉(zhuǎn)Step8，若沒有達(dá)到則轉(zhuǎn)Step3;

Step8：輸出最優(yōu)解。

6 仿真分析

本文在Window10操作系統(tǒng)，Matlab2012a的運(yùn)行環(huán)境下進(jìn)行驗(yàn)證。算法參數(shù)選擇如下：α=7，β=10，m=30，h=0.9，T=10000，TA=10，NCmax=100。

為證明算法的有效性和穩(wěn)定性，以文獻(xiàn)[14]中的算例(E-n22-k4，A-n32-k5，A-n36-k5A-n37-k6，A-n38-k5)作為數(shù)據(jù)源進(jìn)行仿真對(duì)比。其中n后面的數(shù)字代表配送點(diǎn)的個(gè)數(shù)，k后面的數(shù)字代表最少需要的配送車輛，最大迭代次數(shù)為100次，將改進(jìn)后算法的最優(yōu)解與文獻(xiàn)[14]及基本模擬退火蟻群算法的最優(yōu)解進(jìn)行比較，結(jié)果如表1所示。

表1 最優(yōu)值比較(/km)

由表1可知，本文算法的最優(yōu)值與基本模擬退火蟻群算法、文獻(xiàn)[14]的最優(yōu)值相比有一定的改進(jìn)。因此改進(jìn)后的算法具有更好的性能。表1中本算法的路徑圖和算法迭代仿真對(duì)比圖如圖4所示：

圖4 本文算法最優(yōu)值路徑圖與迭代次數(shù)對(duì)比圖

1)(a)表示E-n22-k4的路徑圖，(b)表示改進(jìn)后算法和基本模擬退火蟻群算法的迭代次數(shù)比較圖，解的質(zhì)量提高9.76%，收斂速度提高41.4%。

2)(c)表示A-n32-k5的路徑圖，(d)表示改進(jìn)后算法和基本模擬退火蟻群算法的迭代次數(shù)比較圖，解的質(zhì)量提高7.05%，收斂速度提高42.6%。

3)(e)表示A-n36-k5的路徑圖，(f)表示改進(jìn)后算法和基本模擬退火蟻群算法的迭代次數(shù)比較圖，解的質(zhì)量提高2.65%，收斂速度提高46.8%。

4)(g)表示A-n37-k6的路徑圖，(h)表示改進(jìn)后算法和基本模擬退火蟻群算法的迭代次數(shù)比較圖，解的質(zhì)量提高13.63%，收斂速度提高43.6%。

5)(i)表示A-n38-k5的路徑圖，(j)表示改進(jìn)后算法和基本模擬退火蟻群算法的迭代次數(shù)比較圖，解的質(zhì)量提高8.75%，收斂速度提高47.3%。

由此可知，改進(jìn)后的算法在收斂速度與解的精度上都有提升。

7 結(jié)論

本文針對(duì)蟻群算法在車輛路徑規(guī)劃存在的問題提出自適應(yīng)模擬退火蟻群算法。在蟻群算法的狀態(tài)轉(zhuǎn)移規(guī)則引入道路阻抗系數(shù)，對(duì)全局信息素更新策略的信息素?fù)]發(fā)系數(shù)進(jìn)行調(diào)整，前期避免陷入局部最優(yōu)，后期加快算法收斂速度。最后通過對(duì)不同規(guī)模城市的車輛路徑問題進(jìn)行測(cè)試，結(jié)果表明，改進(jìn)后的算法可以提高解的質(zhì)量和收斂速度。下一步將針對(duì)多配送中心和軟時(shí)間窗的物流路徑問題進(jìn)行研究，用以提高物流車輛路徑規(guī)劃的實(shí)用性。