基于聚類的LNS算法求解異構VRP問題

趙 雄,李 琳

(沈陽航空航天大學 理學院,遼寧 沈陽 110136)

0 引 言

車輛路徑規(guī)劃問題(vehicle routing problem,VRP)是規(guī)定一組車輛在一組客戶集合間運輸貨物,并使車輛路徑滿足相應目標函數(shù)要求的研究,是物流運輸行業(yè)中十分重要的一個研究命題,是優(yōu)化物資分配,調(diào)度運輸?shù)姆椒ㄖ?。VRP自1959年被提出后便得到了學者們的關注,形成以VRP為基礎的各項分支研究。HVRP便是其中之一,主要研究不同車輛在運輸調(diào)度中的物資分配問題,其中車輛以車輛歸屬、車輛屬性等進行區(qū)分。在HVRP下存在不同的研究方向,比如帶時間窗的HVRP問題[1-3](heterogeneous fixed fleet vehicle routing problem with time windows,HVRPTW)、帶取送貨的HVRP問題[4-5](heterogeneous fixed fleet vehicle routing problem simultaneous pickup and delivery,HVRPSPD)等。

VRP已知是NP難問題,可知HVRP也是NP難問題。精確方法求解問題具有一定難度,為能快速求解問題,部分學者通過模擬自然演變,采用元啟發(fā)式方法進行求解,并取得了不錯的成果。Wu[6]在求解車輛數(shù)量限制下的VRP時,使用自適應大鄰域搜索算法,并將算法的消除與添加兩個變換步驟加以改進,將客戶運用聚類方法分類,并在消除變換過程按照聚類結果消除,避免單客戶消除方法中客戶返回原位置這種算力上的浪費。Molina[7]在求解HVRPTW時設計了一種具有局部搜索的混合蟻群算法(ant colony system,ACS),稱為memetic-ACS算法,并在其實驗中得到了新的最優(yōu)解。

魯建廈[8]研究了不同初始解對算法的影響,并證明使用聚類算法生成的初始解能使算法收斂速度有較大改進。Meliani[9]和Wei[10]在其研究中就用C-W節(jié)約算法來求解模型的初始解。Jin[11]使用多啟動策略來增加每次迭代的初始解的多樣性,以此加大產(chǎn)生當前最優(yōu)解的可能性。閆軍[12]通過將客戶集合分成不同的子群,簡化數(shù)據(jù)復雜度然后再進行求解。

為提高初始解效率,該文通過均值漂移聚類算法將客戶分成多個子類,在初始化時優(yōu)化每條路徑對客戶個體的選擇,從而優(yōu)化算法初始解。而后通過單鏈設計優(yōu)化鄰域變換方法,加快LNS算法的收斂速度,并通過三組實驗驗證了MS-LNS算法的合理性及有效性。

1 問題描述與數(shù)學模型

HVRP包括車輛數(shù)量限制下(heterogeneous fleet vehicle routing problem)的HFVRP和無車輛數(shù)量限制(fleet size and mix vehicle routing problem)的FSMVRP兩類[13]。HFVRP主要求解在現(xiàn)有資源下如何優(yōu)化分配,而FSMVRP則更側重于市場需求的最優(yōu)調(diào)度方案。該文研究了FSMVRP。

1.1 問題描述

該模型以最小化總成本為目標函數(shù)值。共有N個客戶需要服務,每個客戶的需求量為qi。車場標記為0點。運輸車輛數(shù)量為K,共有M種車輛。異構車輛按照最大載荷量區(qū)分,第k種車輛的載荷為Qk,啟動成本為Ck,單位行駛成本為Cu。車輛從車場出發(fā)服務客戶,服務完后回到車場。dij表示客戶i到j的距離。

1.2 數(shù)學模型

(1)

s.t.

(2)

(3)

(4)

其中,式(1)F為目標函數(shù),最小化車輛總成本;式(2)保證每輛車必經(jīng)過0點,即車輛必從0點出發(fā)且回到0點;式(3)保證每個客戶只有一輛車服務,且只服務一次(此條件可以消除子路徑的可能性);式(4)保證車輛不會超載。xijk為0-1變量,當車輛k經(jīng)過弧ij時為1,否則為0。

2 基于均值漂移聚類的LNS算法

