基于密度峰值聚類的VRPTW問題研究

吳 斌，宋 琰，程 晶，董 敏

(南京工業(yè)大學(xué) 經(jīng)濟與管理學(xué)院，江蘇 南京 211816)

帶時間窗的車輛路徑問題(vehicle routing problems with time windows, VRPTW)是車輛調(diào)度問題的拓展[1]，廣泛存在于快遞、商超和外賣配送中，對其研究具有重要的理論意義和現(xiàn)實價值。目前，VRPTW已經(jīng)被運籌學(xué)、計算機、交通運輸?shù)阮I(lǐng)域研究人員關(guān)注[2]。VRPTW的優(yōu)化算法有精確算法和啟發(fā)式算法。精確算法可以得到精確解，但計算量隨著問題規(guī)模增大呈指數(shù)增長。啟發(fā)式算法擁有強大的全局搜索能力，因而對于大型復(fù)雜問題，只能使用啟發(fā)式算法[3-5]。目前相關(guān)的文獻已經(jīng)有很多。文獻[6]提出了混合粒度禁忌搜索算法求解VRPTW問題，該方法雖然局部搜索能力強，但時間復(fù)雜度高且結(jié)果嚴(yán)重依賴初始解。文獻[7]克服了蟻群算法在最后階段容易產(chǎn)生不可行解的弊端，建立了良好的積極反饋機制，但算法耗時且容易停滯。文獻[8]利用人工蜂群算法解決VRPTW問題，并且算法收斂速度很快。文獻[9]使用改進的遺傳算法解決具有強制回程特征的雙目標(biāo)車輛路徑問題，結(jié)果顯示算法具有良好的全局搜索能力，計算速度快，但難以獲得全局最優(yōu)解。文獻[10]研究DVRP (dynamic vehicle routing problem)問題，提出混合粒子群和變鄰域搜索的求解方法，在DVRP場景里(維修服務(wù)、快遞)能夠得到有優(yōu)勢的解。Jiang 等[11]使用最佳客戶插入原則PFIH(push forward insertion heuristic)構(gòu)建初始解，再基于SA (simulated annealing)和LNS (large neighborhood search)的混合策略來優(yōu)化初始解, 并且用回歸迭代策略計算每輛車的最佳離開時間。Xu等[12]應(yīng)用基于迭代次數(shù)的線性遞減函數(shù)為粒子群算法提供全局和局部搜索能力之間的平衡，并且結(jié)合遺傳算法的交叉操作避免算法早熟收斂。

上述研究側(cè)重算法設(shè)計，缺乏針對問題特征的求解。在現(xiàn)實世界的配送中，如外賣、快遞、商超配送等很多場景都是客戶聚集的。如何通過聚類方法，減小問題規(guī)模，提高計算速度，獲得更強的全局尋優(yōu)能力，是亟待解決的問題。

2014年Rodriguez等[13]在提出了一種新型聚類算法——DPC (density peak clustering)。該算法能快速發(fā)現(xiàn)任意形狀數(shù)據(jù)集的密度峰值點 (即聚類中心)，并高效進行樣本點分配和離群點剔除。DPC算法在聚類過程中較少需要人為干預(yù)，能大幅提高聚類結(jié)果準(zhǔn)確性。目前DPC已在一些領(lǐng)域成功應(yīng)用。鄒旭華等[14]將DPC算法運用于彩色圖像分割，并且具有較好的分割效果。Chen等[15]應(yīng)用DPC確定面部圖像中年齡族群的密度峰值，再根據(jù)面部照片到密度峰值的距離來預(yù)測照片主人的年齡。文獻[16]用DPC結(jié)合MDNS (multi-document news summarization)模型生成具有較小冗余的新聞?wù)?，解決了BOW(bag of words)模型存儲量高，計算復(fù)雜的問題。DPC已經(jīng)在計算機視覺、自然語言處理和社交網(wǎng)絡(luò)[17-18]等領(lǐng)域成功應(yīng)用，但在物流領(lǐng)域的應(yīng)用還非常少。

