基于蟻群算法的物流配送中車輛路徑優化問題研究

張 偉

（蘭州交通大學 機電技術研究所，甘肅 蘭州 730070）

ZHANG Wei

(Electromechanical Technology Research Institute of Lanzhou Jiaotong University,Lanzhou 730070,China)

0 引言

在經濟全球化的大趨勢下，物流行業也發生了一定的變化，已經從傳統的運輸服務行業逐漸向著綜合性物流系統型行業的模式發展。現階段，很多國家及地區都形成了較為完善的物流理念，擁有著成熟的物流技術，我國物流行業發展雖然緩慢，但是由于我國資源豐富，鐵路、公路等物流基礎設施建設比較完善，為物流行業發展提供了良好的環境，使得我國的物流行業齊頭并進，逐漸具備了與國外先進物流技術相媲美的實力。

現代化物流配送是市場經濟發展的要求，對促進大眾消費、優化資源配置等方面都具有較大的影響。物流配送方案的好壞，在很大程度上決定了物流配送的效率與成本，同時也影響著實現物流服務行業的附加價值。而物流配送車輛路徑優化問題，早在1959年就由Dantzig 及Ramser 提出，后來這一說法引起了物流科學、組合數學、應用數學、運籌學等學者、專家們的重視，成為組合優化領域的熱門話題。關于物流配送車輛路徑優化問題，定義為：對物流貨物裝卸點進行有效的組織，安排恰當的行車路徑，保證物流配送車輛能夠有序的通過這些裝卸點，并能夠在一定的交貨時間、貨物需求量、時間限制等約束條件下，盡可能實現用最少車輛、最少時間、最短行程完成物流配送任務。

在近幾十年的研究中，有關配送車輛路徑優化算法出現很多，包括精確算法、智能優化算法以及啟發算法等，其中精確算法在路徑優化中的應用計算復雜程度較高，具有一定的局限性；啟發式算法中包括SWeep 算法以及C-W 算法等，這些算法雖然具有速度快的優勢，但是如果客戶數量過多時，就會增加算法搜索的難度，不容易找到最優路徑；人工智能算法的出現，在一定程度上提高了路徑優化的效率，其中神經網絡算法、遺傳算法等都屬于人工智能算法中的一種。然而物流配送車輛路徑優化工作是一項復雜的大規模工作，有些算法在網絡結構、參數確定等方面還存在缺陷，不能同時滿足時間、成本、車輛等因素條件。

蟻群算法也屬于智能優化算法的一種，主要是利用正反饋并行機制，并根據螞蟻之間的相互協作在最短時間找到食物與巢穴的最短路徑現象確定的一種算法。蟻群算法具有求解速度快、并行性能力強等優勢，近年來在水運、鐵路、公路等領域都得到了廣泛的應用。本文也將蟻群算法應用到物流配送車輛路徑優化問題中，通過此原理建立數學模型，并通過模型找出路徑優化的最優解。

1 建立數學模型

在物流配送工作過程中，其實就是討論以什么樣的路徑進行運輸，也就是在已知客戶需求量以及車輛載重量的基礎上，探討怎樣以最短的時間、最少的成本，縮短配送路程。在尋找最短路徑過程中，還需要滿足以下幾個條件：第一，所有的物流配送車輛必須將配送中心作為起點和終點，完成一個配送的循環；第二，每輛配送車僅能為一條路線服務，并且每輛配送車僅能訪問一個客戶；第三，在配送路線上，客戶需求量不能超過車輛配送的載重量總和；第四，車輛的路線不能重復。

根據上述的幾個約束條件，在物流配送車輛路徑優化問題上，就是尋找最優路徑。我們可以將物流配送中心用v0表示，將配送地點用vi表示，用k 表示配送中心車輛數目的上限，用Q 表示配送車輛的載重。這樣就能將配送路徑優化數學模型表示為：

2 關于蟻群算法的相關理論

本文中所講的蟻群算法，屬于仿生優化算法中的一種，是一種新興的算法工具，主要是通過模仿螞蟻蟻群的行為，得出最優解。其實，蟻群算法主要是模仿螞蟻覓食的過程，將螞蟻覓食的路徑當做是物流配送車輛運輸的路徑，將螞蟻行動的錄像集合作為移動線路，并利用分布式協作以及正反饋機制，獲取最優解。這種算法魯棒性強，并且具有很快的求解速度，廣泛應用于二次分配、作業調度、旅行等領域，并具有良好的應用效果。

