解決需求可拆分車輛路徑問題的先聚類后路徑方法

閔嘉寧，金 成，陸俐君

（1.無錫太湖學(xué)院，無錫 214064；2.南京大學(xué) 管理學(xué)院，南京 210093）

0 引言

需求可拆分車輛路徑問題SDVRP（Split Delivery Vehicle Routing Problem）松弛了經(jīng)典VRP中對(duì)每個(gè)客戶只能訪問一次的約束[2]。這種松弛使得一個(gè)客戶的需求可以由多輛車送貨，或由一輛車多次送貨；也就是說，當(dāng)車輛的剩余容量不足以為某個(gè)客戶提供完整的送貨需求時(shí)，車輛仍然可以向該客戶提供與車輛剩余容量相等的送貨，而客戶的剩余需求可以由其他車輛（或此輛車的下一次）提供送貨。這樣可以充分利用車輛的容量，降低使用的車輛數(shù)、減少碳排放和行駛距離，進(jìn)一步優(yōu)化車輛路徑問題。因此，SDVRP一經(jīng)提出，迅速成為VRP的一個(gè)重要分支，受到越來越多的關(guān)注[2]。

國外關(guān)于算法的研究正式開始于1989年，Dror和Trudeau[1]提出了一種局部搜索算法，并驗(yàn)證了當(dāng)客戶點(diǎn)的送貨需求較大時(shí)，SDVRP的解決方案明顯優(yōu)于VRP。Belenguer等[3]為SDVRP構(gòu)建了多面體模型，基于切平面法設(shè)計(jì)了一種混合算法；他們解決了規(guī)模相對(duì)較小的問題，取得了良好的效果。Archetti等[4,5]提出了一種TSA算法和基于這個(gè)TSA的改進(jìn)的三階段算法。Chen等[6]首先通過節(jié)約算法得到初始解，然后通過拆分客戶點(diǎn)的需求改進(jìn)路徑。Jin等[7]提出了帶有效不等式的兩階段算法。Jin等[8]提出了基于列生成算法的SDVRP混合啟發(fā)式算法。Tan[9]設(shè)計(jì)了蟻群算法，實(shí)例驗(yàn)證表明，隨著點(diǎn)需求/車輛容量的比例增加，需求分解的優(yōu)勢(shì)也隨之增大。Gulczynski等[10]提出限制最小拆分需求量，開發(fā)了一個(gè)端點(diǎn)混合整數(shù)算法、通過一種增強(qiáng)的記錄到記錄的旅行算法進(jìn)行求解。Aleman等[11,12]提出了自適應(yīng)記憶算法和變量鄰域TSA算法，并驗(yàn)證了后者優(yōu)于前者。Archetti等[13]提出了列生成的精確算法，先把問題域分割成較小的子域，然后在子域中優(yōu)化路徑，試圖縮小精確算法和啟發(fā)式算法獲得的最優(yōu)解的差距。Wilck IV等[14]開發(fā)了一種SDVRP求解的構(gòu)造啟發(fā)式算法，計(jì)算結(jié)果表明，在行駛距離和計(jì)算速度方面性能優(yōu)于列生成方法和兩階段法。

國內(nèi)研究開始的比較晚，但是近年來關(guān)注度逐年提高。2006年謝毅[15]設(shè)計(jì)了一個(gè)用于求解SDVRP問題的禁忌搜索算法（TSA）和一個(gè)遺傳算法（GA），案例分析表明，TSA在最優(yōu)解和時(shí)間消耗方面優(yōu)于GA。侯立文[16]采用了具有改進(jìn)轉(zhuǎn)移概率的最大-最小螞蟻系統(tǒng)，設(shè)計(jì)了求解過程和分割點(diǎn)選取規(guī)則。孟凡超等[17]研究了TSA來解決這個(gè)問題。謝秉磊等[18]提出了蟻群算法。劉旺盛等[19,20]提出了k-means聚類算法，并設(shè)計(jì)了兩種不同的算法：一種是先分組后路徑；另一種方法是先路徑后分組，比較表明，先分組后路徑的方法有更好的性能。馬華偉[21]建立了多時(shí)間窗的SDVRP數(shù)學(xué)模型，設(shè)計(jì)了一種改進(jìn)的蟻群算法求解問題。汪婷婷[22]提出了基于反應(yīng)閾值和求解刺激值的SDVRP問題的蜜蜂群體優(yōu)化模型。向婷等[23]提出了一種“分組而后路徑”的聚類算法：根據(jù)最近原則分組，通過設(shè)定分割閾值來限制車輛的負(fù)載達(dá)到一定的范圍，并且使用蟻群優(yōu)化算法來安排路線。