綜上所述，針對目前算法在處理大規(guī)模VRPTW問題時易陷入局部最優(yōu)、計算時間長等弊端，本文提出一種基于密度峰值聚類 (DPC)與遺傳算法(Genetic algorithm, GA)相結(jié)合的混合優(yōu)化算法DGA (density peak clustering with genetic algorithm)。通過對客戶進行聚類，將大規(guī)模問題劃分為小規(guī)模的子問題，然后用遺傳算法對每個子問題求解。

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

1.1 問題描述

假設(shè)物流配送網(wǎng)絡(luò)由一個配送中心(用0表示)和N個節(jié)點組成，其中N∈Z+。車輛均?？吭谂渌椭行模渌椭行奶峁┴浳锊囕v進行統(tǒng)一調(diào)度規(guī)劃，車輛根據(jù)規(guī)劃線路將貨物運送至各個節(jié)點。對VRPTW的配送流程作如下定義。

1) 各節(jié)點的需求量已知，且每個節(jié)點的需求量mi小 于可用車型的最大容量qk。

2) 所有車輛從配送中心出發(fā)，完成配送任務(wù)后，需要返回配送中心，且車輛不能超載。

3) 配送中心擁有足夠的貨物來滿足客戶需求。

4) 所有的節(jié)點只能被某一輛車服務(wù)一次。

1.2 VRPTW模型[19]

決策變量如下。

ti為到達節(jié)點i的時間。

wi為在節(jié)點i的等待時間。

xijk∈0,1： 車輛k從i到j(luò)為1，否則為0。ij;i,j∈0,1,2,···,N。

參數(shù)如下。

K為配送車輛總數(shù)量；

N為節(jié)點總數(shù)量；

yi為任意實數(shù)；

dij為i,j節(jié)點之間的歐氏距離；

cij為i,j節(jié)點之間的配送成本；

mi為i點的需求；

qk為車輛k的總?cè)萘浚?/p>

ei為 節(jié)點i的最早到達時間；

li為節(jié)點i的最晚到達時間；

fi為 在節(jié)點i的服務(wù)時間；

rk為車輛k的最大行駛時間。

目標(biāo)函數(shù)為

約束條件為

模型中，0點為配送中心，車輛從配送中心出發(fā)。式(1)為目標(biāo)函數(shù)，目的是最小化總配送成本。式(2)～(10)為模型需要滿足的約束條件，其中，式(2)表示車數(shù)量約束；式(3)確保了每輛車從配送中心出發(fā)并返回配送中心；式(4)～(5)保證每個節(jié)點只能被一輛車服務(wù)，且只能服務(wù)一次；式(6)為車容量約束；式(7)為車輛k的最大行駛時間約束；式(8)~(10)為節(jié)點的時間窗約束。

2 密度峰值聚類結(jié)合遺傳算法求解VRPTW問題

2.1 密度峰值聚類算法

DPC算法能夠發(fā)現(xiàn)任意形狀的簇，樣本點無需迭代，調(diào)節(jié)參數(shù)少，思路直觀明快，易于理解。該聚類算法的核心思想在于對聚類中心的刻畫。Rodriguez等[13]認(rèn)為聚類中心同時具有以下2個特點：1) 聚類中心點的自身密度很大；2) 聚類中心與比其密度大的數(shù)據(jù)點的距離相對較遠。DPC主要有2個需要計算的量，局部密度ρi和相對距離δi。

定義1[13]當(dāng)數(shù)據(jù)點離散時，

當(dāng)x＜0時 ，χ(x)=1，否則，χ(x)=0。當(dāng)數(shù)據(jù)點連續(xù)時，

其中，dij表示i,j兩點之間的歐氏距離，dc為截斷距離。

定義2[13]相對距離δi，

對于局部密度ρi最大的樣本i，δi=maxjdij。

