基于聚類蟻群算法的物流最優路徑

馬 寧

(華北水利水電大學公共管理學院， 鄭州 450046)

物流是商品從生產者轉移到消費者的過程中最重要的一環，尤其是現今網購的日漸發達，物流也隨之變得越來越重要。其中物流配送的最優路徑問題，對于提升整個物流運輸水平尤為關鍵[1]。一個科學的物流配送路徑，不僅能夠使運輸的效率得到大大的提高，還要能夠降低對物流運輸資源的消耗。

關于物流最優路徑的求解問題，目前，眾多學者對其進行了研究。蟻群算法[2-6]作為一種仿生類算法，已經廣泛應用在許多尋找最優解的問題上。隨后研究人員Dorigo基于蟻群算法研究了旅行商分配[7]和車間調度[8]問題的最優解。Stutzle[9]提出的MMAS(max-min ant system)以及Gambardella等[10]提出的HAS(hybrid ant system)，都在一定程度上提高了蟻群算法的檢索效率。Juliandri等[11]通過整數規劃來求解最優路線集。Masutti等[12]使用蜜蜂啟發方式來求解最優路徑。Akhand等[13]通過旅行商分配問題，尋找路徑的最優解。Sarwonno等[14]對蟻群算法的全過程進行了分析。以上這些研究雖然對算法的性能有一定的提升，但它們都是一種“盡力而為”的算法，并沒有結合物流運輸的實際情況，比如用戶對于送達時間的要求以及物流運輸資源的有限性。

本文在聚類蟻群算法的基礎上加入了用戶收貨時間和運輸車空置率的影響因素，對原始算法進行優化。

1 蟻群算法的基本原理

蟻群算法是一種仿生學算法，其已經被廣泛應用在組合最優解的問題中。其主要分為基于路徑最優解的方式和基于聚類的方式。

1.1 基于路徑最優解的蟻群算法

最優路徑問題的最典型案例就是，地點i到地點j的最短路徑尋找。假設螞蟻數量為m，那么信息要素更新和轉移概率計算的方法為

τij(t+1)=ρτij(t)+Δτij

(1)

(2)

最優尋路就是每一只螞蟻在經過每一條路徑時都留下信息要素，而后面經過的螞蟻根據信息要素的大小選擇路徑。經過數次的迭代以后，就可以得到最優的路徑。

1.2 基于聚類的蟻群算法

該算法一個最典型的示例就是：一個系統中有多個節點，每個節點都放置多種不同類的物品，一個螞蟻在隨機運動中遇到某個節點時，會拿起數量最對的種類的物品，而放下數量最少的種類的物品。簡單來說就是在某點放下物品的概率與該點該物品種類的數量多少成反比。拿起和放下物品的概率為

(3)

(4)

式中：Pp為拿起的概率；Pd為放下的概率。這種方式能夠在保證總體物品種類和數量不變的情況下，完成物品的聚類。

1.3 最優路徑問題的算法選擇

一個典型的物流最優路徑問題如圖1所示。

A為貨物配送中心；1～9為客戶地址圖1 物流配送示意圖Fig.1 Logistics distribution schematic map

物流配送車需要從A點出發，并將貨物送給1～9的客戶；不同客戶還存在時間要求；對于配送公司而言，還有配送車空置率和成本等要求。那么，在滿足上述約束的前提下，如何安排最優運輸次序，如何選擇最優運送路徑，這是一個典型的物流最優路徑問題，本文采用基于聚類的蟻群算法，對這一問題進行了探索。

2 物流配送的模型建立

2.1 參數與路徑模型

假設客戶的地理方位和送貨需求都是已知確定的。貨物集散中心的運輸車輛為m，客戶數量為n，客戶集合為N，貨物集散中心可以被賦值為1，網絡中頂點的集合設為D(包括貨物集散中心和客戶集合)，運輸車集合為K。N、D、K分別為

N={2,3,…,n}

(5)

D={1}∪N

(6)

K={1,2,…,m}

(7)

貨物集散中心的運輸車出發時間為T0，客戶i收到貨物的時間為Ti，客戶i的收貨時間窗口為(ETi，LTi)，客戶要求貨物的運送量為Q，運輸車k所服務的客戶集合為Sk，運輸車在客戶i處的停留時間為Wi，運輸車在客戶i處進行服務的時間為Si，客戶i和客戶j之間的距離為dij。

由此，可以建立運輸車的路徑模型。

變量的決策為

(8)

(9)

模型的數學表示為

(10)

(11)

(12)

(13)

(14)

(15)

(16)

ETi≤Ti+Wi≤LTi, ?i∈N

(17)

X=Xik∈D

(18)

式(10)為路徑的約束(盡量最短)；式(11)為運輸車承載量的約束(不超過規定承載量)；式(12)為客戶的配送和服務次數的約束(為1次)；式(13)、式(15)為運輸車路徑的約束(不能形成回路且必須返回貨物集散中心)；式(14)為運送順序的約束(從客戶i到客戶j)；式(16)為貨物送達時間；公式(17)為貨物送達時間的約束(必須在客戶要求的時間窗口內)；式(18)為路徑約束(所有道路必須是連通的)。

