混合烏鴉算法求解帶軟時間窗的車輛路徑問題

閆 龍，石小娟，唐 源

(山東工商學院 管理科學與工程學院，山東 煙臺 264005)

0 引 言

1987年Solomon將顧客的時間窗約束引入VRP中，提出了帶時間窗的車輛路徑問題(vehicle routing problem with time windows，VRPTW)，此后的研究中也衍生出多種VRP變體問題[1-3]。時間窗約束可分為軟時間窗約束與硬時間窗約束，軟時間窗約束指物品需盡可能在顧客指定的時間窗內(nèi)送達，否則將產(chǎn)生懲罰成本；硬時間窗約束規(guī)定若車輛無法在指定時間內(nèi)將貨物送達，則服務(wù)失敗。在實際生活中，食物、生活用品等物流配送都可歸結(jié)為帶軟時間窗的車輛路徑問題。目前關(guān)于VRPSTW的求解多采用啟發(fā)式算法，謝九勇等[4]研究了帶多軟時間窗的VRP，提出嵌套多鄰域結(jié)構(gòu)的禁忌搜索算法。夏揚坤等[5]采用改進禁忌搜索算法求解帶軟時間窗的超市配送問題。Xu等[6]構(gòu)建了帶軟時間窗的多目標綠色VRP模型，提出改進非支配排序遺傳算法。何美玲等[7]針對VRPSTW，設(shè)計了一種將變鄰域搜索算法與蟻群算法結(jié)合的混合算法。Xia等[8]采用改進禁忌搜索算法求解開放式VRPSTW。符卓等[9]考慮軟時間窗以及需求可依訂單拆分的現(xiàn)實情況，設(shè)計了一種改進禁忌搜索算法。

綜上可知，啟發(fā)式算法可有效求解VRPSTW。烏鴉搜索算法(CSA)作為一種新型智能啟發(fā)式算法，近年來已被成功應(yīng)用于求解車間調(diào)度[10]、0～1背包[11]等優(yōu)化問題，但將其用于求解VRP的研究較少。本文將烏鴉搜索算法與自適應(yīng)大規(guī)模鄰域搜索算法結(jié)合，提出一種混合烏鴉搜索算法(HCSA)，并將其應(yīng)用于求解VRPSTW。通過3組仿真對比實驗，驗證了HCSA的尋優(yōu)性能與有效性。

1 問題描述及模型構(gòu)建

1.1 帶軟時間窗的車輛路徑問題描述

(1)

圖1 折線軟時間窗

1.2 模型建立

綜上，以總成本最小為優(yōu)化目標，建立如下數(shù)學模型

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

2 混合烏鴉搜索算法

烏鴉搜索算法同粒子群算法、蟻群算法、灰狼算法等群智能優(yōu)化算法類似，通過模擬烏鴉尋找其隱藏食物的方式來搜尋求解問題的最優(yōu)解。本文根據(jù)車輛路徑問題的特征，采用基于顧客序列的整數(shù)編碼方式對烏鴉空間位置向量進行編碼，設(shè)計最短距離與最小懲罰兩種初始化規(guī)則，并根據(jù)烏鴉的智能搜索行為，對其感知概率進行改進，提出一種基于自適應(yīng)大規(guī)模鄰域搜索策略的混合烏鴉搜索算法(HCSA)。

2.1 編碼方式

本文采用基于顧客序列的整數(shù)編碼方式對烏鴉搜索食物時的空間位置向量進行編碼，假設(shè)顧客數(shù)目為10，則烏鴉i的空間位置向量即為10維的整數(shù)編碼序列，如烏鴉i的位置為Xi=[4 8 9 7 1 3 2 5 10 6]， 在滿足時間窗、載重量等約束條件的情況下可將其解碼為加入配送中心0的超路徑[13]向量Yi=[0 4 8 9 0 7 1 3 2 0 5 10 6 0]， 該向量即代表配送方案有3輛車，路徑分別為 [0 4 8 9 0]、 [0 7 1 3 2 0]、 [0 5 10 6 0]。