根據(jù) ρi和δi選擇聚類中心點，計算 γi=ρiδi。選取 γi值大的點作為聚類中心，這些點具有較大的局部密度和相對距離，具有作為聚類中心的特征。

DPC的不足在于聚類效果依賴截斷距離dc的設(shè)定。文獻[20]提出基于基尼系數(shù)自適應(yīng)調(diào)整截斷距離dc。Wang等[21]結(jié)合數(shù)據(jù)場理論，使用原始數(shù)據(jù)集的熵獲取截斷距離，提出的計算點勢能的方法如式(14)所示。在一個數(shù)據(jù)集中，數(shù)據(jù)密集區(qū)域的點勢能較大，稀疏區(qū)域的點勢能較小。這表明數(shù)據(jù)域的勢能與點的局部密度具有類似的效果。對于數(shù)據(jù)集{x1,x2,···,xn}, 每個點的勢能計算公式為

式(14)類似Gaussian kernel的計算，其中∥x?xi∥代表歐氏距離，σ是需要確認(rèn)的變量值。對于勢能集{φ1,φ2,···,φn}，定義數(shù)據(jù)域的熵值H為

圖1 σ值優(yōu)化圖Figure 1 σ-value optimization graph

從圖1可以看出，隨著σ 不斷曾大，熵值先減小再增大，故可以取得熵最小時的σ 值。根據(jù)Gaussian分布3B原則[22]，每個點的影響半徑為作為聚類算法，一個點只能影響位于其影響半徑內(nèi)的點。故取σ 為5.4437時的截斷距離計算后再根據(jù) γ?Point決策圖選取聚類中心，選取過程更加簡單直觀。

2.2 VRPTW的遺傳算法優(yōu)化方法

2.2.1 編碼和解碼

針對本文問題，采用簡單直觀的序列編碼方法。將客戶點編號為1 ,2,···,N，然后根據(jù)此編號設(shè)計編碼，隨機生成長度為N的P個染色體，染色體中的每個基因為編號中的某個編號，代表一個客戶，每一個染色體對應(yīng)一種配送方案。解碼按染色體順序進行，從第1個基因開始分配車輛，直到該車滿載或不能滿足下一個客戶的需求為止，然后安排下一輛車，最終該染色體所對應(yīng)客戶全部得到車輛分配。

2.2.2 遺傳操作

交叉和變異是遺傳算法操作算子的基本形式，通過交叉和變異操作，可以不斷搜索靠近最優(yōu)解。本文采用適用于車輛路徑問題的部分匹配交叉(partially matching crossover, PMX)[23]法，具體交叉過程如圖2所示。

圖2 PMX交叉過程Figure 2 PMX crossover process

Step1在父代染色體中隨機選取兩個交叉點；

Step2交換兩個交叉點間的基因，圖中為基因3、4、5、6與6、9、2、1交換；

Step3從父代中繼承未選定交叉的基因7、8；

Step4對剩余位置做映射及沖突檢測。根據(jù)交換的2組基因建立一個映射關(guān)系，形成1 ?6? 3、2? 5 、9? 4三組映射關(guān)系。父代1中基因1經(jīng)過映射變?yōu)榛?(基因6存在沖突)，基因2變?yōu)榛?，基因9變?yōu)榛?。用相同的方法對父代2做映射，最終形成圖2中的2個子代。

由于本文為整數(shù)編碼，所以不同于二進制編碼的變異方式。變異步驟如圖3所示。首先選擇一個父代染色體隨機選擇2個點作為起止點s和e，然后將起止點之間的基因反轉(zhuǎn)，生成新的子代染色體。

圖3 變異過程Figure 3 Mutation process

2.2.3 遺傳算法流程及約束處理

Step1根據(jù)序列編碼規(guī)則隨機產(chǎn)生P個染色體以滿足約束(4)~(5)，構(gòu)成初始種群，設(shè)置迭代次數(shù)L=1。

