貪婪鯨魚優化算法求解帶時間窗的快遞末端配送路徑問題

王 迪 金 輝

(遼寧工業大學汽車與交通工程學院 遼寧 錦州 121001)

0 引 言

快遞行業迎來井噴式增長，但快遞末端配送效率卻依然低效和滯后，不能有效地滿足顧客的特殊要求，既浪費了配送成本又降低了顧客的滿意度。在快遞末端配送路徑過程中，行駛距離的浪費和不必要的等待時間是造成快遞配送效率低下和顧客滿意度降低的主要原因之一。因此，對快遞末端的配送路徑進行優化研究是非常有必要的，而帶有時間窗約束的快遞末端配送路徑問題(VRPTW)則是研究的重點內容。解決VRP的常用方法有確定性算法[1](如動態規劃、分支定界算法等)和隨機算法[2](如GA[3]、ACO[4]、SAA[5]、TS[6]等)。

鯨魚優化算法(Whale Optimization Algorithm，WOA)是Mirjalili等[7]于2016年提出的一種基于座頭鯨魚狩獵方法的元啟發式算法。它成功應用于各種復雜的離散優化問題，如資源調度問題[8]、建筑工地的工作流程規劃[9]、選址與路徑規劃[10]和神經網絡訓練[11]等。在算法改進和應用方面，閆旭等[12]提出了混合隨機量子鯨魚優化算法求解TSP問題；滕德云等[13]把鯨魚優化算法與拓撲結構相結合地改進鯨魚優化算法，用來求解多目標無功優化調度問題；涂春梅等[14]提出了混沌反饋自適應鯨魚優化算法；劉竹松等[15]提出了正余混沌雙弦鯨魚優化算法(CSCWOA)；鐘明輝等[16]提出了一種隨機調整控制參數的高效的鯨魚優化算法(EWOA)；褚鼎立等[17]提出了基于自適應權重和模擬退火的鯨魚優化算法。

綜上所述，WOA可以用來求解連續性優化問題。因此，本文通過對錦州市多家快遞公司的快遞配送情況進行調研，結果發現客戶滿意度和配送效率不盡理想，主要原因在于每個客戶點在接受快件的時間段不同，造成快遞員的來回奔波和不必要的時間等待，不僅大大降低了快遞員配送效率，同時也使客戶滿意度大打折扣。因此，本文將貪婪交換機制引入到鯨魚優化算法中，通過建立基于貪婪鯨魚優化算法(GWOA)的帶時間窗的快遞末端配送路徑模型，并對實例進行求解，結果證明GWOA具有更好的收斂速度和更佳的局部尋優能力。

1 快遞末端配送路徑問題的描述

快遞末端配送路徑問題可以描述為：快遞員從配送中心(快遞配送網點)出發，沿特定路線將客戶的商品送到每個客戶點手中，然后需要在固定時間前返回到出發點(快遞配送網點)。在此期間快遞員可以根據自己的經驗選擇距離較短、節約時間的路線來完成快遞的配送，也可以根據某些客戶的特殊需求，優先給他們進行配送，前提是保證所有的客戶點在指定時間前都被服務到并且只能被服務一次。因此應合理規劃快遞末端配送路徑，在滿足客戶時間窗、客戶需求、配送車輛載重限制、快遞車輛最大行駛距離等約束條件下，實現配送時間最短、配送路線距離最短、配送成本最低、客戶滿意度最大等。

用圖論的角度表示，快遞末端配送路徑問題可以用一個有向完備圖G=(V，E)來描述，其中有配送需求的所有的客戶點集合可以用V={1,2,…,n}來表示，E={(i,j)|i,j∈V,i≠j}表示顧客與顧客之間邊的集合，K={1,2,…,M}表示配送車輛的集合。

2 快遞末端配送數學模型

2.1 模型假設

為了保證快遞配送能夠在客戶要求的時間窗內送達，建立基于客戶滿意度的快遞末端配送路徑優化模型，就是要將能否滿足客戶時間窗要求作為評價客戶滿意度的主要指標。如果快遞員能夠將快件在客戶所要求的時間窗內送達時，則客戶的滿意度為1，否則為0[20]。

為了便于下面的實例分析，在構建模型時，只考慮一個快遞員(即一輛配送車輛)的快遞末端配送路徑的優化研究。即快遞員需要用一輛配送車輛完成對所有客戶點的快遞配送，從而完成一個閉合的配送路徑圖。假設如下：