2.2 種群初始化

本文設(shè)計了最短距離與最小懲罰兩種初始化規(guī)則如下：

(1)最小距離成本初始化規(guī)則。車輛從配送中心出發(fā)，隨機選擇一個顧客a作為初始訪問顧客，根據(jù)時間窗、載重量等約束條件進行訪問可行性判斷，將符合訪問條件的顧客加入可訪問列表V，從V中選取距離a最近的顧客作為下一個訪問節(jié)點，直到所有顧客被訪問完畢。

(2)最小懲罰成本初始化規(guī)則。同上所述，隨機選擇顧客作為初始訪問顧客，依次計算該顧客可訪問列表V中每個顧客的時間窗懲罰成本，選擇懲罰成本最小的顧客作為下一個訪問顧客，直至所有顧客均被服務(wù)。

2.3 烏鴉搜索行為設(shè)計

烏鴉被認為是最聰明的鳥類，它們會把多余的食物藏在隱蔽的地點，并在幾個月之后還能回憶起食物的隱藏位置。此外，烏鴉還會觀察其它烏鴉隱藏食物的地點，并跟隨它們到達藏食之處，趁其它烏鴉離開之際偷走食物。假設(shè)烏鴉i決定跟隨烏鴉j接近其隱藏食物的位置，則可能會出兩種情況：①烏鴉j不知道被烏鴉i跟隨。在這種情況下，烏鴉i將會跟隨烏鴉j找到隱藏的食物。②烏鴉j知道被烏鴉i跟隨。則烏鴉j為了保護它的食物不被竊取，會進入搜索空間的另一個位置以欺騙烏鴉i。這兩種搜索行為可用式(11)來表示

(11)

(12)

其中，rj為[0，1]之間均勻分布的隨機數(shù)，APj，iter表示烏鴉j在iter代的感知概率。這兩種搜索行為分別對應(yīng)于確定性搜索和隨機性搜索兩種搜索模式，兩者之間的平衡主要由感知概率AP決定，較大的AP值可增加解的多樣性，原算法中的AP為一個固定值，本文引入自適應(yīng)調(diào)整策略，令AP=e-μ*iter/Mt， 該值會隨著迭代次數(shù)的增加而變大，使得算法在前期傾向于全局隨機性搜索，在后期則更可能采用局部確定性搜索，其中μ為自適應(yīng)調(diào)整系數(shù)，改進后的公式如式(12)所示。對應(yīng)于兩種搜索模式，本文設(shè)計了6種確定性鄰域搜索算子與4種隨機性鄰域搜索算子如下。

(1)確定性鄰域搜索算子：①最大成本節(jié)約移除算子。依次計算移除每個顧客點i(i=1，2，…，n) 可節(jié)約的距離成本與時間窗懲罰成本之和costi，優(yōu)先移除costi值最大的顧客點。②最大時間窗懲罰成本移除算子。依次計算每個顧客違反時間窗約束的懲罰成本，移除時間窗懲罰成本值較大的前Dr個顧客，Dr取顧客總數(shù)n的0.15～0.2[14]倍。③相似度移除算子。隨機選擇顧客點d作為參考節(jié)點，依次計算其它顧客與參考節(jié)點的相似度，優(yōu)先移除相似度最大的顧客。相似度由兩顧客是否在同一輛車、需求量、時間窗以及服務(wù)時間的相近程度決定，顧客j(j=1，2，…，n) 與d的相似度計算公式如下

(13)

(14)

④距離成本貪婪插入算子。隨機選擇顧客點c，判斷并找出其所有可插入位置，計算顧客c插入到每個位置增加的距離成本，將其插入到成本增量最小的位置。⑤時間窗懲罰成本貪婪插入算子。依次計算選定顧客點插入到每個可插入位置的時間窗懲罰成本增加量，選擇成本增量最小的位置插入。⑥全局最優(yōu)成本插入算子。判斷找出Dr個被移除顧客點的可插入位置，依次計算每個顧客點所有可插入位置的時間窗懲罰成本與距離成本增量之和，優(yōu)先選擇總成本增量最小的顧客點插入。