圖1 是蟻群路徑搜索過程圖：

如圖1 所示，用字母A 代表蟻巢，將食物源用字母F 表示，同時設置一個障礙物，用CD 表示。由于存在障礙物，螞蟻在覓食過程中必須穿過障礙物，穿過障礙物的路徑有多種，螞蟻會通過相互之間的合作機制、信息素更新機制等，選擇最短的路徑作為覓食路線。

3 基于蟻群算法的物流配送車輛路徑優化設計

在物流配送車輛路徑優化算法設計過程中，利用蟻群算法，主要包括確定蟻群數目、設定蟻群路徑選擇規則、信息素更新機制規則等幾個方面：

3.1 確定蟻群數目。假設一共有n 個客戶數，相應的蟻群中就具有m 個螞蟻數量，則螞蟻數量可以用下面的表達式表示：m其中在時間t 點，在客戶i 位置上，螞蟻的數量就表示為bi（t）。

3.2 蟻群路徑選擇規則。在物流配送車輛路徑優化設計過程中，基于蟻群算法，螞蟻（k）從一個客戶到下一個客戶中間轉移的過程中，需要考慮到下一個客戶路徑中信息素濃度、路徑總長度等問題。我們可以將允許訪問的客戶點用j 表示，將配送中心用o 表示，這樣就能將螞蟻從上一個客戶點到下一個客戶點轉移路徑的概率用相關的計算公式表示出來，具體表示為：

在上式中，權重系數用a、b 表示，而螞蟻從上一個客戶到下一個客戶所用的時間用tij表示，將信息啟發式因子用α 表示，而期望啟發式因子用β 表示。而兩個客戶之間路徑關聯啟發式信息值用ηij（t）表示，并且可以將ηij（t）定義為：ηij（t）=1/dij，其中，dij是兩個客戶自檢的距離。

3.3 信息素更新機制規則。利用蟻群算法過程中，為了對循環最優解進行充分的利用，并且保證盡快的找到最優解，需要在每次循環后，將每只螞蟻帶來的相關信息進行及時的更新，同時在信息素更新過程中還需要遵循一定的規則。如果將信息素揮發系數用ρ 表示，其中ρ 是0 到1 之間的一個隨機數值，將信息素殘留因子用1-ρ 表示；一次循環中路徑中增加的信息素可以用ΔTij表示，設ΔTij的初始值為0。那么就能夠將信息素更新操作的規則用以下兩個式子表示出來：

4 物流配送中車輛路徑優化實現

在物流配送車輛路徑優化問題求解方面，利用蟻群算法，主要是用人代替螞蟻來尋找物流客戶點，如果下一個客戶服務點中，車輛總載重量如果被超出，或者是兩者之間的距離比車輛一次行駛的最大距離遠，這需要配送車輛回到配送中心，同時也表示該配送車輛完成了這次的配送任務，該輛配送車就能夠進行下一個服務站點的任務，直到有一個客戶獲得了一次完整的服務為止，這就說明人工螞蟻完成了一次循環。在經過一個循環后，根據每一個人工螞蟻在循環過程中得到的信息，對路徑中的信息素增加量進行有效的計算，同時進行信息素更新操作，這樣重復的循環后，就會有大部分人工螞蟻找出相同的路徑，同時也會找到最短的路徑，這樣就完成了最優解的算法設計。本文將這個構成步驟整理為以下幾點：

第一步，將參數進行初始化設置，然后對有需求的客戶進行相關數據讀取，之后產生全局最初解。

第二步，在物流配送中心設置m 個人工螞蟻，將初始時間以及迭代次數都設置為0，同時進行蟻群禁忌表建立。

第三步，對于每一個人工螞蟻，需要從列表中查出其沒有到達過的節點，同時根據上文中提到的轉移概率的公式，通過詳細的計算、分析，為人工螞蟻選擇合理的下一個客戶服務點。

第四步，對兩個客戶服務點路徑中的貨運總量進行計算，如果路徑中的貨運總量比車輛最大載重量大，那么就直接進行下一個步驟；如果沒有超過，就能夠將該節點作為可行點，并跳轉到第六步中。

