結(jié)合DBSCAN聚類算法和粒子群算法的大規(guī)模路徑優(yōu)化方法研究

丁 喬，李 旭，王建春 DING Qiao, LI Xu, WANG Jianchun

（山東科技大學(xué) 交通學(xué)院，山東 青島266590）

0 引 言

隨著電子商務(wù)的迅猛發(fā)展，物流行業(yè)迎來難得發(fā)展機遇的同時也面臨著巨大挑戰(zhàn)，現(xiàn)代物流業(yè)發(fā)展的目標是在滿足客戶需求的同時降低運作成本，但配送環(huán)節(jié)的成本占比最高且居高不下，成為阻礙物流發(fā)展的一個瓶頸。為了有效地組織配送業(yè)務(wù)，Dantzig 等[1]將配送過程抽象化，于1959年提出了車輛路徑問題（Vehicle Routing Problems, VRPs）。從此大量的國內(nèi)外學(xué)者對車輛路徑問題進行了廣泛且深入的研究，并且取得了豐碩的成果。目前VRPs 問題的求解規(guī)模一般為數(shù)百個客戶點，但在實際配送實例中該問題的規(guī)模遠不止如此，比如在上海，菜鳥驛站每天有大約30 萬個包裹需要配送，這些問題的規(guī)模往往成千上萬。VRPs 問題是一個典型的NP-hard 問題，求解大規(guī)模的車輛路徑問題具有很大的挑戰(zhàn)性。

車輛路徑優(yōu)化問題屬于NP-Hard 問題，一經(jīng)提出就引來大批國內(nèi)外研究人員的深入探索，如今對于此問題的研究主要集中在車輛路徑優(yōu)化模型的建立[2-4]和車輛路徑優(yōu)化模型求解算法的研究[5-8]，通過對建立車輛優(yōu)化數(shù)學(xué)模型的深入研究使得車輛路徑優(yōu)化問題越來越多樣化，越來越符合最后一公里的配送實際；通過對模型求解算法的研究，使得模型的求解速度和精度不斷提高，已達到能夠更好解決這個NP 難題的目的，但目前對于大規(guī)模的車輛路徑問題研究相對較少，其中：王文蕊[9]通過地理信息的分級管理實現(xiàn)車輛路徑問題規(guī)模的降低，最后通過濟南市區(qū)卷煙配送對提出方法進行驗證。冉崇善[10]將該問題分為兩個階段進行研究，分別為利用基于基地啟發(fā)式分區(qū)算法進行區(qū)域劃分和利用改進的遺傳算法來確定具體的一條配送線路的先后次序，完成配送路徑優(yōu)化任務(wù)。馬漢武[11]在大規(guī)模車輛路徑問題引入裝卸頻率的概念后，建立優(yōu)化模型并設(shè)計改進混合遺傳算法進行求解。由上述文獻可知，廣大學(xué)者對于大規(guī)模車輛路徑問題的研究主要是從如何將其規(guī)模降低的角度來進行思考和解決的。本文提出一種結(jié)合自適應(yīng)DBSCAN 聚類算法的路徑優(yōu)化方法，通過DBSCAN 將客戶點形成若干個聚類簇，將大規(guī)模的城市果蔬配送路徑優(yōu)化問題轉(zhuǎn)換成常規(guī)的路徑優(yōu)化問題，然后通過粒子群算法進行求解，完成路徑優(yōu)化。

1 自適應(yīng)DBSCAN 聚類算法

DBSCAN 是基于密度空間的聚類算法，與K-means 不同，它不需要確定聚類數(shù)量，由數(shù)據(jù)聚類結(jié)果顯示聚類數(shù)量，并且其可以用于凹數(shù)據(jù)集，適合用于不規(guī)則分布客戶點的聚類分析。DBSCAN 需要確定兩個參數(shù)：Eps為在一個點周圍鄰近區(qū)域的半徑；MinPts為鄰近區(qū)域內(nèi)至少包含點的個數(shù)。Eps的選擇根據(jù)實際問題而定，MinPts的選擇通常采用k-距離圖像法來確定。本文采用一種自適應(yīng)DBSCAN 聚類分析方法，通過利用數(shù)據(jù)集自身分布特性生成候選Eps和MinPts，自動尋找到聚類簇數(shù)量變化的穩(wěn)定區(qū)間，此時對應(yīng)的參數(shù)即為要選擇的最優(yōu)參數(shù)。但是文獻[12]中的方法計算量巨大，適合用于樣本數(shù)量較少的情況，對于樣本數(shù)量巨大的情況該方法所需的計算時間會顯著增加。因此本文對該方法進行了改進，將Eps和MinPts候選參數(shù)的選擇由全局取期望值改成了抽樣取期望值，具體步驟如下：

