基于蟻群算法在VRP中的應(yīng)用研究*
——以呼和浩特A物流公司為例

□ 文宗川，王 慧

(1.內(nèi)蒙古工業(yè)大學(xué) 經(jīng)濟管理學(xué)院,內(nèi)蒙古 呼和浩特 010051；2.內(nèi)蒙古工業(yè)大學(xué) 人文學(xué)院,內(nèi)蒙古 呼和浩特 010081;3.內(nèi)蒙古創(chuàng)新方法研究中心,內(nèi)蒙古 呼和浩特 010051)

物流作為最終成本的削弱邊界，是繼增加生產(chǎn)、節(jié)約成本，提高效率、降低損耗兩大利潤源之后的第三利潤源，其經(jīng)濟意義不言而喻。而配送作為現(xiàn)代物流管理中的七大要素之一，它是現(xiàn)代市場的新經(jīng)濟系統(tǒng)、當(dāng)代新興科學(xué)方法和系統(tǒng)供應(yīng)鏈思想的綜合產(chǎn)物，其中車輛路徑問題(Vehicle Routing Problem,以下簡稱VRP)是配送中的主要研究方向?；赩RP的相關(guān)研究主要概括為精確式算法與啟發(fā)式算法[1]，如遺傳算法、蟻群算法、禁忌搜索算法、模擬退火算法、粒子群算法等。其中多數(shù)學(xué)者都是基于有時間約束的VRP模型，改進蟻群算法提高收斂速度，降低車輛使用量使運行距離變短[2-4]。也有學(xué)者通過禁忌搜索算法求解車輛路徑問題，如構(gòu)建鄰域算子和鄰域交換點禁忌表，測試數(shù)據(jù)結(jié)果[5-6]。針對車輛運輸路徑(Vehicle Routing)與車輛運輸速度(VehicleSpeed)的相關(guān)性，經(jīng)營成本與收益的線性關(guān)系比，采用科學(xué)合理的方法確定車輛運輸?shù)穆肪€規(guī)劃是物流配送活動重中之重，通過對傳統(tǒng)的配送系統(tǒng)進行路徑優(yōu)化，可以大幅度提高資源的利用率。

本文以呼和浩特市新城區(qū)A物流公司的派送網(wǎng)點為例，基于蟻群算法對車輛路徑問題進行優(yōu)化，針對不同配送路線的車輛路徑問題構(gòu)造相應(yīng)數(shù)學(xué)模型并進行MATLAB仿真模擬。

1 蟻群算法求解模型

1.1 蟻群算法原理

蟻群算法的基本原理可以通過Dorigo M研究蟻群尋找食物過程的例子進行解釋，圖1(圖中d代表長度，T代表時間段，ant代表螞蟻數(shù)量)是蟻群尋找食物的簡化示意圖。假設(shè)X是蟻群的蟻巢，Y是蟻群目標食物源，N與M分別是假設(shè)障礙物，由于障礙物的原因，蟻群不能直接抵達Y目標，蟻群只能由N經(jīng)過A到達Y，或者由M經(jīng)過A到達Y。假設(shè)一個時間單位分別有100只螞蟻由A到Y(jié)或者由X到B，由于開始沒有蟻群形成信息濃度差，蟻群在抵達B時，選擇兩條路線的概率相等，所以每一條路徑都有50只螞蟻。隨著時間的推移，蟻群的選擇路徑上有信息素的積累，B-M、A-M路徑的信息素濃度是B-N、A-N路徑的兩倍左右，又根據(jù)不同蟻群數(shù)量的移動，B-M-A的路徑信息素濃度越來高，會導(dǎo)致更多的螞蟻選擇該路線，從而找出蟻巢到食物源的最短路徑。根據(jù)以上的蟻群路線模擬，可知蟻群之間的信息素濃度差與信息交換是一個正反饋的過程。

圖1 不同時間段的信息素濃度對螞蟻選擇路徑的影響

1.2 蟻群算法路徑運輸模型

(1)

在式(1)中，Aa為螞蟻k尚未尋找的食物點集合，這個集合在進化過程中不斷調(diào)整。α，β分別表示螞蟻在運動過程中所積累的信息素和啟發(fā)式因子在螞蟻路徑選擇中所起的不同作用。相關(guān)信息素更新規(guī)則如下：

τnm(t+t1)=ρ·τnm(t)+△τnm

(2)

(3)

式中，ρ為信息殘留程度。

式中，△τnm為本次循環(huán)中留在路徑n和m上的總信息素量，有三種計算方法：