在求解HVRP問題時常使用隨機算法或貪心算法生成初始解。相較于隨機算法,貪心算法獲取的初始解距最優(yōu)解更近,能加快算法前期收斂進度,但由于貪婪算法的最近鄰選擇機制減弱了初始解群的多樣性,使算法容易出現(xiàn)早熟現(xiàn)象。為找到更合適的初始解,加快算法收斂,該文提出使用均值漂移聚類算法區(qū)分客戶子集,依照客戶子集初始化客戶列表。

2.1 編 碼

總路徑Ω采用單鏈編碼方式?？蛻魪?開始編號V={1,2,…,N}。車輛依照類型從客戶集后一位開始編號M={N+1,N+2,…,N+L},其中任意一個元素表示一類車輛。每輛車的子路徑Ωk表示為(N+1,3,5,9,12,4,7),其中起始點為車輛類別,其后所有點為子路徑中的客戶點?？偮窂奖硎緸棣?{Ω1,Ω2,…,ΩK}。

2.2 均值漂移聚類算法初始化

均值漂移聚類的主要方法是在客戶區(qū)域內(nèi)設置M個移動點粒子Xm,在每次迭代過程中移動點粒子搜索掃描半徑內(nèi)的所有客戶點,依照公式(5)(其中Sm為fm限制條件)生成移動向量來更新移動點坐標(6),當某些移動點十分接近的時候將這些移動點合并,直到所有移動點不再變化時停止迭代。此時剩余移動點的個數(shù)就代表客戶點聚類的個數(shù),而每個移動點掃描過的客戶就屬于此類別的客戶子集。

(5)

(6)

初始化步驟為:

Step1:隨機選擇車輛k,生成子路徑Ωk;

Step2:隨機選擇客戶子集Vl,l∈M,隨機選擇其中一客戶作為當前點i,添加到Ωk末尾;

Step3:選Vl中距當前點i最近的客戶點j=argmin{dij},?j∈Vl添加到Ωk末尾,令i=j;

Step4:判斷下列三種情況:若車輛k達到載荷上限或最長工作時間,Vl中還存在未服務客戶則隨機選擇車輛k=k',重新生成子路徑Ωk并返回步驟3;若車輛k未達到載荷上限和最長工作時間,Vl中客戶已完全服務,則返回步驟2;若車輛k達到載荷上限或最長工作時間,且Vl中客戶已完全服務,則進行步驟5;

Step5:判斷客戶是否全部分配完成:是,則初始化完成;否,則回到步驟1。

2.3 鄰域變換

該文使用四種鄰域變換方法:insert、swap、two-swap、載重少車輛重新分配(redistribution)。insert為將總路徑Ω中隨機位置的客戶插入到此路徑的其他位置當中;swap是隨機選取Ω中兩個不同的客戶互相交換其位置;two-swap是同時選4個不同客戶兩兩交換位置(two-swap相當于執(zhí)行兩次swap)。在每次迭代時多次搜索當前解鄰域,盡可能找到使目標函數(shù)值更好的解。

由于編碼的特殊性質(zhì),使得前三種變換方法不用處理子路徑內(nèi)及子路徑間的區(qū)別,且車輛編號與客戶編號在同一編碼當中,使得前三種變換方法產(chǎn)生了兩種不同的變換形式,見圖1和圖2。

圖1 insert變換

圖2 swap變換

Step1:檢測總路徑中每條子路徑載貨率是否達到標準h;

Step2:將所有未達到標準的子路徑從總路徑中刪除,生成客戶子集Vl;

Step3:計算Vl中總客戶需求量Qd,判斷其與不同車輛載荷間的關系:若Qd>max{Qk},?k∈K則轉到步驟4;若Qk>Qd>hQk,?k∈K則轉到步驟5;若Qd

Step5:選擇對應車輛k,按照總路徑初始化方式生成子路徑;

2.4 變換后解的接受準則

該文采用模擬退火算法的接受準則判斷每次變換后的路徑能否替換當前解。當前解的目標函數(shù)值高于當前個體最優(yōu)解時,通過計算公式(7)得到接受概率,再通過輪盤賭形式?jīng)Q定是否接受當前解。其優(yōu)點在于前期溫度值T較高時使粒子具有較大的容錯能力,可以讓粒子在鄰域內(nèi)快速移動;而后期T值減小使粒子容錯能力減弱,增強了粒子鄰域搜索能力,加快收斂進程。每當接受準則成功執(zhí)行時需要更新溫度值T=ρT。其中ρ為溫度變化率。