步驟1：計算數(shù)據(jù)集D的距離分布矩陣[13]，n為樣本大小，即：

步驟2：對距離矩陣Dn×n的每一行元素進行升序排列，則第i列的元素隨機取x個組成Di。

步驟3：對Di中的所有元素取平均數(shù)對所有的i值進行計算，最終得到Eps參數(shù)候選列表DEps：

步驟4：生成MinPts參數(shù)候選列表DMinPts，在數(shù)據(jù)集D中隨機選取x個對象，對于步驟3 得到的Eps參數(shù)候選列表DEps，依次計算每一個DEps列表中的Eps候選值的領(lǐng)域?qū)ο髷?shù)量，并計算對象數(shù)量的數(shù)學(xué)期望，作為數(shù)據(jù)集D的鄰域密度閾值MinPts參數(shù)，即：

式中：Ni表示第i個對象的Eps鄰域?qū)ο髷?shù)量，x表示從數(shù)據(jù)集D中隨機抽取的對象數(shù)。

步驟5：依次選用DEps列表和DMinPts列表中的元素作為Eps和MinPts參數(shù)，輸入DBSCAN 算法中對數(shù)據(jù)集進行聚類分析，分別得到不同輸入?yún)?shù)下對應(yīng)的聚類簇數(shù)，當聚類簇數(shù)連續(xù)3 次相同時，認為聚類結(jié)果趨于穩(wěn)定，記該聚類簇數(shù)為最優(yōu)聚類簇數(shù)M。

步驟6：繼續(xù)執(zhí)行步驟5，直到聚類簇數(shù)不為M，則選擇最后一次聚類簇數(shù)為M時對應(yīng)的Eps和MinPts為最優(yōu)參數(shù)。

2 路徑優(yōu)化模型及求解算法

2.1 路徑優(yōu)化問題建模

本文所研究的城市生鮮配送車輛路徑優(yōu)化問題，可以看做是帶時間窗的車輛路徑問題（Vehicle Routing Problems with Time Windows，VRPTW），以車輛的最大載荷和客戶的時間窗為主要約束，目標函數(shù)由固定成本、運輸成本、制冷成本和懲罰成本四部分組成，如公式（4） 所示：

約束：

其中：式（5） 表示每個客戶點只能有一輛車為其服務(wù)；式（6） 表示每輛車的載重不能超過最大載荷；式（7） 表示到達客戶點的車和離開客戶點的車數(shù)量相同。

其中參數(shù)和決策變量的含義如表1 所示。

2.2 粒子群算法

粒子群算法（Pariticle Swarm Optimization，PSO），PSO 的優(yōu)勢在于簡單容易實現(xiàn)，同時又有深刻的智能背景，既適合科學(xué)研究，還特別適合工程應(yīng)用，并且易于實現(xiàn)、收斂速度快和沒有許多參數(shù)需要調(diào)整。一經(jīng)提出就被學(xué)術(shù)界廣泛關(guān)注，集中針對PSO 中的參數(shù)調(diào)整優(yōu)化和種群結(jié)構(gòu)改進以及與其他職能算法相融合等方面進行了深入的研究[14-17]，近些年粒子群算法也被廣泛的應(yīng)用于物流最后一公里的配送問題中。

表1 參數(shù)及決策變量表

將PSO 應(yīng)用于物流最后一公里配送中，則問題的求解目標即為配送所產(chǎn)生的的成本最小，每一個粒子表示一種可行的配送方案，通過PSO 算法的迭代規(guī)則，最終找到配送成本最低的配送方案。粒子群算法的一般數(shù)學(xué)模型：假設(shè)在N 維空間進行搜索，粒子i 的信息可用兩個N 維向量來表示：