(2)隨機性鄰域搜索算子：①隨機移除算子。隨機選擇Dr個顧客點加入移除列表R。②隨機車輛移除算子。從當前解中隨機選擇一輛車，將整輛車的顧客作為移除點。③隨機遺憾準則插入算子。每次從遺憾值最大的前y個顧客中隨機選擇一個顧客作為移除節(jié)點，遺憾值計算規(guī)則如下：依次計算每個可插入位置的距離與時間窗成本總和的增量，遺憾值即為前x個總成本增量次優(yōu)值與最優(yōu)值的差值總和。④隨機貪婪成本插入算子。依次計算每個可插入位置的總成本(包括距離成本與時間窗懲罰成本)增量，從總成本增量最少的前r個位置中隨機選擇一個插入位置。

各算子權(quán)重自適應(yīng)更新策略如下：設(shè)各算子的初始權(quán)重一致，若新解Xnew優(yōu)于全局最優(yōu)解，則加5分；若Xnew優(yōu)于原解Xorign，加3分；否則不加分。設(shè)ωorign與ωnew分別代表算子原始權(quán)重與更新后的權(quán)重，θ為更新系數(shù)，ε為分數(shù)，π表示算子使用次數(shù)。權(quán)重更新公式如式(15)所示

(15)

2.4 算法流程

本文改進的混合烏鴉搜索算法(HCSA)的執(zhí)行流程如下。

算法：HCSA

輸入：最大迭代次數(shù)Mt，種群數(shù)量P，距離矩陣D，顧客位置矩陣L，車輛容量Q，顧客數(shù)目n，需求量d，時間窗TW，服務(wù)時間s。

輸出：最優(yōu)路徑Xb。

(1)根據(jù)2.2節(jié)生成初始種群Xj，j=1，2，…，n， 計算每只烏鴉的適應(yīng)度值f(Xj)，j=1，2，…，n， 初始化當前迭代次數(shù)t；

(2)whilet≤Mt

(3)foreach烏鴉

(4)Ifrand≤e-μ*iter/Mt

(5) 烏鴉采用確定性方法搜索食物，根據(jù)2.3節(jié)(1)ALNS(①～⑥)對食物所在空間進行自適應(yīng)大鄰域搜索；

(6)else

(7) 烏鴉隨機選擇空間中的位置，采用2.3節(jié)(2) ALNS(①～④)對解向量進行鄰域搜索；

(8)endif

(9) 計算經(jīng)過鄰域搜索后烏鴉的適應(yīng)度值f(Xnew)，iff(Xnew)

(10)endfor

(11)記錄每次迭代的最優(yōu)解，將其加入G(i)(i=1，2，…，n) 列表；

(12)更新烏鴉種群位置，t=t+1；

(13)根據(jù)G(i)列表判斷，當?shù)螖?shù)s_num>u時，停止迭代；

(14)endwhile

3 算例分析

3.1 參數(shù)設(shè)置

HCSA的各相關(guān)參數(shù)設(shè)置如下：最大迭代次數(shù)Mt=500，種群數(shù)量P=100，感知概率AP=0.5，各因素A、B、C、D的權(quán)重均設(shè)為0.25，y=n/2，x=3，r=n/2，更新系數(shù)θ=0.3，自適應(yīng)調(diào)整系數(shù)μ=4，終止迭代次數(shù)u=Mt/5；目標函數(shù)中的參數(shù)值與文獻[12]一致：違反時間窗懲罰系數(shù)p1=1，p2=0.5，p3=1.5，p4=2，顧客的容忍水平β=0.5，單位車輛固定啟用成本C1=60，單位距離成本C2=8。

3.2 實驗及結(jié)果分析

為驗證HCSA的性能，本文采用不同算例進行3組仿真對比實驗，所有實驗均應(yīng)用MATLAB編程進行求解。