2.2 算法模型

當運輸車輛在地點i為某位客戶完成服務以后，那么可以按照如下規則來選擇下一個服務的客戶j。

(19)

式(19)中：S為可以選擇的下一個客戶，U=allow為還需要被服務的客戶的集合，在客戶集合中選擇距離最短的客戶。這樣運輸車輛在每次送貨時，都在未被服務的客戶中選擇下一個服務對象，這樣一直迭代循環到最短路徑。下一個服務客戶的選擇概率Pijk可以表示為

(20)

式(20)中：allowk為車輛k在t時刻完成一個客戶的服務后，可選擇的下一個服務客戶的集合；τij(t)為t時刻，客戶i到客戶j的信息要素(初始值為常量)；ηij(t)為t時刻，客戶i到客戶j的可見度；α和β為信息素和啟發因子對路徑選擇的影響程度。

當下一個服務客戶的集合為空時，就表示完成了一次迭代循環。下一輪迭代循環的起始時刻為t+1，根據上一輪循環殘留的信息要素，對信息要素進行更新。其更新方式為

τij(t+1)=ρτij(t)+Δτij(t,t+1)

(21)

(22)

(23)

式中：ρ為信息要素的持久程度，其值為0～1；m為運輸車輛；式(22)為t時刻到t+1時刻，路徑i到j的信息要素增量；Q為一次迭代循環所釋放的信息要素總量；lk為一次迭代循環運輸車k所走過的路徑長度。

算法的具體步驟如下。

(1)初始化每一個參數，確定貨物集散中心到每一個客戶之間路徑的距離，和客戶到客戶之間路徑的距離。

(2)運輸車從貨物中心出發開始配送，即i=1；在滿足式(17)的前提下，完成對客戶j的服務；按照規則尋找下一個需要服務的客戶，重復服務過程；經過多次的尋找，完成對系統內所有客戶的服務；最后返回貨物集散中心。

(3)通過式(20)，從上一步中路徑集合尋找最短路徑的下一位客戶，并根據該客戶的需求重新分配運輸車。

(4)根據式(12)更新信息要素，并回到步驟(2)重新開始；直到達到規定的最大迭代循環次數。

3 案例應用

通過一個理想化案例來證實上述模型的可行性。某物流貨物集散中心總共有4輛運輸車；車輛的平均時速均為50 km/h；每輛車最大運輸量為2 500 kg；每輛車百公里耗油均為11 L；貨物集散中心編號為1，客戶編號為2～15；運輸車的最早出發時間為早晨7:30；每個客戶的服務時間均相同。每個客戶對于送貨時間要求、貨物數量要求、以及地理位置坐標如表1所示。

表1 客戶信息

假設運輸車在貨物運輸過程中，處于不會出現意外情況、道路距離即為兩點間的直線距離、并且交通狀況暢通無阻的理想條件下。為了更方便地看出1～16的各個節點之間的距離，將其計算出來，并用表2來統計。

在使用傳統的蟻群算法進行最優路徑的求解時，都會是一種“盡力快速到達”的方式；即不考慮資源的浪費，以求在最短的時間內完成貨物的運輸任務。采用傳統的蟻群算法得到的運輸車路線、空載率、運輸量、車輛行駛里程等數據如表3所示。

由表3的數據可知，貨物集散中心的四輛運輸車全部使用，分為四條線路，在客戶要求的時間內，完成所有客戶的貨物運送任務。這種路徑安排方式的成本(運輸車行駛里程482.4 km)，和運輸車浪費情況(空載率)都可以從表3中得出。

表2 距離信息

表3 原始算法貨運數據

考慮客戶時間窗口之后，得到的運輸車路線、空載率、運輸量、車輛行駛里程等數據如表4所示。

由表4的數據可知，貨物集散中心的四輛運輸車只使用了三輛，分為三條線路，在客戶要求的時間內，完成所有客戶的貨物運送任務。這種路徑安排方式的成本(運輸車行駛里程416.2 km)，和運輸車浪費情況(空載率)都可以從表4中得出。

兩種算法對比之下可以發現，雖然傳統算法在最短的時間內將貨物送達，但這在實際中并不是一個硬性的要求，且改進后的算法依然可以滿足客戶對于送貨時間的要求。在成本節約方面，改進算法減少了車輛總行駛里程66.4 km；在車輛分配方面，改進算法節約了一輛運輸車的使用；在空置率方面，改進算法極大地減低了運輸車的空置率。

表4 改進算法貨運數據

4 結論

綜上所述，研究了物流配送的最優路徑問題，并且建立了配送的模型；以蟻群算法為基礎，加入客戶收貨時間要求和運輸車輛空置率這兩大要素，對原始算法進行了優化和提高，使其可以更加契合實際應用情況。最終通過對模型案例的分析可以說明，改進后的算法有效地降低了物流運輸的成本、節約了物流運輸的資源、降低了運輸車的空置率。使物流過程向著低成本和高效率的方向又前進了一步。