P=e(F(Papb)-F(Ω))/T

(7)

算法流程見圖3。

圖3 MS-LNS算法流程

先使用聚類算法將客戶分為多個子群,而后對每個子群使用貪婪算法,這樣既能兼顧貪婪算法對初始解群的優(yōu)化,也能保證初始種群的多樣性。該文通過單鏈編碼方式改進變換方法使得每次變換的空間更大,搜索速度更快。對于使用率較差的車輛使用redistribution變換重排。以此三種方式對LNS算法進行改進,加快LNS求解速度。

3 仿真實驗

3.1 實驗數(shù)據(jù)

使用Golden[14]及Penna[15]提供的13-17、20號算例和對應車輛數(shù)據(jù)(表1中共有六種不同的運輸車輛Ver.A-Ver.F),以及Solomon[16]中c201、r201、rc201算例進行實驗。Solomon算例使用20號算例中車輛數(shù)據(jù)進行實驗。表1中Q為車輛載荷,C為車輛固定成本。

表1 車輛數(shù)據(jù)

3.2 參數(shù)設計

為保證算法的收斂速度與跳出局部最優(yōu)的能力,需要優(yōu)化現(xiàn)有的算法參數(shù)。文中算法涉及兩個參數(shù),即聚類算法掃描半徑r和模擬退火溫度變化量ρ。分別通過以下兩種方式計算適合文中算法的參數(shù)值:

3.2.1 聚類算法掃描半徑r

為保證使用均值漂移聚類時不會出現(xiàn)過多孤立點,保證客戶集合分類符合實際,采用箱型圖檢測客戶點距離并嘗試1/4位數(shù),中位數(shù),3/4位數(shù)做掃描半徑的效果。15、16號算例為50個客戶點(圖4(a)),17號算例為75個客戶點(圖4(b)),20號算例為100個客戶點(圖4(c))。

圖4 四組數(shù)據(jù)在1/4位數(shù)時的客戶分類

四組客戶數(shù)據(jù)在取中位數(shù)作為掃描半徑時都無法對客戶集合進行分類,取1/4位數(shù)時每組的分類情況如圖4所示。在1/4位數(shù)周圍取值進行驗證時發(fā)現(xiàn),相較于rc201,15號及17號客戶數(shù)據(jù)的分類對掃描半徑的取值十分敏感,令15號數(shù)據(jù)的掃描半徑r=20.7時,分類個數(shù)縮減到3個。令r=19時分類的數(shù)據(jù)較r=20.2時有比較明顯的變化,而r=17時15號客戶數(shù)據(jù)則被分為六類。為保證分類質(zhì)量,在3.2節(jié)計算當中使用1/4位數(shù)進行計算求解。

3.2.2 模擬退火溫度變化率ρ

采用多組不同的變化率對算例進行檢測,以檢查不同變化率之間的差別,找到盡可能好的參數(shù)值。如圖5所示,共設置4組參數(shù)值0.95、0.9、0.8、0.7。依照算法生成50個粒子迭代變換1 000次,總計10次實驗的平均結果。

圖5 模擬退火溫度變化率ρ變化曲線

模擬退火的接受條件(7)中粒子每接受一次變換,溫度變量T便會依照變化率ρ進行變化,當ρ過大時會導致溫度T變化緩慢,粒子變換的容錯能力過強,不利于粒子的局部搜索;而當ρ過小時T變化過快,會導致算法過快收斂,無法跳出局部最優(yōu)解?？梢钥闯霾徽撛趫D5(a)還是在圖5(b),當變化率ρ=0.9時,算法收斂能力最好。當ρ=0.8或0.7時,算法收斂能力相差不大,但都弱于ρ=0.9的時候,說明ρ=0.9時可以保持良好的收斂性能,具有較快的下降速度。

3.3 實驗結果

進行了三組仿真實驗。實驗一通過比較同種車輛下與異種車輛下的總成本、總路徑長度及實際平均載貨率,驗證異構車輛在VRP中是否存在優(yōu)勢。實驗二通過比較20號數(shù)據(jù)、c201、r201、rc201在MS-LNS算法及LNS算法下的實驗結果,檢驗均值漂移算法是否對算法收斂有增益效果。實驗三使用文中算法計算13-16號算例并與Penna[15]中結果進行比較。該文使用java編程,在Intel(R) Core(TM) i5-4200H CPU @ 2.80 GHz計算機上運行。