式（8） 表示第i 個粒子的位置。

式（9） 表示第i 個粒子的速度。粒子通過以下式子來更新自己的速度和位置：

其中：

N 是粒子長度，即解空間的維度；

i=1,2,3,…,M是種群大小；

c1和c2是學(xué)習因子，又稱加速系數(shù)；

rand1和rand2是介于［0,1 ］之間的隨機數(shù)；

Pbes是粒子i在第k次迭代中第d維的個體極值點位置；

Gbes是整個粒子群在d維的全局極值點的位置。

3 案例分析

本文選取了青島市黃島區(qū)1572 個餐飲店作為配送點，配送中心選擇當?shù)匾延械纳r批發(fā)市場，通過本文的方法先對這些餐飲店進行聚類分析，將大規(guī)模的路徑優(yōu)化問題簡化成正常規(guī)模的路徑優(yōu)化問題，然后建立路徑優(yōu)化模型并利用粒子群算法完成對這1572 個客戶點的配送任務(wù)。

圖1 為餐飲店的分布圖，由圖1 可知餐飲店的分布具有一定的規(guī)律性，具有集中分布的特點，但是有一些分布區(qū)域集中的餐飲店數(shù)量巨大，不利于進行路徑優(yōu)化計算，所以需要采用自適應(yīng)DBSCAN 算法對餐飲店進行聚類分析，利用餐飲店之間的位置空間關(guān)系，將餐飲店進行分類分區(qū)域。

圖1 餐飲店分布圖

圖2 參數(shù)序列與聚類簇數(shù)折線圖

通過本文的自適應(yīng)DBSCAN 候選參數(shù)選擇方法，得到MinPts和Eps參數(shù)列表，將參數(shù)列表中的參數(shù)對逐個代入DBSCAN算法，得出對應(yīng)的聚類簇數(shù)，如圖2 所示，由圖3 可知在第19、20、21 組參數(shù)得到的聚類簇數(shù)連續(xù)3 次都為8 個，第22 組為6 個，依據(jù)本文的方法選出最優(yōu)MinPts為68，最優(yōu)Eps為1118.29m。聚類結(jié)果如圖3 所示。不同的顏色表示不同的聚類簇，其中會有少量的噪聲點，本文處理的方式是將噪聲點歸入就近的聚類簇。各個聚類簇成員數(shù)量如表2 所示。

圖3 聚類結(jié)果顯示

表2 各聚類簇成員數(shù)量表

為了驗證該研究方法和數(shù)學(xué)模型的可行性，選擇當?shù)氐难覎u農(nóng)貿(mào)批發(fā)市場為配送中心，以聚類簇1 的餐飲店為配送客戶點來完成配送任務(wù)。采用Matlab 編程實現(xiàn)粒子群算法，所建立的路徑優(yōu)化數(shù)學(xué)模型進行仿真計算，仿真結(jié)果如圖4 所示，其中編號0 表示配送中心，其他客戶點編號為1-289，本次任務(wù)一共使用了14 輛配送車輛，總成本為2680.7562 元，計算所用時長為16 秒，每輛車具體的配送路徑如表3 所示。

圖4 路徑優(yōu)化結(jié)果展示

表3 車輛配送路徑表

4 結(jié) 論

該研究將自適應(yīng)DBSCAN 聚類分析算法和粒子群聚類算法相結(jié)合，通過使用聚類分析算法將配送客戶點進行分類，將大規(guī)模車輛路徑優(yōu)化問題轉(zhuǎn)變?yōu)檎Ｒ?guī)模車輛路徑問題，然后根據(jù)生鮮農(nóng)產(chǎn)品配送的實際情況建立生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化模型，使用粒子群算法對模型進行求解，對解決大規(guī)模車輛路徑優(yōu)化問題提供了新的解決方案，豐富了車輛路徑優(yōu)化問題的解決理論。最后通過青島市黃島區(qū)1572 個餐飲店進行實例驗證，證明了本研究方法的可行性和合理性。