結合DBSCAN聚類算法和粒子群算法的大規模路徑優化方法研究

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

（山東科技大學 交通學院，山東 青島266590）

0 引 言

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

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

1 自適應DBSCAN 聚類算法

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

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

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

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

步驟4：生成MinPts參數候選列表DMinPts，在數據集D中隨機選取x個對象，對于步驟3 得到的Eps參數候選列表DEps，依次計算每一個DEps列表中的Eps候選值的領域對象數量，并計算對象數量的數學期望，作為數據集D的鄰域密度閾值MinPts參數，即：

式中：Ni表示第i個對象的Eps鄰域對象數量，x表示從數據集D中隨機抽取的對象數。

步驟5：依次選用DEps列表和DMinPts列表中的元素作為Eps和MinPts參數，輸入DBSCAN 算法中對數據集進行聚類分析，分別得到不同輸入參數下對應的聚類簇數，當聚類簇數連續3 次相同時，認為聚類結果趨于穩定，記該聚類簇數為最優聚類簇數M。

步驟6：繼續執行步驟5，直到聚類簇數不為M，則選擇最后一次聚類簇數為M時對應的Eps和MinPts為最優參數。

2 路徑優化模型及求解算法

2.1 路徑優化問題建模

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

約束：

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

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

2.2 粒子群算法

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

表1 參數及決策變量表

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

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

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

其中：

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

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

c1和c2是學習因子，又稱加速系數；

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

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

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

3 案例分析

本文選取了青島市黃島區1572 個餐飲店作為配送點，配送中心選擇當地已有的生鮮批發市場，通過本文的方法先對這些餐飲店進行聚類分析，將大規模的路徑優化問題簡化成正常規模的路徑優化問題，然后建立路徑優化模型并利用粒子群算法完成對這1572 個客戶點的配送任務。

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

圖1 餐飲店分布圖

圖2 參數序列與聚類簇數折線圖

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

圖3 聚類結果顯示

表2 各聚類簇成員數量表

為了驗證該研究方法和數學模型的可行性，選擇當地的薛家島農貿批發市場為配送中心，以聚類簇1 的餐飲店為配送客戶點來完成配送任務。采用Matlab 編程實現粒子群算法，所建立的路徑優化數學模型進行仿真計算，仿真結果如圖4 所示，其中編號0 表示配送中心，其他客戶點編號為1-289，本次任務一共使用了14 輛配送車輛，總成本為2680.7562 元，計算所用時長為16 秒，每輛車具體的配送路徑如表3 所示。

圖4 路徑優化結果展示

表3 車輛配送路徑表

4 結 論

該研究將自適應DBSCAN 聚類分析算法和粒子群聚類算法相結合，通過使用聚類分析算法將配送客戶點進行分類，將大規模車輛路徑優化問題轉變為正常規模車輛路徑問題，然后根據生鮮農產品配送的實際情況建立生鮮農產品配送路徑優化模型，使用粒子群算法對模型進行求解，對解決大規模車輛路徑優化問題提供了新的解決方案，豐富了車輛路徑優化問題的解決理論。最后通過青島市黃島區1572 個餐飲店進行實例驗證，證明了本研究方法的可行性和合理性。