王 迪 金 輝

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

0 引 言

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

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

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

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

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

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

2 快遞末端配送數(shù)學(xué)模型

2.1 模型假設(shè)

為了保證快遞配送能夠在客戶要求的時(shí)間窗內(nèi)送達(dá)，建立基于客戶滿意度的快遞末端配送路徑優(yōu)化模型，就是要將能否滿足客戶時(shí)間窗要求作為評價(jià)客戶滿意度的主要指標(biāo)。如果快遞員能夠?qū)⒖旒诳蛻羲蟮臅r(shí)間窗內(nèi)送達(dá)時(shí)，則客戶的滿意度為1，否則為0[20]。

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

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

(2) 不考慮配送車輛在服務(wù)每個(gè)客戶點(diǎn)時(shí)的等待時(shí)間。

(3) 快遞員在進(jìn)行快遞配送時(shí)，能保證每個(gè)客戶的快件都在配送之列，不作其他特殊區(qū)別。

模型參數(shù)設(shè)置：

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

決策變量：

2.2 模型構(gòu)建

對于以上模型假設(shè)，建立如下的目標(biāo)函數(shù)：

(1)

(2)

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

約束條件為：

(3)

(4)

(5)

(6)

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

(7)

(8)

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

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

3.1 鯨魚優(yōu)化算法

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

圖1 泡泡網(wǎng)捕食法

3.1.1搜索獵物

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

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

(9)

D=|C·Xrand-X|

(10)

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

A=2a·r-a

(11)

C=2·r

(12)

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

a=2-2t/M

(13)

式中：M為最大迭代次數(shù)。

3.1.2泡網(wǎng)攻擊

在此階段，座頭鯨將其他鯨魚引向獵物的位置。 因此，其余鯨魚靠近領(lǐng)頭鯨魚并包圍獵物。通過以下方程對這種環(huán)繞現(xiàn)象進(jìn)行數(shù)學(xué)建模：

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

(14)

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

(15)

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

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

(16)

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

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

(17)

式中：P是[0,1]中的隨機(jī)數(shù)。

3.2 貪婪的鯨魚優(yōu)化算法

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

圖2 初始節(jié)點(diǎn)矩陣X

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

(18)

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

(19)

(20)

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

圖3 貪婪交換

3.3 算法求解步驟與流程

圖4為GWOA的求解流程。

圖4 GWOA算法求解流程圖

具體操作步驟如下：

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

步驟2如果當(dāng)前迭代次數(shù)≤最大迭代次數(shù)，則繼續(xù)步驟3，否則輸出當(dāng)前最優(yōu)路線。

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

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

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

步驟6更新當(dāng)前鯨魚位置，直至當(dāng)前迭代次數(shù)滿足算法最大迭代次數(shù)，輸出結(jié)果最優(yōu)路線。

4 實(shí)例研究

4.1 數(shù)據(jù)來源

通過對錦州市多家快遞公司的快遞配送情況進(jìn)行調(diào)研，發(fā)現(xiàn)客戶滿意度和配送效率不盡理想，各個(gè)快遞公司的配送情況和服務(wù)質(zhì)量不盡相同，因此本文選擇了其中某一快遞公司進(jìn)行研究。本文數(shù)據(jù)的來源是根據(jù)實(shí)地調(diào)研所得，主要以A快遞公司某一快遞員在一天內(nèi)所進(jìn)行快遞配送的34個(gè)客戶點(diǎn)作為研究目標(biāo)。

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

表1 客戶點(diǎn)坐標(biāo)、服務(wù)時(shí)間及時(shí)間窗

續(xù)表1

4.2 運(yùn)行結(jié)果與分析

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

(a) ACO優(yōu)化路徑 (b) WOA優(yōu)化路徑

(c) GA優(yōu)化路徑 (d) GWOA優(yōu)化路徑

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

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

表2 運(yùn)行結(jié)果對比表

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

5 結(jié) 語

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