□ 文宗川,王 慧
(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仿真模擬。
蟻群算法的基本原理可以通過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)
在式(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)流程圖
以內(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.1 實驗坐標與參數(shù)設(shè)置
①實驗坐標。
圖3 在MATLAB中的模擬坐標點
②參數(shù)設(shè)置。
表2 參數(shù)設(shè)置表
2.2.2 實驗結(jié)果
通過蟻群算法求解模型在MATLAB中運算得出不同迭代次數(shù)中所獲的求解結(jié)果。注:這些結(jié)果都是在迭代中選取的較優(yōu)解,由于蟻群算法本身就是一種隨機搜索算法,每次實驗都會產(chǎn)生不同的解,所以選取的解都是隨機的。但是,通過多次的實驗與迭代次數(shù)可以看到隨機值的趨勢。
通過不同迭代次數(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)在配送途徑中。
本文引述當(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)用。