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

閔嘉寧，金 成，陸俐君

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

0 引言

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

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

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

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

1 數學模型

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

2 CRTS算法描述

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

2.1 前期處理

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

2.2 對客戶分組

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

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

2）最大最小距離聚類的執行過程

Step1：令車場為x1作為第1聚類中心z1；

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

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

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

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

Step7：按照最小距離原則，劃分所有的點構成組；終止運行。

2.3 調整各組的負載重量

客戶點聚類分組后，計算并調整各組的負載重量。

1）“推出” 操作的執行過程

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

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

2）“拉入” 操作的執行過程

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

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

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

Step4：如果點t的負載重量dt=(Q-wgA)且B組的負載重量wgB＞Q，移動(合并)點t(dt)進入組A；

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

Step6：如果A組的負載重量wgA為[α*Q, Q]，則結束對組A的處理；如果wgA＜ α*Q，則轉到步驟2；

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

2.4 優化組內路徑

執行完“調整各組的負載重量”后，問題域被劃分為幾個較小的子問題域——聚類組，因此可以采用許多成熟的搜索算法來進行組內路徑優化，獲得最優解。本文采用禁忌搜索算法。限于篇幅，本文不討論這個問題。

3 案例研究

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

3.1 案例組1

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

表1 CRTS與TSVI計算結果比較

續（表1）

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

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

圖1 案例組1三個實例的計算結果

3.2 案例組2

案例組2中四個實例來自文獻[19,23]。各實例的客戶數，客戶總需求量，車輛最大裝載量，所需車輛數如表2所示。各實例的客戶位置、需求以及車場位置等基本信息見文獻。

表2 案例組2各實例的基本信息

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

圖2 案例組2四個實例的執行結果

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

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

4 結論

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