蟻群循環(huán)系統(tǒng)(Ant-cycleSystem)模型信息素增量的計算公式

(4)

蟻群數(shù)量系統(tǒng)(Ant-quantitySystem)模型信息素增量的計算公式

(5)

蟻群密度系統(tǒng)(Ant-densitySystem)模型信息素增量的計算公式

(6)

基本蟻群算法實現(xiàn)流程如圖2。

圖2 蟻群算法實現(xiàn)流程圖

2 仿真驗證與結(jié)果分析

2.1 在呼和浩特市A物流公司車輛派送點的地理信息采集與處理

以內(nèi)蒙古呼和浩特市新城區(qū)為車輛路徑問題信息處理區(qū)，基于蟻群算法解決現(xiàn)實VRP問題模擬A物流公司在該區(qū)域進行小區(qū)與社區(qū)間的快遞配送路徑規(guī)劃問題，規(guī)劃最短路徑配送路線，以達到降低車輛油耗、配送等待時間最短的目的。為優(yōu)化處理信息，減少其他路徑規(guī)劃影響因素，故忽略在配送途中出現(xiàn)的天氣、環(huán)境、其他車輛等影響因素。各小區(qū)與社區(qū)之間距離以直線距離為實驗?zāi)M距離。通過信息采集，選取小區(qū)與社區(qū)數(shù)共計10處。

對采集信息區(qū)測量實際直線距離，并繪制直線路徑，選取一點為派送起始點，為使計算精確，對該調(diào)查社區(qū)點進行坐標化處理，以公主府公園坐標為原點(0，0)，并對其他坐標賦值，見表1。

表1 小區(qū)點位具體坐標與賦值表

2.2 MATLAB仿真模擬

2.2.1 實驗坐標與參數(shù)設(shè)置

①實驗坐標。

圖3 在MATLAB中的模擬坐標點

②參數(shù)設(shè)置。

表2 參數(shù)設(shè)置表

2.2.2 實驗結(jié)果

通過蟻群算法求解模型在MATLAB中運算得出不同迭代次數(shù)中所獲的求解結(jié)果。注：這些結(jié)果都是在迭代中選取的較優(yōu)解，由于蟻群算法本身就是一種隨機搜索算法，每次實驗都會產(chǎn)生不同的解，所以選取的解都是隨機的。但是，通過多次的實驗與迭代次數(shù)可以看到隨機值的趨勢。

2.3 實驗結(jié)果分析

通過不同迭代次數(shù)的運輸發(fā)現(xiàn)最短路徑有多種選擇方式，在實際配送路徑中也應(yīng)該考慮實時狀況選擇合適的配送路線。

①實驗比照。

表3 各迭代次數(shù)對照表

圖4 各迭代次數(shù)中的車輛路徑最優(yōu)解

②分析對比。

通過實驗數(shù)據(jù)的驗證對比，能夠更加清晰、直觀地看到不同迭代后的最短路徑與最短長度。綜合所有結(jié)果發(fā)現(xiàn)，迭代次數(shù)越多，長度越短，得到的較優(yōu)解也越佳，在經(jīng)過更多的迭代后且在迭代結(jié)果相同時會得出最優(yōu)解，在相同解中，路徑規(guī)劃也有不同，更加符合蟻群算法的隨機性，在選擇過程中也應(yīng)該落實現(xiàn)實情況。在不同迭代次數(shù)的解中，每種解也構(gòu)造了不同的審美視角，在解決VRP問題中，實現(xiàn)快速求解路徑也應(yīng)當(dāng)實現(xiàn)在配送途徑中。

3 結(jié)論

本文引述當(dāng)前物流的配送問題以VRP為研究方向，在旅行商問題的基礎(chǔ)思想上運用VRP實現(xiàn)方法進行可行性研究，利用蟻群算法驗證呼和浩特新城區(qū)配送路徑可行性，與常規(guī)方法相比該方法具備較好地路徑規(guī)劃方案的最短路徑以及運算時間短的特點，在配送中能較好的節(jié)省成本和時間。通過驗證，在相同最短路徑規(guī)劃中會出現(xiàn)不同規(guī)劃路徑，配送者可結(jié)合配送出發(fā)點、途中具體情況，如出現(xiàn)路段維修、交通堵塞、天氣狀況等其他情況進行合理選擇。車輛路徑規(guī)劃不僅僅是物流領(lǐng)域，還可以拓展到其他領(lǐng)域中，可進行城市交通的優(yōu)化與升級，對于生產(chǎn)企業(yè)中的選址建廠問題也可廣泛應(yīng)用。