第五步，對客戶需求點等待的時間進行計算，如果符合時間窗的相關要求，就能在禁忌表中加入該點，同時計算兩個點之間的路徑費用、長度等，跳轉到第三步進行；否則就在可行點集合中加入該點，同時進入下一步。

第六步，統計車輛的數目，然后判斷可行點的集合，如果集合為空集，則直接進入下一個步驟。如果集合不是空集，則需要從集合中獲取沒有經過搜索的點，同時將時間最短的節點作為起點，跳回到第三步進行。

第七步，更新每一個人工螞蟻帶來的信息素增量。

第八步，搜索人工螞蟻路徑的最短值以及路徑的最短距離，同時計算最短路徑對應的費用，并及時的更新信息素。在循環開始時，對所有的人工螞蟻進行迅游，對人工螞蟻搜索過后的邊進行信息素更新，不然就進行本循環中找到的最優路徑。

第九步，對本次循環以及所有的路徑最優解進行比對，如果本次循環比全局最優解路徑更短，就將其作為最優解，同時更新最優解列表。

第十步，找到全局的最優解或者迭代次數達到上限，就表示該程序完成，否則就需要從第二步驟開始進行重復上述過程。

可以將本步驟用圖2 表示：

5 仿真實驗

假設一個物流配送中心一共有30 輛車，每輛車的載重量相等，都為12噸，同時向30 個服務客戶提供物流配送服務，客戶的坐標資料是已知的，每一個客戶的客戶需求量也是已知的。客戶資料如表1 所示。

采用專業的仿真計算機平臺，平臺主要為3.4GMHz 的CPU、4G 內存，Windows2007 操作系統，在VB6.0 語言環境下進行編程實現。用同時設置蟻群算法的相關參數，具體設置如表2 所示。

實驗結果如下：

當迭代達到283 次時，求出了路徑的最優解，并且最優路徑的長度通過計算得到為165。

同時，仿真實驗中還將蟻群算法與遺傳算法、模擬退火算法等進行了有效的對比，用每一種算法運行10 次，然后通過計算，對比結果的平均值，其中遺傳算法找出的最優路徑長度為183.2，整個過程花費了50 多秒，成功率為65%；模擬退火算法找出的最優路徑的長度為172.4，過程時間為42 秒，成功率為78%；本文中提到的算法，最優路徑長度為165，整個過程花費的時間為21 秒，成功率高達98%。這些數據說明了蟻群算法在物流配送車輛路徑優化中具有獨特的應用優勢，能夠在短時間找出最短路徑，是提高物流配送效率的有效方式。

6 總結

通過上述分析可知，物流配送中車輛路徑優化問題關系到物流配送的成本、效率等，關系到客戶的滿意度，是現階段物流行業關心的問題之一。本文提出了一種基于蟻群算法的物流配送中車輛路徑優化方式，基于蟻群算法的魯棒性、快速性等特點，短時間找出最短的配送路徑。并且通過仿真實驗證明了，本文提出的優化算法有效性極高，值得在物流行業中大范圍的使用與推廣。

表1

表2

[1]章兢，周泉.基于免疫克隆算法的物流配送車輛路徑優化研究[J].湖北大學學報，2012,28(2):114-115.

[2]亓霞，陳森發，黃鵾.基于免疫算法的物流配送車輛路徑優化問題研究[J].土木工程學報，2013,26(3):99-100.

[3]尚華艷.物流配送中車輛路徑問題研究[J].武漢理工大學，2013,14(4):63-64.

[4]荊海霞.物流配送中雙向運輸車輛路徑優化問題研究[J].武漢大學學報，2013,26(6):54-55.

[5]曹二保.物流配送車輛路徑問題模型及算法研究[J].湖南大學學報，2013,18(9):247-248.

[6]戴錫.車輛路線問題的二階段啟發式算法及其在現代物流配送中的應用[J].復旦大學學報，2013,28(7):511-512.

[7]元興.物流配送中心車輛路徑優化中的幾種算法研究[J].計算機仿真，2011,18(7):41-42.

[8]衛田，范文慧.基于NSGAⅡ的物流配送中車輛路徑問題研究[J].計算機集成制造系統，2013,28(3):110-111.

[9]鐘石泉.物流配送車輛路徑優化方法研究[J].天津大學學報，2011,18(8):45-46.

[10]肖健梅，黃有方，李軍軍.基于離散微粒群優化的物流配送車輛路徑問題[J].系統工程，2011,17(8):78-79.