本研究領(lǐng)域中使用的大多數(shù)算法是啟發(fā)式和元啟發(fā)式方法，為了找到最優(yōu)解，需要多次迭代和結(jié)果比較而后取優(yōu)，雖然可以獲得較優(yōu)的行駛距離，但是計(jì)算過程非常耗費(fèi)時(shí)間。為了解決這個(gè)問題，本文提出了一個(gè) “先聚類后路徑”算法：首先，根據(jù)最近原則對(duì)客戶點(diǎn)按距離進(jìn)行聚類；然后，采用“推出”和“拉入”操作，通過對(duì)客戶的需求拆分，調(diào)整每個(gè)聚類的負(fù)載需求，在沒有迭代的情況下獲得最佳的重量平衡的聚類組；最后，采用禁忌搜索方法對(duì)聚類組中的路徑進(jìn)行優(yōu)化。這樣，可以在較短的時(shí)間內(nèi)獲得近優(yōu)解。該算法將在減少計(jì)算時(shí)間和獲得較優(yōu)的行駛距離方面更具實(shí)用價(jià)值。

1 數(shù)學(xué)模型

式(2)描述了每個(gè)客戶點(diǎn)至少被訪問一次；式(3)是流守恒約束；式(4)是子路徑消除約束；式(5)描述了只有當(dāng)車輛v訪問客戶i時(shí)，車輛v才服務(wù)客戶i；式(6)保證了滿足所有客戶需求；式(7)保證每輛車不超載；式(8)描述了當(dāng)車輛v從i直接到j(luò)時(shí)，=1；否則，=0；式(9)描述了yiv是車輛v為點(diǎn)i 送貨的重量。

2 CRTS算法描述

該算法是一種基于先聚類后路徑策略的三階段算法CRTS（The Clustering first Routing later based Three Stage Algorithm）。第一階段——對(duì)客戶進(jìn)行分組：根據(jù)其地理位置，采用最大最小距離聚類方法對(duì)客戶點(diǎn)進(jìn)行分組。第二階段——調(diào)整每組的重量：采用“推出”和“拉入”操作，根據(jù)每個(gè)點(diǎn)的負(fù)載需求調(diào)整各組的重量，確定每個(gè)組的客戶點(diǎn)。“推出”是將一個(gè)組的額外重量推給那些重量小于Q的鄰組；“拉入”是從重量超過Q的鄰組中提取重量到重量小于Q的組中。第三階段——優(yōu)化組內(nèi)路徑：采用搜索算法優(yōu)化組內(nèi)路徑。該算法的具體過程如下。

2.1 前期處理

對(duì)負(fù)載需求di＞Q(i=1,2,…,n) 的客戶點(diǎn)單獨(dú)處理。di=Q的負(fù)載需求由一輛車進(jìn)行送貨，該點(diǎn)剩余的重量(di=di-Q)(i=1,2,…,n)以及其他的點(diǎn)di＜Q進(jìn)入CRTS算法。

2.2 對(duì)客戶分組

1）最大最小距離聚類算法的基本思想

最大最小距離聚類方法是一種模式識(shí)別方法。首先，按照最遠(yuǎn)距離原則，選擇相距最遠(yuǎn)的點(diǎn)作為聚類中心，以提高初始數(shù)據(jù)集的分割效率[24]。然后，根據(jù)最近距離原則，將所有距離最近的點(diǎn)就近歸入聚類組。

2）最大最小距離聚類的執(zhí)行過程

Step1：令車場(chǎng)為x1作為第1聚類中心z1；

Step2：計(jì)算各點(diǎn)i(i =1,2,…,n) 到z1的距離Di1；

Step3：當(dāng)Dk1=max{Di1}，選取xk作為第2聚類中心z2；

Step4：計(jì)算各點(diǎn)i(i=1,2,…,n)到z1和z2的距離Di1和Di2；

Step6：假如z3存在，計(jì)算Dl=max{min(Di1, Di2, Di3)}(i=1,2,…,n)，以及Dj＞θ*D12，選取xj作為第4聚類中心z4；以此類推，直至Dj≤θ*D12；

Step7：按照最小距離原則，劃分所有的點(diǎn)構(gòu)成組；終止運(yùn)行。

