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

□ 文宗川，王 慧

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

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

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

1 蟻群算法求解模型

1.1 蟻群算法原理

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

圖1 不同時(shí)間段的信息素濃度對(duì)螞蟻選擇路徑的影響

1.2 蟻群算法路徑運(yùn)輸模型

(1)

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

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

(2)

(3)

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

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

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

(4)

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

(5)

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

(6)

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

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

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

2.1 在呼和浩特市A物流公司車(chē)輛派送點(diǎn)的地理信息采集與處理

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

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

表1 小區(qū)點(diǎn)位具體坐標(biāo)與賦值表

2.2 MATLAB仿真模擬

2.2.1 實(shí)驗(yàn)坐標(biāo)與參數(shù)設(shè)置

①實(shí)驗(yàn)坐標(biāo)。

圖3 在MATLAB中的模擬坐標(biāo)點(diǎn)

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

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

2.2.2 實(shí)驗(yàn)結(jié)果

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

2.3 實(shí)驗(yàn)結(jié)果分析

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

①實(shí)驗(yàn)比照。

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

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

②分析對(duì)比。

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

3 結(jié)論

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