(1) 快遞員用于配送快遞的配送車輛為同一標配，即統一為電動三輪車，并且車輛在配送過程中的行駛速度固定，同時不考慮車輛的容量限制。

(2) 不考慮配送車輛在服務每個客戶點時的等待時間。

(3) 快遞員在進行快遞配送時，能保證每個客戶的快件都在配送之列，不作其他特殊區別。

模型參數設置：

顧客點集合N={1，2，…，n}；客戶i和客戶j之間的距離用dij表示；c表示快遞電動三輪車行駛單位距離的平均費用；v表示快遞電動三輪車輛在進行快遞配送時的平均行駛速度；客戶i到客戶j的距離時間用tij表示；客戶i要求的時間窗用[Ei,Li]表示；Tmax為快遞員返回到配送網點的最晚時間；tsi表示客戶i接受快遞的服務時間；Ati表示快遞員到達客戶i的時間。

決策變量：

2.2 模型構建

對于以上模型假設，建立如下的目標函數：

(1)

(2)

式(1)是第一目標函數，表示的是在配送過程中成本費用最??；式(2)為第二目標函數，表示的是在配送過程中能夠滿足的最大客戶滿意度值。

約束條件為：

(3)

(4)

(5)

(6)

Ati=At(i-1)+ts(i-1)+dij/v

(7)

(8)

約束條件式(3)-式(5)是為了保證每個客戶點只能被快遞車輛服務一次；式(6)表示快遞車輛在完成配送任務后返回配送中心；式(7)表示快遞員到達客戶點i的時刻；式(8)表示配送車輛需要在最晚時間之前返回到快遞網點。

3 鯨魚優化算法(WOA)及求解步驟

3.1 鯨魚優化算法

WOA是通過模仿座頭鯨的智能和壯觀的泡泡網喂養技術而形成的一種新型元啟發式優化算法，如圖1所示，其捕食方式稱為泡泡網捕食方法[7]。座頭鯨成群狩獵，并在海洋中捕食獵物，即小魚或磷蝦。一旦獵物被定位，鯨魚會下潛約12米并開始在其周圍形成螺旋氣泡網。隨著鯨魚的向上移動，氣泡的螺旋形狀網絡限制了魚類向一個共同點的移動。最后，鯨魚通過襲擊這個位置來獲得獵物。

圖1 泡泡網捕食法

3.1.1搜索獵物

鯨魚在海洋(n維搜索空間)中搜索獵物，并隨機行走，而無須跟隨任何頭鯨。在該階段其數學模型表示如下：

X(t+1)=Xrand-A·D

(9)

D=|C·Xrand-X|

(10)

式中：X是大小為1×n的位置矢量；Xrand是從當前群體中隨機選擇的位置矢量；t表示的是當前迭代次數；A和C為系數向量，定義如下：

A=2a·r-a

(11)

C=2·r

(12)

式中：r是一個均勻分布的隨機矢量，其取值范圍為[0，1]。A的值控制著鯨魚的運動，當|A|≥1時鯨魚能夠獨立地探索和搜索空間；當|A|<1時他們利用最佳解決方案進行開發探索。式(11)中a為控制參數，它的值隨著迭代次數的增加在2到0之間線性遞減變化。

a=2-2t/M

(13)

式中：M為最大迭代次數。

3.1.2泡網攻擊

在此階段，座頭鯨將其他鯨魚引向獵物的位置。 因此，其余鯨魚靠近領頭鯨魚并包圍獵物。通過以下方程對這種環繞現象進行數學建模：

X(t+1)=X*(t)-A·D

(14)

D=|C·X*(t)-X(t)|

(15)

式中：X*(t)是WOA當前迭代中的最佳位置向量；A的大小取決于a(式(11))，它在迭代過程中從2線性減小到0(式(13))。這模擬了成群狩獵時鯨魚的收縮行為。此外，這位領導者還創建了一個螺旋形的氣泡墻，其他鯨魚以食物為攻擊對象，其建模如下：

X(t+1)=D′·ebl·cos(2πl)+X*(t)

(16)

式中：D′=|X*-X(t)|；b是常數；l是[-1，1]之間的均勻分布的隨機數。

座頭鯨在包圍圈里收縮距離時，會在圈里沿著螺旋路徑方向不斷向獵物移動，為了模擬這種同步過程，WOA假設鯨魚在進行狩獵的過程中選擇兩種策略的概率相同，其閾值為0.5，表達式可寫為：

(17)

式中：P是[0,1]中的隨機數。

3.2 貪婪的鯨魚優化算法