2.3 調(diào)整各組的負(fù)載重量

客戶點(diǎn)聚類分組后，計(jì)算并調(diào)整各組的負(fù)載重量。

1）“推出” 操作的執(zhí)行過程

Step1：假如一個(gè)組的負(fù)載重量wg在 [α*Q, Q]之間，而且只有兩個(gè)點(diǎn)，那么這兩個(gè)點(diǎn)就形成一條路徑，其中α大于負(fù)載率小于1；假如有μ1個(gè)這樣的組，那么就有μ1條路徑；

Step2：假如一個(gè)組的負(fù)載重量wg在[Q, 2*Q]之間，而且只有兩個(gè)點(diǎn)，那么基于Q、這兩個(gè)點(diǎn)就形成一條路徑，剩余的負(fù)載wg-Q轉(zhuǎn)入步驟4；假如有μ2個(gè)這樣的組，就形成了μ2條路徑；

2）“拉入” 操作的執(zhí)行過程

Step1：按順序訪問負(fù)載重量wg＜Q的組（例如，組A）；

Step2：尋找距離A組中心點(diǎn)i最近的鄰組點(diǎn)t（例如，組B中的點(diǎn)t）；

Step3：如果點(diǎn)t的負(fù)載重量dt＞(Q-wgA)且B組的負(fù)載重量wgB＞Q，拆分點(diǎn)t成為t1和t2，移動(dòng)dt2=Q-wgA到組A，保留dt1=dt-(Q-wgA)；

Step4：如果點(diǎn)t的負(fù)載重量dt=(Q-wgA)且B組的負(fù)載重量wgB＞Q，移動(dòng)(合并)點(diǎn)t(dt)進(jìn)入組A；

Step5：如果點(diǎn)t的負(fù)載重量dt＜(Q-wgA)，首先，移動(dòng)（合并）點(diǎn)t（dt）進(jìn)入組A；如果B組的負(fù)載重量wgB＞Q，則在B組中搜索最近的點(diǎn)t'，讓t＜-t'；如果wgB＜Q，則在另一個(gè)相鄰的B'組中搜索最近的點(diǎn)t''，讓t＜-t''；最后，進(jìn)入步驟4；

Step6：如果A組的負(fù)載重量wgA為[α*Q, Q]，則結(jié)束對(duì)組A的處理；如果wgA＜ α*Q，則轉(zhuǎn)到步驟2；

Step7：所有組訪問完畢，則終止 “拉入”過程；否則，重復(fù)“拉入”過程。

2.4 優(yōu)化組內(nèi)路徑

執(zhí)行完“調(diào)整各組的負(fù)載重量”后，問題域被劃分為幾個(gè)較小的子問題域——聚類組，因此可以采用許多成熟的搜索算法來進(jìn)行組內(nèi)路徑優(yōu)化，獲得最優(yōu)解。本文采用禁忌搜索算法。限于篇幅，本文不討論這個(gè)問題。

3 案例研究

為了驗(yàn)證CRTS算法的可行性和有效性，采用來自文獻(xiàn)[7,19,23]的案例，并與采用先聚類后路徑策略相應(yīng)的算法TSVI[7]、k-means聚類方法[19]、拆分閾值的聚類方法[23]以及掃描算法[25]進(jìn)行比較。實(shí)驗(yàn)是在Intel (R)核心處理器、8GB內(nèi)存的Windows 7 64位機(jī)器上實(shí)現(xiàn)的。

3.1 案例組1

案例組1來自文獻(xiàn)[7]。案例組1包含有三個(gè)實(shí)例(N7L1-N7L3)，各實(shí)例的客戶數(shù)都是N=7，車輛最大載重量為1，車場(chǎng)坐標(biāo)(0,0)；實(shí)例中客戶點(diǎn)的位置以及各實(shí)例中22次執(zhí)行 (Q1-Q22) 的送貨需求分別見文獻(xiàn)。

表1 CRTS與TSVI計(jì)算結(jié)果比較

續(xù)（表1）

表1比較了TSVI和CRTS算法的總行駛距離(Distance)，計(jì)算所消耗的CPU時(shí)間s(T)，以及CRTS與TSVI總行駛距離相比較的相對(duì)偏差百分率RDP (Relative Deviation Percentage)：RDP=((DistanceCRTS-DistanceTSVI)/ DistanceTSVI)*100%。由于計(jì)算所消耗的CPU時(shí)間s很小，為節(jié)省顯示空間，表1中計(jì)算時(shí)間(T)一欄表示的數(shù)字是CPU時(shí)間s的100倍。加粗字體表示其RDP≤0.0%，粗斜體表示其0.0%＜RDP＜1.0%，涂灰的數(shù)字表示其RDP＞5.0%。RDP≤0.0%和0.0%＜RDP＜1.0%的次數(shù)占總66次執(zhí)行的46.97%；涂灰的數(shù)字占總66次執(zhí)行的12.12%。