實驗一:對17號算例進行10次計算,每次計算共得出四組數(shù)據(jù):總成本、固定成本、移動成本及載重比,再將所得數(shù)據(jù)按照總成本大小順序排列。為減少數(shù)據(jù)區(qū)間不同所造成的影響,使用相對數(shù)進行比較,其計算公式為:qR=qA/q,其中qR代表相對結果,qA代表數(shù)據(jù)絕對值,q代表各組數(shù)據(jù)的平均值。計算結果如圖6所示。

圖6 17號算例實驗結果

其中,車輛類型B的使用量與總成本成反比,而載重比在總成本不斷升高情況下有著逐漸下行的表現(xiàn),說明在車輛低載重比的情況下難以達到最優(yōu)解。分別比較異構車輛與其中四種單一車輛的計算結果,觀察總成本、總路徑長度及實際平均載貨率之間的差別。

由表2可知,B類車輛的計算結果與異構車輛的計算結果十分相近,且比A、C、D類結果要好,該結果正好和圖6中顯示的各類車輛數(shù)量與總成本之間的關系相對應,且異構車輛問題中車輛的平均載重比在五類數(shù)據(jù)中最大,表示異構車輛問題中所有種類車輛都得到了充分的利用。由此可以證明,異構車輛的VRP模型相較于單一車輛的VRP模型具有一定優(yōu)勢。

實驗二:運用MS-LNS算法和LNS算法分別計算20號算例、c201、r201及rc201算例10次,其中實驗結果的平均值如圖7所示。

圖7 MS-LNS算法與LNS算法比較

可以看出,圖7(a)和7(c)中兩種初始化方案尚未產(chǎn)生較大差異,比較(a)(c)兩圖的迭代曲線可知:兩種算法的收斂速度相當。在圖7(b)和圖7(d)中均值漂移算法使得初始值相較于使用貪心算法有較大改進,圖7(b)中雖然MS-LNS在起始點位置的目標函數(shù)值與LNS相比稍差,但后續(xù)迭代過程中MS-LNS的收斂速度卻比LNS的收斂速度要快,使得1 000次迭代后MS-LNS算法的結果要比LNS算法的更好。

實驗三:將文中算法與四種算法進行比較,數(shù)據(jù)如表3～表5所示。其中FSMFD模型的目標函數(shù)為固定成本與移動成本總和最小,FSMF模型為固定成本最小,FSMD模型指移動成本最小。BKs指目前對應算例中的最優(yōu)解值,CG算法及計算結果由文獻[17]給出,SMA-U1由文獻[18]給出,VNS1由文獻[19]給出。時間(t)單位為秒。%為MS-LNS算法與ILS-RVND算法的增量百分比。從表3可以看出,文中算法在最優(yōu)值(m)上與Penna[15]的改進算法還有一定差距。文中算法最優(yōu)解與ILS-RVND算法的平均差距為2.67%。在求得文中算法最優(yōu)解情況下所耗時間(t)要少,算例13所耗時間比ILS- RVND少20.39 s,算例14的時間少6.25 s,算例15少6.15 s,算例16少10.97 s。

表3 FSMFD模型結果

表4 FSMF模型結果

表5 FSMD模型結果

在FSMFD模型中MS-LNS算法的平均耗時較ILS-RVND算法減少了59.33%;在FSMF模型中平均耗時減少了66.58%;在FSMD模型中減少了66.15%。由此驗證了文中算法的高效性和可行性。

4 結束語

在基本HVRP模型的基礎上,根據(jù)客戶點分布的空間特性,提出了結合均值漂移聚類的大鄰域搜索算法,設計了三組仿真實驗。三組仿真實驗結果分別驗證了異構車輛配送方案在求解VRP問題中的效果更好,表明均值漂移聚類算法在隨機分布和聚類分布這兩類客戶數(shù)據(jù)下對LNS算法的收斂速度提高更有效果。未來的研究方向可以對車輛的不同屬性,如車輛載荷、車輛移動成本等因素進行敏感性分析,研究不同屬性變化情況對目標函數(shù)的影響。