Step2對染色體解碼，把對不滿足車容量、車輛最大行駛時間以及時間窗約束的染色體刪除。評估第L代的種群，設(shè)計的適應(yīng)度評價函數(shù)為

找到最優(yōu)解及適應(yīng)值，轉(zhuǎn)Step 3。

Step3判斷迭代次數(shù)L是否到達最大迭代次數(shù)Lmax，是則轉(zhuǎn)Step 6。

Step4依據(jù)輪盤賭原則從種群中選擇染色體作為父代染色體。

Step5采取復(fù)制，交叉，變異操作直至產(chǎn)生P個染色體，形成新的種群，轉(zhuǎn)Step 2。

Step6獲取最優(yōu)解方案，輸出結(jié)果。

2.3 DGA求解VRPTW問題的流程

1) 利用密度峰值聚類對客戶點進行聚類，將位置相近的客戶安排在同一個類簇中；2) 對每一個類簇應(yīng)用遺傳算法求解，求得的解根據(jù)車容量和客戶需求約束來對車輛進行分配。這樣不僅可以最大限度的減少車輛的行駛里程，還能夠保證車輛能夠嚴(yán)格地滿足客戶的時間窗要求。DGA算法流程如圖4所示。

3 仿真實驗

3.1 DPC算法進行客戶聚類

選擇Solomon benchmark中的C1數(shù)據(jù)集進行仿真實驗。該數(shù)據(jù)集中每個實例都包含100個客戶、25輛車，每輛車的容量為200。本文算法運行環(huán)境為64位Windows 10系統(tǒng)，處理器為Intel(R)Core(TM)i7-7700HQ 2.80 GHz，內(nèi)存為8 G，編程語言為Python。1) 用DPC對C101數(shù)據(jù)集的100個客戶的位置坐標(biāo)進行聚類，讓地理位置相似度高的客戶安排在一起配送，簡化配送流程。采用熵估計的方法計算C101數(shù)據(jù)集的聚類參數(shù)——截斷距離dc，如圖5所示，求得使熵H最小的σ 值 3.8429，與此對應(yīng)的最優(yōu)dc≈8.1519。2) 進行聚類中心的選擇，作決策圖，得到聚類中心點為10個，如圖6所示。3) 對非聚類中心點進行歸類，結(jié)果如圖7所示，客戶點被聚類到各個類簇，其中藍色的點為配送中心，坐標(biāo)值為(40, 50)，黑色點為各個類簇的聚類中心。

圖4 DGA算法流程Figure 4 DGA algorithm flow

圖5 熵優(yōu)化Figure 5 Entropy optimization

圖6 決策圖 (dc=8.1519)Figure 6 Decision graph

圖7 客戶聚類結(jié)果(C101)Figure 7 Customer clustering results (C101)

對10個客戶類簇進行可視化(圖8)，圖中橫坐標(biāo)為點索引，縱坐標(biāo)為該點到對應(yīng)聚類中心的距離?？梢钥吹剑刂悬c到聚類中心的距離相對平均，沒有距離差很大的客戶點需要去安排配送。

圖8 各類簇中樣本點到聚類中心的距離Figure 8 The distance from the sample points in each cluster to the cluster center

3.2 遺傳算法優(yōu)化配送線路

Solomon數(shù)據(jù)集中假設(shè)車速為單位距離，這樣可以使得各節(jié)點之間旅行時間tij和節(jié)點之間的歐氏距離dij相等。設(shè)置遺傳算法交叉率為0.8，變異率為0.1，種群規(guī)模為100，迭代500代。以C101數(shù)據(jù)集為例，將遺傳算法運行10次獲得最優(yōu)值，具體路徑及車輛到達每個客戶點的時間見表1(車輛列括號內(nèi)為車裝貨量)，算法所求得最優(yōu)解的車輛路徑圖如圖9所示，圖中每種顏色代表一輛車。最優(yōu)值為828.94，車輛平均滿載率為91%。