案例組1三個(gè)實(shí)例執(zhí)行的總行駛距離結(jié)果如圖1所示，兩種不同算法曲線的吻合度很好，表明CRTS算法是可行的、有效的，尤其是計(jì)算所消耗的CPU時(shí)間s遠(yuǎn)低于TSVI。

圖1 案例組1三個(gè)實(shí)例的計(jì)算結(jié)果

3.2 案例組2

案例組2中四個(gè)實(shí)例來自文獻(xiàn)[19,23]。各實(shí)例的客戶數(shù)，客戶總需求量，車輛最大裝載量，所需車輛數(shù)如表2所示。各實(shí)例的客戶位置、需求以及車場(chǎng)位置等基本信息見文獻(xiàn)。

表2 案例組2各實(shí)例的基本信息

表3 CRTS與K-means聚類算法、拆分閾值聚類算法和掃描算法計(jì)算結(jié)果比較

圖2 案例組2四個(gè)實(shí)例的執(zhí)行結(jié)果

表3比較了K-means聚類算法、拆分閾值聚類算法、掃描算法以及CRTS的總行駛距離（Distance），計(jì)算所消耗的CPU時(shí)間(T)，以及CRTS分別與這些算法在總行駛距離和計(jì)算所消耗的CPU時(shí)間s比較的相對(duì)偏差百分率為RDP(Dis.)(RelativeDeviationPercentageforDistan ce)和RDP(T)，RDP(Dis.)=((DistanceCRTS–Distance某算法)/Distance某算法)*100%，RDP(Dis.)=((TimeCRTS–Time某算法)/Time某算法)*100%。表3中CRTS的計(jì)算結(jié)果采用了加粗字體。CRTS分別與前3種算法比較的RDP(Dis.)和RDP(T)的值都是百分率；正值表示CRTS的值大，負(fù)值表示CRTS的值小，凡負(fù)值涂有灰色。

表3顯示：1）從總行駛距離來看，N=15、N=20和N=50三個(gè)實(shí)例中拆分閾值聚類算法最低，分別比CRTS低0.815%、4.067%和4.39%；N=36實(shí)例的CRTS最低，比拆分閾值聚類算法低0.805%；2）從計(jì)算所消耗的CPU時(shí)間s來看，CRTS最低，N=15、N=20、N=36和N=50實(shí)例分別比拆分閾值聚類算法低27.82%、30.37%、20.40%和58.51%。圖2清晰表明：CRTS算法是可行的、有效的；圖2(a)的曲線顯示了N=20、N=36和N=50三個(gè)算例的總行駛距離的差別范圍比較小，可以取得較好的總行駛距離；圖2(b)顯示CRTS的計(jì)算所消耗的CPU時(shí)間s遠(yuǎn)低于其他3種算法。

4 結(jié)論

本文介紹了SDVRP的數(shù)學(xué)模型，其目標(biāo)函數(shù)是使用最低數(shù)量的車輛、通過安排合適的路線盡量減少總行駛距離。為了實(shí)現(xiàn)該目標(biāo)，本文基于“先聚類后路徑”方法提出了三階段算法CRTS：第一階段，采用最大最小距離聚類的方法對(duì)客戶點(diǎn)域進(jìn)行聚類，按照使用最小車輛數(shù)的原則將所有客戶點(diǎn)分成子域，形成聚類組；第二階段，采用“推出”和“拉入”操作，根據(jù)車輛最大負(fù)載重量Q值調(diào)整各組的負(fù)荷需求，獲得重量平衡的聚類組；第三階段，優(yōu)化各組的路徑，最小化總行程距離。兩個(gè)案例組7個(gè)實(shí)例70次運(yùn)行結(jié)果表明，CRTS算法為SDVRP提供了可行、有效的解決方案。該算法在總行駛距離的路徑安排中可以取得較好的結(jié)果，尤其在計(jì)算時(shí)間方面，性能優(yōu)于本文選用的TSVI算法、k-means聚類方法、拆分閾值聚類方法以及掃描算法等。