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

□ 文宗川，王 慧

(1.內蒙古工業大學 經濟管理學院,內蒙古 呼和浩特 010051；2.內蒙古工業大學 人文學院,內蒙古 呼和浩特 010081;3.內蒙古創新方法研究中心,內蒙古 呼和浩特 010051)

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

本文以呼和浩特市新城區A物流公司的派送網點為例，基于蟻群算法對車輛路徑問題進行優化，針對不同配送路線的車輛路徑問題構造相應數學模型并進行MATLAB仿真模擬。

1 蟻群算法求解模型

1.1 蟻群算法原理

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

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

1.2 蟻群算法路徑運輸模型

(1)

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

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

(2)

(3)

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

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

蟻群循環系統(Ant-cycleSystem)模型信息素增量的計算公式

(4)

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

(5)

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

(6)

基本蟻群算法實現流程如圖2。

圖2 蟻群算法實現流程圖

2 仿真驗證與結果分析

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

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

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

表1 小區點位具體坐標與賦值表

2.2 MATLAB仿真模擬

2.2.1 實驗坐標與參數設置

①實驗坐標。

圖3 在MATLAB中的模擬坐標點

②參數設置。

表2 參數設置表

2.2.2 實驗結果

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

2.3 實驗結果分析

通過不同迭代次數的運輸發現最短路徑有多種選擇方式，在實際配送路徑中也應該考慮實時狀況選擇合適的配送路線。

①實驗比照。

表3 各迭代次數對照表

圖4 各迭代次數中的車輛路徑最優解

②分析對比。

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

3 結論

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