表1 DGA計算C101各車輛行駛路徑及到達各客戶點時間Table 1 Driving path and arrival time of C101 vehicles calculated by DGA

圖9 各類簇車輛路徑Figure 9 Vehicle paths of various clusters

3.3 算法比較

運用DGA對其他C1類型數(shù)據(jù)實例進行仿真實驗，并與其他算法進行對比。各實例計算結(jié)果如表2所示，可視化如圖10所示。從平均值角度分析，DGA的解優(yōu)于OV[24]、SA[19]和Tabu[19]算法得出的解，并且接近于最優(yōu)解。

文獻[25]中的最優(yōu)解是在禁忌搜索中引入精確算法得到的。將禁忌搜索算法找到的優(yōu)秀解(350~450個)保存在集合T中，提出集合劃分問題(該問題也是NP-難問題)，然后通過調(diào)用精確求解器Cplex來求解，得到了目前已知的最優(yōu)解。該方法雖然找到了最優(yōu)解，但算法運行時間較長。本文提出的方法與最優(yōu)解之間有偏差，主要是在C103和C104這2個問題上未找到最優(yōu)解。通過比較最優(yōu)解和DGA的優(yōu)化結(jié)果，發(fā)現(xiàn)每條線路中的客戶是相同的，僅客戶的配送路徑不一致。這是由于C103和C104是時間窗十分寬松的VRPTW問題。此類問題配送線路的可行解空間更大，需要較強的路徑優(yōu)化算法。為突出聚類對算法的影響，本文僅采用基本遺傳算法進行路徑優(yōu)化，沒有對遺傳算法進行改進或者引入啟發(fā)式算法進行后優(yōu)化，造成線路的優(yōu)化結(jié)果有偏差。

圖10 各算法計算結(jié)果可視化Figure 10 Visualize the calculation results of each algorithm

表2 各算法結(jié)果對比Table 2 Comparison of results of various algorithms

從表2所求得的最優(yōu)值來看，OV、SA、Tabu算法在C102、C103和C104數(shù)據(jù)集中均會陷入局部最優(yōu)，但本文算法在這3個數(shù)據(jù)集上仍能得到最接近最優(yōu)值的解，最大誤差為0.91%，說明本文提出的DGA算法具有較好的魯棒性。聚類可以將原始數(shù)據(jù)集拆分成多個小數(shù)據(jù)集，通過減小問題規(guī)模來提高解的質(zhì)量。表3記錄了C102、C103 和C104三個實例聚類后每個類簇所要配送的客戶數(shù)量。通過對比發(fā)現(xiàn)，聚類使原本的100個客戶的優(yōu)化問題，變成每個類簇進行10個客戶左右的線路優(yōu)化，大大減少了計算量和計算難度。因此，DGA在求解大規(guī)模問題時具有較大參考意義。聚類保留了客戶的地理位置聚集特征，不僅能得到比GA[19]更快更好的解，而且得到的解在實際中更加方便物流配送。

表3 C102、C103、C104聚類計算結(jié)果Table 3 C102, C103, C104 cluster calculation results

4 結(jié)束語

本文提出密度峰值聚類與遺傳算法相結(jié)合的混合算法求解VRPTW問題。通過聚類縮小遺傳算法求解問題的規(guī)模，提高了結(jié)果的準(zhǔn)確性，同時還加快了求解速度。該方法克服了傳統(tǒng)遺傳算法容易陷入局部最優(yōu)的缺點。通過實例驗證，并與其他算法進行對比，解的質(zhì)量最多提升了26.4%，證明了DGA在處理VRPTW問題時具有一定的優(yōu)越性。DGA在求解大規(guī)模問題時可以加快問題的求解過程，擴大了VRPTW問題的研究規(guī)模。但聚類算法在Solomon隨機數(shù)據(jù)集上的效果不太好，因為客戶點位置隨機，DPC不能發(fā)揮最大效用。因此，如何針對隨機客戶數(shù)據(jù)集改進聚類算法是下一步需要研究的問題。