閆 龍，石小娟，唐 源

(山東工商學(xué)院 管理科學(xué)與工程學(xué)院，山東 煙臺(tái) 264005)

0 引 言

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

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

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

1.1 帶軟時(shí)間窗的車輛路徑問(wèn)題描述

(1)

圖1 折線軟時(shí)間窗

1.2 模型建立

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

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

2 混合烏鴉搜索算法

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

2.1 編碼方式

本文采用基于顧客序列的整數(shù)編碼方式對(duì)烏鴉搜索食物時(shí)的空間位置向量進(jìn)行編碼，假設(shè)顧客數(shù)目為10，則烏鴉i的空間位置向量即為10維的整數(shù)編碼序列，如烏鴉i的位置為Xi=[4 8 9 7 1 3 2 5 10 6]， 在滿足時(shí)間窗、載重量等約束條件的情況下可將其解碼為加入配送中心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è)計(jì)了最短距離與最小懲罰兩種初始化規(guī)則如下：

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

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

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

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

(11)

(12)

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

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

(13)

(14)

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

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

各算子權(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ù)，ε為分?jǐn)?shù)，π表示算子使用次數(shù)。權(quán)重更新公式如式(15)所示

(15)

2.4 算法流程

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

算法：HCSA

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

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

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

(2)whilet≤Mt

(3)foreach烏鴉

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

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

(6)else

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

(8)endif

(9) 計(jì)算經(jīng)過(guò)鄰域搜索后烏鴉的適應(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)列表判斷，當(dāng)?shù)螖?shù)s_num>u時(shí)，停止迭代；

(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；目標(biāo)函數(shù)中的參數(shù)值與文獻(xiàn)[12]一致：違反時(shí)間窗懲罰系數(shù)p1=1，p2=0.5，p3=1.5，p4=2，顧客的容忍水平β=0.5，單位車輛固定啟用成本C1=60，單位距離成本C2=8。

3.2 實(shí)驗(yàn)及結(jié)果分析

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

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

表1 25個(gè)顧客點(diǎn)的算例求解結(jié)果

表2 50個(gè)顧客點(diǎn)的算例求解結(jié)果

表3 100個(gè)顧客點(diǎn)的算例求解結(jié)果

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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