本文使用元啟發式方法解決復雜的VRP問題，需要對節點進行排列。因此，生成了基于節點隨機排列的初始解矩陣(X)如圖2所示。

圖2 初始節點矩陣X

式中：Xi,j指的是第i條鯨魚所訪問的第j個節點，使用式(18)更新解矩陣的元素。

(18)

式中：i從1到m變化，j從1到n變化，k是要使用式(19)-式(20)進行交換和評估的節點。

(19)

(20)

式(19)和式(20)分別是式(9)和式(16)的離散形式。搜索區域的離散化增加了WOA在求解過程中陷入局部最小值的概率，并通過引入貪婪交換技術來克服該問題。貪婪選擇有助于減少生成以及低效路線的路徑計算。在j=3和k=5時貪婪交換對Xi的影響如圖3所示。如果交換前j的鄰居所覆蓋的距離(圖3(b)中的10+2=12)大于交換后的距離(圖3(c)中7+2=9)，算法更新Xi(圖3(d))交換導致相鄰距離減小，因此路線的總長度減小。

圖3 貪婪交換

3.3 算法求解步驟與流程

圖4為GWOA的求解流程。

圖4 GWOA算法求解流程圖

具體操作步驟如下：

步驟1隨機初始化生成鯨魚路線Xi，其中，i=1,2,…,m。

步驟2如果當前迭代次數≤最大迭代次數，則繼續步驟3，否則輸出當前最優路線。

步驟3計算所有鯨魚個體Xi之間的距離，尋找距離最短的路線為當前最佳行駛路線。同時對于每一個搜索代理，更新參數a、A、C、l和p。

步驟4當p<0. 5時，若A<1，利用式(20)計算k值，式(18)更新當前路線Xi(即鯨群個體的空間位置)；若A≥1，利用式(19)計算k值，式(18)更新當前路線Xi。

步驟5當p≥0. 5 時，利用式(20)計算k值，式(18)更新當前路線Xi。

步驟6更新當前鯨魚位置，直至當前迭代次數滿足算法最大迭代次數，輸出結果最優路線。

4 實例研究

4.1 數據來源

通過對錦州市多家快遞公司的快遞配送情況進行調研，發現客戶滿意度和配送效率不盡理想，各個快遞公司的配送情況和服務質量不盡相同，因此本文選擇了其中某一快遞公司進行研究。本文數據的來源是根據實地調研所得，主要以A快遞公司某一快遞員在一天內所進行快遞配送的34個客戶點作為研究目標。

配送時間從9點開始，18點結束，因此將配送中心的配送服務時間設置為0到9，即時間窗為[0, 9]，其服務時間為0。其中：行駛單位距離的平均費用為c=3元/km；快遞員在進行快遞配送時的平均行駛速度為v=10 km/h；編號“1”為配送中心，編號“2”到“35”為配送客戶點。具體情況如表1所示。

表1 客戶點坐標、服務時間及時間窗

續表1

4.2 運行結果與分析

利用MATLAB對GWOA算法進行編程，并對實例進行運行求解。為保證其實驗結果能夠和其他算法求得的結果合理公平地進行對比，所有算法都設置相同的參數值，具體為：M=50，N=40，b=1。圖5為求解最優路線對比圖，圖6為迭代次數對比圖，表2為運行結果對比表。

(a) ACO優化路徑 (b) WOA優化路徑

(c) GA優化路徑 (d) GWOA優化路徑

(a) ACO迭代 (b) WOA迭代

(c) GA迭代 (d) GWOA迭代

表2 運行結果對比表

通過對比發現GWOA求得的最優路徑、最短距離、最低行駛費用和最高滿意度值皆優于GA、ACO和WOA，說明將貪婪交換技術引入到WOA中十分有效。在最短距離和平均距離方面，GWOA求得的兩者之間的差距比較穩定，并且差值也比較小一些，說明GWOA在求最優值和平均值方面比較穩定。在收斂性方面，GWOA能在較少次數內收斂到最短距離，和其他算法相比，說明貪婪交換技術與WOA的結合在一定程度方面改進了算法的收斂速度。

5 結 語

針對快遞末端配送路徑優化問題，本文提出了WOA的改進方法——貪婪交換方法與WOA的結合，使其在求解快遞車輛路徑優化問題時具有改進的收斂特性。通過實例研究，并與基本的WOA、ACO和GA算法比較，結果表明，GWOA可以提供更加準確的結果，并且具有更好的收斂速度。因此，本文提出的改進算法也可以應用于其他離散的NP-hard問題。