(1)實驗1：本組實驗的算例選自文獻[7]，文獻[7]從Solomon 經(jīng)典算例包含的6種不同類型算例C1、R1、RC1、C2、R2、RC2中各選取一例，并考慮25、50、100這3種客戶規(guī)模。將本文提出的HCSA與何美玲等[7]提出的IACO進行對比分析，結(jié)果見表1～表3，其中GAP值表示HCSA與IACO相比較的優(yōu)化率，GAP=100%×(HCSA所得最優(yōu)解-IACO所得最優(yōu)解)/IACO所得最優(yōu)解。

表1 25個顧客點的算例求解結(jié)果

表2 50個顧客點的算例求解結(jié)果

表3 100個顧客點的算例求解結(jié)果

由上表可以看出，顧客規(guī)模為25、50的算例求解結(jié)果中，2/3的GAP為負值，顧客規(guī)模為100的求解結(jié)果中，所有GAP值均為負數(shù)；在所有算例中，5個算例的優(yōu)化率超過30%，C201(100個顧客)算例的優(yōu)化率則達到47.24%；綜上可知，HCSA的求解結(jié)果優(yōu)于IACO，具備較強的尋優(yōu)能力，可有效求解小、中及大規(guī)模算例。

(2)實驗2：采用文獻[12]提出的軟時間窗問題算例，將本文提出的HCSA與文獻[12]的超啟發(fā)式遺傳算法、文獻[15]的改進蟻群算法進行對比，結(jié)果見表4。GAP為HCSA與其它算法相對比的總成本優(yōu)化率，GAP=100%×(HCSA所得最優(yōu)解-各算法所得最優(yōu)解)/各算法所得最優(yōu)解， 3種算法求解的最優(yōu)配送路徑如圖2所示。

表4 不同算法結(jié)果對比

圖2 各算法最優(yōu)配送路徑

從表4可以看出，HCSA求得的總成本值最小，相比文獻[12]的超啟發(fā)式遺傳算法與文獻[15]的改進蟻群算法分別降低了13.58%、0.96%；HCSA所得方案相比于文獻[12]車輛數(shù)減少了一輛，車輛裝載率小幅提升；文獻[15]求得的車輛數(shù)少，車輛裝載率高，但每輛車的行駛距離過長，導致配送方案的距離成本過高，從而拉高了總成本值。綜合對比顯示，本文所提HCSA求得的配送方案更優(yōu)，算法優(yōu)化性能更強。

(3)實驗3：采用本文的模型與算法，選取Solomon算例中具有100個顧客點的時間窗較窄的C1型算例與時間窗較寬的C2型算例進行求解，求解結(jié)果見表5、表6，其中BKS代表已知最優(yōu)解。

由表5、表6可知，在C1、C2型共17個標準算例中，13個算例求得的車輛數(shù)與距離值與最優(yōu)解一致，算例C103、C104、C207、C208的車輛數(shù)達到最優(yōu)，且距離值與最優(yōu)解相差較小，由此驗證HCSA的優(yōu)化性能與有效性，表明其具備求解大規(guī)模VRP的可行性。

表5 C1型算例求解結(jié)果

表6 C2型算例求解結(jié)果

4 結(jié)束語

本文研究了帶軟時間窗的車輛路徑問題，首先考慮車輛固定啟用成本、距離成本以及時間窗懲罰成本建立以最小化總成本為目標的數(shù)學優(yōu)化模型。其次提出一種混合烏鴉搜索算法，設(shè)計兩種種群初始化規(guī)則，根據(jù)烏鴉在搜索食物時的不同搜索模式，對其感知概率進行自適應(yīng)調(diào)整，將烏鴉搜索算法與ALNS結(jié)合，設(shè)計了5種鄰域破壞算子與5種鄰域修復算子。最后，與已有文獻算例結(jié)果的對比顯示HCSA求得的總成本更低，求解結(jié)果更新了部分算例的最優(yōu)解；HCSA可求得部分Solomon標準算例的最優(yōu)解，驗證了算法在求解大規(guī)模VRP上的有效性。由此表明HCSA可有效求解VRPSTW，未來可嘗試應(yīng)用于求解其它組合優(yōu)化問題。